I currently have a working intersection for an AABB and a OBB. The problem is that my method for working out the axis and sign for the MTD isn't working correctly and I am not sure why.

Currently I am testing each of the 15 potential separating axes and finding the penetration depth for each axis.

If the penetration depth is smaller than the current value for the penetration depth then the penetration depth is updated and the corresponding axis is stored.

At the the end of the test, if the two bounding volumes are intersecting then the AABB position is corrected by using the smallest penetration depth and its corresponding axis to push it out of the OBB.

Can anyone tell me why my method is not working correctly?

Thank you.

Currently I am testing each of the 15 potential separating axes and finding the penetration depth for each axis.

If the penetration depth is smaller than the current value for the penetration depth then the penetration depth is updated and the corresponding axis is stored.

At the the end of the test, if the two bounding volumes are intersecting then the AABB position is corrected by using the smallest penetration depth and its corresponding axis to push it out of the OBB.

Can anyone tell me why my method is not working correctly?

Thank you.

```
private bool TestAABBOBB(CD_OrientedBoundingBox oBB, ref Contact contact)
{
/* [Axes of potential separation]
*
* (1, 0, 0) A0
* (0, 1, 0) A1
* (0, 0, 1) A2
*
* obb.axis(0) B0
* obb.axis(1) B1
* obb.axis(2) B2
*
* (1, 0, 0) x obb.axis(0) A0 x B0
* (1, 0, 0) x obb.axis(1) A0 x B1
* (1, 0, 0) x obb.axis(2) A0 x B2
*
* (0, 1, 0) x obb.axis(0) A1 x B0
* (0, 1, 0) x obb.axis(1) A1 x B1
* (0, 1, 0) x obb.axis(2) A1 x B2
*
* (0, 0, 1) x obb.axis(0) A2 x B0
* (0, 0, 1) x obb.axis(1) A2 x B1
* (0, 0, 1) x obb.axis(2) A2 x B2
*
*/
// Two objects are separated if the sum of the radius (halfwidth) of their projections is
// less than the distance between their centre projections
Matrix AbsR = Matrix.Identity;
float d = 0; // Distance between the two box's centre projections
Vector3 mtd_Axis = Vector3.Zero; // Axis of minimum translation distance (used to calculate normal)
float mtd_Sign = 1; // Changes the direction of the mtd_Axis based on the translation vector t
float penetration = float.MaxValue; // Used to store minimum penetration value between the two boxes
float ra = 0; // Projection of box A's radius onto the potential axis of separation (L) [AABB]
float rb = 0; // Projection of box B's radius onto the potential axis of separation (L) [OBB]
float radius_Sum = 0;
// Compute rotation matrix expressing OBB in AABB's coordinate frame
// Use Matrix.Invert(oBB.Orientation_Matrix) (if orientation is NOT an orthonormal 3x3 rotation matrix)
Matrix R = Matrix.Transpose(oBB.Orientation_Matrix);
// Compute translation vector t
Vector3 t = oBB.Centre - Centre;
// Don't need to bring translation into AABB's coordinate frame as AABB has unit vectors for axes (i.e. axis aligned)
// Compute common subexpressions
// Add in an epsilon term to counteract arithmetic errors when two edges are parallel and their cross product is (near) null
AbsR.M11 = Math.Abs(R.M11) + GameConstants.EPSILON;
AbsR.M12 = Math.Abs(R.M12) + GameConstants.EPSILON;
AbsR.M13 = Math.Abs(R.M13) + GameConstants.EPSILON;
AbsR.M21 = Math.Abs(R.M21) + GameConstants.EPSILON;
AbsR.M22 = Math.Abs(R.M22) + GameConstants.EPSILON;
AbsR.M23 = Math.Abs(R.M23) + GameConstants.EPSILON;
AbsR.M31 = Math.Abs(R.M31) + GameConstants.EPSILON;
AbsR.M32 = Math.Abs(R.M32) + GameConstants.EPSILON;
AbsR.M33 = Math.Abs(R.M33) + GameConstants.EPSILON;
int index = -1; // Index of axis with smallest penetration
int axis_Index = 0; // Current axis being tested
// Test axes L = A0, L = A1, L = A2 (A's basis vectors)
for (int i = 0; i < 3; i++)
{
ra = Vector3Index.Get(ref Extents, i);
rb =
oBB.Extents.X * MatrixHelper.Get(ref AbsR, i, 0) +
oBB.Extents.Y * MatrixHelper.Get(ref AbsR, i, 1) +
oBB.Extents.Z * MatrixHelper.Get(ref AbsR, i, 2);
// Distance between box centres (translation vector)
d = Math.Abs(Vector3Index.Get(ref t, i));
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
}
// Test axes L = B0, L = B1, L = B2 (B's basis vectors)
for (int i = 0; i < 3; i++)
{
ra =
Extents.X * MatrixHelper.Get(ref AbsR, 0, i) +
Extents.Y * MatrixHelper.Get(ref AbsR, 1, i) +
Extents.Z * MatrixHelper.Get(ref AbsR, 2, i);
rb = Vector3Index.Get(ref oBB.Extents, i);
d = Math.Abs(t.X * MatrixHelper.Get(ref R, 0, i) + t.Y * MatrixHelper.Get(ref R, 1, i) + t.Z * MatrixHelper.Get(ref R, 2, i));
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
}
// Test axis L = A0 x B0
ra = Extents.Y * AbsR.M31 + Extents.Z * AbsR.M21;
rb = oBB.Extents.Y * AbsR.M13 + oBB.Extents.Z * AbsR.M12;
d = Math.Abs(t.Z * R.M21 - t.Y * R.M31);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A0 x B1
ra = Extents.Y * AbsR.M32 + Extents.Z * AbsR.M22;
rb = oBB.Extents.X * AbsR.M13 + oBB.Extents.Z * AbsR.M11;
d = Math.Abs(t.Z * R.M22 - t.Y * R.M32);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A0 x B2
ra = Extents.Y * AbsR.M33 + Extents.Z * AbsR.M23;
rb = oBB.Extents.X * AbsR.M12 + oBB.Extents.Y * AbsR.M11;
d = Math.Abs(t.Z * R.M23 - t.Y * R.M33);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A1 x B0
ra = Extents.X * AbsR.M31 + Extents.Z * AbsR.M11;
rb = oBB.Extents.Y * AbsR.M23 + oBB.Extents.Z * AbsR.M22;
d = Math.Abs(t.X * R.M31 - t.Z * R.M11);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A1 x B1
ra = Extents.X * AbsR.M32 + Extents.Z * AbsR.M12;
rb = oBB.Extents.X * AbsR.M23 + oBB.Extents.Z * AbsR.M21;
d = Math.Abs(t.X * R.M32 - t.Z * R.M12);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A1 x B2
ra = Extents.X * AbsR.M33 + Extents.Z * AbsR.M13;
rb = oBB.Extents.X * AbsR.M22 + oBB.Extents.Y * AbsR.M21;
d = Math.Abs(t.X * R.M33 - t.Z * R.M13);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A2 x B0
ra = Extents.X * AbsR.M21 + Extents.Y * AbsR.M11;
rb = oBB.Extents.Y * AbsR.M33 + oBB.Extents.Z * AbsR.M32;
d = Math.Abs(t.Y * R.M11 - t.X * R.M21);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A2 x B1
ra = Extents.X * AbsR.M22 + Extents.Y * AbsR.M12;
rb = oBB.Extents.X * AbsR.M33 + oBB.Extents.Z * AbsR.M31;
d = Math.Abs(t.Y * R.M12 - t.X * R.M22);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
axis_Index++;
// Test axis L = A2 x B2
ra = Extents.X * AbsR.M23 + Extents.Y * AbsR.M13;
rb = oBB.Extents.X * AbsR.M32 + oBB.Extents.Y * AbsR.M31;
d = Math.Abs(t.Y * R.M13 - t.X * R.M23);
radius_Sum = ra + rb;
if (radius_Sum < d)
{
return false;
}
if (radius_Sum - d < penetration)
{
penetration = radius_Sum - d;
index = axis_Index;
}
//Console.WriteLine(index);
if (index == 0) // A0
{
mtd_Axis = Axis_X;
mtd_Sign = (t.X < 0.0f) ? -1.0f : 1.0f;
}
if (index == 1) // A1
{
mtd_Axis = Axis_Y;
mtd_Sign = (t.Y < 0.0f) ? -1.0f : 1.0f;
}
if (index == 2) // A2
{
mtd_Axis = Axis_Z;
mtd_Sign = (t.Z < 0.0f) ? -1.0f : 1.0f;
}
if (index == 3) // B0
{
mtd_Axis = oBB.Axis_X;
mtd_Sign = (t.X < 0.0f) ? -1.0f : 1.0f;
}
if (index == 4) // B1
{
mtd_Axis = oBB.Axis_Y;
mtd_Sign = (t.Y < 0.0f) ? -1.0f : 1.0f;
}
if (index == 5) // B2
{
mtd_Axis = oBB.Axis_Z;
mtd_Sign = (t.Z < 0.0f) ? -1.0f : 1.0f;
}
if (index == 6) // A0 x B0
{
mtd_Axis = Vector3.Cross(Axis_X, oBB.Axis_X);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_X;
}
mtd_Sign = (t.X < 0.0f) ? -1.0f : 1.0f;
}
if (index == 7) // A0 x B1
{
mtd_Axis = Vector3.Cross(Axis_X, oBB.Axis_Y);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_X;
}
mtd_Sign = (t.X < 0.0f) ? -1.0f : 1.0f;
}
if (index == 8) // A0 x B2
{
mtd_Axis = Vector3.Cross(Axis_X, oBB.Axis_Z);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_X;
}
mtd_Sign = (t.X < 0.0f) ? -1.0f : 1.0f;
}
if (index == 9) // A1 x B0
{
mtd_Axis = Vector3.Cross(Axis_Y, oBB.Axis_X);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Y;
}
mtd_Sign = (t.Y < 0.0f) ? -1.0f : 1.0f;
}
if (index == 10) // A1 x B1
{
mtd_Axis = Vector3.Cross(Axis_Y, oBB.Axis_Y);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Y;
}
mtd_Sign = (t.Y < 0.0f) ? -1.0f : 1.0f;
}
if (index == 11) // A1 x B2
{
mtd_Axis = Vector3.Cross(Axis_Y, oBB.Axis_Z);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Y;
}
mtd_Sign = (t.Y < 0.0f) ? -1.0f : 1.0f;
}
if (index == 12) // A2 x B0
{
mtd_Axis = Vector3.Cross(Axis_Z, oBB.Axis_X);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Z;
}
mtd_Sign = (t.Z < 0.0f) ? -1.0f : 1.0f;
}
if (index == 13) // A2 x B1
{
mtd_Axis = Vector3.Cross(Axis_Z, oBB.Axis_Y);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Z;
}
mtd_Sign = (t.Z < 0.0f) ? -1.0f : 1.0f;
}
if (index == 14) // A2 x B2
{
mtd_Axis = Vector3.Cross(Axis_Z, oBB.Axis_Z);
if (mtd_Axis == Vector3.Zero)
{
mtd_Axis = Axis_Z;
}
mtd_Sign = (t.Z < 0.0f) ? -1.0f : 1.0f;
}
// Since no separating axis has been found, the OBBs must be intersecting
contact.normal = mtd_Axis * mtd_Sign;
contact.penetration = penetration;
return true;
}
```

