664 12. Collision and Rigid Body Dynamics
orders. That said, the technique I’ve seen used most oft en goes something like
this:- The forces and torques acting on the bodies in the physics world are
integrated forward by Δt in order to determine their tentative positions
and orientations next frame. - The collision detection library is called to determine if any new contacts
have been generated between any of the objects as a result of their
tentative movement. (The bodies normally keep track of their contacts
in order to take advantage of temporal coherency. Hence at each step of
the simulation, the collision engine need only determine whether any
previous contacts have been lost and whether any new contacts have
been added.) - Collisions are resolved, oft en by applying impulses or penalty forces
or as part of the constraint solving step below. Depending on the SDK,
this phase may or may not include continuous collision detection (CCD,
otherwise known as time of impact detection or TOI). - Constraints are satisfi ed by the constraint solver.
At the conclusion of step 4, some of the bodies may have moved away from
their tentative positions as determined in step 1. This movement may cause
additional interpenetrations between objects or cause other previously sat-
isfi ed constraints to be broken. Therefore, steps 1 through 4 (or sometimes
only 2 through 4, depending on how collisions and constraints are resolved)
are repeated until either (a) all collisions have been successfully resolved
and all constraints are satisfi ed, or (b) a predefi ned maximum number of
iterations has been exceeded. In the latt er case, the solver eff ectively “gives
up,” with the hope that things will resolve themselves naturally during sub-
sequent frames of the simulation. This helps to avoid performance spikes
by amortizing the cost of collision and constraint resolution over multiple
frames. However, it can lead to incorrect-looking behavior if the errors are
too large or if the time step is too long or is inconsistent. Penalty forces can
be blended into the simulation in order to gradually resolve these problems
over time.
12.4.10.1. The Constraint Solver
A constraint solver is essentially an iterative algorithm that att empts to satisfy
a large number of constraints simultaneously by minimizing the error between
the actual positions and rotations of the bodies in the physics world and their
ideal positions and rotations as defi ned by the constraints. As such, constraint
solvers are essentially iterative error minimization algorithms.