# MTD from overlap with an OBB. I'm not sure I understand the following.

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

## Recommended Posts

Hi guys, Here I have a test for the minimum translation distance for an AABB and an OBB, but the problem it is not producing correct results. I understand that I have to test the extents but I am not sure which projected axes to use.
        private void GetMTD(int axis, CD_OrientedBoundingBox oBB, ref float mtd_Val, ref int mtd_axis)
{
// The absolute intersect intervals on the 'left' and 'right'
float d0 = 0.0f;
float d1 = 0.0f;

Vector3 oBB_Max = oBB.MaxPoint;
Vector3 oBB_Min = oBB.MinPoint;
Vector3 aABB_Max = MaxPoint;
Vector3 aABB_Min = MinPoint;

d0 = Vector3Index.Get(ref oBB_Max, axis) - Vector3Index.Get(ref aABB_Min, axis);
d1 = Vector3Index.Get(ref aABB_Min, axis) - Vector3Index.Get(ref oBB_Min, axis);

float d = (d0 < d1) ? -d0 : d1;

// The signed minimum intersection between all three axes
if (Math.Abs(d) < Math.Abs(mtd_Val))
{
mtd_Val = d;
mtd_axis = axis;
}
}


The min/max point for OBB returns the extents in world space coordinates which is where I believe I am going wrong but just using local space coordinates doesn't work either. Can anyone tell me where I have made my mistakes? Thank you.

##### Share on other sites
Quote:
  Vector3 oBB_Max = oBB.MaxPoint; Vector3 oBB_Min = oBB.MinPoint; Vector3 aABB_Max = MaxPoint; Vector3 aABB_Min = MinPoint; d0 = Vector3Index.Get(ref oBB_Max, axis) - Vector3Index.Get(ref aABB_Min, axis); d1 = Vector3Index.Get(ref aABB_Min, axis) - Vector3Index.Get(ref oBB_Min, axis);

This looks wrong to me.

The projected interval of an obb along an axis is NOT the dot product of the min and max points of the obb box (or aabb box for that matter).

Also, the
if (Math.Abs(d) < Math.Abs(mtd_Val))

is valid only if the axis is normalised. Else the projected interval (do and d1) will be scaled by the axis length.

##### Share on other sites
Quote:
 The projected interval of an obb along an axis is NOT the dot product of the min and max points of the obb box (or aabb box for that matter).

I haven't used a dot product here.

oBB.MaxPoint returns the Extents transformed by the world transform (rotation and translation but not scale)

oBB.MinPoint returns -Extents transformed by the world transform.

Quote:
 Also, the if (Math.Abs(d) < Math.Abs(mtd_Val))is valid only if the axis is normalised. Else the projected interval (do and d1) will be scaled by the axis length.

Can you please explain how this should be changed if I am to use non normalised axes?

Thanks again oliii.

##### Share on other sites
ok :)

assuming your interval calculations are correct and all, you can work with the length square of the mtd instead of the length. That saves you several square roots. The length of the axis square, is the axis dot product itself.

YOu will loose the sign of the mtd value as well, so you need to keep a record of it.