How exactly do you want us to help you?

Why dont you start validating whether it works or not by visualising some test-cases and see if everything works as expected.

AABB - Axis Aligned Bounding Box

OBB - Oriented Bounding Box

MTD - ?

Like with the ray-box intersection problem, is there any reason why you can't intersect the OBB with the AABB? So that the answer is in AA space.

The 9 other axes are perpendicular to what exactly? Perpendicular to an axis can define many planes.

The code for dealing with ra, rb, and d, makes sense, I can't imagine that part is wrong. The problem is likely to be about the axes and projection. I'm wondering if the method may not be able to produce the answer you want. I'm thinking that by projection, you lose the distinction between front and back planes. The projection from the front would be the same as the projection from the back. The distances you use would be the same, how could it know which is nearer?

That said, I might be missing something in the code. Any chance you could write the code with a function you call for each projection? Simply to help with this question, I understand you might want to avoid the overhead normally.

Near the end of the function, you're using the sign of t.x to decide which side of the projecting plane to use. I think for this to work, t needs to be in the space of the projection. t is in world space, the relative translation along the x axis is not significant unless the smallest penetration is along that axis.

ra = Vector3Index.Get(ref Extents, i)

Doesn't appear to get the radius of the AABB in axis i, it gets the extent. If you were to draw the AABB onto a plane and draw a circle of radius ra, it would touch the Extents of the box at the sides. The corners of the AABB would be outside of the circle.

