Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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).

enter image description here

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();
    }
}
share|improve this question
1  
A common thing to look into for things like this is when the object gets either enough velocity or acceleration to completely pass through what it would collide with. I can not say this is what is happening here so I can not give this as an answer. You can check to see if the object was ahead of you and is now behind you then go through the dt in smaller increments to find out when and more precisely where it hit if this is the case. –  James Jul 30 '12 at 23:24
    
@James I'm almost sure that's not the case, since my collision detection method is completely different from usual implementations. For every object in the scene, I'm mathematically computing exact collision time (if any) and check if that collision time is smaller than time step. –  Ali.S Jul 30 '12 at 23:56
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
I think that is the case, but how can I solve it? I mean as you can see I'm checking next collision to be at least eps seconds after previous one. but still I'm having this issue. –  Ali.S Aug 1 '12 at 0:04
    
After it's started the rebound, check to see if it's still colliding with the wall, then move it another step further. –  Raceimaztion Aug 1 '12 at 1:02
    
Well you could look at closing velocity I guess. If it is positive then you can have a collision, if it is negative then you cannot. –  Mikael Högström Aug 1 '12 at 9:59
add comment

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

share|improve this answer
    
Oh yeah, this might also make your 'minimum interval between collisions' check unnecessary, depending on your implementation. –  Timo Sep 7 '12 at 15:12
    
I'm pretty sure that was causing the problem, but still I've already added a epsilon value into my equations and that didn't help. I ended up stepping the world forward as low as eps, and that solved the problem. –  Ali.S Sep 7 '12 at 18:59
add comment

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?

share|improve this answer
    
that's the whole code responsible for collision checking and object movements. and besides I've forgot to mention I've defined eps value which is 1e-6 as possible error. –  Ali.S Jul 30 '12 at 22:43
    
Thought that may have been the case, which is part of what I was referring to in my comment about a lack of context. It would also be useful to see a use-case where it fails, and not just pure code. –  Bloodyaugust Jul 30 '12 at 23:01
    
I don't know what is causing the problem either, and I can't find any specific case where the code fails. even with very low velocity the it might miss the collision, then again it can easily handle collisions where most engines fail. –  Ali.S Jul 30 '12 at 23:59
    
Not sure how decreasing the precision is supposed to help the situation? –  user_123abc Jul 31 '12 at 12:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.