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. Ad vancing 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 simulation spends huge amounts of time within frames computing motion that is not even visible."
 |
| Animating large numbers of tightly confined objects is a simulation nightmare, because each collision requires a new iteration of the simulation loop. A technique by Miami researchers avoids this by calculating only collisions that will have a visual impa |
In contrast, the new system uses a fixed time step, rather than one that infinitely approaches zero. It is built on a quadratic-programming method that calculates new positions, momenta, and accelerations strictly at frame time (1/30th second). For each fixed time step, each body in the scene has a target position and orientation representing where its trajectory would take it in one time step in the absence of a collision. The OBA algorithm moves the bodies as close as possible to their targets without overlapping. In the event of a potential overlap, the algorithm avoids it by translating and rotating the body. Consequently, the technique can compute plausible visible states at frame times without executing the numerous in-between steps. Basically, at the end of each time step, the technique synchronizes all collisions and static contacts that would have occurred during the course of a time step.
For situations where objects pass through each other, such as a bullet piercing an object, a hybrid OBA can be employed, which re-introduces some micro steps to simulate the effect, but keeps them to a minimum.
The researchers stress that the algorithm is useful for scenes where plausible animations are adequate. Says Schmidl, "OBA generates simulations that look right, but due to its approximating character, the technique is not well suited for simulations that have to be 100 percent physically accurate, such as manned space flight." Also, because of the computational overhead of quadratic programming, there is no performance gain to the technique for scenes in which there are few rigid bodies.
A particular benefit of the new system is that it can easily be integrated into existing commercial animation software. "People who are not necessarily mathematical programming experts can make use of it in their programs," says Schmidl. He notes that current processing limitations preclude real-time performance, which would be necessary for use in computer-game development.
On the R&D agenda for the new technique are parallel implementation and extensions of the technology to handle other domains, such as flexible and deformable objects, cloth, and possibly molecules. More information on the technology can be found at http://www.cs.miami.edu.
Diana Phillips Mahoney is chief technology editor of Computer Graphics World.