The two boxes could intersect at the corners and this test would say they were not intersecting.

Is Extents the distance from the center of the box, or the entire dimension of the box?

>> Vector3 t = oBB.Centre - Centre;

From what I understand that calculates the world space translation from OBB center to AABB center. Putting the translation into AABB space (given that the axis of AABB are same as the world).

However, for the sign of t.x to work, it needs to be in projection space. I don't think I explained that properly before. Specifically t would need to be transformed for each projection so that its y and z are measured along the projection plane. That way t.x would tell you wether the OBB was in front or behind.

However, you would get the same result from the dot product I mentioned.

>>>> Any chance you could write the code with a function you call for each projection?

>> Each function would have to be different as the values for t and R change each time.

Could you not pass t and R as parameters?

Would you be interested in a different method of doing this that I think is simpler, more accurate and faster (at least as far as I can be certain)?

That happens when you are calculating d but not when you are getting mtd_Sign from t.z, though I haven't got an exact grasp of the math in the code yet.

I'm also not sure if all the uses of abs() in the earlier calculations, they might be distorting the answer. Also the extents vs bounding radius problem I mentioned before. I've drawn a diagram to illustrate that. The dashed red circle is the one the code uses, it's radius is the extent of the box. As you can see, it dosen't include the corners of the box. The solid red circle is the bounding circle of the box, somewhat bigger than its extents.

