views:

206

answers:

2

Hello,

I want to find when a collision between a static and a moving ball occurs, but the algorithm I came up with, sometimes doesn't detect a collision and the moving ball goes through the static one. The moving ball is affected by gravity and the static one is not.

Here's my collision detection code:

GLfloat whenSpheresCollide(const sphere2d &firstSphere, const sphere2d &secondSphere)
{
    Vector2f relativePosition = subtractVectors(firstSphere.vPosition, secondSphere.vPosition);
    Vector2f relativeVelocity = subtractVectors(firstSphere.vVelocity, secondSphere.vVelocity);

    GLfloat radiusSum = firstSphere.radius + secondSphere.radius;

    //We'll find the time when objects collide if a collision takes place

    //r(t) = P[0] + t * V[0]
    //
    //d^2(t) = P[0]^2 + 2 * t * P[0] * V[0] + t^2 * V[0]^2
    //
    //d^2(t) = V[0]^2 * t^2 + 2t( P[0] . V[0] ) + P[0]^2
    //
    //d(t) = R
    //
    //d(t)^2 = R^2
    //
    //V[0]^2 * t^2 + 2t( P[0] . V[0] ) + P[0]^2 - R^2 = 0
    //
    //delta = ( P[0] . V[0] )^2 - V[0]^2 * (P[0]^2 - R^2)
    //
    //  We are interested in the lowest t:
    //
    //t = ( -( P[0] . V[0] ) - sqrt(delta) ) / V[0]^2
    //

    GLfloat equationDelta = squaref( dotProduct(relativePosition, relativeVelocity) ) - squarev( relativeVelocity ) * ( squarev( relativePosition ) - squaref(radiusSum)  );

    if (equationDelta >= 0.0f)
    {
        GLfloat collisionTime = ( - dotProduct(relativePosition, relativeVelocity) - sqrtf(equationDelta) ) / squarev(relativeVelocity);

        if (collisionTime >= 0.0f && collisionTime <= 1.0f / GAME_FPS)
        {
            return collisionTime;
        }
    }

    return -1.0f;
}

And here is the updating function that calls collision detection:

void GamePhysicsManager::updateBallPhysics()
{
    //
    //Update velocity
    vVelocity->y -= constG / GAME_FPS;  //v = a * t = g * 1 sec / (updates per second)

    shouldApplyForcesToBall = TRUE;

    vPosition->x += vVelocity->x / GAME_FPS;
    vPosition->y += vVelocity->y / GAME_FPS;

    if ( distanceBetweenVectors( *pBall->getPositionVector(), *pBasket->getPositionVector() ) <= pBasket->getRadius() + vectorLength(*vVelocity) / GAME_FPS )
    {
        //Ball sphere
        sphere2d ballSphere;
        ballSphere.radius = pBall->getRadius();
        ballSphere.mass = 1.0f;
        ballSphere.vPosition = *( pBall->getPositionVector() );
        ballSphere.vVelocity = *( pBall->getVelocityVector() );


        sphere2d ringSphereRight;
        ringSphereRight.radius = 0.05f;
        ringSphereRight.mass = -1.0f;
        ringSphereRight.vPosition = *( pBasket->getPositionVector() );
        //ringSphereRight.vPosition.x += pBasket->getRadius();
        ringSphereRight.vPosition.x += (pBasket->getRadius() - ringSphereRight.radius);
        ringSphereRight.vVelocity = zeroVector();


        GLfloat collisionTime = whenSpheresCollide(ballSphere, ringSphereRight);

        if ( collisionTime >= 0.0f )
        {
            DebugLog("collision");
            respondToCollision(&ballSphere, &ringSphereRight, collisionTime, pBall->getRestitution() * 0.75f );
        }

        //
        //Implement selection of the results that are first to collide collision

        vVelocity->x = ballSphere.vVelocity.x;
        vVelocity->y = ballSphere.vVelocity.y;

        vPosition->x = ballSphere.vPosition.x;
        vPosition->y = ballSphere.vPosition.y;
    }

Why isn't the collision being detected in 100% of cases? It's being detected only in 70% of cases. Thanks.

UPDATE: Problem seems to be solved when I change FPS from 30 to 10. How does FPS affect my collision detection?

+1  A: 

How large are the sphere's and how fast are they moving? Can a sphere "jump" over the second one during a frame (i.e., is it's velocity vector longer than it's width?).

Along those lines, what happens if you remove the upper limit here:

if (collisionTime >= 0.0f && collisionTime <= 1.0f / GAME_FPS)
{
    return collisionTime;
}

If the sphere was moving too fast, maybe your algorithm is detecting a collision that happened more than one frame ago .. (?)

Seth
The spheres are approximately the same size.Generally, this upper limit defines if the collision will happen during the next frame. If yes, it reports a collision.
Ilya
+1  A: 
delta = ( P[0] . V[0] )^2 - V[0]^2 * (P[0]^2 - R^2)

Shouldn't that be delta = b2 - 4 ac?


[Edit] Oh I see, you factored the 4 out. In that case, are you sure you're considering both solutions for t?

t = ( -( P[0] . V[0] ) - sqrt(delta) ) / V[0]^2

and

t = ( -( P[0] . V[0] ) + sqrt(delta) ) / V[0]^2
BlueRaja - Danny Pflughoeft
I'm using an alternative formula that can be used when coefficient before x is even.
Ilya
I'm considering only one solution - the lesser time. I'm not interested in the bigger time because it will occur when the distance between objects will be 0 for the second time (collision itself occurs for lesser time).
Ilya
It may very well be due to rounding errors - the program is expecting the collision to happen next frame, but, due to slight rounding errors, by the next frame the collision should have already happened. Try replacing your `floats` with `doubles`, or have the collision happen a few frames early (replace `collisionTime <= 1.0f / GAME_FPS` with, say, `collisionTime <= 1.9f / GAME_FPS`)
BlueRaja - Danny Pflughoeft
If replacing float with double fixes a problem, then your algorithm is wrong! I do agree with BlueRaja's second statement, look at how you're handling collisionTime and make sure that you're not taking steps that are too big.
miked
The "will the collision happen this frame" approximation could also be giving incorrect results because it doesn't account for the velocity changing from one frame to the next: So whereas if the velocity were constant it would work (minus the rounding errors), the way it is now frame 2 may predict the collision will happen on frame 3, while frame 3 will say the collision happened on frame 2!
BlueRaja - Danny Pflughoeft