Sign in to follow this  
Spa8nky

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

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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?

*---*
| |
*-----------*
| | | |
*-----------*
| |
*---*

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this