How do I deal with separating axes whose cross product equals 0,0,0?

Started by
3 comments, last by Spa8nky 14 years, 1 month ago
When testing all potential separating axes for an AABB OBB intersection I must use the cross product of two axes. If the cross product of the 2 axes for the 2 shapes is (0,0,0) then the intersection test fails. For example if the y axis is the same for both the AABB and the OBB is the same then the axis will equal (0,0,0)

axis = Vector3.Cross(Vector3.UnitY, b.Axis_Y);  // A1 x B1
If I then project the vertices for each shape onto this axis then the intersection test will fail. If I say that the axis is Vector3.UnitY then the collision response is incorrect, but it is still correct for all other axes. This is my axis test code:

        public static bool TestAABBOBB(Shape3D s1, Shape3D s2, ref Contact3D contact)
        {
            // [Test Encompassing Spheres]
            // • If the two spheres based on each shape's radius overlap then it is worth checking for collision 
            // • This is cheaper than testing doing a full test for collision each time
            if (!TestRadiusRadius(s1, s2))
            {
                return false;
            }

            CD_AABB a = (CD_AABB)s1;
            CD_OBB b = (CD_OBB)s2;

            // Minimum Translation Vector parameters
            float mtv_Distance = float.MaxValue;            // Set current minimum distance (max float value so next value is always less)
            Vector3 mtv_Axis = Vector3.Zero;                // Axis along which to travel with the minimum distance

            // [Axes of potential separation]
            // • Each shape must be projected on these axes to test for intersection
            //          
            // (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
            Vector3 axis = Vector3.Zero;

            // For each separating axes
            for (int i = 0; i < 15; ++i)
            {
                switch (i)
                {
                    case 0:
                        axis = Vector3.UnitX;                           // A0
                        break;
                    case 1:
                        axis = Vector3.UnitY;                           // A1
                        break;
                    case 2:
                        axis = Vector3.UnitZ;                           // A2
                        break;
                    case 3:
                        axis = b.Axis_X;                                // B0
                        break;
                    case 4:
                        axis = b.Axis_Y;                                // B1
                        break;
                    case 5:
                        axis = b.Axis_Z;                                // B2
                        break;
                    case 6:
                        axis = Vector3.Cross(Vector3.UnitX, b.Axis_X);  // A0 x B0
                        break;
                    case 7:
                        axis = Vector3.Cross(Vector3.UnitX, b.Axis_Y);  // A0 x B1
                        break;
                    case 8:
                        axis = Vector3.Cross(Vector3.UnitX, b.Axis_Z);  // A0 x B2
                        break;
                    case 9:
                        axis = Vector3.Cross(Vector3.UnitY, b.Axis_X);  // A1 x B0
                        break;
                    case 10:
                        axis = Vector3.Cross(Vector3.UnitY, b.Axis_Y);  // A1 x B1
                        break;
                    case 11:
                        axis = Vector3.Cross(Vector3.UnitY, b.Axis_Z);  // A1 x B2
                        break;
                    case 12:
                        axis = Vector3.Cross(Vector3.UnitZ, b.Axis_X);  // A2 x B0
                        break;
                    case 13:
                        axis = Vector3.Cross(Vector3.UnitZ, b.Axis_Y);  // A2 x B1
                        break;
                    case 14:
                        axis = Vector3.Cross(Vector3.UnitZ, b.Axis_Z);  // A2 x B2
                        break;
                }

                if (!IntersectThruAxis(axis, a, b, ref mtv_Distance, ref mtv_Axis))
                {
                    return false;
                }
            }

            // Calculate Minimum Translation Vector (MTV)
            Vector3 d = a.Position - b.Position;
            mtv_Axis = Vector3.Dot(d, mtv_Axis) < 0 ? -mtv_Axis : mtv_Axis;

            contact.normal = mtv_Axis;
            contact.penetration = Math.Abs(mtv_Distance) + Settings.EPSILON;

            // Objects are intersecting
            return true;
        }

How do I deal with this scenario correctly? Thank you.
Advertisement
Short answer: skip cross-product axes whose (squared) length is below a given threshold (epsilon).
That works great, thanks jyk.

Why would I be getting a different pentration depth and collision response for (0,1,0) when testing the AABB and OBB?

