Game Development Reference

In-Depth Information

where
J
is a matrix of partial derivatives known as the Jacobian. The resulting

matrix is sparse and easy to invert, which makes it useful for large systems, such

as collections of particles.

1.7.4 Verlet Methods

A popular game physics method, mainly due to [Jakobsen 01], is Verlet integra-

tion. In its most basic form, it is a velocity-less scheme, instead using the position

from the previous frame. As we often don't care about the velocity of particles,

this makes it very useful for particle systems.

The general formula for the Verlet method is as follows:

x
i−
1
+
h
2
a
i
.

x
i
+1
=2
x
i
−

While standard Verlet is quite stable, it has the disadvantage that it doesn't

incorporate velocity. This makes it difficult to use with velocity-dependent forces.

One possible solution is to use Leapfrog Verlet:

=
v
i−
1
/
2
+
h
a
i
,

v
i
+1
/
2

x
i
+1

=
x
i
+
h
v
i
+1
/
2
.

However, this does not compute the velocity at the current time step, but in-

stead at the half-time step (this is initialized by using a half-interval Euler step).

While we can take an average of these over two time steps for our force calcula-

tion, we still have problems with impulse-based collision systems, which instan-

taneously modify velocity to simulate contact forces. One solution to this is use

the full velocity Verlet:

v
i
+1
/
2

=
v
i
+
h/
2
a
i
,

x
i
+1

=
x
i
+
h
v
i
+1
/
2
,

v
i
+1

=
v
i
+1
/
2
+
h/
2
a
i
+1
.

However, unlike Euler's method, this does require two force calculations, and we

can get similar stability with the last method we'll consider.

More information on Verlet methods can be found in Chapter 11.

1.7.5 Symplectic Euler Method

We've already seen the symplectic Euler method previously—in fact, it's the

method we were using for the simulation equations in Section 1.6. It is a semi-

implicit method, in that it uses the explicit Euler method to update velocity but