Jump to content
  • Advertisement
taby

Swept sphere triangle intersection

Recommended Posts

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

Share this post


Link to post
Share on other sites
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? 

Share this post


Link to post
Share on other sites
Posted (edited)

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.

Edited by taby

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Posted (edited)

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;
}
Edited by taby

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Posted (edited)

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

Edited by taby

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!