Game Development Reference

In-Depth Information

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

2
. (See
Figure 4.4(b)
.)

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

s

∈
S

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

≡

A

∩P
S
(
s
). For a convex shape
S
,

F

can

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

plane

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
)

unambiguously.

4.4.1

Polytopes

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.