The other method I mentioned is a bit easier to understand. For any two boxes to be intersecting (whether OBB or AABB), at least one point of one of the boxes must be inside the other box. It's possible for them to intersect with no points from box A in box B, but then there would have to be points from box B in box A.

So you calculate a matrix that transfrorms box B into box A's space (the inverse of box A's transform). You transform the points of box B and test them against box A to see which is nearest to one to its extent, that gives the mtd.

Specifically, if the transformed position of a point of B is inside A, you would check its x against the width of A. The point of B which is most inside A's width is the minmum X penetration. You do the same with Y and X and choose which face of A to push it toward.

If the points of B aren't inside A, then check A against B. If no points are inside, the boxes do not intesect. This is not a perfect solution, it's end result would have similar characteristics to the method you're using now.

bounding-circle.gif

I'm don't understand what the purpose of those cross product axes is. My understanding of the method would say that the axes of the AABB and the OBB would be enough. Could you explain what they are for?

When you say they are a problem, do you mean that mtd_Axis would not be perpendicular to any face of either object? The dot product would work with any mtd_axis and t.

>>>> Also the extents vs bounding radius problem I mentioned before.

>>I am yet to encounter this problem with my AABB/AABB collision detection which also uses box extents.

AABB to AABB is a much simpler problem, as you know, a matter of testing numerical ranges. The code will not be the same. Perhaps the exents part of the code is more complex than it appears, still I would have expected that error, does it use the world space extents of the OBB (after rotation)?

This one is on us!

(Get your first solution completely free - no credit card required)

UNLOCK SOLUTION
Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.