Transforming 2D AABB into OOB space doesn't work with rotations correctly.

Started by
7 comments, last by Spa8nky 14 years, 2 months ago
For my AABB OBB test I transform the AABB into OBB space and perform an AABB collision test:

        public static bool TestAABBOBB(Shape s1, Shape s2, ref Contact2D contact)
        {
            CD_AABB2D a = (CD_AABB2D)s1;
            CD_OBB2D b = (CD_OBB2D)s2;

            // Transform AABB into OBB space
            Vector2 min = Vector2.Transform(a.MinPoint, b.World_Transform);     // MinPoint is in World Coordinates
            Vector2 max = Vector2.Transform(a.MaxPoint, b.World_Transform);     // MaxPoint is in World Coordinates
            Vector2 dim = max - min;

            //(max + min) * 0.5f
            CD_AABB2D c = new CD_AABB2D(b.Position, dim.X, dim.Y); 

            return TestAABBAABB(a, c, ref contact);
        }

The collision test works fine until I rotate the OBB. Is the method for transforming the AABB correct? The world transform for the OBB is as follows:

                    world_Transform =
                        // Translate centroid to origin first (only required if centroid is not (0,0,0))
                        //Matrix.CreateTranslation(new Vector3(-centre, 0.0f)) * 
                        Matrix.CreateScale(width, height, 0f) *
                        Matrix.CreateRotationZ(rotation) *
                        Matrix.CreateTranslation(position.X, position.Y, 0f);

Thank you.
Advertisement
c is a bounding box the transformed size of a at b's position.

I don't see where b's OBB is used.

Also, I don't know what TestAABBAABB does, but does it account for overlapping boxes for which no corners of one box lie within the corners of the other?
     *---*     |   | *-----------* |   |   |   | *-----------*     |   |     *---*

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

Quote:
Also, I don't know what TestAABBAABB does, but does it account for overlapping boxes for which no corners of one box lie within the corners of the other?


