Fast and Robust Triangle-Triangle Overlap Test using Orientation Predicates
Philippe Guigue and Olivier Devillers
This paper appears in issue Volume 8, Number 1.
Purchase this issue from the akpeters.com web site.
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. The source code is available online.
Philippe Guigue, INRIA Sophia-Antipolis, BP 93, 2004 Route des Lucioles06902 Sophia-Antipolis Cedex, France Philippe.Guigue@sophia.inria.fr
Olivier Devillers, INRIA Sophia-Antipolis, BP 93, 2004 Route des Lucioles06902 Sophia-Antipolis Cedex, France Olivier.Devillers@sophia.inria.fr
This is one of two simultaneous triangle-triangle overlap papers in this issue; see also Shen, Heng and Tang 03. This paper has also been chosen for inclusion in the book Graphics Tools—The JGT Editors’ Choice; see addendum below.
Downloadable C source code is available here: triangle_triangle_intersection.c (19K HTML text). It contains three routines:
tri_tri_overlap_test_3d(), the three-dimensional predicate described in the paper
tri_tri_overlap_test_2d(), the two-dimensional predicate
tri_tri_intersection_test_3d(), the version that computes the line segment of intersection if the triangles do overlap and are not coplanar.
Added version that computes the line of intersection.
Bug fix. Thanks to Tushar Udeshi for pointing it out!
A Ray-Triangle Intersection Test
As part of the inclusion of this paper in the book Graphics Tools—The JGT Editors’ Choice, the authors discuss how the value of determinants introduced in the paper can be used to obtain an efficient solution for the ray-triangle intersection problem, and provide source code. See: Fast Ray-Triangle Intersection Test Using Orientation Determinants