A Fast Triangle-Triangle Intersection Test

Tomas Möller
Prosolvia Clarus AB

This paper appears in issue Volume 2, Number 2.
Purchase this issue from the akpeters.com web site.

Abstract

This paper presents a method, along with some optimizations, for computing whether or not two triangles intersect. The code, which is shown to be fast, can be used, for example, in collision detection algorithms.

Author Information

Tomas Möller, Prosolvia Clarus AB, Chalmers University of Technology, Gardavagen, S-41250S-41250 Gothenberg, Sweden tompa@clarus.se

Source Code

Downloadable C code contains three routines:

  • tri_tri_intersect(), the algorithm as described in the paper.
  • NoDivTriTriIsect(), a newer version (June 2001) that runs a bit faster. Optimized by the author, replacing divisions with some multiplications (from an idea by Dave Eberly).
  • tri_tri_intersect_with_isectline(), a version that computes the line of intersection when the triangles overlap().

Revision history:

  • 22 Oct 1997
    • Program creation.
  • 28 Jul 1998
    • Added #include <math.h>
      Thanks to Max Fischer for catching this.
  • 25 Jun 2001
    • Added optimized version and version that computes the line of intersection.

Errata

  • Page 26, after equation (1), the text reads:
    (multiplied by a constant |N2|)
    but the correct constant is the square of that value, i.e. the text should read:
    (multiplied by a constant N2 · N2)

BibTeX Entry

@article{Moller97,
  author = "Tomas Möller",
  title = "A Fast Triangle-Triangle Intersection Test",
  journal = "journal of graphics, gpu, and game tools",
  volume = "2",
  number = "2",
  pages = "25-30",
  year = "1997",
}