A fast triangle to triangle intersection test for collision detection

摘要

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).