Bodies in motion: a new simulation technique optimizes complex collision calculations. (techwatch).

The ability to effectively simulate interactions among convex 3D objects in a computer-generated environment has helped graphics and animation specialists achieve unprecedented levels of realism in complex scenes. This has been a particular boon for filmmakers struggling to achieve effects for which traditional cinematographic techniques would be too expensive or impossible.

But while current techniques for rigid-body simulation are effective in a good number of situations, they perform poorly when the scenes being computed have many objects in close proximity. In such a scenario, says Victor Milenkovic, a graphics researcher in the Computer Science Department at the University of Miami, "each time two bodies collide or make or break a static contact, the simulator must interrupt the numerical integration of velocities and accelerations, and even for simple scenes, the number of discontinuities per frame time step can rise to the millions."

To address this deficiency, Milenkovic and colleague Harald Schmidl have developed an optimization-based animation (OBA) algorithm capable of simulating scenes that include many convex three-dimensional bodies. The technique, which can handle scenes with hundreds of concurrent contact points per frame and large numbers of solids in a single cluster, targets the "small time step" problem of conventional simulation methods.

Most current simulators--whether geared toward particles, solids, fluids, deformable objects, or other phenomena--rely on a loop that repeatedly processes the objects' states to generate snapshots of individual frames, which, when played back, show a system of bodies in motion. In the loop, when pairs of objects collide, their computed distance becomes zero, the simulation stops, and impulses and forces are applied to resolve collisions and static contacts. At each full frame time, the simulator issues a redraw command and displays a snapshot of the new body states.

When there are a large number of rigid bodies in a scene or when they are tightly confined, the number of collisions rises and the time that passes without a collision moves toward zero. These numerous, tiny time steps are computationally draining. Advancing only 1/30th of a second time step within a frame involves a large number of "micro" steps that require many computations. More collisions require more iterations of the simulation loop to simulate the same duration of motion. Thus, says Schmidl, "the ...