Triangle-triangle tests, plus the art of benchmarking

Over the years, several methods have been suggested for testing the intersection status of two triangles. Perhaps the most well-known presentations are by [Möller97] and [Held97]. Other presentations include [Roy98], [Shen03], and [Guigue03].

Last year yet another triangle-triangle method was suggested by [Tropp06]. The Tropp et al method is interesting and all (using an algebraic rather than geometric approach), but to be completely honest I’m not really tremendously impressed or interested in these newer, more complex algorithms that have been presented in the last few years. Yes, sure, they do reduce the number of floating-point operations compared to previous methods, but… er… I don’t care. Counting individual operations is not where it’s at any more, and hasn’t been for many years!

The benchmarks that are run in these papers suggest that the new methods are perhaps 20% or even 40% faster than the baseline test (which is typically the one described by Möller), but we get this by doing extra if-tests and overall we get much more complicated code. But if I really care about getting a faster test (which I sometimes do) then I’m not going to go running after these more complicated tests and their 20-40% speedups. No, I’d instead implement a SIMD version of the simplest possible test, and get something like 3-4x improvement doing this. 20-40% vs. 300-400%, which would you rather have? Yeah, I thought so.

The other issue is that the benchmarks of these kind of papers are suspect anyway. Frequently they test the primitives in some large number of random configurations and report the average time it took to do a test. Plus they compare results to see if they get the same tests right. Bzzt! Wrong! First, this kind of testing is very unlikely to hit the cases where the tests fail due to robustness issues.

For example, in many real world cases you will have triangles settling on other triangles, but you’ll never see that happen in a random test. The “settling” case will quickly show up robustness issues when the triangles are becoming near parallel and coplanar, thereby degenerating into the 2D triangle-triangle test that most of these papers never deal with (they typically just “return 0”). Can you say “Oops!?” These random tests are also unlikely to test the other cases that would show up robustness problems, such as the one illustrated in [Robbins03].

Second, the other problem with the 10,000 random tests approach is that it nicely hides the cost of fetching code and data into cache, and effectively just turns into an instruction-counting test. For the real-world case of game code, we would probably just do some small handful of triangle-triangle tests, and here the cache (miss) costs would dominate completely and the paper benchmark is completely misleading!

So, I’m not really sure where I’m going with this. Perhaps it’s this. First, these new methods to test triangle-triangle, ray-triangle, sphere-box, or whatever it might be, are interesting in an abstract sort of way, but not necessarily in a practical sense, so don’t assume “newer is better.” Second, if you happen to be the one who writes one of these papers in the future, please-oh-please make sure you don’t resort to the usual utterly-useless-and-retarded random-configuration benchmark to prove how “good” your method is, because if you do, I will laugh at you and ridicule you in this blog.

References

• [Guigue03] Guigue, Philippe. Olivier Devillers. “Fast and Robust Triangle-Triangle Overlap Test using Orientation Predicates,” Journal of Graphics Tools, vol. 8, no. 1, pp. 25-42, 2003. Also available as INRIA Research Report 4488: http://hal.inria.fr/inria-00072100/en/ [code]
• [Held97] Held, Martin. “ERIT: A Collection of Efficient and Reliable Intersection Tests,” Journal of Graphics Tools, vol. 2, no. 4, pp. 25-44, 1997.
• [Möller97] Möller, Tomas. “A Fast Triangle-Triangle Intersection Test,” Journal of Graphics Tools, vol. 2, no. 2, pp. 25-30, 1997. http://www.cs.lth.se/home/Tomas_Akenine_Moller/pubs/tritri.pdf
• [Robbins03] Robbins, Steven. Sue Whitesides. “On the Reliability of Triangle Intersection in 3D,” in Computational Science and Its Applications, volume 2669 of LNCS, Montreal, Canada, pp. 923-930, May 2003. http://www.sumost.ca/steve/publications/triangle-intersection.ps
• [Roy98] Roy, Uptal. V. Ramana Dasari. “Implementation of a Polygonal Algorithm for Surface-Surface Intersections,” Computers and Industrial Engineering, vol. 34, no. 2, pp. 399-412, 1998.
• [Shen03] Shen, Hao. Pheng Ann Heng. Zesheng Tang. “A Fast Triangle-Triangle Overlap Test Using Signed Distances,” Journal of Graphics Tools, vol. 8, no. 1, pp. 17-24, 2003.
• [Tropp06] Tropp, Oren. Ayellet Tal. Ilan Shimshoni. “A Fast Triangle to Triangle Intersection Test for Collision Detection,” Computer Animation and Virtual Worlds, vol. 17, no. 5, pp. 527-535, December 2006. http://www.ee.technion.ac.il/~ayellet/Ps/TroppTalShimshoni.pdf [alt. link]