HELP! Continuous collision detection for simple objects

[FD]

Hi guys!

I'm modifying a physics engine which relies on continuous collision detection (not your 4D-GJK, but a simple triangle-sphere scheme). I was asked to implement support for capules, spheres, and boxes, e.g. I need an algorithm for calculating the collision point and collision time between a sphere and a box, a sphere and a capsule, and a sphere and a box where only the sphere is moving. Are there any ready algorithms for the case?

[Olivier_uk]

Yeah.

Sphere-Box.

You need to find which faces are candidates for collision. This should be relatively straight forward with a bit of partitioning. There can only be a maximum of three faces (say, the sphere is facing a corner)

Then you simply test the box against each potential faces (same as sphere-triangle), take the first occurance.

Like for triangles, it's also using space partitioning techniques to determine the collision.

With further tests, you can cull the features that can potentially collide with the sphere, to reduce the collision tests.

Sphere-Capsule.

For sphere-capsule, it's similar to sphere-segment collision, only the segment has a 'radius'. Note that the sphere-segment test is also related to the sphere-sphere test.

There should be a sphere-segment test for in the sphere-triangle code.

As for the 'only the sphere is moving', it's exactly the same as a moving box vs a moving sphere. In any cases, when you test two moving objects, one is made static (the box, or the capsule), and the sphere's movement is then made relative (Vsphere' = VSphere - Vbox).

[Olivier_uk]

If you need more details (implementation if you want), shout. I've got loads of code examples.

[FD]

Oliver,

I do shout. A _continuous_ sphere-segment collision case doesn't seem that obvious to me

[Olivier_uk]

If you have sphere triangle tests working, there should be a sphere segment implementation somewhere (unless they use the 'ellipsoid collision' which is broken in any case).

ok then...

Sphere - vertex :
sphere [O, r, D] // O : centre, r : radius, D, displacement
vertex [V] // V : vertex position

doing a test between a moving sphere [O, D, r] and a vertex [V] is equivalent to doing a ray versus a static sphere intersection. If you want, make the sphere static, and fire a ray from vertex [V, -D], back towards the sphere [O, r]. It's the conceptually same thing as firing a ray [O, D] from the sphere centre towards the sphere [V, r].

so, ray [O, D] equation :
1. P(t) = O + D * t

P(t) is on sphere [V, r] if
2. (P(t) - V)^2 = r^2

merge the equations 1. and 2. and you get a second order equation to solve.
3. ((O - V) + D * t)^2 - r^2 = 0

3. is equivalent to the equation
a * t^2 + b * t + c = 0

where :
a = (D . D)
b = (D . (O - V)) * 2
c = (O - V).(O - V) - r^2

typical ray - sphere equation solving.

now for a moving sphere versus a segment.
sphere [O, r, D]
segment [A, B].

the equation is practically the same. doing moving sphere vs segment is equivalent to firing ray [O, D] towards capsule [A, B, r].

ray equation.
P(t) = O + D * t

cylinder equation :
((P(t) - A) x (B - A))^2 = r^2 * (B - A)^2
AO = O - A
AB = B - A
(AO x AB + (D x AB) * t)^2 - (r^2 * (AB.AB)) = 0

again, second order equation to solve. All you have extra are the cross products.

then you have some logic to perform to test against the caps (or the rounded ends for capsules).

If your segmentr is a capsule, then 'r' is simply the sum of the sphere radius and the capsule radius.

[Olivier_uk]

code (untested) :

Code: Select all

//
// solve vector equation : (P + V * t)^2 = r2
// equation in form : a*t^2 + b * t + c = 0
// a = (V . V)
// b = (P . V) * 2
// c = (P . P) - r2  
// returns first positive root.
//
// special cases :
// -----------------
// if (c < 0), we have intersection -> returns 0 time.
// if (b > 0), the two objects move away from each other. no collision.
//
bool SolveCollision(Vector P, Vector V, float r2, float tmax, float& t)
{
    float a = (V * V); // dot product
    float b = (P * V) * 2.0f;
    float c = (P * P) - r2;

    if(c <= 0.0f) 
    {
        t = 0.0f; // intersection
        return true;
    }
  
    if(b > 0.0f) 
    {
        return false;
    }

    float d = (b*b) - (4.0f * a * c);
    if(d < 0.0f) return false;

    d = sqrt(d);
    float t0 = (-b - d) / (2.0f * a);
    float t1 = (-b + d) / (2.0f * a);

    if (t0 > t1) swapf(t0, t1);
    if (t1 < 0.0f || t0 > tmax) return false;
    t = max(t0, 0.0f);

    return true;
}

//
// Extract collision info from a collision result
// t : result of the collision test
//     t = 0 : we have an intersection
//     t > 0 : we have a collision
// collision info : [Ncoll, tcoll, Ncoll].
//                      Dcoll : intersection depth.
//                      Ncoll : normal of collision.
//                      tcoll : time of collision (=0 if intersection).
//
void CalculateCollisionInfo(float t, Vector P, Vector V, float r, float& tcoll, Vector& Ncoll, Vector& Dcoll)
{
    tcoll = t; // time of collision
    Ncoll = (P + V * t); // normal of collision
    float l = Ncoll.Length();
    Ncoll /= l; // normalise.
    Dcoll = Ncoll * (r - l); // intersection depth (shoudl be 0 if it was a forward collision. aka (r = l)).

    return true;
}

//
// Solve a second order polynomial equation
// P : relative position
// V : relative velocity
// r : relative radius
// r2 : radius in squared space (not necessary = r*r).
// tmax : max possible time of collision
// [tcoll, Ncoll, Dcoll] : collision result
//
bool SolveCollision(Vector P, Vector V, float r, float r2, float tmax, float& tcoll, Vector& Ncoll, Vector& Dcoll)
{
    // solve polynomial for t.
    float t;
    if (!SolveCollision(P, V, r2, tmax, t)) 
        return false;
  
    // derive the collision result.    
    return CalculateCollisionInfo(t, P, V, r, tcoll, Ncoll, Dcoll);
}

//
// sphere A: [PA, VA, ra]
// Vertex B: [PB]
// max time of collision : tmax
// collision info : [Ncoll, tcoll, Dcoll].
//
bool CollideSphereVertex(Vector PA, Vector VA, float ra, Vector PB, float tmax, Vector& Ncoll, float& tcoll, Vector& Dcoll)
{
    return SolveCollision((PA - PB), VA, ra, (ra*ra), tmax, tcoll, Ncoll, Dcoll);
}

//
// sphere A: [PA, VA, ra]
// sphere B: [PB, VB, rb]
// max time of collision : tmax
// collision info : [Ncoll, tcoll, Dcoll].
//
bool CollideSphereSphere(Vector PA, Vector VA, float ra, Vector PB, Vector VB, float rb, float tmax, Vector& Ncoll, float& tcoll, Vector& Dcoll)
{
    return CollideSphereVertex(PA, (VA-VB), (ra+rb), PB, tmax, Ncoll, tcoll, Dcoll);
}

//
// sphere : [PA, VA, ra]
// segment : [PB0, PB1]
// max time of collision : tmax
// collision info : [Ncoll, tcoll, Dcoll].
//
bool CollideSphereSegment(Vector PA, Vector VA, float ra, Vector PB0, Vector PB1, float tmax, Vector& Ncoll, float& tcoll, Vector& Dcoll)
{
    Vector E(PB1 - PB0);
    Vector P((PA - PB0) ^ E); // '^' = cross product
    Vector V(VA ^ E); // '^' = cross product
    float e2 = (E * E);
    float ra2 = (ra * ra) * e2; // E isn't normalised. need to scale the radius in the calculations

    float t;    
    if(!SolveCollision(P, V, ra2, tmax, t))
        return false;

    // bounds check
    Vector QA = PA + VA * t;
    float e = ((QA - PB0) * E) / e2;

    // need to check with the vertex P0
    if (e <= 0.0f)
    {
        return CollideSphereVertex(PA, VA, ra, PB0, tmax, Ncoll, tcoll, Dcoll);
    }
    // need to check with the vertex P1
    else if (e >= 1.0f)
    {
        return CollideSphereVertex(PA, VA, ra, PB1, tmax, Ncoll, tcoll, Dcoll);
    }
    // we've hit the segment
    else
    {
        // derive the collision result.    
        QA -= (PB0 + E * e); // point on the edge at the perpendicular of QA.
        return CalculateCollisionInfo(t, QA, Vector(0, 0, 0), ra, tcoll, Ncoll, Dcoll);
    }
}

//
// sphere : [PA, VA, ra]
// capsule : [PB0, PB1, rb]
// max time of collision : tmax
// collision info : [Ncoll, tcoll, Dcoll].
//
bool CollideSphereCapsule(Vector PA, Vector VA, float ra, Vector PB0, Vector PB1, float rb, float tmax, Vector& Ncoll, float& tcoll, Vector& Dcoll)
{

    return CollideSphereSegment(PA, VA, (ra + rb), PB0, PB1, tmax, Ncoll, tcoll, Dcoll);
}