generic swept sphere collision detection algorithm.

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Olivier_uk
Posts: 12
Joined: Mon Sep 03, 2007 2:18 pm

generic swept sphere collision detection algorithm.

Post by Olivier_uk » Thu Sep 06, 2007 12:10 pm

All that sphere collision talk got me thinking a little. I am thinking of an algorithm to collide spheres against over convex shapes, which is similar to the GJK algorythm, and is an iterative method. However it requires square roots to find the point of contact (due to the sphere's nature). It's using the closest point search on a convex shape, working out a plane at that point, and colliding the pshere against that plane until the plane collision point is within the tolerance.

Code: Select all

//
// sphere [P, v, r].
// convex object [].
// probe limit : tmax
// Collision result : [Ncoll, tcoll, dcoll]
//                     Ncoll : normal of collision
//                     tcoll : time of collision
//                     dcoll : distance between sphere and convex object (negative -> intersection).
//
bool Collide(const Vector& P, const Vector& V, const Vector& r, const ConvexObject& Convex, float tmax, Vector& Ncoll, float& tcoll, float& dcoll)
{
    const float search_tolerance = 1.0E-8f;
    const float contact_tolerance = 1.0E-5f;

    while (1)
    {
        bool contained; // is the point contained in the convex shape (only of convex shape is a closed volume).
        Vector Q   = Convex.ClosestPoint(P, contained); // closest point on the convex object from sphere centre.
        Vector PQ = (P - Q);
        float d2 = (PQ * PQ);

        // intersection
        if (d2 <= (r*r))
        {
            float sign = (contained)? -1.0f : 1.0f;
            float d = sqrt(d2) * sign;
            tcoll = 0.0f;
            Ncoll = PQ / d;
            dcoll = (d - r); // distance of the sphere to convex shape (negative means intersection)
        }

        Vector N = PQ / sqrt(d2); // normal of plane (normalised)
        float denom = (V * N);
        if(denom < search_tolerance) return false; // sphere behind the plane -> no collision

        float numer  = (r - (PQ * N));
        float t = numer / denom;
        if (t < 0.0f || t > tmax) return false; // time to collision to the plane. out of bounds -> no collision
     
        // point of contact on the plane
        Vector C = (P + V * t) - (N * r);
        
        // delta from the closest point
        Vector H = (C - Q);
        float delta_squared = (H * H);
    
        // the closest point on the convex object is out collision point. 
        // we have found our contact.
        if(delta_squared < (contact_tolerance * contact_tolerance))
        {
            tcoll = t;
            Ncoll = N;
            dcoll = (H * N); // distance of sphere to the convex shape surface (signed)
            return true;
        }
    }
}
the iteration count should be quite small. However, I haven't analysed it in depth.

That algo should be quite similar to the swept GJK, only you'd be working with closest points for each iterations.

Also, the end condition isn't great, especially when the incident angle is very shallow. I think using the deviation from the plane normals between iterations should work better. Same problem as with GJK (working with tolerances).

User avatar
Erwin Coumans
Site Admin
Posts: 4140
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: generic swept sphere collision detection algorithm.

Post by Erwin Coumans » Sat Sep 08, 2007 4:56 am

Haven't checked your code in details, but you probably describe Conservative Advancement (CA).

GJK doesn't find the time of impact, it only can find the closest points/distance/overlap. You might refer to Gino van den Bergen's continuous collision detection papers, which mix conservative advancement with GJK?

CA is used to iteratively find the time of impact, and it just needs a closest point calculation. It originates from Brian Mirtichs PhD thesis. Young Kim uses Conservative Advancement, and uses Swift++ for the closest point calculation.

Have you checked out http://graphics.ewha.ac.kr/catch/ and http://graphics.ewha.ac.kr/fast papers?
Hope this clarifies things,
Erwin

Christer Ericson
Posts: 25
Joined: Mon Jun 27, 2005 4:30 pm
Location: Los Angeles
Contact:

Re: generic swept sphere collision detection algorithm.

Post by Christer Ericson » Sun Sep 09, 2007 8:36 pm

Olivier_uk wrote:All that sphere collision talk got me thinking a little. I am thinking of an algorithm to collide spheres against over convex shapes, which is similar to the GJK algorythm, and is an iterative method. However it requires square roots to find the point of contact (due to the sphere's nature). It's using the closest point search on a convex shape, working out a plane at that point, and colliding the pshere against that plane until the plane collision point is within the tolerance.
This looks very similar to Gino's GJK ray cast. Possibly identical, with the exception that in Gino's method you would spherically extend the convex object by the radius r, which makes things nicer, conceptually.

Code: Select all

        Vector PQ = (P - Q);
BTW, this was very confusing to me trying to read the code! PQ is a vector from P to Q, i.e. PQ = Q - P. QP would have been a better name for this vector.

Code: Select all

        // intersection
        if (d2 <= (r*r))
        {
            float sign = (contained)? -1.0f : 1.0f;
            float d = sqrt(d2) * sign;
            tcoll = 0.0f;
            Ncoll = PQ / d;
            dcoll = (d - r); // distance of the sphere to convex shape (negative means intersection)
        }
Shouldn't there be a "return true" here?

PS. Erwin, is it really necessary to have that "Code:" header for each code block? In particular, it makes single-line code quotes like the one above look ugly.

Olivier_uk
Posts: 12
Joined: Mon Sep 03, 2007 2:18 pm

Re: generic swept sphere collision detection algorithm.

Post by Olivier_uk » Tue Sep 11, 2007 9:27 am

I would thought it would be the natural extension to GJK for performing swept tests, I don't think it was anything new really. And I got my vector naming convention wrong :oops:

I will try that in a test app to see if it works. I have an app already in place.

And btw, the algo is wrong, The closest point should be taken from the last collision point result found, not from the start position (what would be the point apart from wanting to run an infinite loop? :mrgreen: ).

User avatar
Erwin Coumans
Site Admin
Posts: 4140
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: generic swept sphere collision detection algorithm.

Post by Erwin Coumans » Tue Sep 11, 2007 6:58 pm

It would be good to use the common name 'conservative advancement' for this technique. Both your implementation and Gino's GJK ray cast are varieties on the common theme. CA just relies on closest points.

Once we agree on the naming, we can focus on the interesting bits that you improved/optimized. Gino's contribution to CA was mixing the CA loop with the GJK closest points loop.

Christer, haven't had time to customize the forum for the 'code' blocks, this is just default behaviour of phpbb3...
Thanks!
Erwin

Post Reply