UCLA

Position-based methods have become popular for real-time

simulation in computer graphics. In contrast to traditional simulation

methods, which are based on Newtonian dynamics, particularly forces, a

Position-Based Dynamics (PBD) method computes the positional changes

directly, based on a set of well-defined geometric constraints.

Therefore, position-based methods are reputed to be more controllable,

stable, and faster, which make them well-suited for use in interactive

environments. This thesis introduces position-based approaches to

addressing the important tasks of virtual crowd simulation and virtual

layout synthesis.

For crowd simulation, we introduce a novel method that runs at

interactive rates for up to hundreds of thousands of agents. Our

method enables the detailed modeling of per-agent behavior in a

Lagrangian formulation. We model short-range and long-range collision

avoidance to simulate both sparse and dense crowds. On the particles

representing agents, we formulate a set of positional constraints that

can be readily integrated into a standard PBD solver. We augment the

tentative particle motions with planning velocities to determine the

preferred velocities of agents, and project the positions onto the

constraint manifold to eliminate colliding configurations. The local

short-range interaction is represented with collision and frictional

contact between agents, as in the discrete simulation of granular

materials. We incorporate a cohesion model for simulating collective

behaviors and propose a new constraint for dealing with potential

future collisions. Our method is suitable for use in interactive

games.

For layout synthesis, we propose a position-based interior layout

synthesis method that is able to rapidly synthesize large scale

layouts that were previously intractable. An interior layout modeling

task can be challenging for non-experts, hence the existence of

interior design professionals. Recent research into the automation of

this task has yielded methods that can synthesize layouts of objects

respecting aesthetic and functional constraints that are non-linear

and competing. These methods usually adopt a purely stochastic scheme,

which samples from a distribution of layout configurations, a process

that is slow and inefficient. We introduce an alternative

physics-based, continuous layout synthesis technique, which results in

a significant gain in speed and is readily scalable. We demonstrate

our method on a diverse set of examples and show that it achieves

results similar to conventional layout synthesis based on a Markov

chain Monte Carlo (McMC) state-search step, but is faster by at least

an order of magnitude and can handle layouts of unprecedented size and

tight layouts that can overwhelm McMC.