Layout design using locally satisfiable proposals

• US 9,959,675 B2
• Filed: 06/09/2014
• Issued: 05/01/2018
• Est. Priority Date: 06/09/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gal, Ran, Kohli, Pushmeet, Ofek, Eyal, Shapira, Lior
• Primary Examiner(s): Johnson, M Good
• Application Number:
  US14/300,224
• Publication Number:
  US 20150356774A1
• Time in Patent Office: 1,422 Days
• Field of Search: None
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 19/006 Mixed reality object pose determination, tracking or camera calibration for mixed reality G06T7/00
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts

Abstract

A “Layout Optimizer” provides various real-time iterative constraint-satisfaction methodologies that use constraint-based frameworks to generate optimized layouts that map or embed virtual objects into environments. The term environment refers to combinations of environmental characteristics, including, but not limited to, 2D or 3D scene geometry or layout, scene colors, patterns, and/or textures, scene illumination, scene heat sources, fixed or moving people, objects or fluids, etc., any of which may evolve or change over time. A set of parameters are specified or selected for each object. Further, the environmental characteristics are determined automatically or specified by users. Relationships between objects and/or the environment derived from constraints associated with objects and the environment are then used to iteratively determine optimized self-consistent and scene-consistent object layouts. This enables the Layout Optimizer to augment environments with arbitrary content in a structured constraint-based process that adapts to changing scenes or environments.

Claims

1. A computer-implemented process, comprising:

using a computer to perform process actions for;

receiving a set of one or more virtual objects;

receiving a set of parameters for each virtual object;

receiving characteristics of an arbitrary environment into which the virtual objects will be mapped;

receiving a set of constraints that define relative relationships between any of the objects, any of the parameters of those objects, and any of the characteristics of the arbitrary environment;

setting variables of an initial layout for each virtual object that maps each of the virtual objects into the environment;

performing an iterative update of the layout of each object such that the layout of each object in each iterative update is consistent with the characteristics of the environment and is also consistent with the layout of each of the other objects until a global cost of the constraints is minimized; and

wherein each iteration uses locally satisfiable proposals, which generate multiple different candidate layouts for each virtual object in each iteration, to select a single one of the multiple different candidate layouts for each virtual object by simultaneously updating and optimizing the variables of the layout of all of the virtual objects relative to one or more of the other virtual objects, the characteristics of the environment, and the constraints.

2. The computer-implemented process of claim 1 wherein each iteration further comprises process actions for using a fusion-move process that proposes multiple new labels for each variable of the layout.

3. The computer-implemented process of claim 2 wherein the multiple labels proposed for each variable during each iteration are automatically selected such that they satisfy any applicable constraints.

4. The computer-implemented process of claim 1 wherein a new iterative update of the layout of each object is performed whenever any constraint changes.

5. The computer-implemented process of claim 1 wherein a new iterative update of the layout of each object is performed whenever any of the characteristics of the arbitrary environment changes.

6. The computer-implemented process of claim 5 further comprising using the layout of each object existing prior to the changes to the environment as an additional set of constraints that forces the new iterative update of the layout of each object to be as close as possible to the layout of each object existing prior to the changes.

7. The computer-implemented process of claim 1 wherein a new iterative update of the layout of one or more of the other objects is performed whenever any of the parameters of any virtual object changes.

8. The computer-implemented process of claim 1 wherein:

the environment is an image;

wherein one or more of the virtual objects are text objects; and

wherein the iterative update of the layout of the text objects places those objects as overlays on the image in locations that avoid covering salient regions of the image.

9. The computer-implemented process of claim 1 wherein one or more of the virtual objects, the parameters, the environmental characteristics and the constraints are selected via a user interface from one or more libraries of predefined and user-configurable virtual objects, parameters, environmental characteristics and constraints.

10. The computer-implemented process of claim 1 wherein the environment is a real-world 3D environment and wherein the characteristics of the arbitrary dynamic environment include parameters of one or more physical objects in the environment.

11. The computer-implemented process of claim 10 wherein one or more of the virtual objects are components of an interactive 3D game that are mapped to the real-world 3D environment by the iterative update of the layout of each object.

12. A system, comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to;

receive a set of one or more virtual objects and a set of parameters for each virtual object;

receive a set of constraints that define relative relationships between any of the objects and any of the parameters of those objects;

performing an iterative update of a layout of each virtual object using the parameters of the other virtual objects and the set of constraints until a global cost of the constraints is minimized; and

wherein each iteration uses locally satisfiable proposals, which generate multiple different candidate layouts for each virtual object in each iteration, to select a single one of the multiple different candidate layouts for each virtual object by simultaneously updating and optimizing the layout of all of the virtual objects relative to one or more of the other virtual objects and the constraints.

13. The system of claim 12 further comprising:

receiving characteristics of an arbitrary environment into which the virtual objects will be mapped;

wherein the constraints further define relative relationships between any of the objects, any of the parameters of those objects, and any of the characteristics of the arbitrary environment; and

wherein each iteration of the iterative update uses locally satisfiable proposals to simultaneously update and optimize the layout of all of the virtual objects relative to one or more of the other virtual objects, the characteristics of the environment, and the constraints.

14. The system of claim 12 wherein each iteration further comprises:

using a fusion-move process that proposes multiple new labels for one or more variables of the layout; and

wherein the multiple labels proposed for any variable during each iteration are automatically selected such that they satisfy any applicable constraints.

15. The system of claim 12 further comprising:

automatically performing a new iterative update of the layout of the objects whenever any of the virtual objects, the parameters, or the constraints change; and

wherein the layout of each object existing prior to any changes to any of the virtual objects, the parameters, or the constraints is used to construct an additional set of constraints that forces the new iterative update of the layout of each object to be as close as possible to the layout of each object existing prior to the changes.

16. A computer-readable storage device having computer executable instructions stored therein, said instructions causing a computing device to execute a method comprising:

receiving a set of one or more virtual objects;

receiving a set of parameters for each virtual object;

receiving characteristics of an environment, including parameters of one or more physical objects present in the environment, into which the virtual objects will be mapped;

performing an iterative update of a configuration for each virtual object that maps each of the virtual objects into the environment based on the parameters of the other virtual objects and with the characteristics of the environment until a global configuration cost of the parameters associated with each virtual object is minimized; and

wherein each iteration uses locally satisfiable proposals, which generate multiple different candidate layouts for each virtual object in each iteration, to select a single one of the multiple different candidate layouts for each virtual object by simultaneously updating and optimizing the configuration of all of the virtual objects relative to one or more of the other virtual objects and the characteristics of the environment.

17. The computer-readable storage device of claim 16 wherein the iterative update is performed based on a set of constraints that define relative relationships between any of the virtual objects, any of the parameters of those virtual objects, and any of the characteristics of the environment.

18. The computer-readable storage device of claim 16 further comprising automatically performing a new iterative update of the configuration of the virtual objects whenever any of the virtual objects, the parameters, or the characteristics of the environment have changed.

19. The computer-readable storage device of claim 18 wherein the configuration of each virtual object existing prior to any changes to any virtual objects, the parameters, or the characteristics of the environment is used to construct a set of constraints that forces the new iterative update of the configuration of each virtual object to be as close as possible to the configuration of each object existing prior to the changes.

20. The computer-readable storage device of claim 16 wherein each iteration further comprises:

using a fusion-move process that proposes multiple new labels for one or more variables of the configuration; and

wherein the multiple labels proposed for any variable during each iteration are automatically selected such that they satisfy a set of constraints that define relative relationships between any of the virtual objects, any of the parameters of those virtual objects, and any of the characteristics of the environment.