Graphics Reference
In-Depth Information
the principal coordinate axis most parallel with
L
. To summarize, the interval overlap
method proceeds as follows.
1. Compute the plane equation of triangle 1. Exit with no intersection if the vertices
of triangle 2 are all on the same side of this plane.
2. Compute the plane equation of triangle 2. Exit with no intersection if the vertices
of triangle 1 are all on the same side of this plane.
3. Compute the line
L
of intersection between the two planes.
4. Determine which principal coordinate axis is most parallel with the intersection
line
L
.
5. Compute scalar intersection intervals for each triangle with
L
, as projected onto
this principal axis.
6. The triangles intersect if the intersection intervals overlap; otherwise, they do not.
C code for this test is publicly available for download on the Internet.
A test of roughly the same time complexity as the interval overlap method, but
conceptually easier, is the penetration method used in the ERIT package of inter-
section tests [Held97]. It tests if the second triangle straddles the plane of the first
triangle, exiting with “no intersection” if not. Otherwise, the line segment realizing
this intersection is computed. This segment is then tested for intersection and con-
tainment against the first triangle, to determine the final intersection status of the
two triangles. This penetration method can be summarized as follows.
1. Compute the plane equation of triangle 1. Exit with no intersection if the vertices
of triangle 2 are all on the same side of this plane.
2. Compute the intersection between triangle 2 and the plane of triangle 1. This is a
line segment in the plane of triangle 1.
3. Test if the line segment intersects or is contained in triangle 2. If so, the triangles
intersect; otherwise, they do not.
As an optimization to step 3, Held suggests projecting the line segment and triangle
2 to the principal plane the triangle is most parallel with and solving the intersection
as a 2D triangle/line-segment test.
The final method mentioned here, similar to the interval overlap method, is pre-
sented in [Devillers02]. The first two steps are identical, but then the Devillers method
relies on bringing the two triangles into a canonical form to simplify the interval over-
lap test on the line
L
of intersection between the two planes. The canonical form is
achieved by cyclical permutation of the triangle vertices so that the vertex that lies
alone on one side of the plane of the other triangle is the first vertex of each triangle
