Graphics Reference
In-Depth Information
A
C
F
F
E
L
D
B
L
B
A
E
C
D
(a)
(b)
Figure 5.19
In the general case, two triangles intersect (a) when two edges of one triangle
pierce the interior of the other or (b) when one edge from each pierces the interior of the
other.
A triangle-triangle test can therefore be implemented in terms of (up to) six edge-
triangle tests. If an edge of one triangle intersects the other triangle, the triangles
intersect. If all six tests fail, they are not intersecting.
The case in which the triangles are coplanar, or one or both triangles are degenerate
(with two or more coincident vertices, turning the triangles into lines or points), is not
handled correctly by this test. In fact, none of the suggested algorithms for triangle-
triangle intersection handle these cases by default: they all rely on theirs being handled
as special cases.
A second approach is to apply the separating-axis test. For intersecting two trian-
gles, 11 separating axes must be tested: one axis parallel to the face normal for each of
the two triangles, plus nine combinations of edges, with one edge from each triangle.
For each axis, the triangles are projected onto the axis and the projection intervals
are tested for overlap. If the projection intervals are found disjoint on any axis, the
triangles are nonintersecting and the test can immediately exit. However, when the
projection intervals overlap on all 11 axes the triangles must be intersecting.
A test similar in spirit to the separating-axis test is the
interval overlap method
suggested by [Möller97b]. However, it is much less expensive than the previous two
tests. As a first step, it tests if the two face normals act as separating axes. This is done
by testing, for both triangles, whether the vertices of one triangle lie fully on one side
of the plane of the other triangle. If so, the triangles are nonintersecting. If not, at this
point, the planes of the triangles must be intersecting in a line
L
,
L
(
t
)
=
P
+
t
d
, where
d
n
2
is the cross product of the two triangle normals
n
1
and
n
2
. Furthermore,
this line must also be intersecting both triangles. The scalar intersection intervals
between each triangle and
L
are now computed (these correspond to the intersection
points marked with black dots in Figure 5.19). Now, only if these scalar intervals
intersect do the triangles intersect. As an optimization, instead of directly computing
the triangle intersection intervals with
L
the intervals are computed and intersected on
=
n
1
×
