We help IT Professionals succeed at work.

AABB OBB Collision.  Intersection is detected correctly but MTD isn't always correct.

2,291 Views
Last Modified: 2013-12-26
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.
        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;
        }

Open in new window

Comment
Watch Question

CERTIFIED EXPERT

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

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.

Author

Commented:
Sorry, I should explain.

The method I am using to find the MTD axis, is it correct?  Should I be finding the smallest penetration value?  The penetration value will always be positive if a result is returned as radius_Sum > d.

If my method of determining the MTD is correct, why would it take the wrong axis as the smallest penetration value when the AABB is overlapping one of the OBB faces?

Thanks
Hello Dr Spankenstein,  could you explain what you mean by MTD? As in -

AABB - Axis Aligned Bounding Box
OBB - Oriented Bounding Box
MTD - ?

Author

Commented:
MTD = Minimum Translation Distance.

The problem I am having is that I can't find which OBB axis the AABB is intersecting.  If I knew which axis the AABB was intersecting then I could use that axis as the surface normal.
I assume you plan to ignore any other intersections other than the minimum?

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.
Could you explain the method a little?  I'm not familiar with the objects the code is using, so its difficult to know if I'm interpreting it correctly.  Its difficult to tell if something in the code is incorrect or just syntax.

Author

Commented:
AABB - Axis Aligned Box
OBB - Oriented Bounding Box

The two bounding volumes (AABB and OBB) are know to be separating if the sum of their projected radii (onto axis L) is less than the distance between the projection of their center points.

All 15 possible separating axes are tested:

The 3 coordinates axes of both the AABB and OBB.
The remaining 9 are perpendicular to an axis from each.

If none of the axes are separating then the AABB/OBB intersect.  The problem is that my method does not find correctly which, out of all the axes being tested, is the face normal.

I have tried finding the smallest overlap using:

The sum of the following:

            float ra;                       // Projection of box A's radius onto the potential axis of separation (L) [AABB]
            float rb;                       // Projection of box B's radius onto the potential axis of separation (L) [OBB]

minus:

float d;                        // Distance between the two box's centre projections

OR

penetration = radius_Sum - d;

However, this does not return the correct axis for the normal (mtd_axis).  The direction along normal is found using mtd_Sign, indicating +1 or -1.

Hope that helps dude and thanks for helping.
That does help some, still more questions though.

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.
Is the object to find the minimum intersection or the closest distance of the non-intersecting boxes?
Apologies for making so many comments.  I'm gradually understanding the code.

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.

I think you can calculate the side of the projection with the dot product of t and mtd_Axis.  Let me know if I'm thinking along the right lines.
The line -

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?

Author

Commented:
>> The 9 other axes are perpendicular to what exactly?

(1, 0, 0) x obb.axis(0)      A0 x B0 is perpendicular to both A0 and B0 (where x = cross product)
(1, 0, 0) x obb.axis(1)      A0 x B1 is perpendicular to both A0 and B1
etc.

>> Is the object to find the minimum intersection or the closest distance of the non-intersecting
>> boxes?        

Yes, that's correct.  The minimum intersection should correspond to the surface normal, but I might be wrong with this line of thinking.

>> t is in world space, the relative translation along the x axis is not significant unless the smallest
>> penetration is along that axis.

Doesn't the following line bring t into object space:
   
 // Compute translation vector t
 Vector3 t = oBB.Centre - Centre;

t is projected onto L using the rotation matrix (R) bringing the OBB into AABBs coordinate frame.

>> 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.

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

Center + Extents = Max point on box,
Center - Extents = Min point on box; (opposite corner)

>> Apologies for making so many comments.  I'm gradually understanding the code.
No worries, thanks for taking the time out to understand it and help me.
>> Doesn't the following line bring t into object space:
>> 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)?
>> t is projected onto L using the rotation matrix (R) bringing the OBB into AABBs coordinate frame.

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.

Author

Commented:
>>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)?

Definitely.  I am probably over complicating the whole process.

Using the dot product of t and the mtd_axis results in the same problems as before.  I've attached what I changed in case I didn't follow what you suggested correctly.
if (index == 0) // A0
            {
                mtd_Axis = Axis_X;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 1) // A1
            {
                mtd_Axis = Axis_Y;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 2) // A2
            {
                mtd_Axis = Axis_Z;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 3) // B0
            {
                mtd_Axis = oBB.Axis_X;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 4) // B1
            {
                mtd_Axis = oBB.Axis_Y;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 5) // B2
            {
                mtd_Axis = oBB.Axis_Z;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 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 = (Vector3.Dot(t, mtd_Axis) < 0.0f) ? -1.0f : 1.0f;
            }

Open in new window

I wasn't expecting that to be the whole answer.  Looking at some of the other math I can see other areas where it might go wrong. For example, where that dot product is used to find mtd_Sign, it might be necessary use t from AABB to OBB or from OBB to AABB, depending on which object's planes you are projecting on to.  I'm pretty sure the dot product is the right way to do it though.

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

Author

Commented:
Thank you for an alternative approach.

>> I'm pretty sure the dot product is the right way to do it though.

Absolutely, I've now got the following cases working perfectly (see attached code):

            /* [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

However, the cross product axes are going to require a different approach:

             * (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

Using the dot product of t and the axis in question I can find the correct direction where:
mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;

>> I'm also not sure if all the uses of abs() in the earlier calculations, they might be distorting the
>> answer.

Without the abs() no collision is detected.

>> 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.

How would you suggest tackling the remaining separating axes?


if (index == 0) // A0
            {
                mtd_Axis = Axis_X;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 1) // A1
            {
                mtd_Axis = Axis_Y;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 2) // A2
            {
                mtd_Axis = Axis_Z;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 3) // B0
            {
                mtd_Axis = oBB.Axis_X;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 4) // B1
            {
                mtd_Axis = oBB.Axis_Y;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }
            if (index == 5) // B2
            {
                mtd_Axis = oBB.Axis_Z;
                mtd_Sign = (Vector3.Dot(t, mtd_Axis) > 0.0f) ? -1.0f : 1.0f;
            }

Open in new window

Good to know I'm understand well enough to make part of it work.

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)?

Author

Commented:
>>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?

I thought that too but unfortunately face normals from the axes of the AABB and the OBB are not enough.

If you take a look at the following on Page 6:

http://www.cs.umu.se/kurser/TDBD24/VT07/lectures/Lecture7.pdf

This should explain why they are needed and perhaps help as to why my collision response is not correct when dealing with these axes.

>>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)?

The extents of the OBB are not in world space, they are transformed into AABB space, hence R.

Thanks again, satsumo.
I've read the document you linked to and I'm still thinking it through.  I haven't given up yet (I will let you know if I do).

Author

Commented:
Thanks dude. I really appreciate your help.  This problem is a difficult one.
I did find a bug in the code as shown in #25892890.  However, I never found the solution to the entire problem.  As such I wouldn't object if the question was closed with a refund.
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION
Unlock the solution to this question.
Join our community and discover your potential

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.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.