Game Development Reference
objects are already interpenetrating at the beginning of the time step, then no nor-
mal is defined. For these cases, which generally are resting contacts, we need a
different method for computing the proper contact data.
We could compute a pair of witness points to the penetration depth. The
penetration-depth vector is orthogonal to the boundaries of the objects and as such
is a pretty good approximation of a contact normal. The corresponding witness
points could pass as contact points with reasonable fidelity. There are, however, a
few issues with using the penetration depth for obtaining contact data.
First of all, computing the penetration depth is often a lot harder than com-
puting the distance. For general convex objects, the penetration depth can be
found using the expanding polytope algorithm (EPA) [van den Bergen 03]. EPA
is computationally a lot more expensive than GJK and has some initialization
problems for shallow contacts. If we restrict ourselves to polytopes, we can re-
sort to feature-walking or brute-force approaches, but still, the conclusion would
remain that computing penetration depths is harder than computing distances.
Secondly, for triangle meshes, the penetration-depth vectors of the individual
triangles that intersect a query object may not be a good representation of the
actual contact. The shortest translation that separates the object from a triangle
may have a significant lateral component, so an object that intersects an edge
between two triangles is likely to collect two “fighting” normals that point towards
each other. Figure 5.6 depicts this situation. In any physics system, these fighting
normals would show the edge as an obstacle along the path of a sliding or rolling
object, making the object bump into the edge and change direction. Obviously,
this behavior is not what we want.
It is clear that an algorithm for computing penetration depths, such as EPA,
is not our best option for getting contact data, at least not for shallow contacts.
For shallow contacts, we are better off computing closest-point pairs. However,
in order to return a proper normal from a closest-point pair, the query objects
need to have some clearance, since otherwise, the closest points coincide and the
normal will be zero.
Figure 5.6. Contact normals that are derived from the penetration-depth vectors may
cause a sliding or rolling object to bump into an edge of a perfectly flat mesh.