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

}

}

}