# 2D OBB intersection - Code not working correctly

This topic is 2980 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've attempted an implementation of this tutorial: http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/ - That works on the separating axis theory. The resulting code seems to treat both OBB's as circles with a radius equal to their extents...Obviously, this is not desirable. I've not optimized it, as I want to get it working, first. Could I get some error-checking? Thanks. It looks good to me. *SNIP* - Check the following posts. [Edited by - Narf the Mouse on April 24, 2010 5:05:40 AM]

##### Share on other sites
Turns out I needed to check normals and adjust the projected edges. However, one rather large problem remains...

...It doesn't correctly calculate collisions when I rotate the box. A bit of a problem for a supposed AABBxAABB test...I'll keep looking and help would be appreciated.
            public static Vector2[] getCorners(Vector2 halfSize, ref Radian rotation)            {                halfSize.Rotate(rotation);                Vector2[] corners = new Vector2[] { Vector2.Zero, Vector2.Zero, Vector2.Zero, Vector2.Zero };                corners[0].X = -halfSize.X;                corners[0].Y = -halfSize.Y;                corners[1].X = halfSize.X;                corners[1].Y = -halfSize.Y;                corners[2].X = halfSize.X;                corners[2].Y = halfSize.Y;                corners[3].X = -halfSize.X;                corners[3].Y = halfSize.Y;                return corners;            }            public static Vector2[] GetNormals(Vector2[] corners)            {                Vector2[] normals = new Vector2[4];                Vector2 v1, v2;                v1 = corners[0];                v2 = corners[1];                normals[0] = new Vector2(v2.Y - v1.Y, v2.X - v1.X);                v1 = corners[1];                v2 = corners[2];                normals[1] = new Vector2(v2.Y - v1.Y, v2.X - v1.X);                v1 = corners[2];                v2 = corners[3];                normals[2] = new Vector2(v2.Y - v1.Y, v2.X - v1.X);                v1 = corners[3];                v2 = corners[0];                normals[3] = new Vector2(v2.Y - v1.Y, v2.X - v1.X);                return normals;            }            public static Vector2[] GetAxis(Vector2[] corners)            {                Vector2[] axis = new Vector2[4];                axis[0] = corners[0] - corners[1];                axis[1] = corners[1] - corners[2];                axis[2] = corners[2] - corners[3];                axis[3] = corners[3] - corners[0];                return axis;            }            public static Vector2[] GetProjected(Vector2[] corners, Vector2[] axis)            {                Vector2[] projected = new Vector2[] { Vector2.Zero, Vector2.Zero, Vector2.Zero, Vector2.Zero };                Vector2 axis1;                double first;                for (Int32 t = 0; t < 4; ++t)                {                    axis1 = axis[t];                    first = Vector2.Dot(corners[t], axis1) / axis1.SquaredLength;                    projected[t].X = first * axis1.X;                    projected[t].Y = first * axis1.Y;                }                return projected;            }            public static void GetMinAndMax(Vector2 axis, Vector2 center, Vector2[] projected, out double min, out double max)            {                min = max = Vector2.Dot(axis, center + projected[0]);                double dot;                for (Int32 t = 0; t < 4; ++t)                {                    dot = Vector2.Dot(axis, center + projected[t]);                    if (dot < min)                        min = dot;                    if (dot > max)                        max = dot;                }            }            public static bool IntersectionOBBXOBB(                ref Vector2 centerA, ref Vector2 halfSizeA, Radian rotationA,                ref Vector2 centerB, ref Vector2 halfSizeB, Radian rotationB                )            {                Vector2[] cornersA = getCorners(halfSizeA, ref rotationA);                Vector2[] cornersB = getCorners(halfSizeB, ref rotationB);                Vector2[] normalsA = GetNormals(cornersA);                Vector2[] normalsB = GetNormals(cornersB);                Vector2[] axisA = GetAxis(cornersA);                Vector2[] axisB = GetAxis(cornersB);                Vector2[] projectedA = GetProjected(cornersA, axisA);                Vector2[] projectedB = GetProjected(cornersB, axisB);                Vector2 toNormal = (centerA - centerB).Normalized;                double minA, maxA;                double minB, maxB;                for (Int32 t = 0; t < 4; ++t)                {                    if (Vector2.Dot(normalsA[t], toNormal) >= 0)                    {                        GetMinAndMax(axisA[t], centerA, projectedA, out minA, out maxA);                        GetMinAndMax(axisA[t], centerB, projectedB, out minB, out maxB);                        if (maxA < minB                            || minA > maxB)                            return false;                    }                }                for (Int32 t = 0; t < 4; ++t)                {                    if (Vector2.Dot(normalsB[t], toNormal) >= 0)                    {                        GetMinAndMax(axisB[t], centerA, projectedA, out minA, out maxA);                        GetMinAndMax(axisB[t], centerB, projectedB, out minB, out maxB);                        if (maxA < minB                            || minA > maxB)                            return false;                    }                }                return true;            }

