Quick and Simple Collision Detection
Author
Ok, I have spent so, so much time trying to get some simple sphere-triangle collision detection to work. I've looked at a bunch of tutorials over the internet, and have not been able to figure it out. So far, the best result I hve had so far was my own implementation, however, it is a bit flawed when it comes to colliding into two polygons that are sticking out at a point... It's close, but not perfect. Anyway, I just need some simple collision detection between a sphere and a triangle, I have some physics code to handle the collision response.
EDIT: I developed my sphere-tri code based on the flipcode.net article by Paul Nettle (amazing!). My ray-tri intersection code works fine, it's just when it comes to sphere-tri intersection... I'm a bit confused on how I should go about using this... I have used this code in a few homebrew projects, but now that I am an iPhone developer, I need to perfect this code.
a triangle has 3 verts each with position and the sphere has a center and radius
One easy way to do it would be
.for each vert
. if((sphere.center - vert.pos).length() < radius)
. you collided
The problem would be that the length function takes excess processing power. but there are ways around it. Just look up vector length or magnitude formula and you might see what I mean.
One easy way to do it would be
.for each vert
. if((sphere.center - vert.pos).length() < radius)
. you collided
The problem would be that the length function takes excess processing power. but there are ways around it. Just look up vector length or magnitude formula and you might see what I mean.
Instead of using the length of the vector you can use the squared length and compare it to the squared radius. Thus the computation boils down to x*x + y*y + z*z < r*r (no costly operations involved).
The problem with this approach is that it won't detect collisions if the triangle is hitting the sphere but not its vertices.
Have a look at this thread. Basically you'd first perform a sphere-plane test with the triangle's plane. If the test is negative, there's no collision, if the sphere hits the plane, check if the collision point lies within the triangle. If not you have to check against the edges and vertices of the triangle.
So a collision takes place, if:
- the sphere hits the plane
- and the collision point is inside the triangle or the sphere hits and edge or vertex.
Hope that helps.
Thomas
The problem with this approach is that it won't detect collisions if the triangle is hitting the sphere but not its vertices.
Have a look at this thread. Basically you'd first perform a sphere-plane test with the triangle's plane. If the test is negative, there's no collision, if the sphere hits the plane, check if the collision point lies within the triangle. If not you have to check against the edges and vertices of the triangle.
So a collision takes place, if:
- the sphere hits the plane
- and the collision point is inside the triangle or the sphere hits and edge or vertex.
Hope that helps.
Thomas
I dont know if this would be faster but if you get the closest point on a line for the center point of the sphere for each of the 3 edges then compair the distance versus the radius you get collision detection in 3 checks at most.
Just an idea though I havent taken the time to do the compairison between closest point on line and sphere to plain test.
Just an idea though I havent taken the time to do the compairison between closest point on line and sphere to plain test.
Quote:One easy way to do it would beThis is the problem with 'do it yourself' solutions to collision detection problems such as this: it's very easy to get it wrong. (The above algorithm, for example, will miss cases where the sphere collides with an edge of the triangle.)
.for each vert
. if((sphere.center - vert.pos).length() < radius)
. you collided
IIRC, even the algorithm in the Nettle article has some issues (there's a follow-up article by Kaspar Fauerby that describes what I believe is a more robust version of the algorithm).
Anyway, if you just need a static test, all you really need is a 'closest point on triangle to point' function; from there, you can determine if there's an intersection, and also construct the minimum translational vector, if needed.
The dynamic test is more complicated. If you need more info on this, you might try Fauerby's paper if you can find it (I had pretty good luck with it), or check out Dave Eberly's docs and code at geometrictools.com.
Another option would be to use a pre-existing physics or collision detection engine (if you've been charged with writing a production-quality application, this might be the best choice).
Quote:I dont know if this would be faster but if you get the closest point on a line for the center point of the sphere for each of the 3 edges then compair the distance versus the radius you get collision detection in 3 checks at most.Still not sufficient (collisions between the sphere and the interior of the triangle will be missed).
in broad terms, this is what it does...
struct Sphere{ Vector m_position; Vector m_velocity; float m_radius;};struct Triangle{ Vector m_v0; Vector m_v1; Vector m_v2; Vector m_normal;}; bool solve( const Sphere* sphere, // the sphere const Triangle* triangle, // the triangle float& tcoll, // time of collision Vector& pcoll) // point of collision on triangle{ Vector pplane; // point of intersection on triangle plane Vector pclosest; // point on triangle closest to pplane. // project velocity onto normal. float v = sphere->m_velocity.dotProduct(triangle->m_normal); // sphere centre distance to triangle plane. float h = (sphere->m_position - triangle->m_v0).dotProduct(triangle->m_normal); // sphere underneath triangle. ignore (works only with closed geometry). if(h < 0.0f) return false; // sphere moving away from triangle plane. ignore. (works only with closed geometry). if(v > 0.0f) return false; // sphere intersects triangle plane. // or velocity parallel to plane. if((h < sphere->m_radius) || (v > -0.00001f)) { // point on plane is projection of sphere position onto the plane pplane = sphere->m_position - triangle->m_normal * h; } else { // time of collision of the sphere with the plane float tplane = (sphere->m_radius - h) / v; // point of collision of the sphere with the plane pplane = sphere->m_position + sphere->m_velocity * tplane; } // find closest point to pplane on triangle. // if pplane 'inside' triangle, pclosest will be equal to pplane. Vector pclosest = triangle->closestPoint(pplane); // distance vector between the sphere position and the point on triangle. Vector distance = (sphere->m_position - pclosest); float dist2 = (distance.dotProduct(distance)); // closest point inside the sphere. we have an intersection. if(dist2 < (sphere->m_radius * sphere->m_radius)) { tcoll = 0.0f; // time of collision (0). pcoll = pclosest; // point of collision on triangle. return true; } // time of intersection of the sphere against a ray started // from closest point, and going against the velocity. // if we miss, no collision. float tray; if(!sphere->intersect(pclosest, -sphere->m_velocity, tray)) return false; // ray intersected. setup the collision info. tcoll = tray; // time of collision pcoll = pclosest; // point of collision on triangle return true;}
Author
The code above looks really good! I'll definitely check it out tomorrow. I scanned through it, and I am not sure what the "triangle->closestPoint(pplane)" function call does mathematically. I'm assuming it finds the closest point on the triangle from intersection point only if the intersection point is not within the triangle to see if the sphere has still made a collision with the edge of the current triangle. This is the part I am having trouble in within my own implementation...
I also had another question too! Did you guys (the ones using it) copy and paste the peroxide.dk code into your game, or did you make your own implementation based on the reading? I have tried to just copy and paste the code into my own project, and by the time I convert it into standard ANSI-C, it works somewhat. Anyway, the code has two syntax errors in it: one in the TCollisionPacket structure where there should be a semi-colon after eRadius, and there is an extra bracket in the collideWithWorld() function... The new and improved version is the one I was working on, and my camera will often get stuck in small gaps, and trying to get it to 'jump' does not work at all.
Since there's code posted, I'll try it out first though! =D
I also have another question too. Lets say my object collides with multiple planes at once. Should handle the collision response for every single plane, or should I add all of their normals together, and make one response based off of it?
[Edited by - Vincent_M on January 27, 2009 5:39:58 AM]
I also had another question too! Did you guys (the ones using it) copy and paste the peroxide.dk code into your game, or did you make your own implementation based on the reading? I have tried to just copy and paste the code into my own project, and by the time I convert it into standard ANSI-C, it works somewhat. Anyway, the code has two syntax errors in it: one in the TCollisionPacket structure where there should be a semi-colon after eRadius, and there is an extra bracket in the collideWithWorld() function... The new and improved version is the one I was working on, and my camera will often get stuck in small gaps, and trying to get it to 'jump' does not work at all.
Since there's code posted, I'll try it out first though! =D
I also have another question too. Lets say my object collides with multiple planes at once. Should handle the collision response for every single plane, or should I add all of their normals together, and make one response based off of it?
[Edited by - Vincent_M on January 27, 2009 5:39:58 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
