What is it about?
Consider two triangles that intersect. Are there vertices of one triangle inside the other? Do their edges cross? Answering these questions is a part of any intersection algorithm, but if the answers aren't consistent with one another, perhaps due to inaccurate calculations or round-off error, you may find the intersection disappears. This algorithm ensures the answers are consistent even under the effects of error, so you can be certain the calculated intersection is at least close to the exact one.
Featured Image
Photo by the blowup on Unsplash
Why is it important?
There are many intersection algorithms for triangles, some of which are also robust. Ours is special because it was designed with consistency and parsimony in mind: Each step uses all relevant information from the previous steps. Ours also has a proof of its robustness, which is often missing for other robust algorithms.
Perspectives
Making this algorithm was a lot of fun. It gave me a chance to touch on fields like geometry and graph theory that I don't often get to work with. I'm proud of the final result and I think the design philosophies we used can be applied just about everywhere. Certainly, I'll be keeping them front of mind for a while.
Conor McCoid
Universite de Geneve
Read the Original
This page is a summary of: A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point Arithmetic, ACM Transactions on Mathematical Software, June 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3513264.
You can read the full text:
Resources
Contributors
The following have contributed to this page