##### Share on other sites
The follow almost works. I say "almost" because it only really handles rotations of 45 degree increments. Why this might be, I don't know.

            public static Vector2[] getCorners(Vector2 halfSize, ref Radian rotation)            {                // halfSize.Rotate(rotation);                Vector2[] corners = new Vector2[] { Vector2.Zero, Vector2.Zero, Vector2.Zero, Vector2.Zero };                corners[0].X = -halfSize.X;                corners[0].Y = -halfSize.Y;                corners[0].Rotate(rotation);                corners[1].X = halfSize.X;                corners[1].Y = -halfSize.Y;                corners[1].Rotate(rotation);                corners[2].X = halfSize.X;                corners[2].Y = halfSize.Y;                corners[2].Rotate(rotation);                corners[3].X = -halfSize.X;                corners[3].Y = halfSize.Y;                corners[3].Rotate(rotation);                return corners;            }            public static Vector2[] GetNormals(Vector2[] corners)            {                Vector2[] normals = new Vector2[4];                Vector2 v1, v2;                v1 = corners[0];                v2 = corners[1];                normals[0] = new Vector2(v2.Y - v1.Y, v2.X - v1.X).Normalized;                v1 = corners[1];                v2 = corners[2];                normals[1] = new Vector2(v2.Y - v1.Y, v2.X - v1.X).Normalized;                v1 = corners[2];                v2 = corners[3];                normals[2] = new Vector2(v2.Y - v1.Y, v2.X - v1.X).Normalized;                v1 = corners[3];                v2 = corners[0];                normals[3] = new Vector2(v2.Y - v1.Y, v2.X - v1.X).Normalized;                return normals;            }            public static Vector2[] GetAxis(Vector2[] corners)            {                Vector2[] axis = new Vector2[4];                axis[0] = corners[0] - corners[1];                axis[1] = corners[1] - corners[2];                axis[2] = corners[2] - corners[3];                axis[3] = corners[3] - corners[0];                return axis;            }            public static Vector2[] GetProjected(Vector2[] corners, Vector2[] axis)            {                Vector2[] projected = new Vector2[] { Vector2.Zero, Vector2.Zero, Vector2.Zero, Vector2.Zero };                Vector2 axis1;                double first;                for (Int32 t = 0; t < 4; ++t)                {                    axis1 = axis[t];                    first = Vector2.Dot(corners[t], axis1) / axis1.SquaredLength;                    projected[t] = first * axis1;                    // projected[t].X = first * axis1.X;                    // projected[t].Y = first * axis1.Y;                }                return projected;            }            public static void GetMinAndMax(Vector2 axis, Vector2 center, Vector2[] projected, out double min, out double max)            {                min = max = Vector2.Dot(axis, center + projected[0]);                double dot;                for (Int32 t = 0; t < 4; ++t)                {                    dot = Vector2.Dot(axis, center + projected[t]);                    if (dot < min)                        min = dot;                    if (dot > max)                        max = dot;                }            }            public static bool IntersectionOBBXOBB(                ref Vector2 centerA, ref Vector2 halfSizeA, Radian rotationA,                ref Vector2 centerB, ref Vector2 halfSizeB, Radian rotationB                )            {                Vector2[] cornersA = getCorners(halfSizeA, ref rotationA);                Vector2[] cornersB = getCorners(halfSizeB, ref rotationB);                Vector2[] normalsA = GetNormals(cornersA);                Vector2[] normalsB = GetNormals(cornersB);                Vector2[] axisA = GetAxis(cornersA);                Vector2[] axisB = GetAxis(cornersB);                Vector2[] projectedA = GetProjected(cornersA, axisA);                Vector2[] projectedB = GetProjected(cornersB, axisB);                Vector2 toNormal = (centerB - centerA).Normalized;                double minA, maxA;                double minB, maxB;                for (Int32 t = 0; t < 4; ++t)                {                    if (Vector2.Dot(normalsA[t], toNormal) >= 0)                    {                        GetMinAndMax(normalsA[t], centerA, cornersA, out minA, out maxA);                        GetMinAndMax(normalsA[t], centerB, cornersB, out minB, out maxB);                        if (maxA < minB                            || minA > maxB)                            return false;                    }                }                for (Int32 t = 0; t < 4; ++t)                {                    if (Vector2.Dot(normalsB[t], toNormal) >= 0)                    {                        GetMinAndMax(normalsB[t], centerA, cornersA, out minA, out maxA);                        GetMinAndMax(normalsB[t], centerB, cornersB, out minB, out maxB);                        if (maxA < minB                            || minA > maxB)                            return false;                    }                }                return true;            }

##### Share on other sites
Quote:
 I've attempted an implementation of this tutorial: http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/ - That works on the separating axis theory.
Although the tutorial appears to be correct (based on a quick read-through at least), what it describes isn't really the standard (and preferred) method for detecting intersection between two oriented rectangles using the SAT.

First of all, there's no need to compute the edge normals from the corners. If you have the corners, that means you know the orientation of the box, and if you know the orientation, you know the normals. Computing the normals from the corners is sort of a strange, roundabout way of doing things.

Second of all, the corners are not needed for the projection calculation - in fact, there's no need to compute the corners at all. All that's needed (for each box) is the center, orientation (specifically, the basis vectors for the box), and the extents.

In any case, I'd recommend looking at some other references to see how the test is typically implemented.
Quote:
 The resulting code seems to treat both OBB's as circles with a radius equal to their extents...Obviously, this is not desirable.
That's not what the SAT does, but from your later posts it looks like you've already figured this out.
Quote:
 ...It doesn't correctly calculate collisions when I rotate the box. A bit of a problem for a supposed AABBxAABB test...
Did you mean 'OBBxOBB test'?

##### Share on other sites
Yeah, this one does seem convoluted. I'll look for another example.

That's what that particular code does; I was remarking that it shouldn't be doing that.

Yes, I did.

##### Share on other sites
Bit of a problem - A lot of what looks like expired links in the Collision Detection article section. Still, there's other resource.

##### Share on other sites
Ahah! I should have been doing GetMinAndMax with Axis, not Normals. It works perfectly, now.

Thanks. :)

Edit: Or no, it doesn't. I rotated the other box and it's over-detecting.

Edit: Tested and working!

[Edited by - Narf the Mouse on April 24, 2010 6:28:26 PM]

• 17
• 11
• 14
• 9
• 49
• ### Forum Statistics

• Total Topics
631393
• Total Posts
2999763
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!