Game Development Reference

In-Depth Information

Figure 10.6.
Minimizing the number of nonzero elements. The first plot shows
S
without

ordering. The second plot shows
L
without ordering. The third plot shows
S
after ordering.

And the last plot shows
L
after ordering
S
.

Equation (10.22) as

x
=
S
−
1
b.

Unfortunately, that leads to no improvement. The main drawback is that although

S
is symmetric,
S
−
1
is not, and
S
−
1
b
would have an
O
(
n
2
) complexity.

Instead, it is better to precompute the Cholesky factorization of
S
:

S
=
LL
T
,

where
L
is a lower triangular matrix. Then, solve Equation (10.22) using the

Gauss elimination method.

The Cholesky factorization is performed in a precomputation stage. Much

literature exists on this subject, which we are not going to describe here. We do

know that the number of zero elements in
L
must be maximized. A good way

of maximizing the number of zeroes is ordering the system matrix
S
beforehand.

We recommend the use of the
minimum degree algorithm
. Figure 10.6 shows the

nonzero elements in
S
and
L
for a particular model. The dots show the nonzero

elements. It can be appreciated that the minimum degree algorithm drastically re-

duces the number of nonzero elements in the Cholesky factorization. We suggest

looking at [Press et al. 07] to learn more about Cholesky factorization and [Tinney

and Walker 67] to learn more about the minimum degree algorithm.

10.5 Surface-Mesh Update

A coarse mesh implies a faster simulation but it also implies less appeal.To keep

real-time simulations, two meshes are built for each object (see
Figure 10.7
)
:

•

a volumetric coarse representation made of tetrahedrons and used only for

the physical simulation,