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 B ) in this case (see Table 4.3 ). However, most edge pairs
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)).