Fast 3D Triangle-Box Overlap Testing

Tomas Akenine-Möller
Chalmers University of Technology

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

Abstract

A fast routine for testing whether a triangle and a box are overlapping in three dimensions is presented. The test is derived using the separating axis theorem, whereafter the test is simplified and the code is optimized for speed. We show that this approach is 2.3 vs. 3.8 (PC vs. Sun) times faster than previous routines. It can be used for faster collision detection and faster voxelization in interactive ray tracers. The code is available online.

Author Information

Tomas Akenine-Möller, Chalmers University of Technology, Department of Computer Engineering412 96 Gothenberg, Sweden tompa@acm.org

Source Code

Downloadable C code contains a routine triBoxOverlap() implementing the algorithm described in the paper.

BibTeX Entry

@article{AkenineMoller01,
  author = "Tomas Akenine-Möller",
  title = "Fast 3D Triangle-Box Overlap Testing",
  journal = "journal of graphics, gpu, and game tools",
  volume = "6",
  number = "1",
  pages = "29-33",
  year = "2001",
}