Game Development Reference

In-Depth Information

12.2.2 Constraint Solver

The threads of the cloth are modeled as distance constraints. An individual con-

straint strives to maintain a constant distance between two particles. A particle

typically has more than one constraint attached to it. This network of constraints

is solved with a relaxation solver.

A relaxation solver simply solves each individual constraint independently

of the other constraints in the system. Solving one constraint will potentially

violate the other connected constraints. However, each time we iterate over all

the constraints in the system, the overall global error is reduced. Given enough

time, the system converges to a solution.

To solve an individual constraint, we directly update the positions of the at-

tached particles [Provot 95].

Vector3 pa = constraint.m particleA.currentPosition;

Vector3 pb = constraint.m particleB.currentPosition;

float
targetDistance = constraint.m restingDistance;

Vector3 dp = pa
−
pb;

distance = dp.length();

float
derr = (distance
−
targetDistance)/distance;

pa += dp
∗
0.5
∗
derr;

pb
−
=dp
∗
0.5
∗
derr;

Often, the rate of convergence for a relaxation solver can be improved slightly

by using a technique called over-relaxation. With over-relaxation, we simply

overshoot our target by a percentage of the existing error. This technique can

cause unwelcome artifacts, so use with caution. In the context of character cloth,

I have found that a value of 1.15 allows us to perform 10% fewer iterations while

remaining artifact free. This makes some intuitive sense. Since the cloth tends

to have more stretching along the longer noncyclical paths during the course of

a simulation, over-shooting helps accelerate the global shrinking in those direc-

tions, i.e., hanging capes or shirts have their bottoms pulled up quicker.

float
relaxationFactor = 1.15;

pa += dp
∗
0.5
∗
derr
∗
relaxationFactor;

pb

−

∗

∗

∗

=dp

0.5

derr

relaxationFactor;