Game Engine Architecture

639

t 1 (which is just v(t 1 )) and extrapolating it linearly to the next time step t 2. As
we can see in Figure 12.23, linear extrapolation does not necessarily provide us
with a particularly good estimate of the true position at the next time step r(t 2 ),
but it does work reasonably well as long as the velocity is roughly constant.
Figure 12.23 suggests another way to interpret the explicit Euler method—
as an approximation of a derivative. By defi nition, any derivative is the quo-
tient of two infi nitesimally small diff erences (in our case, dr/dt). The explicit
Euler method approximates this using the quotient of two fi nite diff erences. In
other words, dr becomes Δr and dt becomes Δt. This yields

d

dt t

t

t

t

t

t

rr

v

rr rr

≈

=

−

−

=

−

Δ

Δ

Δ

;

()

() () () ()

1 21.

21

t 21 t

t

which again simplifi es to Equation (12.5). This approximation is really only
valid when the velocity is constant over the time step. It is also valid in the
limit as Δt tends toward zero (at which point it becomes exactly right). Obvi-
ously, this same analysis can be applied to Equation (12.6) as well.

12.4.4.2. Properties of Numerical Methods

We’ve implied that the explicit Euler method is not particularly accurate. Let’s
pin this idea down more concretely. A numerical solution to an ordinary dif-
ferential equation actually has three important and interrelated properties:

z Convergence. As the time step Δt tends toward zero, does the approxi-
mate solution get closer and closer to the real solution?
z Order. Given a particular numerical approximation to the solution of an
ODE, how “bad” is the error? Errors in numerical ODE solutions are
typically proportional to some power of the time step duration Δt, so
they are oft en writt en using big “O” notation (e.g., O(Δt^2 )). We say that
a particular numerical method is of “order n” when its error term is
O(Δt(n + 1)).
z Stability. Does the numerical solution tend to “sett le down” over time?
If a numerical method adds energy into the system, object velocities will
eventually “explode,” and the system will become unstable. On the other
hand, if a numerical method tends to remove energy from the system, it
will have an overall damping eff ect, and the system will be stable.
The concept of order warrants a litt le more explanation. We usually mea-
sure the error of a numerical method by comparing its approximate equa-
tion with the infi nite Taylor series expansion of the exact solution to the ODE.
We then cancel terms by subtracting the two equations. The remaining Taylor

12.4. Rigid Body Dynamics