Game Development Reference
The signed distance d min = d A −
d B )= d A + d B is between the planes
P A ( s min ) and
P B (
s min ). Equation (4.3) maximizes d over all unit directions
It's easy to see that d min is the same as the standard Euclidean distance in the
case of disjoint shapes A and B . In the case of colliding shapes, it's the minimal
distance and direction we have to translate one of the shapes to get them into
a nonpenetrating but contacting state. Just translate A by
d min s min or B by
d min s min . Empirically, that's one of the least intrusive and most robust ways to
resolve penetration error between two rigid bodies in physics simulation, which
is why we're after it.
Let's call all points from shape S lying in plane
P S ( s ) the support feature
F S ( s )
F S is either a point, a straight line
segment, or a flat convex area on the surface of S . Obviously, in polytopes
∩P S ( s ). For a convex shape S ,
only be a vertex, edge, or face. In Figure 4.4(b),
F A ( s ) is the bold edge on A and
F B (
− s ) is a vertex of B .
It may not be trivially apparent, but
F A ( s ) and
F B (
s ) projected onto any
s ) always intersect. If the projections don't intersect and
we translate B by d min s min , the shapes would not touch, which contradicts the
definition of d min . This observation will help us limit the set of possible MTDs
given the pair of support features.
The important point is that s min defines d min ,
P A ( s ) or
P B (
F A ( s min ),and
F B (
s min )
Even though most of this chapter may be generalized to any convex shape, all
subsequent conclusions and algorithms are described in the domain of polytopes.
For practical reasons, it is assumed that the vertices, edges, and faces, as well as
their connectivity, are easily available during most computations.
It is easy to directly apply the described algorithms to a sphere, capsule,
and wedge. Note that those shapes are Minkowski differences between shape A
(point, segment, and polygon, correspondingly) and sphere B of radius r B located
at o . Just compute the separating axis (SA) 3 and distance for the corresponding
shape A and subtract the r B from the distance.
It is less obvious and more complex, but still possible, to generalize the al-
gorithms to curved (not polytope) shapes. The resulting algorithms may be con-
structed to be iterative or direct computation, but to be efficient and concise, they
must be restricted to relatively limited subclasses of convex shapes, at least from
my experience. These algorithms are not the main topic of this chapter.
3 SA is normally the contact normal.