🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Swept sphere triangle intersection

Started by
13 comments, last by taby 5 years, 3 months ago

Does anyone have working C++ code for swept sphere triangle intersection?

Advertisement

Well ........ I have some 7 year old code (that I'm actually planning on resurrecting)  but it's not super simple. It's really sphere to triangle mesh code which has a few more compilations than just single triangles.

In general you want to test your sphere vs the plane of the triangle, the edges of the triangle and the vertexes of the triangle. When colliding with a mesh you should flag edges and vertexes when tested, because they are shared between triangles and you want to avoid testing them more than once.

Depending on what you are doing you may also have to handle the response. Does the sphere slide along your triangle for instance, if it hits at and oblique angle (which it almost always does). Also if dong response you have to handle two contact intersections, where you slide along the cross product of the normals of the contacts.  It's kind of like your pushing your sphere up a V shaped trench but it actually covers a lot more cases than that. That's the easiest way to think about it though.

When I wrote it, I started with a simple tutorial but it by far did not cover a lot of stuff.  It look me a couple months to actually get it to the point where I could use it for character mesh interactions. However it did end up working very well after everything was debugged and I never got stuck in the geometry. I'm guess there are a lot of decent tutorials these days however.

I would say it's doable if you are a reasonably competent programmer, and also the math really isn't so bad.  Just mostly dot products and cross products.

What exactly do you need it for? 

I'd love to have your code. I'm writing a tennis prediction system. I have it working now with a rectangular net, but I want to do a net that sags in the middle.

Do you need the code to just return a bool, or something like the first time of collision?

Just a bool would be great!

If Alvaro comes with some ground breaking optimized algorithm of sphere-triangle that does not produce first time of collision as a redundant resulting information I am gonna follow this thread

Here is the code for a non-swept sphere, where A,B, and C represent the triangle's three vertices, P represents the sphere centre, and r is the sphere radius. It works beautifully. We are very fortunate to have such algorithms.


// http://realtimecollisiondetection.net/blog/?p=103
bool is_separated(
	custom_math::vector_3 A, 
	custom_math::vector_3 B, 
    custom_math::vector_3 C, 
    custom_math::vector_3 P, 
    double r)
{
	A = A - P;
	B = B - P;
	C = C - P;

	double rr = r * r;
	custom_math::vector_3 V = (B - A).cross(C - A);
	double d = A.dot(V);
	double e = V.dot(V);
	int sep1 = d * d > rr * e;

	if (sep1)
		return true;

	double aa = A.dot(A);
	double ab = A.dot(B);
	double ac = A.dot(C);
	int sep2 = (aa > rr) & (ab > aa) & (ac > aa);

	if (sep2)
		return true;

	double bb = B.dot(B);
	double bc = B.dot(C);
	int sep3 = (bb > rr) & (ab > bb) & (bc > bb);

	if (sep3)
		return true;

	double cc = C.dot(C);
	int sep4 = (cc > rr) & (ac > cc) & (bc > cc);

	if (sep4)
		return true;

	custom_math::vector_3 AB = B - A;
	custom_math::vector_3 BC = C - B;
	custom_math::vector_3 CA = A - C;

	double d1 = ab - aa;
	double e1 = AB.dot(AB);

	custom_math::vector_3 Q1 = A * e1 - AB * d1;
	custom_math::vector_3 QC = C * e1 - Q1;
	int sep5 = (Q1.dot(Q1) > rr * e1 * e1) & (Q1.dot(QC) > 0);

	if (sep5)
		return true;

	double d2 = bc - bb;
	double e2 = BC.dot(BC);
	
	custom_math::vector_3 Q2 = B * e2 - BC * d2;
	custom_math::vector_3 QA = A * e2 - Q2;
	int sep6 = (Q2.dot(Q2) > rr * e2 * e2) & (Q2.dot(QA) > 0);

	if (sep6)
		return true;

	double d3 = ac - cc;
	double e3 = CA.dot(CA);

	custom_math::vector_3 Q3 = C * e3 - CA * d3;
	custom_math::vector_3 QB = B * e3 - Q3;
	int sep7 = (Q3.dot(Q3) > rr * e3 * e3) & (Q3.dot(QB) > 0);

	if (sep7)
		return true;

	return false;
}

I don't know if I'll find the time to implement it, but here's my plan. Change the frame of reference so the triangle is swept, and the sphere is in place. The swept triangle covers a section of space that is a triangular prism. Make out that prism out of 8 triangles and call the function for the non-swept case 8 times. The performance might not be great, but you'd had a reference implementation from that.

Does that make sense?

That makes sense, yes. I'll give it a shot. Thank you so much!

Actually, it comes to mind that I only have to do the collision detection if the ball is on one side of the net at some time and on the other side of the net at that time + delta time. The system I have now supports net types of: rectangular (made of two triangles), regulation (made of three triangles), and saggy (made of many triangles). The collision detection works with all nets, which are basically just a bunch of triangles.

Thanks for the ideas, however! I'm just not sure how to sweep the triangle. Should I simply stretch out the triangle in the direction of its face normal? How far should I stretch it out? I dunno.

court-3.png

This topic is closed to new replies.

Advertisement