Collision detection error
Author
I was trying to write a simple sphere-triangle collision for my engine, so I searched this forum and found some codes that seems to work. It works for small triangles, but when the sphere collides with a triangle that is alot larger then it is, it goes through it. Does anyone know how I can fix this? I got Tri-Shpere collision code from here
Quote:Original post by FireViperThe problem could be due to tunneling. How large is the average per-update displacement for the sphere, relative to its radius?
I was trying to write a simple sphere-triangle collision for my engine, so I searched this forum and found some codes that seems to work. It works for small triangles, but when the sphere collides with a triangle that is alot larger then it is, it goes through it. Does anyone know how I can fix this? I got Tri-Shpere collision code from here
The example you linked to is for discrete (static) sphere-triangle intersection, whereas perhaps you need a swept test. I imagine oliii has a swept sphere-triangle demo as well (perhaps he'll see this thread and post a link). Other good references include the 'Improved Collision Detection and Response' paper by Kasper Fauerby, and Dave Eberly's website, geometrictools.com.
Yeah, I would think that's tunneling. Small sphere, large triangle, if the sphere moves too quickly, it will miss teh triangle when it 'jumps' to the next frame's poistion. BTW, tunneling is even worse with very small triangles and a big sphere.
I have another example based on the same principle, that prevent tunnelling by slicing the sphere's displacement into segments or a maximum of 1/3 the sphere radius. This improves things, but it's hardly the solution to all things.
It's got several 'main.cpp', I think increasing complexity fo the demo. The first one is just like the old one, and suffers tunneling, then it goes up to the last, trying to prevent tunneling with the slice technique.
What you want ultimately is a swept sphere algorithm. Swept sphere algos use the sphere velocity to predict a future collision, and are much more accurate. No matter how fast the sphere moves (within reasonable limits), and no matter how big or small the triangle is (within reasonable limits!), it will always detect the collision accurately.
Here's mine, but you will see the code gets a lot more complex.
You can also see Paul Nettle's implementation, which in my opinion, is flawed, but seems to work somehow. It'sa lot simpler, but the idea of taking the closest point does not work 100%, which is really unfortunate (I love the simplicity of the algo).
You can ignore his elipsoid trick, and use just sphere, it's the same thing.
Note that collision detection algorithms do not like discrepancies in size between objects, especially very long and thin objects. That introduces all sorts of floating point errors and aliasing. If you hav a very large triangle (say 1km edge length), and a small sphere (1 meter size), it's better to tessalate the triangle to a reasonable size first for the collision detection (say, a max of 15m edge length).
I have another example based on the same principle, that prevent tunnelling by slicing the sphere's displacement into segments or a maximum of 1/3 the sphere radius. This improves things, but it's hardly the solution to all things.
It's got several 'main.cpp', I think increasing complexity fo the demo. The first one is just like the old one, and suffers tunneling, then it goes up to the last, trying to prevent tunneling with the slice technique.
What you want ultimately is a swept sphere algorithm. Swept sphere algos use the sphere velocity to predict a future collision, and are much more accurate. No matter how fast the sphere moves (within reasonable limits), and no matter how big or small the triangle is (within reasonable limits!), it will always detect the collision accurately.
Here's mine, but you will see the code gets a lot more complex.
You can also see Paul Nettle's implementation, which in my opinion, is flawed, but seems to work somehow. It'sa lot simpler, but the idea of taking the closest point does not work 100%, which is really unfortunate (I love the simplicity of the algo).
You can ignore his elipsoid trick, and use just sphere, it's the same thing.
Note that collision detection algorithms do not like discrepancies in size between objects, especially very long and thin objects. That introduces all sorts of floating point errors and aliasing. If you hav a very large triangle (say 1km edge length), and a small sphere (1 meter size), it's better to tessalate the triangle to a reasonable size first for the collision detection (say, a max of 15m edge length).
oliii, do you happen to have some collision response code that goes with your "3DSpherePolygonCollision.cpp"?
I used some older code of yours that I found on your site, "spheres.zip", but it has some bugs in it that I wasn't able to fix all (like bug when moving parallel to the triangle, plus some NaNs that happen sometimes, and some false positives).
I used some older code of yours that I found on your site, "spheres.zip", but it has some bugs in it that I wasn't able to fix all (like bug when moving parallel to the triangle, plus some NaNs that happen sometimes, and some false positives).
Author
Hey oliii, thanks for all the collision detection info.
I finished reading most of " Paul Nettle's implementation", and have a decent understanding of the algorithm, but I'm a little confused about the code. Do I move the shpere then check for collisions? or do I check for collisions, and then move the sphere?
I finished reading most of " Paul Nettle's implementation", and have a decent understanding of the algorithm, but I'm a little confused about the code. Do I move the shpere then check for collisions? or do I check for collisions, and then move the sphere?
with swept tests, you have a 'safe' position, a disaplcement / velocity, and a range (time of the frame, length of segment, ...). Let's keep it simple and use [position, velocity, time].
WHat you do is try to detect a collision from the position at the start of the frame, along the velocity vector, up to the frame time.
If you find one, you then move the sphere to the time of collision, reflect the sphere off the collision surface, and do another check with the remaining of the time left. Rouglhly it looks like this.
WHat you do is try to detect a collision from the position at the start of the frame, along the velocity vector, up to the frame time.
If you find one, you then move the sphere to the time of collision, reflect the sphere off the collision surface, and do another check with the remaining of the time left. Rouglhly it looks like this.
void Update(float dt){ Velocity += Gravity * dt; // add gravity while (dt > 0.0f) { float tcoll; // time of collision Vector Ncoll; // collision surface normal Vector Dcoll; // intersection vector bool collided = FindCollision(Position, Velocity, dt, radius, Ncoll, Dcoll, tcoll); if (!collided) break; Position += Dcoll + Velocity * tcoll; // move sphere to time of collision, and push it away if it was an intersecction Velocity -= 2.0f * Velocity.DotProduct(Ncoll) * Ncoll; // reflect velocity off the collision surface dt -= tcoll; // reduce the time fo the search } // no more collision detected. Move to the end of the frame. Position += Velocity * dt;}
A word of warning. You have to introduce tolerances to avoid running into infinite loops. The code above is only pseudo code.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
