Game Development Reference

In-Depth Information

Figure 4.20.
Computing
e
for a flat angle arc: (a) edge, normals, and arc orientation;

(b) flat-angle arc direction; (c) flipped normal order; and (d) flipped edge direction, which

is only free in the flat-angle case.

simply assume
e
=

according to

the right-hand rule. See Figure 4.20(b) for an example. If we switch
n
0
and
n
1

and keep the direction of
e
, we'll effectively flip the arc (see
Figure 4.20(c)
)
. If

we flip the direction of
e
, we'll also effectively flip the arc (see
Figure 4.20(d)
)
.

Thus, it is always possible to choose the direction of
e
that works with our arc-arc

test. Just keep in mind the direction of the arc from
n
0
to
n
1
: it must be consis-

tent with right-hand-rule rotation with regard to direction
e
, and that is all that is

needed for the arc-arc test to work.

Notice that the arc-arc test does not work with arcs of over 180
◦
. Neither does

the origin-in-tetrahedron test work with such arcs. Fortunately, polytope SAT

does not have to deal with such cases, as all normals of the collision shape must

point “outwards” of the shape. In nonpolytope cases, special care must be taken.

For example, the one edge in a capsule shape maps to a great circle on

±

norm
||·||
(
v
1
−

v
0
) and choose the sign

±

2
,sowe

S

must employ a different kind of edge-edge culling.

Figure 4.21.
SAT traits: (a) SAT can skip vertex-vertex pairs for penetrating shapes;

(b) SAT search space is inherently concave: the typical and simple Minkowski sum may

have six (or more) local minima (corresponding penetrating distance vectors shown).