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.