All other axis allow the collision response to be smooth, but the axis that they share makes the responsive shape jitter.

Am I right that I will not need to test the same axis twice, so I can also skip testing any of the OBB axes that are equal to the AABBs axes:

                    case 3:                        {                            axis = b.Axis_X;                        // B0                            if (axis == a.Axis_X)                            {                                continue;                            }                            break;                        }


Should I test the squared length of the cross product here for equality or would an == operator be sufficient?

The updated test now looks like the following:

            // For each separating axis            for (int i = 0; i < 15; ++i)            {                switch (i)                {                    case 0:                        axis = a.Axis_X;                            // A0                        break;                    case 1:                        axis = a.Axis_Y;                            // A1                        break;                    case 2:                        axis = a.Axis_Z;                            // A2                        break;                    case 3:                        {                            axis = b.Axis_X;                        // B0                            if (axis == a.Axis_X)                            {                                continue;                            }                            break;                        }                    case 4:                        {                            axis = b.Axis_Y;                        // B1                            if (axis == a.Axis_Y)                            {                                continue;                            }                            break;                        }                    case 5:                        {                            axis = b.Axis_Z;                        // B2                            if (axis == a.Axis_Z)                            {                                continue;                            }                            break;                        }                    case 6:                        axis = Vector3.Cross(a.Axis_X, b.Axis_X);   // A0 x B0                        break;                    case 7:                        axis = Vector3.Cross(a.Axis_X, b.Axis_Y);   // A0 x B1                        break;                    case 8:                        axis = Vector3.Cross(a.Axis_X, b.Axis_Z);   // A0 x B2                        break;                    case 9:                        axis = Vector3.Cross(a.Axis_Y, b.Axis_X);   // A1 x B0                        break;                    case 10:                        axis = Vector3.Cross(a.Axis_Y, b.Axis_Y);   // A1 x B1                          break;                    case 11:                        axis = Vector3.Cross(a.Axis_Y, b.Axis_Z);   // A1 x B2                        break;                    case 12:                        axis = Vector3.Cross(a.Axis_Z, b.Axis_X);   // A2 x B0                        break;                    case 13:                        axis = Vector3.Cross(a.Axis_Z, b.Axis_Y);   // A2 x B1                        break;                    case 14:                        axis = Vector3.Cross(a.Axis_Z, b.Axis_Z);   // A2 x B2                        break;                }                // For cross product axes                if (i > 5)                {                    if (axis.LengthSquared() < 0.001f)                    {                        // Do not test axes that are of 0 length                        // Accounting for floating point inaccuracies                        continue;                    }                }                if (!IntersectThruAxis(axis, a, b, ref mtv_Distance, ref mtv_Axis))                {                    return false;                }            }


Thanks again.
I wouldn't bother trying to skip duplicate axes. First of all, if the OBB is truly arbitrarily oriented, it won't be very often that a pair of axes will match up exactly, so an exact equality test probably won't do you much good. Also, it looks you're only checking to see whether a particular axis from the first box is equal to the *corresponding* axis from the second box, but what if, say, the x axis from the first box were equal to the y axis from the second box? You'd want to skip the duplicate in that case as well, but it doesn't look like your code checks for this.

I'm just guessing here, but given the extra code that's required, I don't know that checking for duplicate axes will give you any gains performance-wise.
Quote:Why would I be getting a different pentration depth and collision response for (0,1,0) when testing the AABB and OBB?
That I don't know. I'd recommend that you set up a configuration for which you can figure out the expected results by hand, and then step through the code in the debugger to try and figure out where things are going wrong.
Thank you jyk.

I'm also trying out OBB vs OBB and trying to convert one OBB to an AABB using the inverse (transpose if 3x3 orthonormal) of the rotation matrix.

This way I can use my already implemented TestAABBOBB() function.

To convert the OBB into an AABB I've done the following:

            // Compute rotation matrix expressing b in a's coordinate frame            Matrix R = Matrix.Transpose(a.Rotation) * b.Rotation;            CD_AABB c = new CD_AABB(b.Position, b.Extents.X, b.Extents.Y, b.Extents.Z);            c.Rotation = R;            return TestAABBOBB(c, b, ref contact);


However, this isn't correct. How is the AABB calculation incorrect?

This topic is closed to new replies.

Advertisement