Sign in to follow this  
crows

SAT sphere triangle test, calculating response

Recommended Posts

Hello, I have been looking for a simple method that I understand to test a sphere to a triangle in 3d, so I found this article http://realtimecollisiondetection.net/blog/?p=103 which I was able to implement and works well. I just can't seem to grasp how should I generate a response to the collision, specifically the penetration depth. In concept it should be the least overlap on all axis? How would I go about calculating the response?

Share this post


Link to post
Share on other sites

The penetration depth is the distance between the closest points minus the sphere radius.

The collision normal is the separating axis.

If the triangle is static and you want a positional response then you can shift the sphere center by the penetration depth along the collision normal. Assume p2 is the closest point on the triangle to the sphere center. You can shift the sphere like this:

 

penetration = dot(p2 - center, normal) - radius

center = center + penetration * normal

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

Yes the triangle is static. I understand your reply perfectly, only im not sure on how to calculate the closest points.

Share this post


Link to post
Share on other sites

You can use Barycentric coordinates to find the closest point on the triangle to the sphere center. Here's some personal code of mine you can use:

// Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v)
// with respect to a segment AB.
// The last output value is the divisor.
static B3_FORCE_INLINE void b3Barycentric(float32 out[3],
    const b3Vec3& A, const b3Vec3& B,
    const b3Vec3& Q)
{
    b3Vec3 AB = B - A;
    b3Vec3 QA = A - Q;
    b3Vec3 QB = B - Q;

    float32 divisor = b3Dot(AB, AB);
    
    out[0] = b3Dot(QB, AB);
    out[1] = -b3Dot(QA, AB);
    out[2] = divisor;
}

// Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v, w)
// with respect to a triangle ABC.
// The last output value is the divisor.
static B3_FORCE_INLINE void b3Barycentric(float32 out[4],
    const b3Vec3& A, const b3Vec3& B, const b3Vec3& C,
    const b3Vec3& Q)
{
    b3Vec3 AB = B - A;
    b3Vec3 AC = C - A;

    b3Vec3 QA = A - Q;
    b3Vec3 QB = B - Q;
    b3Vec3 QC = C - Q;

    b3Vec3 QB_x_QC = b3Cross(QB, QC);
    b3Vec3 QC_x_QA = b3Cross(QC, QA);
    b3Vec3 QA_x_QB = b3Cross(QA, QB);

    b3Vec3 AB_x_AC = b3Cross(AB, AC);
    
    float32 divisor = b3Dot(AB_x_AC, AB_x_AC);

    out[0] = b3Dot(QB_x_QC, AB_x_AC);
    out[1] = b3Dot(QC_x_QA, AB_x_AC);
    out[2] = b3Dot(QA_x_QB, AB_x_AC);
    out[3] = divisor;
}


// Return the closest point on a triangle ABC to a point Q.
b3Vec3 Solve3(const b3Vec3& A, const b3Vec3& C, const b3Vec3& C, const b3Vec3& Q)
{
    // Test vertex regions
    float32 wAB[3], wBC[3], wCA[3];
    b3Barycentric(wAB, A, B, Q);
    b3Barycentric(wBC, B, C, Q);
    b3Barycentric(wCA, C, A, Q);
    
    // R A
    if (wAB[1] <= 0.0f && wCA[0] <= 0.0f)
    {
        return A;
    }

    // R B
    if (wAB[0] <= 0.0f && wBC[1] <= 0.0f)
    {
        return B;
    }

    // R C
    if (wBC[0] <= 0.0f && wCA[1] <= 0.0f)
    {
        return C;
    }

    // Test edge regions        
    float32 wABC[4];
    b3Barycentric(wABC, A.point, B.point, C.point, Q);
    
    // This is used to help testing if the face degenerates
    // into an edge.
    float32 area = wABC[3];

    // R AB
    if (wAB[0] > 0.0f && wAB[1] > 0.0f && area * wABC[2] <= 0.0f)
    {
        float32 s = wAB[2];
        B3_ASSERT(s > 0.0f);
        return (wAB[0] * A + wAB[1] * B) / s;
    }

    // R BC
    if (wBC[0] > 0.0f && wBC[1] > 0.0f && area * wABC[0] <= 0.0f)
    {
        float32 s = wBC[2];
        B3_ASSERT(s > 0.0f);
        return (wBC[0] * B + wBC[1] * C) / s;
    }

    // R CA
    if (wCA[0] > 0.0f && wCA[1] > 0.0f && area * wABC[1] <= 0.0f)
    {
        float32 s = wCA[2];
        B3_ASSERT(s > 0.0f);
        return (wCA[0] * C + wCA[1] * A) / s;
    }

    // R ABC/ACB
    float32 s = wABC[3];
    if (s <= 0.0f)
    {
        // Give up. Triangle is degenerate.
        // You should handle all cases correctly in production code.
        return;
    }

    B3_ASSERT(s > 0.0f);
    return (wABC[0] * A + wABC[1] * B + wABC[2] * C) / s;
}

If you want to learn the math read Real-Time Collision Detection book. 

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

Thank you, it works I will have to get that book. When I first tried it did not work, playing around I realized it seem to be the winding on the triangles so I inverted it and it works well, although if 2 triangles make a corner it doesn't behave well. My first thought was that it was pushing the sphere to a place where it would be interpenetrating another triangle so I did a little recursion when a collision is found to solve other collisions and on most cases it's smoother, but I will get jitter on any corner that faces outward. Any resources on how to get rid of this jitter problem?

Share this post


Link to post
Share on other sites
You can implement a position based constraint solver for this. Sharp corners requires a large number of solver iterations. Erin Catto (Box2D) described this algorithm at the end of his presentation: 
 
It should be pretty easy to simplify it to your case and a great exercise. This is a very good resource with no lack of mathematical foundation.
 
Sorry, I cannot list you all the edge cases because I haven't taken the time to implement a robust character controller. But that is not a difficult problem we can tell you.

If your engine supports double side collision the order of the triangle vertices doesn't matter. 

Edited by Irlan Robson

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