Game Development Reference

In-Depth Information

Figure 4.2.
Simplified physics engine pipeline stages and data flow. (Car image from

www.public-domain-photos.com.
)

for finding penetration depth, direction, and location, all of which combined form

one contact point. We can stop there and accumulate contact points over multiple

frames. Or we can find the whole contact manifold, which is more CPU intensive,

but we don't have to keep it in memory if we regenerate it every frame. We'll de-

scribe an algorithm based on the separating axis theorem (SAT).
1
We'll describe

a simple algorithm to find an approximate contact manifold by perturbing pene-

tration direction, finding outlines of the contact surfaces from two convex bodies,

and intersecting them.

The shape in Figure 4.1(d) is a complex rigid object, and our algorithm will

generate many contact manifoldsâ€”one for each leg. But the additional pass of

these contacts may eliminate many of them, leaving only four essential corner

points. As far as the solver is concerned, these four points are even better because

the object stays stable, and it is faster to solve. Also notice that the solver uses the

object's inertia tensor and mass, but does not care what geometrical shape it has.

It may as well be a box on a plane (in this particular case); the solver will work

just the same. This has a practical consequence: we need to design and optimize

in-memory representations of collision shapes primarily for the narrow phase,

and only the narrow phase needs to precache collision shapes for performance

or direct memory access them to the local store on a PlayStation
R

3orother

nonunified memory architectures. Generally, only the narrow phase needs access

to the precise definition of the shape of colliding objects. Just an axis-aligned

bounding box usually suffices for the broad phase, where the solver doesn't care

about the shapes at all, just the contact points.

1
The acronym SAT is also commonly used to refer to a class of algorithms due to the theorem.