Physics System ignores collision in some rare cases

Question

I've been developing a simple physics engine for my game. since the game physics is very simple I've decided to increase accuracy a little bit. Instead of formal integration methods like fourier or RK4, I'm directly computing the results after delta time "dt". based on the very first laws of physics :

dx = 0.5 * a * dt^2 + v0 * dt
dv = a * dt

where a is acceleration and v0 is object's previous velocity. Also to handle collisions I've used a method which is somehow different from those I've seen so far. I'm detecting all the collision in the given time frame, stepping the world forward to the nearest collision, resolving it and again check for possible collisions. As I said the world consist of very simple objects, so I'm not loosing any performance due to multiple collision checking. First I'm checking if the ball collides with any walls around it (which is working perfectly) and then I'm checking if it collides with the edges of the walls (yellow points in the picture).

the algorithm seems to work without any problem except some rare cases, in which the collision with points are ignored. I've tested everything and all the variables seem to be what they should but after leaving the system work for a minute or two the system the ball passes through one of those points. Here is collision portion of my code, hopefully one of you guys can give me a hint where to look for a potential bug!

void PhysicalWorld::checkForPointCollision(Vec2 acceleration, PhysicsComponent& ball, Vec2& collisionNormal, float& collisionTime, Vec2 target)
{
    // this function checks if there will be any collision between a circle and a point
    // ball contains informations about the circle (it's current velocity, position and radius)
    // collisionNormal is an output variable
    // collisionTime is also an output varialbe
    // target is the point I want to check for collisions

    Vec2 V = ball.mVelocity;
    Vec2 A = acceleration;
    Vec2 P = ball.mPosition - target;

    float wallWidth = mMap->getWallWidth() / (mMap->getWallWidth() + mMap->getHallWidth()) / 2;
    float r = ball.mRadius / (mMap->getWallWidth() + mMap->getHallWidth()); 

    // r is ball radius scaled to match actual rendered object.

    if (A.any()) // todo : I need to first correctly solve the collisions in case there is no acceleration
        return;
    if (V.any()) // if object is not moving there will be no collisions!
    {
        float D = P.x * V.y - P.y * V.x; 
        float Delta = r*r*V.length2() - D*D;
        if(Delta < eps)
            return;
        Delta = sqrt(Delta);
        float sgnvy = V.y > 0 ? 1: (V.y < 0?-1:0);
        Vec2 c1(( D*V.y+sgnvy*V.x*Delta) / V.length2(),
               (-D*V.x+fabs(V.y)*Delta) / V.length2());
        Vec2 c2(( D*V.y-sgnvy*V.x*Delta) / V.length2(),
               (-D*V.x-fabs(V.y)*Delta) / V.length2());
        float t1 = (c1.x - P.x) / V.x;
        float t2 = (c2.x - P.x) / V.x;
        if(t1 > eps && t1 <= collisionTime)
        {
            collisionTime = t1;
            collisionNormal = c1;
        }
        if(t2 > eps && t2 <= collisionTime)
        {
            collisionTime = t2;
            collisionNormal = c2;
        }
    }
}

// this function should step the world forward by dt. it doesn't check for collision of any two balls (components)
// it just checks if there is a collision between the current component and 4 points forming a rectangle around it.
void PhysicalWorld::step(float dt)
{
    for (unsigned i=0;i<mObjects.size();i++)
    {
        PhysicsComponent &current = *mObjects[i];
        Vec2 acceleration = current.mForces * current.mInvMass;
        float rt=dt;
        // stores how much more the world should advance
        while(rt > eps)
        {
            float collisionTime = rt;
            Vec2 collisionNormal = Vec2(0,0);           
            float halfWallWidth = mMap->getWallWidth() / (mMap->getWallWidth() + mMap->getHallWidth()) / 2;

            // we check if there is any collision with any of those 4 points around the ball
            // if there is a collision both collisionNormal and collisionTime variables will change
            // after these functions collisionTime will be exactly the value of nearest collision (if any)
            // and if there was, collisionNormal will report in which direction the ball should return.
            checkForPointCollision(acceleration,current,collisionNormal,collisionTime,Vec2(floor(current.mPosition.x) + halfWallWidth,floor(current.mPosition.y) + halfWallWidth));
            checkForPointCollision(acceleration,current,collisionNormal,collisionTime,Vec2(floor(current.mPosition.x) + halfWallWidth, ceil(current.mPosition.y) - halfWallWidth));
            checkForPointCollision(acceleration,current,collisionNormal,collisionTime,Vec2( ceil(current.mPosition.x) - halfWallWidth,floor(current.mPosition.y) + halfWallWidth));
            checkForPointCollision(acceleration,current,collisionNormal,collisionTime,Vec2( ceil(current.mPosition.x) - halfWallWidth, ceil(current.mPosition.y) - halfWallWidth));
            // either if there is a collision or if there is not we step the forward since we are sure there will be no collision before collisionTime

            current.mPosition += collisionTime * (collisionTime * acceleration * 0.5 + current.mVelocity);
            current.mVelocity += collisionTime * acceleration;
            // if the ball collided with anything collisionNormal should be at least none zero in one of it's axis
            if (collisionNormal.any()) 
            {               
                collisionNormal *= Dot(collisionNormal, current.mVelocity) / collisionNormal.length2(); 
                current.mVelocity -= 2 * collisionNormal;
                // simply reverse velocity along collision normal direction
            }
            rt -= collisionTime;
        }
        // reset all forces for current object so it'll be ready for later game event 
        current.mForces.zero();
    }
}

Answer 1

This looks very similar to a problem I once had when making my own physics hack, although I can't really see from your code if this is the case here. My problem was that when an object collided at a slow speed my collision handling didn't move it enough away from the collision (so it didn't solve interpenetration). That mean that a second collision would be reported, resulting in the exact opposite contact normal to the first one, making the object just keep moving. In my case it only occurred when an object moved slowly enough making it very hard to detect. If you think this might be the case here, just use one object and set debug breakpoint to hit if you have two collisions with a very short interval.

Answer 2

This is probably a rounding error. They can cause both (1) missing collisions and (2) items 'sticking' together for a time.

This site explains a solution (search for 'due to rounding' on the page):

Computer Science Canada - Perfect Circle-Circle Collision Detection

Answer 3

In the case of any sort of collision detection, I always check for floating point number comparisons. They are inaccurate, and often a result is not what you expect it to be when you compare them. Try truncating them to 4 digits or so.

Looking at your code however, you haven't given us much context, and the above is only a suggestion to try/check. Perhaps you could give us a more complete example?