Game Development Reference
Figure 4.2. Simplified physics engine pipeline stages and data flow. (Car image from
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
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.