Graphics Reference
In-Depth Information
lies in the plane of the triangle, any point on the segment in intersection with the
triangle realizes the closest points. An alternative method for determining the closest
points between a segment and a triangle, based on a vector calculus approach, is
outlined in [Eberly01] and [Schneider02].
5.1.11
Closest Points of Two Triangles
As for the case of determining the closest pair of points between a segment and a tri-
angle, there may be an infinite number of equally close points between two triangles.
However, the closest points between two triangles
T
1
and
T
2
can always be realized in
such a way that one point lies on the boundary of one of the triangles. Consequently,
a pair of closest points between two triangles can be found by computing the closest
points between segment and triangle for all six possible combinations of an edge
from one triangle tested against the other triangle. The pair of points having the least
(squared) distance then corresponds to the closest pair of points of minimum global
distance.
Segment-triangle distance tests are fairly expensive, and thus a better realization
is that the closest pair of points between
T
1
and
T
2
can be found to occur either
on an edge from each triangle (Figure 5.12a) or as a vertex of one triangle and a
point interior to the other triangle (Figure 5.12b). The problem now becomes that
of computing the closest points among all pairs of edges, one from each triangle,
and the closest point on the opposite triangle for each vertex of each triangle (when
said vertex projects interior to the other triangle). In all, six vertex-triangle tests and
nine edge-edge tests are required. Out of all pairs of closest points, the one with the
overall smallest distance corresponds to the globally closest pair of points between
the triangles.
If the triangles are not known a priori to be disjoint, an additional test is required to
rule out the intersection of the two triangles. When intersecting, the distance between
(a)
(b)
Figure 5.12
The closest pair of points between two triangles can be realized (a) as lying on
an edge from either triangle or (b) as a vertex of one triangle and a point interior to the other
triangle.
