Layout design using locally satisfiable proposals

Patent metadata

Field	Value
Publication number	US-9959675-B2
Application number	US-201414300224-A
Country	US
Kind code	B2
Filing date	Jun 9, 2014
Priority date	Jun 9, 2014
Publication date	May 1, 2018
Grant date	May 1, 2018

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.

First claim

What is claimed is:

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

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Gal Ran
• Kohli Pushmeet
• Ofek Eyal
• Shapira Lior

Classifications

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06T19/006 Primary

  Mixed reality (object pose determination, tracking or camera calibration for mixed reality G06T7/00) · CPC title

• G06T2219/2004

  Aligning objects, relative positioning of parts · CPC title

• G06T19/20

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06F17/50

  Physics · mapped topic