Sign in to follow this  
phb5000

Sphere-Triangle Collision

Recommended Posts

I dont know how long I've looking for a simple solution to a sphere-triangle collision detection, but I cant seem to find any concrete solutions to it! My situation is as follows: + I have a sphere (representing a first person shooter camera) + I have a mesh (representing a level) Collision Detection: + Check distance from the plane of nearby faces to the sphere's position + If <= Radius then make sure the sphere is within the triangle. <-- problem The data I have to use is the position of the sphere, the normal of the face plane, and the three vertices of the face itself. How can I know check to see that If the sphere where to be touching the face plane Exactly (which will mostly likely never happen) is the point in the area of the triangle? Should I go for a different approach? Should I generate a triangular prism representing the face + normal data * distance to sphere. Then check if they overlap? Any suggestions, links, or any other resources are appreciated! Thank you,

Share this post


Link to post
Share on other sites
How about:

Compute the minimum distance from the triangle to the center of the sphere. Mathematically, this could be a minimization double integral in barycentric coordinates. If the distance is less than r then you have a collision.

Share this post


Link to post
Share on other sites
Project the position (center) of the sphere along the surface normal. If the value is greater than the spheres radius, the sphere doesn't penetrate the triangle so break. Otherwise, find the image of the sphere projected on the plane and test whether that point is inside the triangle.

Share this post


Link to post
Share on other sites
Quote:
Original post by WhardieJones
Compute the minimum distance from the triangle to the center of the sphere. Mathematically, this could be a minimization double integral in barycentric coordinates. If the distance is less than r then you have a collision.
If you just need a discrete test, I'd go for this method. The info returned by the closest point test can be used to resolve the intersection, which also gives you fairly natural sliding collision response. This will only work for objects that move relatively slowly, though.

Share this post


Link to post
Share on other sites
Hey!! I have posted the correct method here (your thread on the DirectX forum)...

Sorry man, Ive wrote the wrong code but now its right...the problem was with the s and t computation...just confused with the distance between a point and a line computation :P...read that and if you have any questions its just ask ;)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Mathematically, this could be a minimization double integral in barycentric coordinates. If the distance is less than r then you have a collision.


Would you mind elaborating/posting a source on this?

Share this post


Link to post
Share on other sites
phb5000, please read this excellent article by David Eberly. You can find the source code as well at his site.

Quote:
Original post by jjd
Project the position (center) of the sphere along the surface normal. If the value is greater than the spheres radius, the sphere doesn't penetrate the triangle so break. Otherwise, find the image of the sphere projected on the plane and test whether that point is inside the triangle.

Unfortunately, this is not enough. Even if the sphere center's projection onto the plane is outside the triangle, the sphere can still collide with the triangle.

WhardieJones, didn't you mean to minimize the distance function between the sphere's center and the triangle? In any case, this is not a "simple" minimization problem because the barycentric coordinates are subject to the following constraints:
0 <= s,t
1 >= s+t

Share this post


Link to post
Share on other sites
An alternative way is to do the integral in cartesian. It would probably be easiest to create an isomorphism from the plane to the standard basis in R^2. One would then have an integral of the form:
int[int[distance(x,y),y,mx+b,nx+c],x,x0,x1]

of course be sure to map x,y back before computing distance. This can be computed analytically and the results hardcoded in a C++ function.

Two reasons why I initially chose barycentric:
1) The boundaries are constants, not parametric functions
2) There aren't any special cases I'm aware of. Cartesian you might need to be careful if m is infinite.

Share this post


Link to post
Share on other sites
Quote:
Original post by phb5000

My situation is as follows:
+ I have a sphere (representing a first person shooter camera)
+ I have a mesh (representing a level)


My solution was:
the level data is organized into sectors, each sector consists of a convex collection of interconnected(?continguous?) polygons
when my sphere moves, i project the velocity into each polygon of the sector, and find the shortest intersection (which is also < sphere radius). Since the sectors are convex, the shortest plane intersection must be the triangle we are hitting, no need to check the triangle edges.
unfortunatly... concave edges can be possible, where two sectors meet each other... that part of my code is sometimes buggy... still working on it

still, if you can recognize cases where the convexity constraint holds for your map, can be useful

Share this post


Link to post
Share on other sites
integrals take a long time to calculate.
if you have 100,000 planes to check the collision it will get low framerates.
the best thing to use is vectors.
there are no exeptions.
and since you probably have your surface normals calculated for lightning it will be fast.
you can also write a shader to do this because a gpu is good at vector calculations.

you just take the distance from the center of the sphere to the plane.



ax+by+cz+d
distance = --------------
sqrt(a²+b²+c²)

(a,b,c) is the normal vector of your plane.

(x,y,z) is the center of the sphere.

ax+by+cz+d=0 is the equation of your plane.

now you draw a line through the center of the sphere perpendicular to the plane.

the intersection point of your line with your plane is:

(a,b,c)*distance
(x1,y1,z1)= (a,b,c)- ----------------
sqrt(a²+b²+c²)

(x1,y1,z1) is the intersection piont.



and with the dot product you can check if the intersection point is inside the triangle.





x3
| \\
| \\
| \\
| c \\
| \\
x1---------x2

if c is inside the triangle, the sum of the angles between x1;c;x2 and x2;c;x3 and x1;c;x3 will be 360°. if c is outside the triangle, is will not be 360°

this is documented in:

opengl game programming by dave astle and kevin hawkins from prima tech's game development series



this should work

good luck

