Basic Primitive Tests - Real-Time Collision Detection - page 145

This overall approach works well and is simple to implement. However, it is pos-
sible to derive a more efficient solution by applying the same basic method used for
finding the closest point on a triangle. First, the Voronoi feature region in which the
point P is located is determined. Once the feature has been obtained, Q is given by
the orthogonal projection of P onto this feature. For a tetrahedron there are 14 overall
Voronoi feature regions that must be considered: four vertex regions, six edge regions,
and four face regions. If P does not lie in one of the feature regions, P must by default
be contained in the tetrahedron. The tests for containment in a feature region are
similar to those made earlier for the triangle. For example, P is now determined to lie
in the vertex Voronoi region of A if the following expressions are satisfied.

( P − A ) · ( B − A ) ≤ 0

( P − A ) · ( C − A ) ≤ 0

( P − A ) · ( D − A ) ≤ 0

For P to lie in theVoronoi region associated with edge AB , the following tests would
have to be satisfied (again assuming a known counterclockwise winding of the faces).

( P − A ) · ( B − A ) ≥ 0

( P − B ) · ( A − B ) ≥ 0

( P − A ) · (( B − A ) × n ABC ) ≥ 0, where n ABC = ( B − A ) × ( C − A )

( P − A ) · ( n ADB × ( B − A )) ≥ 0, where n ADB = ( D − A ) × ( B − A )

Analogous sets of expressions can be defined for testing containment in the
remaining regions. At first glance, this may not seem like an improvement over
the earlier test. However, many of the computed quantities are shared between dif-
ferent Voronoi regions and need not be recomputed. It is also possible to simplify
the expressions involved in testing the Voronoi regions using the Lagrange identity,
similar to the optimization done for the closest-point-on-triangle test. In this case, it
turns out that all tests can be composed in terms of just 10 different dot products.

5.1.7 Closest Point on Convex Polyhedron to Point

Several approaches are available for locating the point on a convex polyhedron H
closest to a point P in space. A simple-to-implement O ( n ) method is to compute
the point on each polyhedron face closest to P and return the one closest to P .A
concurrently run test determines if P lies inside all faces of H , in which case P is
interior to H . To speed up the test, the face distance calculation would have to be run
only when P lies in front of the face.