I sort of implied this in passing in my triangle-triangle tests post, but let’s state it officially: coplanarity (or collinearity) in your inputs will almost always screw you over in one way or another! Here’s another example of what can go wrong: this time performing continuous collision detection between a moving point and a moving triangle. (In case this looks familiar it’s probably because you’ve seen me mention it before in other forums, but hey, self-plagiarization is OK as long as you’re not trying to publish!)
Let’s start by looking at the methods proposed for this problem. One of the first papers to address the continuous collision detection problem of moving point vs. moving triangle was [Moore88]. Their solution was to solve the parametric vector equation
p+tv = p0 + tv0 + u((p1-p0)+t(v1-v0)) + v((p2-p0)+t(v2-v0))
where p is the point with velocity v over the time step, the pi and vi terms are the triangle vertices and their velocities, and t, u, and v are the parametric variables. This resolves to a 5-th order polynomial in t. Moore and Wilhelms solved the polynomial using a binary search technique (to guarantee convergence). The full test only needs to be performed if the signed distance to the triangle plane of the point in its start and end position have different signs.
A 5-th degree polynomial isn’t exactly appetizing, so in [Provot97], Xavier Provot suggested a different method to solve the same problem. Provot notes that a necessary (but not sufficient) condition for the point to intersect the triangle is for it to lie in the plane of the triangle. We can test coplanarity using the trusty scalar triple product. (Hmm… someone, remind me to blog about the scalar triple product.)
Given a point p with velocity v and a triangle abc with vertex velocities va, vb, and vc, we can define the parametric vectors
ap(t) = (p+tv) - (a+tva) = (p-a)+t(v-va),
ab(t) = (b-a)+t(vb-va), and
ac(t) = (c-a)+t(vc-va).
p will lie in the plane of abc when
Dot(ap(t), Cross(ab(t), ac(t))) = 0,
that is, when the vector ap lies in the plane of ab and ac.
In other words, what Provot suggests is that we solve the above equation for t, and for each t-value found, we bring the point and triangle to their positions for that t-value and perform a containment test to see if the point lies in the triangle. The smallest t for which the point lies inside the triangle is returned as the time of intersection. This approach of Provot’s has been been referenced/used in a lot of places, e.g. in [Bridson02], [Redon04], and [Hutter07].
So, well, this is great and all, except for one niggly little thing… it doesn’t work!
The problem is that when the point and the triangle move together in the same plane you cannot solve for a unique t value for which the point lies in the plane of the triangle, and the method breaks down. (This is also the case for the Moore-Wilhelms method, btw.) In this context it’s somewhat ironic that [Bridson02] has ‘robust’ in the title and chides Provot for “not properly account[ing] for rounding errors”, but suffers from unaccounted-for robustness issues in its own use of Provot’s method in exactly the case I outlined. Oops! To be robust you’d have to special-case this situation, which turns your reasonably elegant code pretty ugly because you now have to solve the problem in 2D after detecting this degenerate case. Plus you need tolerances for deciding when you drop to 2D, etc. It’s u-g-l-y.
Unfortunately, I’m not aware of a better solution. You could probably use interval arithmetic and solve the problem that way, perhaps with interval-Newton, but that doesn’t exactly categorize as a better solution in my book (no pun intended). Well, it would be completely robust I guess, so better in that sense at least.
BTW, note that an approach very similar to Provot’s was described in [Schömer95] (also without noting the coplanarity problem), so perhaps the method should not be attributed to Provot, as is typically the case, but to Schömer.
OK, so lots of verbiage from Christer again, but what’s the takeway? Well, this: if you don’t have special-case code for coplanarity and collinearity in your geometric calculations, odds are you have (possibly severe) bugs in your code!
- [Bridson02] Bridson, Robert. Ronald Fedkiw. John Anderson. “Robust treatment of collisions, contact and friction for cloth animation,” Proceedings of SIGGRAPH’02, San Antonio, Texas, pp. 594-603, 2002. http://graphics.stanford.edu/papers/cloth-sig02/
- [Hutter07] Hutter, Marco. Arnulph Fuhrmann. “Optimized Continuous Collision Detection for Deformable Triangle Meshes,” Journal of WSCG, Vol.15, No.1-3, pp. 25-32, February 2007. http://wscg.zcu.cz/wscg2007/Papers_2007/journal/D11-full.pdf
- [Moore88] Moore, Matthew. Jane Wilhelms. “Collision Detection and Response for Computer Animation,” Computer Graphics (Proceedings of SIGGRAPH ‘88), vol. 22, pp. 289-298, 1988.
- [Provot97]Provot, Xavier. “Collision and self-collision handling in cloth model dedicated to design garments,” Computer Animation and Simulation ‘97, pp. 177-190, 1997
- [Redon04] Redon, Stephane. Young Kim. Ming Lin. Dinesh Manocha. “Fast Continuous Collision Detection for Articulated Models,” ACM Symposium on Solid Modeling and Applications, June 2004. http://gamma.cs.unc.edu/Articulate/
- [Schömer95] Schömer, Elmar. Christian Thiel. “Efficient collision detection for moving polyhedra,” Proceedings of the Eleventh Annual Symposium on Computational Geometry, pp. 51-60, 1995. http://citeseer.ist.psu.edu/article/omer95efficient.html