Fast 3D Line Segment—Triangle Intersection Test

Nick Chirkov
ArtyShock LLC

This paper appears in issue Volume 10, Number 3.
An electronic version of this article is available.

Abstract

I present a clean algorithm for determining if a line segment intersects a triangle in three dimensions. The algorithm performs a few binary tests that check if a point of intersection of the line segment and triangle plane is inside the triangle. Then I present some essential optimizations for this algorithm that reduce overall computation complexity. The algorithm does not compute an intersection point.

The algorithm is comparable with others, but I believe it is the fastest one when additional memory storage is available.

Author Information

Nick Chirkov, ArtyShock LLC, 1-4 Zheleznodorozhnaya St.431441 Ruzaevka, Morodovia, Russian Federation nickchir@artyshock.net

Timing Comparison

Here is a report on the efficiency of this algorithm as compared with the Moller-Trumbore algorithm: Timing Comparison Report

Source Code

Downloadable C++ source code implements the algorithm described in this paper. Here is the core algothim: C2005.cpp (4K html). And here is an archive containing the test framework with several variants of the algorithm, as well as the Moller-Trumbore code: C2005.zip (12K zip archive).

Images

Errata

Due to a printing error, the second page of this article is missing some subscripts.

Download the corrected page.

BibTeX Entry

@article{Chirkov05,
  author = "Nick Chirkov",
  title = "Fast 3D Line Segment—Triangle Intersection Test",
  journal = "journal of graphics, gpu, and game tools",
  volume = "10",
  number = "3",
  pages = "13-18",
  year = "2005",
}