Game Development Reference
In-Depth Information
constraint, however, we may have invalidated one or more of the cube constraints
by pushing a particle out of the cube. This situation can be remedied by immedi-
ately projecting the offending particle's position back onto the cube surface once
moreābut then we end up invalidating the stick constraint once again.
Really, what we should do is solve for all constraints at once, both the box and
the stick constraints. This would be a matter of solving a system of equations. But
instead of explicitly forming the system and solving it with a separate algorithm
for solving systems of equations, we choose to do it indirectly by local iteration.
We simply repeat the two pieces of code a number of times after each other in the
hope that the result is useful. This yields the following code:
void TimeStep StickInBox()
{ VerletTimeStep();
while (notConverged) {
SatisfyBoxConstraints()
SatisfyStickConstraints()
}
}
While this approach of pure repetition might appear somewhat naive, it turns out
that it actually converges to the solution that we are looking for! The method is
called relaxation (or Jacobi or Gauss-Seidel iteration depending on how you do it
exactly, see [Press et al. 92]). It works by consecutively satisfying various local
constraints and then repeating; if the conditions are right, this will converge to
a global configuration that satisfies all constraints at the same time. It is useful
in many other situations where several interdependent constraints must hold si-
multaneously. As a general algorithm for solving equations, the method doesn't
converge as fast as other approaches do, but for interactive physics simulation it
is often an excellent choice.
We get the following overall simulation algorithm (in pseudocode):
void TimeStep()
{ VerletTimeStep();
// Relaxation step
iterate until convergence {
for each constraint (incl. collisions) {
satisfy constraint
}
}
}