#### Archived

This topic is now archived and is closed to further replies.

# Sphere-triangle coll detect

This topic is 5740 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, i''m trying to find a good sphere-triangle collision detection algorythm for my engine, i''ve looked at the ellipsoid tutorial from gamedev but its really unclear and the pseudo code is very bad, i would like to ask if anybody knows a link to a good sphere-polygon tutorial, if not, can you at least tell me all the steps to find out if a sphere is colliding with a triangle?? I have all the code necessary in the engine to do things like cross product, dot product, vector classes with all operators you can imagine, normal calculation for triangles... I would just need the steps needed to know IF and WHERE a sphere will/wont collide with a triangle polygon. Thank you!

##### Share on other sites
Hm, only collision of a static sphere with a static polygon?
This is quite easy, it would become pretty tricky if you try to do with moving spheres.
Yes, we did it, but don''t ask me. I know it works, but I still can''t teach someone who to do it.

Calculate the distance of the sphere to the plane given by the polygon. Pretty easy if you have the normalized representation of that.
if (Distance(sphereCenter, polygonPlane) > radius) {no collision}

now the tricky part follows: you need to calculate some bounding planes, one for each line of the polygon (you can do it once when you load the poly).
The bounding planes need to fullfill the following:
- each plane has to contain a side of your polygon
- the normals of the bounding planes have to be vertical to the normal of the polygon plane.
- all normals of bounding planes have to point to the outside.

now, if there is still a chance of collision, calculate a maxDist radius depending from the distance of the plane to the sphere.
where arccos is the reverse cos. Maybe you can optimize this.

finally simply calculate the distance of the sphere center to all bounding planes. If for any bounding plane the distance is greater than the calculated maxDist, there is no collision.

The most work is to calculate the bounding planes, if you once have them, every distance check is only 3 multiplications and 3 additions.
The most costy thing will be the calculation of that maxDist.

##### Share on other sites
http://www.gametutorials.com/Tutorials/OpenGL/OpenGL_Pg3.htm

"I believe; therefore, it is." -True Perception
"The Requested Information Is Unknown Or Classified" -Anonymous

##### Share on other sites
Thank you for the URL, and by the way, OF COURSE we want to do it with moving spheres...

##### Share on other sites
Moving Spheres and Polygons. Sure. :D
Well, that''s a lot tricker...

First big trick is to recalculate all velocitys so you can asume the polygon (or the second sphere) as static.

As far I know you now have to do 3 different collision tests.

First is the pretty simple case, if the collision point is INSIDE the polygon (calculate the position of the sphere where it finally touches the plane of the polygon, then check if that touching point is inside the polygon).

Next two cases are when there is no direct hit.
You want now to check if the sphere collides with any edges or corners.
To do this it will help much to imagine the sphere as a ray, and give the targets the radius of the sphere. This will give you same results, but I think the solutions are easier.

Cast a ray from the starting point of the sphere in it''s direction, and check if this ray collides with any cylinder between the corners of the polygon. (I do not know where to find a good tutorial for this now, but it is a raycaster standard problem and you should find some solutions for it).

If there is no collision between the ray and the infinite cylinders (and the first colision test failed, too), there is no collision at all.
If the ray colides with a cylinder, but the collision point isn''t between two corners, the sphere (maybe) colides with a corner of the polygon.

Finally check if the same ray collides with the spheres centered at the corners.
For that ray-sphere collision there are some good tuts on gamasutra.com

yes, i know this will not help you much, but these were the only informations we had, and we made it running, too

##### Share on other sites
Omni, surely you have to do a check against the tri vertices ?

1) If sphere is behind 3 plane equations then hitting surface of tri.
2) if behind two plane equations then it is hitting an edge of the tri.
3) If it is behind only one plane equation then it is hitting a vertex.

If you do not treat 3 different to 2 then your sphere will collide some distance away from the verts.

##### Share on other sites
quote:
Original post by JonnyBoy
Omni, surely you have to do a check against the tri vertices ?

1) If sphere is behind 3 plane equations then hitting surface of tri.
2) if behind two plane equations then it is hitting an edge of the tri.
3) If it is behind only one plane equation then it is hitting a vertex.

Remember you have a moving sphere, projecting it to the position where it touches the plane will give you only the position touching the polygon if it hits the polygon in it''s center. If it only hits an edge or a vertex, touching position is some closer to the plane of the polygon (if any).
So you can''t simply calculate with that position.
But even if you try it this way:
I could show you two cases fulfilling 2), once hitting the vertex and the other time hitting the edge... simply draw a triangle with extreme angles (160, 10, 10 should do) and test it, sphere coliding with a short edge of the triangle and moving over to only hit the edge.
Same triangle will punish you for 3), only sphere hitting the long edge.

I experimented some with simplier ways to get the correct impact position, but finally there were so many special cases, it was much easier and faster to do the checks for full hit, edge hit and vetex hit and get the first hit as result.