Quote:
 private void GetMTD(int axis, CD_OrientedBoundingBox oBB, ref float mtd_ValSquared, ref float mtd_Sign, ref int mtd_axis){ //... //... float axis_legnthSquared = //??? the length of your axis, squared. float d2 = d * d / axis_legnthSquared; if(d2 < mtd_ValSquared) { mtd_ValSquared = d2; mtd_Axis = axis; mtd_Sign = (d < 0.0f)? -1.0f : 1.0f: }}

##### Share on other sites
Thanks for the info oliii but that leaves me with one more question:

How do I find the value of the axis_LengthSquared?

If I have the two axes, one from AABB and one from OBB then isn't the axis_LengthSquared equal to the distance sqaured between the two.

I'm sorry, but I am little confused?

##### Share on other sites
well I'm confused too. Why do you have two axes per test. It just doesn't makes sense. What does the axis integer represents.

The axes of separation are

(1, 0, 0)
(0, 1, 0)
(0, 0, 1)
obb.axis(0)
obb.axis(1)
obb.axis(2)

obb.axis(0) x (1, 0, 0)
obb.axis(0) x (0, 1, 0)
obb.axis(0) x (0, 0, 1)

obb.axis(1) x (1, 0, 0)
obb.axis(1) x (0, 1, 0)
obb.axis(1) x (0, 0, 1)

obb.axis(2) x (1, 0, 0)
obb.axis(2) x (0, 1, 0)
obb.axis(2) x (0, 0, 1)

Each of these is a vector. and each vector has a length.

##### Share on other sites
So am I right in thinking that in each case rb:

            // Test axis L = A0            ra = Extents.X;            rb = aABB.Extents.X * AbsR.M11 + aABB.Extents.Y * AbsR.M12 + aABB.Extents.Z * AbsR.M13;            // Test axis L = A1            ra = Extents.Y;            rb = aABB.Extents.X * AbsR.M21 + aABB.Extents.Y * AbsR.M22 + aABB.Extents.Z * AbsR.M23;            // Test axis L = A2            ra = Extents.Z;            rb = aABB.Extents.X * AbsR.M31 + aABB.Extents.Y * AbsR.M32 + aABB.Extents.Z * AbsR.M33;

is equal to:

(1, 0, 0) = A0
(0, 1, 0) = A1
(0, 0, 1) = A2

In which case is rb (or is it ra + rb) the non normalised length, or is that not the case?

##### Share on other sites
ra is the projection of box A onto the axis (first case, the axis is (1, 0, 0)).
rb is the projection of box B onto the axis.

The axis is (1, 0, 0). The length of the axis is 1 (it is normalised in the that case).

Looks like you are trying to run before you walk. The algorithm you are using looks like the optimised version of the algorithm.

##### Share on other sites
Thank you for helping me understand this further olii!

I now know that I have the following potentially separating axes to test:

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

and I can use a rule of SAT:

Two objects are separated if the sum of radius (halfwidth) of their projections (onto L) is less than the distance between their centre projections

so,

            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 d = 0;            // Distance between their centre projections

Could you tell me if the following is correct please:

If I wanted to find the penetration depth between the two intersecting bounding volumes, could I use the following:

float penetration_Depth = (ra + rb) - d;

Should I then return the smallest penetration depth from testing all axes if they are intersecting?

Thanks again.

EDIT: So here I have my first attempt at obtaining the correct axis and penetration from the intersection test.

I've use an axis_Index variable to see which axis I am currently testing and I set the index to the axis_Index should the penetration be the smallest so far.

At the end of the test, the index denotes which axis I should use for the mtd_axis and the penetration depth at that axis denotes the mtd scalar.

The translation vector t is used to determine the sign based on the axis, so if the axis of the AABB is X then I check the value of t.X, does that sound correct?

Can you tell me if this sensible or have I got the wrong end of the SAT stick?

        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            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;            float d = 0;            // Distance between their centre projections            Matrix AbsR = Matrix.Identity;            float penetration = float.MaxValue;            Vector3 mtd_Axis = Vector3.Zero;            float mtd_Sign = 1;     // Changes the direction of the mtd_Axis based on the translation vector t            // Compute rotation matrix expressing OBB in AABB's coordinate frame            Matrix R = Matrix.Transpose(oBB.Orientation_Matrix);            // OR Matrix.Invert(oBB.Orientation_Matrix) (if orientation is NOT an orthonormal 3x3 rotation matrix)            // Compute translation vector t            Vector3 t = Centre - oBB.Centre;            // Bring translation into AABB's coordinate frame (NOT NEEDED as AABB has unit vectors for axes, i.e. axis aligned)            //t = new Vector3(            //    Vector3.Dot(t, Vector3.UnitX),            //    Vector3.Dot(t, Vector3.UnitY),            //    Vector3.Dot(t, Vector3.UnitZ)            //    );            // 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 betwen 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;        }

[Edited by - Spa8nky on November 5, 2009 8:07:49 AM]

##### Share on other sites
Hey Spa8nky

When I used your code, it was not working very well, so I modified it a bit.

At first it always returned axis 7 (A0 x B0) as the axis with min depth, so I replaced

            if (radius_Sum < d)            {                return false;            }            if (radius_Sum - d < penetration)            {                penetration = radius_Sum - d;                index = axis_Index;            }

with

            temp = radius_Sum - d;            if (temp < 0)            {                return false;            }            if (temp > 0.000001f && temp < penetration)            {                penetration = temp;                index = axis_Index;            }

It still wasn't OK, so I replaced

                if (mtd_Axis == Vector3.Zero)                {                    mtd_Axis = Axis_X;                }                // etc...

with

                if (mtd_Axis.Length() < 0.000001f)                {                    mtd_Axis = Axis_X;                }                // etc...

At the end I combined it with code from other forums and this is the working end result:

public bool Intersects(OrientedBoundingBox other){	Matrix otherAxis = other.rotation * this.InverseRotation;	// transposne matrix and get axis from rows -> get axis from matrix columns :)	Vector3 otherAxisX = new Vector3(otherAxis.M11, otherAxis.M21, otherAxis.M31);	Vector3 otherAxisY = new Vector3(otherAxis.M12, otherAxis.M22, otherAxis.M32);	Vector3 otherAxisZ = new Vector3(otherAxis.M13, otherAxis.M23, otherAxis.M33);	Vector3 distance = Vector3.Transform(other.center - this.center, this.inverseRotation);	float projectedDistance;	float projectedBounds;	float[] penetration = new float[15];	//15 tests	//1 (Ra)x	projectedDistance = (float)Math.Abs(distance.X);	projectedBounds = (this.bounds.X + 		other.bounds.X * (float)Math.Abs(otherAxisX.X) + other.bounds.Y * (float)Math.Abs(otherAxisX.Y) + other.bounds.Z * (float)Math.Abs(otherAxisX.Z));	penetration[0] = projectedBounds - projectedDistance;	if (penetration[0] < 0.0f)	{		return false;	}	//2 (Ra)y	projectedDistance = (float)Math.Abs(distance.Y);	projectedBounds = (this.bounds.Y + 		other.bounds.X * (float)Math.Abs(otherAxisY.X) + other.bounds.Y * (float)Math.Abs(otherAxisY.Y) + other.bounds.Z * (float)Math.Abs(otherAxisY.Z));	penetration[1] = projectedBounds - projectedDistance;	if (penetration[1] < 0.0f)	{		return false;	}	//3 (Ra)z	projectedDistance = (float)Math.Abs(distance.Z);	projectedBounds = (this.bounds.Z + 		other.bounds.X * (float)Math.Abs(otherAxisZ.X) + other.bounds.Y * (float)Math.Abs(otherAxisZ.Y) + other.bounds.Z * (float)Math.Abs(otherAxisZ.Z));	penetration[2] = projectedBounds - projectedDistance;	if (penetration[2] < 0.0f)	{		return false;	}	//4 (Rb)x	projectedDistance = (float)Math.Abs(distance.X * otherAxisX.X + distance.Y * otherAxisY.X + distance.Z * otherAxisZ.X);	projectedBounds = (other.bounds.X + 		this.bounds.X * (float)Math.Abs(otherAxisX.X) + this.bounds.Y * (float)Math.Abs(otherAxisY.X) + this.bounds.Z * (float)Math.Abs(otherAxisZ.X));	penetration[3] = projectedBounds - projectedDistance;	if (penetration[3] < 0.0f)	{		return false;	}	//5 (Rb)y	projectedDistance = (float)Math.Abs(distance.X * otherAxisX.Y + distance.Y * otherAxisY.Y + distance.Z * otherAxisZ.Y);	projectedBounds = (other.bounds.Y + 		this.bounds.X * (float)Math.Abs(otherAxisX.Y) + this.bounds.Y * (float)Math.Abs(otherAxisY.Y) + this.bounds.Z * (float)Math.Abs(otherAxisZ.Y));	penetration[4] = projectedBounds - projectedDistance;	if (penetration[4] < 0.0f)	{		return false;	}	//6 (Rb)z	projectedDistance = (float)Math.Abs(distance.X * otherAxisX.Z + distance.Y * otherAxisY.Z + distance.Z * otherAxisZ.Z);	projectedBounds = (other.bounds.Z + 		this.bounds.X * (float)Math.Abs(otherAxisX.Z) + this.bounds.Y * (float)Math.Abs(otherAxisY.Z) + this.bounds.Z * (float)Math.Abs(otherAxisZ.Z));	penetration[5] = projectedBounds - projectedDistance;	if (penetration[5] < 0.0f)	{		return false;	}	//7 (Ra)x X (Rb)x	projectedDistance = (float)Math.Abs(distance.Z * otherAxisY.X - distance.Y * otherAxisZ.X);	projectedBounds = (this.bounds.Y * (float)Math.Abs(otherAxisZ.X) + this.bounds.Z * (float)Math.Abs(otherAxisY.X) + 		other.bounds.Y * (float)Math.Abs(otherAxisX.Z) + other.bounds.Z * (float)Math.Abs(otherAxisX.Y));	penetration[6] = projectedBounds - projectedDistance;	if (penetration[6] < 0.0f)	{		return false;	}	//8 (Ra)x X (Rb)y	projectedDistance = (float)Math.Abs(distance.Z * otherAxisY.Y - distance.Y * otherAxisZ.Y);	projectedBounds = (this.bounds.Y * (float)Math.Abs(otherAxisZ.Y) + this.bounds.Z * (float)Math.Abs(otherAxisY.Y) + 		other.bounds.X * (float)Math.Abs(otherAxisX.Z) + other.bounds.Z * (float)Math.Abs(otherAxisX.X));	penetration[7] = projectedBounds - projectedDistance;	if (penetration[7] < 0.0f)	{		return false;	}	//9 (Ra)x X (Rb)z	projectedDistance = (float)Math.Abs(distance.Z * otherAxisY.Z - distance.Y * otherAxisZ.Z);	projectedBounds = (this.bounds.Y * (float)Math.Abs(otherAxisZ.Z) + this.bounds.Z * (float)Math.Abs(otherAxisY.Z) + 		other.bounds.X * (float)Math.Abs(otherAxisX.Y) + other.bounds.Y * (float)Math.Abs(otherAxisX.X));	penetration[8] = projectedBounds - projectedDistance;	if (penetration[8] < 0.0f)	{		return false;	}	//10 (Ra)y X (Rb)x	projectedDistance = (float)Math.Abs(distance.X * otherAxisZ.X - distance.Z * otherAxisX.X);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisZ.X) + this.bounds.Z * (float)Math.Abs(otherAxisX.X) + 		other.bounds.Y * (float)Math.Abs(otherAxisY.Z) + other.bounds.Z * (float)Math.Abs(otherAxisY.Y));	penetration[9] = projectedBounds - projectedDistance;	if (penetration[9] < 0.0f)	{		return false;	}	//11 (Ra)y X (Rb)y	projectedDistance = (float)Math.Abs(distance.X * otherAxisZ.Y - distance.Z * otherAxisX.Y);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisZ.Y) + this.bounds.Z * (float)Math.Abs(otherAxisX.Y) + 		other.bounds.X * (float)Math.Abs(otherAxisY.Z) + other.bounds.Z * (float)Math.Abs(otherAxisY.X));	penetration[10] = projectedBounds - projectedDistance;	if (penetration[10] < 0.0f)	{		return false;	}	//12 (Ra)y X (Rb)z	projectedDistance = (float)Math.Abs(distance.X * otherAxisZ.Z - distance.Z * otherAxisX.Z);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisZ.Z) + this.bounds.Z * (float)Math.Abs(otherAxisX.Z) + 		other.bounds.X * (float)Math.Abs(otherAxisY.Y) + other.bounds.Y * (float)Math.Abs(otherAxisY.X));	penetration[11] = projectedBounds - projectedDistance;	if (penetration[11] < 0.0f)	{		return false;	}	//13 (Ra)z X (Rb)x	projectedDistance = (float)Math.Abs(distance.Y * otherAxisX.X - distance.X * otherAxisY.X);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisY.X) + this.bounds.Y * (float)Math.Abs(otherAxisX.X) + 		other.bounds.Y * (float)Math.Abs(otherAxisZ.Z) + other.bounds.Z * (float)Math.Abs(otherAxisZ.Y));	penetration[12] = projectedBounds - projectedDistance;	if (penetration[12] < 0.0f)	{		return false;	}	//14 (Ra)z X (Rb)y	projectedDistance = (float)Math.Abs(distance.Y * otherAxisX.Y - distance.X * otherAxisY.Y);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisY.Y) + this.bounds.Y * (float)Math.Abs(otherAxisX.Y) + 		other.bounds.X * (float)Math.Abs(otherAxisZ.Z) + other.bounds.Z * (float)Math.Abs(otherAxisZ.X));	penetration[13] = projectedBounds - projectedDistance;	if (penetration[13] < 0.0f)	{		return false;	}	//15 (Ra)z X (Rb)z	projectedDistance = (float)Math.Abs(distance.Y * otherAxisX.Z - distance.X * otherAxisY.Z);	projectedBounds = (this.bounds.X * (float)Math.Abs(otherAxisY.Z) + this.bounds.Y * (float)Math.Abs(otherAxisX.Z) + 		other.bounds.X * (float)Math.Abs(otherAxisZ.Y) + other.bounds.Y * (float)Math.Abs(otherAxisZ.X));	penetration[14] = projectedBounds - projectedDistance;	if (penetration[14] < 0.0f)	{		return false;	}	float minPenetration = float.MaxValue;	Vector3 normal = Vector3.Zero;	Vector3[] axis = new Vector3[15];	axis[0] = this.AxisX;	axis[1] = this.AxisY;	axis[2] = this.AxisZ;	axis[3] = other.AxisX;	axis[4] = other.AxisY;	axis[5] = other.AxisZ;	axis[6] = Vector3.Cross(this.AxisX, other.AxisX);	axis[7] = Vector3.Cross(this.AxisX, other.AxisY);	axis[8] = Vector3.Cross(this.AxisX, other.AxisZ);	axis[9] = Vector3.Cross(this.AxisY, other.AxisX);	axis[10] = Vector3.Cross(this.AxisY, other.AxisY);	axis[11] = Vector3.Cross(this.AxisY, other.AxisZ);	axis[12] = Vector3.Cross(this.AxisZ, other.AxisX);	axis[13] = Vector3.Cross(this.AxisZ, other.AxisY);	axis[14] = Vector3.Cross(this.AxisZ, other.AxisZ);	for(int i = 0; i < 15; ++i)	{		float length = axis.Length();		if (length < 1.0e-6f)			continue;		// normalize the penetration depth, axes are not normalized		penetration /= length;		if (penetration < minPenetration)		{			minPenetration = penetration;			normal = axis / length;			this._axisIndex = i;		}	}	if (Vector3.Dot(other.center - this.center, normal) > 0.0f)		normal *= -1.0f;	this._minPenetration = minPenetration;	this._collisionNormal = normal;	other._minPenetration = minPenetration;	other._collisionNormal = normal;	return true;}

Thanks to Ziggyware and Oliii :)

EDIT: The code looks scary only because I coded it all into one function, to minimize the number of function calls. It would look nicer with more functions, but each additional function call slows down the process :)

[Edited by - JinJi on November 20, 2009 8:06:51 PM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 9
• 15
• 14
• ### Forum Statistics

• Total Topics
634070
• Total Posts
3015333
×