A faster triangle-to-triangle intersection test algorithm

作者：Wei Ling yu^*

来源：Computer Animation and Virtual Worlds, 2014, 25(5-6): 553-559.

DOI：10.1002/cav.1558

• triangle-to-triangle intersection
• case-depending
• partial cross product

The triangle-to-triangle intersection test is the most basic component of collision detection. And our algorithm, which firstly computes the line segment between triangle A and the plane of triangle B and uses a new method to detect the intersection between this line and triangle B, can reduce about 10% of time on average, compared with the previous fastest algorithm. Our new method divides the plane of triangle B into four quarter planes by two edges of B, and detects intersection depending on the location of the two endpoints of the segment. After using some techniques like avoiding division and projecting the segment and triangle B on XY, YZ, or ZX plane, the total number of arithmetic operations is reduced to at most 87, which is less than any existing algorithms.

• 出版日期2014-12
• 单位清华大学