Graphics Reference
In-Depth Information
C
C
Q
Q
P
P
P
A
B
A
B
(a)
(b)
Figure 5.11
The closest pair of points between a line segment and a triangle can always be
found either (a) between an endpoint of the segment and the triangle interior or (b) between
the segment and an edge of the triangle.
may be an infinite number of pairs equally close. However, regardless of whether the
segment is parallel to the plane or not it is always possible to locate points such that
the minimum distance occurs either (a) between an endpoint of the segment and the
interior of the triangle or (b) between the segment and an edge of the triangle. These
two cases are illustrated in Figure 5.11.
Case (a) can occur only if the projection of a segment endpoint onto the suppor-
ting plane of the triangle lies inside the triangle. However, even when a segment
endpoint projects inside the triangle an edge of the triangle may provide a closer
point to the segment. Thus, the closest pair of points can be found by computing the
closest pairs of points between the entities
segment
PQ
and triangle edge
AB
,
segment
PQ
and triangle edge
BC
,
segment
PQ
and triangle edge
CA
,
segment endpoint
P
and plane of triangle (when
P
projects inside
ABC
), and
segment endpoint
Q
and plane of triangle (when
Q
projects inside
ABC
)
and returning the pair with the overall smallest minimum separating distance as the
result.
The number of tests required can be reduced in some cases. For example, when both
endpoints project inside the triangle no segment-edge tests are necessary, because
either endpoint projection must correspond to a closest point. When one endpoint
projects inside the triangle, only one segment-edge test is required. When both end-
points project outside the triangle, one of the segment-edge tests is not needed.
For the latter two cases, the necessary segment-edge tests can be determined by
examining which Voronoi regions the segment endpoints lie in.
A remaining case is when the segment intersects the triangle. For a transverse inter-
section, the intersection point corresponds to the closest points. When the segment