[Edited by - delta user on March 17, 2006 11:19:42 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
Quote:
Original post by jjd
Project the position (center) of the sphere along the surface normal. If the value is greater than the spheres radius, the sphere doesn't penetrate the triangle so break. Otherwise, find the image of the sphere projected on the plane and test whether that point is inside the triangle.

Unfortunately, this is not enough. Even if the sphere center's projection onto the plane is outside the triangle, the sphere can still collide with the triangle.

My bad, you're quite right.

Share this post


Link to post
Share on other sites
The integral is calculated only once, please read carefully.

Quote:
Original post by delta user
integrals take a long time to calculate.
if you have 100,000 planes to check the collision it will get low framerates.
the best thing to use is vectors.
there are no exeptions.
and since you probably have your surface normals calculated for lightning it will be fast.
you can also write a shader to do this because a gpu is good at vector calculations.

you just take the distance from the center of the sphere to the plane.



ax+by+cz+d
distance = --------------
sqrt(a²+b²+c²)

(a,b,c) is the normal vector of your plane.

(x,y,z) is the center of the sphere.

ax+by+cz+d=0 is the equation of your plane.

now you draw a line through the center of the sphere perpendicular to the plane.

the intersection point of your line with your plane is:

(a,b,c)*distance
(x1,y1,z1)= (a,b,c)- ----------------
sqrt(a²+b²+c²)

(x1,y1,z1) is the intersection piont.



and with the dot product you can check if the intersection point is inside the triangle.





x3
| \\
| \\
| \\
| c \\
| \\
x1---------x2

if c is inside the triangle, the sum of the angles between x1;c;x2 and x2;c;x3 and x1;c;x3 will be 360°. if c is outside the triangle, is will not be 360°

this is documented in:

opengl game programming by dave astle and kevin hawkins from prima tech's game development series



this should work

good luck


Share this post


Link to post
Share on other sites
Quote:
Original post by delta user
integrals take a long time to calculate.
if you have 100,000 planes to check the collision it will get low framerates.
the best thing to use is vectors... [snip]


According to WhardieJones you can calculate the integral offline, so that's not a problem.

Also your solution suffers from the same problem as jjd's. Collision with the edges or the corners will not be detected. At the moment I'm doing what you are describing except I'm also doing line-sphere intersection with each edge of the triangle. This works ok for now (maybe later I'll try figuring out how to implement Whardie's solution)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by delta user

and with the dot product you can check if the intersection point is inside the triangle.





x3
| \\
| \\
| \\
| c \\
| \\
x1---------x2

if c is inside the triangle, the sum of the angles between x1;c;x2 and x2;c;x3 and x1;c;x3 will be 360°. if c is outside the triangle, is will not be 360°

this is documented in:

opengl game programming by dave astle and kevin hawkins from prima tech's game development series



this should work

good luck


The angle sum method is not good... it Looks good to mathematicians on paper, but in practice, due to floating point innacuracies your angles will Never be exactly 360 degrees.
You can add in a 'fudge factor' where you let it count as inside if its 'close enough' to 360, but this is a pretty weak hack, and also leads to false results when the point is near the edges of the triangle
another consideration is that it requries the use of Trig functions to get the angles, which are incredibly slow...

you're better off using cross product of triangle normal and each edge to generate a triangular prism, and checking what side of each of the 3 prism side planes you are on... it'd be cheaper and more accurate
3 cross products to get the plane normals, 3 dot products to check sidedness of planes Much cheaper than 3 arcCos() trig functions...

Share this post


Link to post
Share on other sites
Compute if the distance between the sphere center any triangle is lower than the sphere radius. If it tests true for a triangle, test if the projection of the sphere center on the triangle plane is inside the triangle through the parametric plane equation. If it doesnt tests true for any triangle, compute the distance between the sphere center and each edge of your collision mesh. The sphere center - vertex distance is also included in the same algorithm. Its a sequence.

Dont know if it can be fast enough but it will works correctly.

Share this post


Link to post
Share on other sites
The key to handle vertex or edge collisions is Voronoi regions.

Write your PointInTriangle in such a way that it gives you the Voronoi region the point in the plane is in, you get this for free if your PointInTriangle uses baricentric coordinates instead of the UGLY angle between edges approach.

What you do is that once you have the closest (vertice or edge) feature given by the Voronoi region, you check the sphere against that feature.

If you have to check for a vertice, in a static check, just check that the distance from the center of the sphere to the vertice is less than the radius of the sphere, if so, you have a collision, the collision normal is the normalized vector (spherecenter-vertice) and the penetration depth is radius-verticedistancetothecenter.

If you have to check for a vertice, in a dynamic check, just do a ray sphere test, where the ray is the movement vector of the sphere and the sphere is a sphere at the vertice position, if there is a collision, find t for the point in which the ray contacts the sphere.

If you have to check for an edge, in a static check, just check that the distance from the center of the sphere to the closest point in the edge to the center of the sphere is less than the radius of the sphere, if so, you have a collision, the collision normal is the normalized vector (spherecenter-closestpoint) and the penetration depth is radius-closestpointdistancetothecenterofthesphere.

If you have to check for an edge, in a dynamic check, just do a ray-cylinder test, where the ray is the movement vector of the sphere and the cilinder is the cylinder given by the edge and the sphere radius (this is a case of ray-ray intersection where one of the rays is "thickened" by the sphere radius), if there is a collision, find t for the point in which the ray contacts the cylinder.

Hope that Helps.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this