Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been learning a bit of collision resolution through a tutorial here and I can't seem to get the AABBvsAABB resolution working, I have CirclevsCircle and AABBvsCircle resolution working with the same method,ResolveCollision

Essentially what happens is I have a test scenario where two AABBs collide with each other. The collision gets detected however, the AABBs will just keep going through each other. If two circles collide, they show the correct response.

If you need the full code you can nab it from my github. This has both Windows and Linux versions.

Here is the data class that is passed to the AABBvsAABB method:

public struct Manifold
{
    public PhysicsObject A, B;
    public float PenetrationDepth;
    public Vector2 Normal;
    public bool AreColliding;
}

Here is the code for testing the collision between the AABB and AABB

public static bool AABBvsAABB (AABB a, AABB b, ref Manifold m)
{
    m.A = a;
    m.B = b;
    m.Normal = b.Position - a.Position;

    //Calculate the extent on the X axis
    float aExtent = (a.Right - a.Left) / 2;
    float bExtent = (b.Right - b.Left) / 2;

    //Find the X overlap
    float xExtent = aExtent + bExtent - Math.Abs (m.Normal.X);

    //SAT Test on X
    if (xExtent > 0) {
        //There was overlap on the X axis, now lets try to Y
        aExtent = (a.Bottom - a.Top) / 2;
        bExtent = (b.Bottom - b.Top) / 2;

        //Calculate Y overlap
        float yExtent = aExtent + bExtent - Math.Abs(m.Normal.Y);

        //SAT Test on Y axis
        if (yExtent > 0){
            //Find which axis has the biggest penetration ;D
            if (xExtent > yExtent){
                if(m.Normal.X < 0)
                    m.Normal = new Vector2(-1,0);
                else
                    m.Normal= Vector2.Zero;
                m.PenetrationDepth = xExtent;   
                m.AreColliding = true;
                return true;
            }
            else {
                if(m.Normal.Y < 0)
                    m.Normal = new Vector2(0,-1);
                else
                    m.Normal= Vector2.Zero;
                m.PenetrationDepth = yExtent;
                m.AreColliding = true;
                return true;
            }
        }
    }
    return false;
}

Lastly here is the ResolveCollision Method.

public static void ResolveCollision(Manifold m)
{
    Vector2 relVelocity = m.B.Velocity - m.A.Velocity;
    //Finds out if the objects are moving towards each other.
    //We only need to resolve collisions that are moving towards, not away.
    float velAlongNormal = PhysicsMath.DotProduct(relVelocity, m.Normal);
    if (velAlongNormal > 0)
        return;
    float e = Math.Min(m.A.Restitution, m.B.Restitution);

    float j = -(1 + e)*velAlongNormal;
    j /= m.A.InvertedMass + m.B.InvertedMass;

    Vector2 impulse = j*m.Normal;
    m.A.Velocity -= m.A.InvertedMass*impulse;
    m.B.Velocity += m.B.InvertedMass*impulse;
}
share|improve this question
    
Normally AABBs are used for collision detection, not for collision resolving. Did you check if those AABBs actually register a collision callback? If not, the resolving codes will never be called. – laishiekai May 8 '13 at 19:05
    
I did and they do. When I debugged it the ResolveCollision method gets called, but I think there is an issue with how this tutorial calculates the AABBvsAABB normal. I was hoping someone could proofread as the guy who wrote this code certainly didn't .___.''' – redcodefinal May 8 '13 at 23:22

I believe that your manifold normals are incorrect. These AABBs will attempt to "push back" along the axis of the greatest intersection, however:

if(m.Normal.X < 0)
  m.Normal = new Vector2(-1,0);
else
  m.Normal= Vector2.Zero;

That code is saying "if B is further left than A, then the direction to resolve penetration is in the negative X axis, otherwise there is no direction."

Try changing the else block to:

else
  m.Normal = new Vector2( 1, 0 );

However this may still not do quite what you want (if you want the AABB to "bounce" off eachother more naturally.) In that case you will want to just compute the B - A and then normalize the vector. (It should have a method on the class to do so.)

Your resolution does not account for penetration depth either, so you will lose a lot of accuracy at greater timeslices.

share|improve this answer
    
Thanks for the advice. I'm working through Part 2 of that tutorial which deals with timestepping and the like. I'll give your answer a try andsee if it gets fixed. :D – redcodefinal May 9 '13 at 18:07
    
I figured out what the problem was, I'll post my code for an explanation. Thank you for trying to help. – redcodefinal May 10 '13 at 2:10
up vote 0 down vote accepted

I fixed the problem by putting a normalized normal into the m.Normal field and multiplied it by a value to flip the normal depending on what axis/axes it was intersecting on.

public static bool TestAABBvsAABB (AABB a, AABB b, ref Manifold m)
        {
            m.A = a;
            m.B = b;
            m.Normal = b.Position - a.Position;

            //Calculate the extent on the X axis
            float aExtent = (a.Right - a.Left) / 2;
            float bExtent = (b.Right - b.Left) / 2;

            //Find the X overlap
            float xExtent = aExtent + bExtent - Math.Abs (m.Normal.X);

            //SAT Test on X
            if (xExtent > 0) {
                //There was overlap on the X axis, now lets try to Y
                aExtent = (a.Bottom - a.Top) / 2;
                bExtent = (b.Bottom - b.Top) / 2;

                //Calculate Y overlap
                float yExtent = aExtent + bExtent - Math.Abs(m.Normal.Y);

                //SAT Test on Y axis
                if (yExtent > 0){
                    //Find which axis has the biggest penetration ;D
                    Vector2 fixnormal;
                    if (xExtent > yExtent){
                        if(m.Normal.X < 0)
                            fixnormal = -Vector2.UnitX;
                        else
                            fixnormal = Vector2.UnitX;

                        m.Normal = PhysicsMath.GetNormal(m.A.Position, m.B.Position) * fixnormal.X;
                        m.PenetrationDepth = xExtent;   
                        m.AreColliding = true;
                        return true;
                    }
                    else {
                        if(m.Normal.Y < 0)
                             fixnormal = -Vector2.UnitY;
                        else
                            fixnormal= Vector2.UnitY;
                        m.Normal = PhysicsMath.GetNormal(m.A.Position, m.B.Position) * fixnormal.Y;
                        m.PenetrationDepth = yExtent;
                        m.AreColliding = true;
                        return true;
                    }
                }
            }

            return false;
        }
