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.
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.
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),
You can read the full text:
The following have contributed to this page