Sign in to follow this  
FireViper

Collision detection error

Recommended Posts

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

Share this post


Link to post
Share on other sites
Quote:
Original post by FireViper
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 problem could be due to tunneling. How large is the average per-update displacement for the sphere, relative to its radius?

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.

Share this post


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

Share this post


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

Share this post


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

Share this post


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


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;
}

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