Game Development Reference

In-Depth Information

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

series:

f
(
x
)=
f
(
a
)+
f
(
a
)

1!

a
)+
f
(
a
)

2!

a
)
2
+
....

(
x

−

(
x

−

In the case of the square root function
f
(
x
)=
√
x
around
a
=
r
2
,wegetthe

following: