Timewarp Rigid Body Simulation
Timewarp Rigid Body Simulation is a paradigm for simulating systems comprising hundreds or thousands of rigid bodies in a physically accurate and efficient manner. The key idea is to evolve the dynamic states as asynchronously as possible, synchronizing states only at the times and to the extents necessary to compute interactions between bodies. Timewarp rigid body simulation facilitates modeling systems that are too large for traditional algorithms, such as factory floors or large, interactive virtual environments.
Background & Objective: Rigid body simulation is difficult because of the discontinuities, such as collisions or contact changes, that affect the otherwise smooth trajectories of state variables. To process discontinuities, traditional high-level simulation loops impose a synchronization among all bodies that is inefficient. The inefficiency is due either to small integration steps or to work wasted when bodies are backed up to the time of a discontinuity. While the inefficiencies are tolerable with small numbers of bodies, the traditional methods become intractable with hundreds or thousands of bodies.
Technical Discussion: The timewarp algorithm (Jefferson, 1985) is a paradigm for distributed discrete event simulation based on simulating individual processes independently and judiciously rolling back computations when causality violations are detected. With some modification, this approach can be adapted to the continuous-time rigid body simulation problem. Each rigid body or articulated body is a separate process, and these processes communicate via collision impulses and contact forces. A key extension of the classic algorithm facilitates the creation and destruction of processes during the course of the simulation; these events occur as contacts form and break. Another rigid body-specific extension is a method to perform broad-phase collision detection between bodies without synchronizing them. This research also addresses implications for controllers, data capture systems, and other programs that interface with the simulation. Special care is needed since advancement of the bodies is not synchronous or even monotonic.    Results from several experiments show that a timewarp rigid body simulator can handle systems with as many as 800 bodies without taking prohibitively small integration steps or wasting excessive work due to rollback. It clearly outperforms traditional algorithms for such large systems.
Contacts:
Joseph Katz
Technology Area: Graphics
Modification Date: January 23, 2007
