Game Development Reference

In-Depth Information

be the face's normal and will be the point shared between areas
A
i
=

G

(
v
i
)
,

i
=0
,...,n
.

In SAT, we seek supporting features for opposite directions in two colliding

shapes
A
and
B
. Thus, to find the pair of supporting features for a direction
s
,

we can find where

−

s
lies in

G

(
A
) for shape
A
support. For shape
B
,we'llfind

where
s
lies in

G
(
B
), or, equivalently, where

−
s
lies in the negated Gauss map

−G
(
B
), with each
x
∈G
(
B
) mapped to

−
x
∈−G
(
B
).

Let's superimpose

G

(
A
) and

−G

(
B
) and call the result

S

. It lets us intuitively

and quickly see the pair of features for any direction
s
.
8

It also shows that if

the Gauss maps

(
f
B
) with features
f
A
on
A
and
f
B
on
B
do not

overlap, there is no separating direction where those features would be the pair of

supporting features, and it doesn't make sense to check them. For example, if the

Gauss maps of a pair of edges do not intersect, we don't have to check that pair

of edges. This eliminates a lion's share of edge pairs to check. It also has another

important consequence.

Whenever a pair of features overlap on

G

(
f
A
) and

−G

, those two features
are
the support-

ing features in any direction that belongs to both of them on

S

. There's no need

to build a DK hierarchy or perform a supporting feature search: in that direction,

we already have all the information to compute the translation distance. If edges

are collinear on

S

, we don't need to take them into account because there will be

several face-vertex feature pairs attaining the same distance. Vertex-vertex inter-

sections form an infinity of possible SA directions, but fortunately, we don't need

to check them if our shapes penetrate. If they don't penetrate, we can easily estab-

lish a candidate SA as a line going through both vertices. If the vertices coincide

(hence we can build no line), we can just assume the shapes penetrate.

If the normal
n
of a face in
A
is outside of

S

(
v
B
), we don't need to

check that face-vertex pair. We probably still need to check direction
n
as a

candidate SA, because
n
will surely be inside at least one spherical polygon

−A

−G

(
v
B
), unless we establish that the corresponding vertex cannot be a

separating supporting feature. It is possible to establish, for example, whether the

vertex is on the “far end” of the convex hull from the other shape (see
http://www

.codercorner.com/blog/?p=24
for details of the idea). But more importantly, it lets

us reduce the support computation to a mere dot product. Wherever area

=

−G

−A

is

overlapped by
n
,

will correspond to the supporting vertex
v
B
on the shape

B
. The signed distance of
v
B
to
f
A
is the separating distance between shapes
A

and
B
in the direction
n
.

−A

8
However, we are not interested in just any direction due to SAT. For penetrating objects, the only

interesting directions are face normals and directions orthogonal to a pair of edges from both shapes.

The latter are the points of intersection between edges on
S
: remember that points on the Gauss map

are also unit vectors, defining directions in
R
3
.