Game Development Reference

In-Depth Information

Figure 4.16.
Filtering
s
in the case of
EE
: (a), (b), and (c) candidate support feature,

requiring additional tests; (d), (e), and (f) noncandidate feature pair.

4.7.2

Limiting Edge-Edge Checks

Since we need to test only the edge pairs for which the respective Gauss maps

overlap, we can quickly reject the majority of edge pairs. The Gauss map of an

edge is an arc that connects the normals of the edge's adjoining faces. Figure 4.16

illustrates that, indeed, if the separating features are two edges the cross product

of the edge directions corresponds to the point of intersection of the edges' Gauss

maps.

In this section, we present a quick test that determines whether two arcs on a

Gauss map intersect. The test boils down to a simple origin-in-tetrahedron test,

which is many times faster than performing a supporting-feature search on the

shapes. These tests work for polyhedra (i.e., polytopes that have volume). How-

ever, with a few simple measures, the test can be performed on arbitrary poly-

topes. See Section 4.7.3 for some additional considerations in the case of flat

(non-three-dimensional) polytopes (such as single polygons, wedges, capsules,

etc.).

The
EE
case deserves some special attention. The support direction is always

s
=

±

norm
||·||
(
e
A
×

e
A
∈

E
(
A
),
e
B
∈

E
(
B
) fail to satisfy even the necessary conditions to be a

support feature pair:

1. Shape
A
must be in front of

P
A
(
s
min
) (Equation (4.1)).

2. Shape
B
must be in front of

P
B
(

−

s
min
) (Equation (4.2)).