It only tests against 2 axes of separation so I'm not sure if that covers that scenario:

        public static bool TestAABBAABB(Shape s1, Shape s2, ref Contact2D contact)        {            CD_AABB2D a = (CD_AABB2D)s1;            CD_AABB2D b = (CD_AABB2D)s2;            // [Separating Axis Theorem]            // • Two convex shapes only overlap if they overlap on all axes of separation            // • In order to create accurate responses we need to find the collision vector (Minimum Translation Vector)               // • Find if the two boxes intersect along a single axis             // • Compute the intersection interval for that axis            // • Keep the smallest intersection/penetration value            // Minimum Translation Vector parameters            float mtv_Distance = float.MaxValue;            // Set current minimum distance (max float value so next value is always less)            int mtv_Axis = 0;                               // Axis along which to travel with the minimum distance            // For each separating axis            for (int i = 0; i < 2; ++i)            {                // Find distance intervals for current two slabs                // Distance is between slab min/max values                float d_S0 = a.MinPoint.Index(i) - b.MaxPoint.Index(i);                float d_S1 = b.MinPoint.Index(i) - a.MaxPoint.Index(i);                // The distance is positive if the intervals do not overlap                // Must be >= to 0 and not > 0, otherwise MTV can equal Vector2.Zero and cause NaN                if (d_S0 >= 0f || d_S1 >= 0f)                {                    return false;                }                // Current distance interval for slabs                float d = (d_S0 > d_S1) ? -d_S0 : d_S1;                // If d is the smallest distance so far                if (Math.Abs(d) < Math.Abs(mtv_Distance))                {                    // Store the distance and the current axis                    mtv_Distance = d;                    mtv_Axis = i;                }            }            // Minimum Translation Vector            Vector2 mtv = Vector2.Zero;            switch (mtv_Axis)            {                case 0:                    mtv.X = mtv_Distance;                    break;                case 1:                    mtv.Y = mtv_Distance;                    break;            }            contact.normal = Vector2.Normalize(mtv);            contact.penetration = Math.Abs(mtv_Distance) + Settings.EPSILON;            // Get the AABB support points using the MTV            Vector2[] supportA = a.FindSupportPoints(contact.normal);            Vector2[] supportB = b.FindSupportPoints(-contact.normal);            //contact.point = GetContactPoints(supportA, supportB);            return true;        }


I tried converting the OBB to an AABB using the following method:

        public static CD_AABB2D ComputeFromOBB(CD_OBB2D obb)        {            Vector2 position = new Vector2();            position.X += Vector2.Dot(obb.Position, Vector2.UnitX);            position.Y += Vector2.Dot(obb.Position, Vector2.UnitY);            // Compute the projection interval radius of obb onto world unit x axis            float r_X = obb.Extents.X * Math.Abs(Vector2.Dot(Vector2.UnitX, obb.Axis_X)) +                obb.Extents.Y * Math.Abs(Vector2.Dot(Vector2.UnitX, obb.Axis_Y));            // Compute the projection interval radius of obb onto world unit y axis            float r_Y = obb.Extents.X * Math.Abs(Vector2.Dot(Vector2.UnitY, obb.Axis_X)) +                obb.Extents.Y * Math.Abs(Vector2.Dot(Vector2.UnitY, obb.Axis_Y));            Vector2 extents = new Vector2();            extents.X = r_X;            extents.Y = r_Y;            return new CD_AABB2D(position, extents.X * 2, extents.Y * 2);        }


but that didn't work for rotations as the computed AABB overlapped where the OOBB didn't.

I'm sure this should be easier than I'm making it.
Again:
Quote:I don't see where b's OBB is used.

Your TestAABBOBB function uses (from what I can see) only b's position. Where do you test something against b's box?

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

I haven't used the OBB. I assumed that by transforming the AABB or creating an AABB from the OBB that I could do a successful AABB/AABB test.

What else do I require?
Unfortunately there's no way you can transform an OBB into an AABB to test against another AABB aside from making an AABB that encompases your OBB, but then your test isn't a very good test.

I think maybe what you are thinking of is how in an OBB vs OBB test, you can transform one OBB into the space of the other so that it becomes an OBB vs AABB test.
Damn, you're right. Sorry for the confusion, I have been a bit foolish.

What are the axes of separation for a 2D AABB/OBB test? Do I test the 2 from the AABB against the 4 of the OBB?

Thank you for your patience with this.

Check out this link, i think it may help you out:

http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/

you may say "no i want AABB vs OBB" but an AABB is really just an OBB with no rotation.

On the last page of that link, it talks about optimizing for OBB vs AABB so check out that article, i think it should help you out quite a bit!
The idea of utilising a radius is great, I have added that to my collison detection routine.

        private static bool TestRadiusRadius(Shape s1, Shape s2)        {            // Calculate squared distance between centres            Vector2 v = s1.Position - s2.Position;            float distance_Squared = Vector2.Dot(v, v);            float radius_Sum = s1.Radius + s2.Radius;            float radius_Sum_Squared = radius_Sum * radius_Sum;            // Spheres intersect if squared distance is less than squared sum of radii            if (distance_Squared < radius_Sum_Squared)            {                return true;            }            return false;        }


The AABB OBB optimisation I read stated:

Quote:
It can really pay off to transform rectangle B into rectangle A’s local space. In order to do this, you should maintain these rectangles in local space and then transform rectangle B into world space and then by the inverse of rectangle A’s world space transform to put rectangle B into rectangle A’s local space. Then, translate both rectangles equally so that rectangle A is centered about the x and y axes. This means that two of the four axes that you need to project vectors onto are the unit (x and y) axes. Simply check for overlap between the x values of the corners of both rectangles and between the y values of the corners of both rectangles. With this solution you only have to actually project the vectors onto arbitrary axes twice, instead of four times.


I'm not sure how beneficial this would be because I would have to create a new AABB based and set its World Transform to the inverse of the OBB's World Transform.

            // Transform a into b's local space            Matrix m = Matrix.Invert(b.World_Transform);            // Translate both boxes to the origin            Vector2 p = a.Position - b.Position;            CD_AABB2D c = new CD_AABB2D(p, a.Width, a.Height);            c.World_Transform = m;


Do I just have to test the following 4 axes if I don't do this:

[AABB]:
a.MinPoint.X - a.MaxPoint.X;
a.MinPoint.Y - a.MaxPoint.Y;

[OBB]:
b.UL - b.LL
b.UL - b.UR

Or are my axes of separation incorrect?

Thank you.

This topic is closed to new replies.

Advertisement