Hm, I hope I didn''t get you wrong

##### Share on other sites
hi, i have a question:

currently i use ellipsoid-triangle collision detection, but i´m not 100% satisfied with it.

i have read an article about cylinder-triangle collision detection. with a cylinder, you can better encapsulate a character like the player or enemys.

but how can i calculate whether a cylinder is in a triangle?

i would use just only one radius here (the same for x/z on top and bottom). and a certain height. the height of the cylinder may change when an enemy ducks or so (or even the cylinder rotates if a character does a special move).

any thoughts and hints would be appreciated!

thanks
gammastrahler

##### Share on other sites
interesting.

I wrote working moving sphere->triangle code quite a while ago.

unfortunatly, the link given to a sphere->triangle test above is a very inaccurate test. The points of the triangle bugger the test up the way it's done there. The method I use I'm quite confident is bang on exact. While I don't doubt that other methods work, I'm pretty happy with how fast mine seems to be..

it assumes that normals on the edges of the triangle that point to the centre of the triangle are precalculated...

First, and this took a long time to get right, there is one thing that needs to be done to get this to work, and thats to have code that given a triangle A, and a point B, the code will find a point C on the triangle that is the closest point possible to B...
My initial thought was to bring the point down to the triangles plane, and then bring it back to the edges 1 by 1. This proved to have disasterous results.

this following code does it.. but is a nightmare to read, and is not at all optimized...

    Vector3 CTriangle::ClosestPointOnTri(Vector3 Point){	Vector3 PointOnTriPlane=Point-PlaneNormal*PlaneNormal.DOT(Point-Vertex1->Vertex);	BYTE ED1=(Vertex3->Vertex-Vertex1->Vertex).DOT(PointOnTriPlane-Vertex1->Vertex)<0;	BYTE ED2=(Vertex1->Vertex-Vertex2->Vertex).DOT(PointOnTriPlane-Vertex2->Vertex)<0;	BYTE ED3=(Vertex2->Vertex-Vertex3->Vertex).DOT(PointOnTriPlane-Vertex3->Vertex)<0;	BYTE ED1r=(Vertex2->Vertex-Vertex1->Vertex).DOT(PointOnTriPlane-Vertex1->Vertex)<0;	BYTE ED2r=(Vertex3->Vertex-Vertex2->Vertex).DOT(PointOnTriPlane-Vertex2->Vertex)<0;	BYTE ED3r=(Vertex1->Vertex-Vertex3->Vertex).DOT(PointOnTriPlane-Vertex3->Vertex)<0;	if (ED1&ED1r)		return Vertex1->Vertex;		else		if (ED2&ED2r)			return Vertex2->Vertex;			else			if (ED3&ED3r)				return Vertex3->Vertex;				else			{			float DistAP1=AntiPlaneVertex1.DOT(PointOnTriPlane-Vertex1->Vertex);			float DistAP2=AntiPlaneVertex2.DOT(PointOnTriPlane-Vertex2->Vertex);			float DistAP3=AntiPlaneVertex3.DOT(PointOnTriPlane-Vertex3->Vertex);			BYTE dap1=(DistAP1<0);			BYTE dap2=(DistAP2<0);			BYTE dap3=(DistAP3<0);			int method=0;											if (!dap1 & !dap2 & !dap3)				return PointOnTriPlane;			if (!ED1r & !ED2 & dap1)				return PointOnTriPlane-AntiPlaneVertex1*AntiPlaneVertex1.DOT(PointOnTriPlane-Vertex1->Vertex);			if (!ED2r & !ED3 & dap2)				return PointOnTriPlane-AntiPlaneVertex2*AntiPlaneVertex2.DOT(PointOnTriPlane-Vertex2->Vertex);			if (!ED3r & !ED1 & dap3)				return PointOnTriPlane-AntiPlaneVertex3*AntiPlaneVertex3.DOT(PointOnTriPlane-Vertex3->Vertex);	};	return PointOnTriPlane;}

Once that is done, finding if a sphere is hitting a tirangle is a 1 liner...
a moving sphere is a tad harder.

for the moving sphere, (and this probably can be optimized a lot, as with the other code) first see where the line it travels will cross the triangles plane, then move the hit back the radius divided by the angle to the normal of the plane, so if it were just a plane, then it would _just_ toutch... then, from this centre point, find the closest point on the triangle. This is the real place the sphere first hits... Lastly, use a quadratic eqn to move the spheres centre so that it is in the right place, and check it's within the end points, and done. you have your test.

a right bugger to get working bang on.

you can see a working physics 'engine' that uses this on my site. It runs at 45hz.. yet you will only see something go under the ground when the suspension screws up. (which it does a fair bit)

http://www.riptorn.8m.com

[edited by - RipTorn on April 30, 2002 10:53:30 PM]