Game Development Reference
In-Depth Information
altogether. This is not the case when acceleration is very large, however. In this case
the term may be significant, and moving to Newton-Euler 2 can be beneficial.
Runga-Kutta 4
Both Newton-Euler integrators assume that acceleration will remain constant dur-
ing the entire update. As we saw in chapter 6 when we looked at springs, the way
acceleration changes over the course of an update can be very significant. In fact, by
assuming that acceleration does not change, we can run into dramatic instabilities
and the complete breakdown of the simulation.
Springs aren't the only thing that can change acceleration quickly. Some patterns
of resting contacts (particularly when a simultaneous velocity resolution algorithm is
used) can have similar effects, leading to vibration or a dramatic explosion of object
stacks.
For both problems a partial solution lies in working out the accelerations needed
in mid-step. The fourth-order Runga-Kutta algorithm 1
(or simply RK4) does just
this.
If you read around on physics engines, you'll see mention of Runga-Kutta integra-
tion. I know some developers have used it quite successfully. Personally I have never
had the need. It is much slower than Newton-Euler, and the benefits are marginal. It
is most useful when dealing with very stiff springs, but as we saw in chapter 6, there
are simpler ways to fake the same behavior.
The biggest problem with RK4, however, is that it requires a full set of forces
midway through the step. When combined with a collision resolution system this can
get very messy. In our case we do not directly determine the forces due to contacts,
and we do not want to run a full collision detection routine in mid-step, so RK4 is
of limited use. Even for force-based engines the extra overhead of calculating mid-
update forces gives a huge performance hit.
I have seen developers use RK4 for the rigid-body update and then a separate
collision resolution step at the end. This could be easily implemented in our engine by
replacing the integrate function of the rigid body. Unfortunately, with the collision
resolution not taking part, RK4 loses most of its power, and I feel that the result is
only useful if you have stubborn spring problems.
16.1.4
T HE B ENEFIT OF P ESSIMISTIC C OLLISION D ETECTION
Our algorithm for collision resolution sometimes misses collisions altogether. Fig-
ure 16.2 shows a situation with one collision. The object shown has a low moment of
inertia, so the resolution of this collision will leave the object as shown. Since there
was only one collision detected, this new interpenetration cannot be resolved at this
time step. The player will see the object interpenetrated until the following frame,
1. Unlike Newton-Euler, it is fourth-order because it takes four samples, not because it uses four levels of
differentiation.

Custom Search