share|improve this answer

I think I've seen some of your other posts as I followed the same tutorial myself here years later.

You've tried to "correct" the logic of the original algorithm by using

//Find which axis has the biggest penetration ;D
                    Vector2 fixnormal;
                    if (xExtent > yExtent){

But that's not the original tutorial's logic which has:

// Find out which axis is axis of least penetration

I had to draw out some cases on paper to understand, but, suppose you have two boxes, one above the other, separated by a small gap and traveling towards each other.

These boxes will overlap on the X-Axis, which is to say they can have almost total penetration if they are directly one above the other.

So if that's the case, the second test is to test along the y-axis. In this example it would fail because the two boxes don't overlap.

But, suppose now we "step" the simulation and the boxes move closer together such that a bit of overlap has occured... not much because we only step the simulation a few milliseconds at a time.

So now, we still have almost total X penetration, because one block is above the other... but we also have a liiiiitttle bit of Y penetration.... due to the collision.

So, we're trying to find the Axis of least penetration because that's the axis along which the collision just occurred.

Here's my copy (C++) of the AABBvsAABB algorithm.

bool AABBvsAABB(Manifold *m)
{

    // Setup a couple pointers to each object
    Box * A = dynamic_cast<Box *>(m->A);
    Box * B = dynamic_cast<Box *>(m->B);

    // Vector from A to B
    Vector2d n = B->_pos - A->_pos;

    AABB abox = A->aabb;
    AABB bbox = B->aabb;

    // Calculate half extents along x axis for each object
    double a_extent = (abox.max.x() - abox.min.x()) / 2;
    double b_extent = (bbox.max.x() - bbox.min.x()) / 2;

    // Calculate overlap on x axis
    double x_overlap = a_extent + b_extent - abs(n.x());

    // SAT test on x axis  ( Separating Axis Theorem )
    if (x_overlap > 0)
    {
        // Calculate half extents along x axis for each object
        double a_extent = (abox.max.y() - abox.min.y()) / 2;
        double b_extent = (bbox.max.y() - bbox.min.y()) / 2;

        // Calculate overlap on y axis
        double y_overlap = a_extent + b_extent - abs(n.y());

        // SAT test on y axis
        if (y_overlap > 0)
        {
            // Find out which axis is axis of least penetration
            //if (x_overlap > y_overlap) // TC: Suspect this logic was wrong implementation of comment above
            if (x_overlap < y_overlap)
            {
                // Create a Collision Manifold...

                // Point towards B knowing that n points from A to B
                // TC: Create a left of right "unit vector" normal
                if (n.x() < 0)
                    m->normal = Vector2d(-1, 0);
                else
                    m->normal = Vector2d(1, 0);
                //m->normal = Vector2d(0, 0);// TC: Suspect there was another bug here.

                if (BOXES_COLLIDE_LIKE_BALLS)
                {
                    m->normal = n.normalized();
                }

                m->penetration = x_overlap;
                return true;
            }
            else // x overlap is greater, so assume is a Y-Axis collision
            {
                // Point toward B knowing that n points from A to B
                // TC: Create either an up or a down vector.
                if (n.y() < 0)
                    m->normal = Vector2d(0, -1);
                else
                    m->normal = Vector2d(0, 1);

                if (BOXES_COLLIDE_LIKE_BALLS)
                {
                    m->normal = n.normalized();
                }

                m->penetration = y_overlap;
                return true;
            }
        }

    }

    // either x does not overlap, or does, but y does not... no collision
    return false;

}

I render my world using a down view of it... kind of like looking down on a pool table with balls and uh... boxes.

What baffled me for some time is that, in my example above, if two boxes travel towards each other at the same speed and aligned with each other, they would stop. It didn't make sense to me. But then I tried the same test with Circle vs Circle. Same thing happened... the balls collide and stop.

And then I realized that this is correct behaviour. If you could perfectly roll two billiard balls towards each other at the same speed, they would stop. (Of course it's next to impossible to achieve this kind of mathematical perfection in reality, but play enough pool and you'll see it happen on occasion.

The same thing applies to the physics being used in the tutorial here for boxes. It's simplistic, but the author mentions that in his explanation and it does indeed work.

share|improve this answer
    
btw - there's a clause in there: if (BOXES_COLLIDE_LIKE_BALLS) { m->normal = n.normalized(); } That was just me playing around with applying the same logic that's used for balls to the AABBvsAABB algorithm. Also, almost all of the comments are from the original tutorial; I've prefixed a few of my own with //TC: . Lastly, I further suspect there is a minor flaw with the AABBvsAABB design such that it assumes the corners of the bounding box are equi-distant from the center (given how it calculates the 1/2 extents). – Troy Chard Jun 5 at 20:10

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.