Premium
A fast triangle to triangle intersection test for collision detection
Author(s) -
Tropp Oren,
Tal Ayellet,
Shimshoni Ilan
Publication year - 2006
Publication title -
computer animation and virtual worlds
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.225
H-Index - 49
eISSN - 1546-427X
pISSN - 1546-4261
DOI - 10.1002/cav.115
Subject(s) - intersection (aeronautics) , rectangle , pentium , computer science , collision detection , collision , algorithm , mathematics , geometry , parallel computing , computer security , engineering , aerospace engineering
The triangle‐to‐triangle intersection test is a basic component of all collision detection data structures and algorithms. This paper presents a fast method for testing whether two triangles embedded in three dimensions intersect. Our technique solves the basic sets of linear equations associated with the problem and exploits the strong relations between these sets to speed up their solution. Moreover, unlike previous techniques, with very little additional cost, the exact intersection coordinates can be determined. Finally, our technique uses general principles that can be applied to similar problems such as rectangle‐to‐rectangle intersection tests, and generally to problems where several equation sets are strongly related. We show that our algorithm saves about 20% of the mathematical operations used by the best previous triangle‐to‐triangle intersection algorithm. Our experiments also show that it runs 18.9% faster than the fastest previous algorithm on average for typical scenarios of collision detection (on Pentium 4). Copyright © 2006 John Wiley & Sons, Ltd.