Sign in to follow this  
Narf the Mouse

2D OBB intersection - Code not working correctly

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

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