Game Engine Architecture

640 12. Collision and Rigid Body Dynamics

terms represent the error inherent in the method. For example, the explicit

Euler equation is

r rr() () () .tt2 11=+t  Δ t

The infi nite Taylor series expansion of the exact solution is

rr() () ()t2 11=+t rrtt t ΔΔ Δ+ 21 () 1 tt^2 + 61 r() 1 t^3 +....

Therefore, the error is represented by all of the terms aft er the v Δt term, which

is of order O(Δt^2 ) (because this term dwarfs the other higher-order terms):

Er=+ +r

=

12 1 2 16 1 3

2

( ) ( ) ...

( ).

tt

Ot

ΔΔ

Δ

tt

To make the error of a method explicit, we’ll oft en write its equation with the

error term added in big “O” notation at the end. For example, the explicit Eu-

ler method’s equation is most accurately writt en as follows:

We say that the explicit Euler method is an “order one” method because it

is accurate up to and including the Taylor series term involving Δt to the fi rst

power. In general, if a method’s error term is O(Δt(n + 1)), then it is said to be an

“order n” method.

12.4.4.3. Alternatives to Explicit Euler

The explicit Euler method sees quite a lot of use for simple integration tasks in

games, producing the best results when the velocity is nearly constant. How-

ever, it is not used in general-purpose dynamics simulations because of its high

error and poor stability. There are all sorts of other numerical methods for solv-

ing ODEs, including backward Euler (another fi rst-order method), midpoint

Euler (a second-order method), and the family of Runge-Kutt a methods. (The

fourth-order Runge-Kutt a, oft en abbreviated “RK4,” is particularly popular.)

We won’t describe these in any detail here, as you can fi nd voluminous infor-

mation about them online and in the literature. The Wikipedia page htt p://

en.wikipedia.org/wiki/Numerical_ordinary_diff erential_equations serves as

an excellent jumping-off point for learning these methods.

12.4.4.4. Verlet Integration

The numerical ODE method most oft en used in interactive games these

days is probably the Verlet method, so I’ll take a moment to describe it in

some detail. There are actually two variants of this method: regular Verlet

and the so-called velocity Verlet. I’ll present both methods here, but I’ll leave

the theory and deep explanations to the myriad papers and Web pages avail-

r rr() () ()t2 11=+t tΔΔ t+Ot( ).^2