Fast Tetrahedron-Tetrahedron Overlap Algorithm

Fabio Ganovelli and Frederico Ponchio
Istituto Scienza e Technologie dell'Informazione, National Research Council

Claudio Rocchini
Istituto Scienza e Tecnologie dell'Informazione, National Research Council

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

Abstract

We present an algorithm to test two tetrahedra for overlap. The algorithm is based on a dimension reduction technique that allows the application of the Separating Axis Theorem, thus avoiding part of the computation needed to perform the Separating Axis Test. Source code is available on the website listed at the end of this paper.

Author Information

Fabio Ganovelli, Istituto di Elaborazione dell’Informazione, National Research Council Pisa, Italy ganovell@iei.pi.cnr.it

Frederico Ponchio, Istituto di Elaborazione dell’Informazione Pisa, Italy ponchio@iei.pi.cnr.it

Claudio Rocchini, Istituto di Elaborazione dell’Informazione Pisa, Italy rocchini@iei.pi.cnr.it

Source Code

C++ source code for the GPR algorithms is available as a header file: tet_a_tet.h (HTML text).

BibTeX Entry

@article{GanovelliPonchioRocchini02,
  author = "Fabio Ganovelli and Frederico Ponchio and Claudio Rocchini",
  title = "Fast Tetrahedron-Tetrahedron Overlap Algorithm",
  journal = "journal of graphics, gpu, and game tools",
  volume = "7",
  number = "2",
  pages = "17-26",
  year = "2002",
}