Sign in to follow this  

Problem with sphere/triangle collisions

This topic is 3463 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I've implemented the "sweping sphere" according to this paper. But it's weird, because it doesnt work for some edges/vertices. Right now I try to get it to work for the vertex (0,0,0). I have a right triangle and if I try to move into the left lowest corner, I move a bit "into" the triangle... the same goes for the lower edge, I can go through it with the top of the spere. But for some other edges, it works perfectly, the collisions are water-tight. So the collision is detected somewhat "late", like here here and here I dont know what it could be. Here is the important code in C# (I use the DirectX classes for Vectors). I use a sphere of radius 1, everything according the to article above.
// Solve the quadratic at^2+bt+c = 0 and check for vali roots, i.e. that are between 0 and max.
public bool LowestRoot(float a, float b, float c, float max, ref float root) {
            if (b * b - 4.0f * a * c < 0.0f)
                return false;
            float r1, r2;
            r1 = (-b - (float)Math.Sqrt(b * b - 4 * a * c))/(2*a);
            r2 = (-b + (float)Math.Sqrt(b * b - 4 * a * c)) / (2 * a);

            if (r1 > r2)
            {
                float temp = r1;
                r1 = r2; r2 = temp;
            }

            if (r1 > 0 && r1 < max)
            {
                root = r1;
                return true;
            }
            else if (r2 > 0 && r2 < max)
            {
                root = r2;
                return true;
            }

            return false;
        }

public bool LineVertexIntersection(Line line, Vector3 vertex, ref float t)
        {
            float A = Vector3.LengthSq(line.v);
            float B = 2.0f * Vector3.Dot(line.v, line.p - vertex);
            float C = Vector3.LengthSq(vertex - line.p) - 1.0f;
            float root = 0;
            
            if(LowestRoot(A,B,C, t, main, ref root)) {
                t = root;
                return true;
            }

            return false;
        }



I call the function above for my moving sphere, and you can see the result in the images. When I collision is detected, I choose not to move the sphere, so there's no way it should look like that if the collision detection worked properly [Edited by - zurekx on June 25, 2008 10:43:34 AM]

Share this post


Link to post
Share on other sites
Back-tracing the ray from the closest point will fail sometimes. The problem is that a few iterations are required for it to work.

something like this.


//-----------------------------------------------------------------------------
// test collision of a ball [m_position, m_velocity, m_radius] against
// a axis aligned box [centre, halfsize].
// --------------------------------------------------
// This algo is iterative, and will work in a way like GJK works
// 1) let {p} = {m_position}.
// 2) find closest point {pcoll} on box to {p}.
// 3) if that point within radius distance, then we have a collision
// 4) else, compute the plane normal, {normal} = [{p} - {pcoll}].normalised().
// 5) find time {t} of collision with the plane [{pcoll}, {normal}].
// 6) if {t} > {tmax}, or point {m_position} back-facing the plane, no collision, we missed.
// 7) move {p} to time of collision : {p} = {m_position} + {m_velocity} * {t}.
// 8) go to 2).
//-----------------------------------------------------------------------------
bool Ball::collide(const Vector& centre, const Vector& halfsize, float& tcoll, Vector& pcoll, float tmax) const
{
// search time
float t = 0.0f;

// search position.
// we will advance the ball forward
// and refine the collision plane
Vector p = m_position;

// radius, plus some extra to terminate the collision iteration.
float r2 = ((m_radius + 0.01f) * (m_radius + 0.01f));
int iter = 0;

while (1)
{
iter++;
if(iter == 2) printf("iter: %d", iter);
else if(iter > 2) printf(", %d", iter);

// find the closest point on box from our search position.
bool inside;
pcoll = closestPointOnBox(p, centre, halfsize, inside);

// position inside the box.
// extreme case when the ball gets inside a brick.
if(inside)
{
if(iter >= 2) printf("\n");
tcoll = t;
return true;
}

// check to see if that point can be our
// final collison point
Vector delta = (p - pcoll);

// see if the point is inside our radius (plus extra).
float d2 = (delta.dotProduct(delta));

// yup, so we have collision
if(d2 < r2)
{
// we have an intersection.
if(iter >= 2) printf("\n");
tcoll = t;
return true;
}

// compute the normal of the plane of collision
Vector n = delta;
n /= sqrt(d2);

// find time of collision with that plane
float denom = (m_velocity * n);
float numer = ((m_position - pcoll).dotProduct(n));

// condition when the search becomes invalid
// (the ball misses the object).
if(denom > -1.0E-8f || numer < 0.0f)
{
if(iter >= 2) printf("\n");
return false;
}

// find time of collision between
// ball and the new collision plane
t = (m_radius - numer) / denom;

// intersection with that plane if invalid
if(t > tmax || t < 0.0f)
{
if(iter >= 2) printf("\n");
return false;
}

// move search position forward.
p = m_position + m_velocity * t;
}
}


In short, the algo they use would be doing one iteration of that routine. It needs a few more for edges and vertices.

the closestPointonBox() can be replaced with the ClosestPointOnTriangle() for testing against triangles.

However, dont use that code yet, It's still prototype. But in short, I believe the algo in that paper isn't 100%.

The root solving isn;t the problem, the problem is using the closest point as the opint of collision.

Share this post


Link to post
Share on other sites
Thanks for the reply! I dont really understand what you mean, could you explain it a little bit more? What back-tracing are you talking about? I only have one single triangle.. shouldnt I be able to detect whether or not Im colliding with e vertex? I just have a single vertex right now.

Share this post


Link to post
Share on other sites
It's the way the compute the collision point by using a ray fired from the closest point on the triangle, and using the opposite direction of the ray, and finding the intersection with the sphere.

For a single vertex, the algo you have should work. But as I said, it will not work 100% with the edges.

Share this post


Link to post
Share on other sites
Let me clearify things a little :) All I want to do (right now, Im debugging) is to check collision between the moving sphere and the single vertex (0,0,0), I ignore the triangle and the edges and all that. So I move the sphere around with the keyboard. For each frame, I compute the line between the old and new position, and I want to know if the sphere, somewhere along this line, intersects the vertex. I mean, that should work right? But for some reason, it gives the wrong answer for some vertices, which is weird.

Edit: feel like i should kill myself. Had some old code from my old intersection-code which only worked for a point..when drawing the sphere, I added 0.5 to the y-coordinate so it would "stand" on the ground. So my collision code is correct, I just rendered the sphere at the wrong place. Sorry!

Share this post


Link to post
Share on other sites

This topic is 3463 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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