Philippe Guigue, Olivier Devillers
This paper presents an
algorithm for determining whether two triangles in three dimensions intersect. The
general scheme is identical to the one proposed by Möller.
The main difference is that our algorithm relies exclusively on the sign of 4 x
4 determinants and does not need any intermediate explicit constructions which
are source of numerical errors. Besides the fact that the resulting code is
more reliable than existing methods, it is also more efficient.
Downloadable C code contains two routines:
tri_tri_overlap_test_3d(), the predicate described in the
paper.
tri_tri_intersection_test_3d(), the version that computes the line segment of intersection
if the triangles do overlap and are not coplanar.
Revision history:
|
|
|
|
July 2002 |
Program creation. |
|
October 2002 |
Added optimizations. |
|
January 2003 |
Added
version that computes the line of intersection. |
|
June 2003 |
Bug fix.
Thanks to Tushar Udeshi
for pointing the bug out! |
Several
solutions exist to test the intersection between three-dimensional triangles,
although the most important ones, due to their efficiency, are the algorithms
proposed by Möller ( Tomas Möller,
A fast triangle-triangle intersection test, Journal of graphics tools,
2(2):25--30, 1997) and Held ( Martin Held, ERIT -- A collection of efficient and reliable intersection tests, Journal of graphics tools,
2(4):25--44, 1997). Both are based on a constructive multistep
process. In the following, we describe these two approaches.
In
the sequel, T1 and T2 denote triangles with vertices p1, q1, and r1, and p2,
q2, r2 respectively. pi_1 and pi_2 denote their
respective supporting planes, and L the line of intersection of the two planes.
Möller's method begins by checking the mutual
intersection of each triangle with the plane of the other. To do so, it
determines for each triangle on which side of the other triangle
's supporting plane its vertices lie. Now, if all vertices of one
triangle lie on the same side and no vertex is on the plane, the intersection
is rejected. Otherwise, the input triangles are guaranteed to intersect the
line of intersection of the two planes. Furthermore, these intersections form
intervals on this line, and the triangles overlap iff
these intervals overlap as well. Hence, the last part of the algorithm computes
a parametric equation L(t) of the line of intersection
of the two planes, finds the intervals (i.e. scalar intervals on L(t)) for
which the line lies inside each triangle and performs a one-dimensional
interval overlap test.
Held's code begins similarly by determining on which
side of the supporting plane pi_1 the vertices p2, q2, r2 lie. If T2's vertices
do not all lie in one of the closed halfspaces
induced by pi_1 the second part directly constructs the line segment s of
intersection between T2 and pi_1 and the problem is reduced to testing whether
the segment s intersects T1. The constructed segment is coplanar with T1 so
this intersection is solved by a a
two-dimensional triangle/line-segment test after projecting to a convenient
plane.
Despite
their efficiency, these multistep processes have two disavantages. First, degenerate cases at each step of the
process need to be handled specifically. Second, using the derived values from
the initial constructions increases the required arithmetic precision and
results in an error-prone implementation. The triangle overlap test that we developped (tri_tri_overlap_test()) does not need any
intermediate construction but relies exclusively on orientation predicates. In
consequence, its implementation has only degree three and is more reliable than
Möller and Held codes.
In
our algorithm tri_tri_overlap_test(), all branching decisions are carried out by evaluating
the sign of orientation predicates which are degree three polynomials. Therefore,
the algorithm has degree three.
To compare this against Möller approach, we
could parametrize the line of intersection of the two
supporting planes as L(t) = O + tD,
where D is the cross-product of the normals to the
plane and O is some point on it, and solve for the values of t (i.e scalar intervals on L) that correspond to the
intersection between the triangles and L. The algorithm then has to compare
these t values. There actually exist two different implementations of the
algorithm in http://www.acm.org/jgt/papers/Moller97/. tri_tri_intersect() uses a
simplified projection of the vertices onto L and has to compare rational
polynomials with numerator of degree four and denominator of degree three. However,
this version contains divisions and shall be seen as a real polynomial
implementation of degree seven. NoDivTriTriIsect() replaces divisions with multiplications and is a little
faster but has to compare degree thirteen polynomials.
Held's algorithm TriTri3d() computes the line segment
of intersection of T2 with the plane pi_1 by evaluating rational polynomial
with numerator four and denominator of degree three. It then solves a
two-dimensional segment-triangle that involves degree two polynomials in the
input variables.
Hence, all three algorithms have degree at least seven. Consequently, our
algorithm allows to limit the arithmetic requirements
of a robust implementation. When operations are implemented in IEEE754 floating
point arithmetic (as originally done in Moller and
Held codes), then fewer bits are lost due to rounding and all branching
decisions are proved to be correct with high probability if the triangles
vertices are independently evenly distributed in a cube. When operations are
implemented exactly using a multiprecision package or
fixed point, then our method requires less arithmetic or allows a larger domain
for input.
While the emphasis of this algorithm is on reducing arithmetic requirements, it can be also proved to be computationally efficient. We now evaluate our code in terms of number of operations. Each code is divided into discrete parts according to the branching structure of its rejection steps. For the purpose of this evaluation, the operations within each code are divided into five types: addition/substraction, multiplication, branching decisions, assignments, divisions and absolute values. Most listed operations take a fixed number of cycles. Floating-point division (resp. conditional branching) takes about six times (resp. 1.25 times) as long as the other operations.
|
Min/Max number of arithmetic
operations. General case. |
||||||
|
Code |
ADD |
MUL |
CMP |
ASS |
DIV |
ABS |
|
tri_tri_overlap_test() |
||||||
|
T1 intersects pi_2? |
24 |
17 |
2 |
21 |
0 |
0 |
|
T2 intersects pi_1? |
24 |
17 |
2 |
21 |
0 |
0 |
|
min(I2) > max(I1)? |
14 |
9 |
7/13 |
12/32 |
0 |
0 |
|
min(I1) > max(I2)? |
14 |
9 |
1 |
12 |
0 |
0 |
|
NoDivTriTriIsect() |
||||||
|
T1 intersects pi_2? |
21 |
20 |
2 |
15 |
0 |
0 |
|
T2 intersects pi_1? |
21 |
20 |
2 |
15 |
0 |
0 |
|
I1 intersects I2? |
15 |
23 |
7/18 |
32/42 |
0 |
3 |
|
tri_tri_intersect() |
||||||
|
T1 intersects pi_2? |
21 |
20 |
2 |
15 |
0 |
0 |
|
T2 intersects pi_1? |
21 |
20 |
2 |
15 |
0 |
0 |
|
I1 intersects I2? |
15 |
10 |
8/24 |
25 |
4 |
3 |
|
TriTri3D() |
||||||
|
T2 intersects pi_1? |
24 |
15 |
6/11 |
24 |
0 |
0 |
|
s intersects T2? |
20/42 |
8/16 |
14/26 |
26/29 |
1/2 |
0 |
Thanks to Julia Flötotto
for valuable discussions and constructive criticism.
Thanks to both Tomas Möller and Ronen Barzel for helping me
improve the contents of the paper.
Last modified: Fri Jun 6 14:38:51 MEST 2003