Creating a layout for an augmented reality (AR) application which embeds virtual objects in a physical environment is difficult as it must adapt to any physical space. We propose a rule-based framework for generating object layouts for AR applications. We present an algorithm for dynamically targeting the AR application to a new environment in real time by solving a constraint-satisfaction problem. Under our framework, the developer of an AR application specifies a set of cost functions (rules) which enforce self-consistency (rules regarding the inter-relationships of application components) and scene-consistency (application components are consistent with the physical environment they are placed in). Our method is general and can be applied to any rule-based layout design problems. We represent layout rules using hyper-graphs where nodes in the graph represent objects and hyper-edges between nodes represent the rules that operate on objects.

Given an environment, we create a layout for an application using a novel solution-space exploration algorithm. Our method exploits the fact that for many types of rules, satisfiable assignments can be found efficiently, in other words, these rules are locally satisfiable. This allows us to sample candidate object values from the known partial probability distribution function for each rule. Experimental results demonstrate that this sampling technique reduces the number of samples required by other algorithms by orders of magnitude enabling us to find rule-consistent augmentations for the scene. We demonstrate several augmented reality applications, which automatically adapt to different rooms and changing circumstances in each room. Our adaptive search algorithm is general and can be used for many other applications such as automatic furniture layout, populating virtual worlds and 2D graphic design.