Sphere-Triangle Collision Detection
Author
Is it just me, or is there a real dirth of articles on the internet about identifying intersections between triangles and spheres?
I have found a few that seem just about alright but a bit buggy/unclear, and so I've got as far as spotting when vertices or edges intersect the sphere. However, I am unable to reliably identify the third case, when the sphere intersects the face of the triangle.
Thanks in advance,
Andy
Yep, others have had trouble too.
http://www.peroxide.dk/papers/collision/collision.pdf has worked for me so far.
http://www.peroxide.dk/papers/collision/collision.pdf has worked for me so far.
Author
For now I was just aiming for a static test.
skittleo: I've seen that paper already, and although it has some code to do the check it is totally uncommented and I'd like to be able to understand the maths that's going on.
skittleo: I've seen that paper already, and although it has some code to do the check it is totally uncommented and I'd like to be able to understand the maths that's going on.
For a test-intersection query for nonmoving triangle and sphere, compute the distance from the sphere center to the triangle. If this distance is larger than the sphere radius, the triangle and sphere do not intersect. All the mathematical details are wrapped up in the algorithm for computing distance from a point to a triangle. My choice is to set this up as a constrained minimization of a quadratic function.
If the triangle has vertices V0, V1, and V2, the triangle points are X(s,t) = V0+s*(V1-V0)+t*(V2-V0) for s >= 0, t >= 0, and s+t <= 1. Let the sphere center be C and radius be R. The squared distance between C and any point X(s,t) on the triangle is Q(s,t) = |X(s,t)-C|^2. The minimum of Q occurs either where its gradient is the zero vector (at an interior point of the triangle) or on an edge s = 0, t = 0, or s+t = 1. The rest is calculus. Other approaches might seem less formidable mathematically, but they all reduce to finding a closest point on the triangle to C.
If the triangle has vertices V0, V1, and V2, the triangle points are X(s,t) = V0+s*(V1-V0)+t*(V2-V0) for s >= 0, t >= 0, and s+t <= 1. Let the sphere center be C and radius be R. The squared distance between C and any point X(s,t) on the triangle is Q(s,t) = |X(s,t)-C|^2. The minimum of Q occurs either where its gradient is the zero vector (at an interior point of the triangle) or on an edge s = 0, t = 0, or s+t = 1. The rest is calculus. Other approaches might seem less formidable mathematically, but they all reduce to finding a closest point on the triangle to C.
Clearly a triangle defines a plane. Test whether the sphere intersects the plane; this is just distance of a point from a plane, right? If the sphere and the plane intersect, project the sphere onto the plane. The problem reduces to testing whether a circle intersects a triangle. You could do this by brute force : Test whether each vertex is inside the circle, each edge intersects the circle, and whether the circle center is inside the triangle. If any of these are true, you have your intersection; if none of them are, you don't.
If speed is of the essence this might be a bit slow, but it should be reasonably easy to understand, at least.
Incidentally, when you say triangle, you did mean a 2D object, right? Or were you referring to a tetrahedron, that is, a pyramid with four faces (counting the bottom)? If the latter, the intersection test does reduce to checking intersection for each triangular vertex as outlined above, plus a test for whether the sphere center is inside the tetrahedron, but the slowness gets worse.
If speed is of the essence this might be a bit slow, but it should be reasonably easy to understand, at least.
Incidentally, when you say triangle, you did mean a 2D object, right? Or were you referring to a tetrahedron, that is, a pyramid with four faces (counting the bottom)? If the latter, the intersection test does reduce to checking intersection for each triangular vertex as outlined above, plus a test for whether the sphere center is inside the tetrahedron, but the slowness gets worse.
I'd recommend the closest-point method, as it's fairly straightforward mathematically and gives you some useful information (the closest point) in return. The closest point, for example, can be used in constructing a translation vector with which to resolve the collision.
If the quadratic minimization method seems daunting, there are 'easier' (if perhaps less elegant) ways of finding the closest point on a triangle. Begin by projecting the point onto the triangle plane. The projected point can then be classified in reference to the triangle's Voronoi regions using 'side planes' or barycentric coordinates. If the projected point is inside the triangle, you have your closest point; otherwise the Voronoi region tells you which feature it is closest to.
Note that I'm not recommending the above approach over the quadratic method; it's just an option to consider.
[Edit]
Just wanted to add that after re-reading King of Men's post I see that he's describing something similar. Intersecting the circle (projected sphere) with the triangle involves finding the closest point on the triangle to the projection of the sphere center onto the triangle plane, so that part is the same. If I understand correctly, he's suggesting then testing for |project(C)-closest|2 <= r2-d2, rather than |C-closest|2 <= r2. IMO the 'projecting the sphere' part just adds a little math and isn't really necessary, but otherwise it's the same idea.
[/Edit]
[Edited by - jyk on May 19, 2005 11:06:53 PM]
If the quadratic minimization method seems daunting, there are 'easier' (if perhaps less elegant) ways of finding the closest point on a triangle. Begin by projecting the point onto the triangle plane. The projected point can then be classified in reference to the triangle's Voronoi regions using 'side planes' or barycentric coordinates. If the projected point is inside the triangle, you have your closest point; otherwise the Voronoi region tells you which feature it is closest to.
Note that I'm not recommending the above approach over the quadratic method; it's just an option to consider.
[Edit]
Just wanted to add that after re-reading King of Men's post I see that he's describing something similar. Intersecting the circle (projected sphere) with the triangle involves finding the closest point on the triangle to the projection of the sphere center onto the triangle plane, so that part is the same. If I understand correctly, he's suggesting then testing for |project(C)-closest|2 <= r2-d2, rather than |C-closest|2 <= r2. IMO the 'projecting the sphere' part just adds a little math and isn't really necessary, but otherwise it's the same idea.
[/Edit]
[Edited by - jyk on May 19, 2005 11:06:53 PM]
Of course you are correct that the projection is an un-necessary step algorithmically, but I thought it might be useful for visualising what's going on. It depends on whether the OP wants to solve his problem with the fastest possible code, the most elegant possible method, or a method that he understands every step of.
Here is the algo I implemented for static ellipsoid-triangle check:
1- Check if the sphere/ellipsoid is in contact with the plane defined by the triangle, if so, get the contact point using d*(-n) where d is the distance from the plane to the sphere/ellipsoid center point (position), if there is no contact return false.
2- Compute the barycentric coordinates for the contact point, if all 3 values are between 0 and 1, we have a direct hit, return true and the contact point (if you need it, in my case, I do).
3- We may have an indirect hit so for each of the 3 rays defined by the triangle edges, find the closest point to the sphere/ellipsoid position, compute this closest point barycentric coordinates, again if all 3 values are inside the 0...1 range, the point is on one of the edges of the triangle, so if there is a collision it must be on that edge.
4- Check if the closest point found on the last step is inside the ellipsoid/sphere, this is a simple check to see if the radius lenght is greater than the distance between the ellipsoid/sphere position and the closest point, if so, we have a collision.
5- at this point if you have a collision and require nothing more, you may return true, but of you need the contact point then you must do a ray-sphere collision test, where the ray origin is the closest point and its direction is -n (the inverted plane normal), this will give you the contact point on the sphere surface, and if you calculate the distance from the closest point on the triangle found 2 steps ago to this contact point you will find the depth of penetration, if you move the ellipsoid/sphere, this amount on the plane normal's direction, the ellipsoid/sphere will be positioned in such a way that it barelly touches the triangle edge.
1- Check if the sphere/ellipsoid is in contact with the plane defined by the triangle, if so, get the contact point using d*(-n) where d is the distance from the plane to the sphere/ellipsoid center point (position), if there is no contact return false.
2- Compute the barycentric coordinates for the contact point, if all 3 values are between 0 and 1, we have a direct hit, return true and the contact point (if you need it, in my case, I do).
3- We may have an indirect hit so for each of the 3 rays defined by the triangle edges, find the closest point to the sphere/ellipsoid position, compute this closest point barycentric coordinates, again if all 3 values are inside the 0...1 range, the point is on one of the edges of the triangle, so if there is a collision it must be on that edge.
4- Check if the closest point found on the last step is inside the ellipsoid/sphere, this is a simple check to see if the radius lenght is greater than the distance between the ellipsoid/sphere position and the closest point, if so, we have a collision.
5- at this point if you have a collision and require nothing more, you may return true, but of you need the contact point then you must do a ray-sphere collision test, where the ray origin is the closest point and its direction is -n (the inverted plane normal), this will give you the contact point on the sphere surface, and if you calculate the distance from the closest point on the triangle found 2 steps ago to this contact point you will find the depth of penetration, if you move the ellipsoid/sphere, this amount on the plane normal's direction, the ellipsoid/sphere will be positioned in such a way that it barelly touches the triangle edge.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
