Game Engine Architecture

641

able on the topic. (For a start, check out htt p://en.wikipedia.org/wiki/Verlet_
integration.)
The regular Verlet method is att ractive because it achieves a high order
(low error), is relatively simple and inexpensive to evaluate, and produces a
solution for position directly in terms of acceleration in one step (as opposed
to the two steps normally required to go from acceleration to velocity and then
from velocity to position). The formula is derived by adding two Taylor series
expansions, one going forward in time and one going backward in time:

(^) r(t 1 += +t) () ()rrt 11 tt t t+^12 r() 1 t^2 + 61 r() 1 t Ot^3 +Δ(^44 ); (^) Δ Δ ΔΔ
r(tt^1 −= −t) () ()rr^11 t^ t+ 21 r()t^1 t^2 −^16 r()t^1 t Ot^3 +Δ(^44 ). Δ Δ ΔΔ
Adding these expressions causes the negative terms to cancel with the corre-
sponding positive ones. The result gives us the position at the next time step
in terms of the acceleration and the two (known) positions at the current and
previous time steps. This is the regular Verlet method:
r(t 1 += −−+t)^2 rr() (t 11 ttt) ()a 1 t Ot^24 +Δ( ). Δ ΔΔ
In terms of net force, the Verlet method becomes
r rr
F
( ) () ( )
()
t tt ( ).
t
m
1 += −−+t^211 t net^1 t Ot^24 +Δ Δ ΔΔ
The velocity is conspicuously absent from this expression. However, it can
be found using the following somewhat inaccurate approximation (among
other alternatives):
v
()t rr(tt) () ( ).
t
1 +=Δ^11 +−Δ +Ot
Δ
t t Δ
12.4.4.5. Velocity Verlet
The more commonly used velocity Verlet method is a four-step process in which
the time step is divided into two parts to facilitate the solution. Given that
a()t 1 =Fr v( , ( ), ( ))tt11 1^ tm is known, we do the following:

1. Calculate r(t t tt 1 += +t) () ()rv 11 t^ +Δ 21 a() .t 1 2 ΔΔ


2. Calculate v(t tt 1 +=+ 21 ΔΔt) ()va 1 12 () .t 1


3. Determine aa(tt 12 += =Δt) ()Fr v( , ( ), ( ))tt22 2^ tm.


4. Calculate vv()( )().t 11 +Δ =t t+ Δ + 2211 tta 1 +Δ Δt^ t

Notice in the third step that the force function depends on the position
and velocity on the next time step, r(t 2 ) and v(t 2 ). We already calculated r(t 2 ) in
step 1, so we have all the information we need as long as the force is not ve-

12.4. Rigid Body Dynamics