Convexity-based Methods - Real-Time Collision Detection - page 384

(a) (b)

Figure 9.1 (a) For two convex objects a local minimum distance between two points is always
a global minimum. (b) For two concave objects the local minimumdistance between two points
(in gray) is not necessarily a global minimum (in black).

Assuming the polyhedra are both in the same frame of reference (accomplished by,
for example, transforming Q into the space of P ), their intersection can be determined
as follows [Moore88].

1. Intersect each edge of P against polyhedron Q (for example, using the method
described in Section 5.3.8). If an edge lies partly or fully inside Q , stop and report
the polyhedra as intersecting.

2. Conversely, intersect each edge of Q against polyhedron P . If an edge lies partly
or fully inside P , stop and report P and Q as intersecting.

3. Finally, to deal with the degenerate case of identical objects (such as cubes) passing
through each other with their faces aligned, test the centroid of each face of
Q against all faces of P . If a centroid is found contained in P , stop and return
intersection.

4. Return nonintersection.

It may seem like the tests of steps 1 and 2 would subsume step 3. However,
floating-point inaccuracies may cause the tests of the first two steps to fail in the
situation described in step 3, thus making the centroid test necessary to handle this
(infrequent) case. In that the edge tests of steps 1 and 2 are quite expensive, the test
might be better expressed as follows.

1. Test each vertex of Q against all faces of P . If any vertex is found to lie inside all
faces of P , stop and return the polyhedra as intersecting.

2. Repeat the previous step, but now testing each vertex of P against the

faces of Q .