Game Development Reference
The number of necessary iterations varies depending on the physical system sim-
ulated and the amount of motion. The relaxation can be made adaptive by mea-
suring the change from the last iteration. If we stop the iterations early, the result
might not end up being quite valid but because of the Verlet scheme, in the next
frame it will probably be better, the next frame even more so, etc. This means that
stopping early will not ruin everything, although the resulting animation might
appear somewhat sloppier.
11.3.3 Cloth Simulation
The fact that a stick constraint can be thought of as a really hard spring should
underline its usefulness for cloth simulation. Assume, for example, that a hexag-
onal mesh of triangles describing the cloth has been constructed. For each vertex
a particle is created, and for each edge a stick constraint between the two corre-
sponding particles is initialized (with the constraint's “rest length” simply being
the initial distance between the two vertices).
To solve for these constraints, we use relaxation as described above. The
relaxation loop could be iterated several times. However, to obtain nice-looking
animations for most pieces of cloth, only one iteration is necessary! This means
that the time usage in the cloth simulation depends mostly on the N square root
operations and the N divisions performed (where N denotes the number of edges
in the cloth mesh). As we shall see, a clever trick makes it possible to reduce this
to just N divisions per frame update—this is really fast, and some might argue
that it probably can't get much faster.
Optimizing away the square root. We now discuss how to get rid of the square
root operation. If the constraints are all satisfied (which they should be, at least al-
most), we already knowwhat the result of the square root operation in a particular
constraint expression ought to be, namely, the rest length r of the corresponding
stick. We can use this fact to approximate the square root function.
Mathematically, what we do is approximate the square root function by its
first-order Taylor expansion at a neighborhood of the squared rest length r 2 (this
is equivalent to one Newton-Raphson iteration with initial guess r ). A real-valued
function f may be approximated around a neighborhood a by using its Taylor
f ( x )= f ( a )+ f ( a )
a )+ f ( a )
a ) 2 + ....
In the case of the square root function f ( x )= √ x around a = r 2 ,wegetthe