This one is a little bit complicated. Because the OBB is not guaranteed to be aligned to the AABBs coordinate system, there is no simple way to compare the boxes coordinates with each other. The most efficient solution in this case is the "separating axis theorem" which states that for any two OBBs that do not touch, a separating axis can be found.
I don't know the exact inner workings, but the algorithm is reliable and very likely the most efficient approach to the problem. So here's the code:
/// <summary>Checks an AABB for intersection with an OBB</summary>
/// <param name="aabbExtents">Extents of the AABB</param>
/// <param name="obbTransform">Orientation and position of the OBB</param>
/// <param name="obbExtents">Extents of the OBB</param>
/// <returns>True if the two boxes are overlapping</returns>
/// <remarks>
/// <para>
/// This method is a helper method for the other intersection checks. It assumes the
/// AABB is sitting right in the center of the coordinate frame. In other words,
/// that the OBB has been transformed into the AABB's local coordinate frame.
/// </para>
/// <para>
/// Idea taken from the "Simple Intersection Tests for Games" article
/// on gamasutra by Gomez. The algorithm uses the separating axis test for
/// all 15 potential separating axes. If a separating axis can not be found,
/// the two boxes are overlapping.
/// (http://www.gamasutra.com/features/19991018/Gomez_1.htm)
/// </para>
/// </remarks>
public static bool CheckContact(
Vector3 aabbExtents, Matrix obbTransform, Vector3 obbExtents
) {
double ra, rb, t;
// A's basis vectors
for(int i = 0; i < 3; ++i) {
ra = VectorHelper.Get(ref aabbExtents, i);
rb =
obbExtents.X * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 0)) +
obbExtents.Y * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 1)) +
obbExtents.Z * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 2));
//t = Math.Abs(VectorHelper.Get(ref obbPosition, i));
t = Math.Abs(MatrixHelper.Get(ref obbTransform, 3, i));
if(t > ra + rb)
return false;
}
// B's basis vectors
for(int k = 0; k < 3; ++k) {
ra =
aabbExtents.X * Math.Abs(MatrixHelper.Get(ref obbTransform, 0, k)) +
aabbExtents.Y * Math.Abs(MatrixHelper.Get(ref obbTransform, 1, k)) +
aabbExtents.Z * Math.Abs(MatrixHelper.Get(ref obbTransform, 2, k));
rb = VectorHelper.Get(ref obbExtents, k);
t = Math.Abs(
obbTransform.M41 * MatrixHelper.Get(ref obbTransform, 0, k) +
obbTransform.M42 * MatrixHelper.Get(ref obbTransform, 1, k) +
obbTransform.M43 * MatrixHelper.Get(ref obbTransform, 2, k)
);
if(t > ra + rb)
return false;
}
// L = A0 x B0
ra =
aabbExtents.Y * Math.Abs(obbTransform.M31) +
aabbExtents.Z * Math.Abs(obbTransform.M21);
rb =
obbExtents.Y * Math.Abs(obbTransform.M13) +
obbExtents.Z * Math.Abs(obbTransform.M12);
t = Math.Abs(
obbTransform.M43 * obbTransform.M21 - obbTransform.M42 * obbTransform.M31
);
if(t > ra + rb)
return false;
// L = A0 x B1
ra =
aabbExtents.Y * Math.Abs(obbTransform.M32) +
aabbExtents.Z * Math.Abs(obbTransform.M22);
rb =
obbExtents.X * Math.Abs(obbTransform.M13) +
obbExtents.Z * Math.Abs(obbTransform.M11);
t = Math.Abs(
obbTransform.M43 * obbTransform.M22 - obbTransform.M42 * obbTransform.M32
);
if(t > ra + rb)
return false;
// L = A0 x B2
ra =
aabbExtents.Y * Math.Abs(obbTransform.M33) +
aabbExtents.Z * Math.Abs(obbTransform.M23);
rb =
obbExtents.X * Math.Abs(obbTransform.M12) +
obbExtents.Y * Math.Abs(obbTransform.M11);
t = Math.Abs(
obbTransform.M43 * obbTransform.M23 - obbTransform.M42 * obbTransform.M33
);
if(t > ra + rb)
return false;
// L = A1 x B0
ra =
aabbExtents.X * Math.Abs(obbTransform.M31) +
aabbExtents.Z * Math.Abs(obbTransform.M11);
rb =
obbExtents.Y * Math.Abs(obbTransform.M23) +
obbExtents.Z * Math.Abs(obbTransform.M22);
t = Math.Abs(
obbTransform.M41 * obbTransform.M31 - obbTransform.M43 * obbTransform.M11
);
if(t > ra + rb)
return false;
// L = A1 x B1
ra =
aabbExtents.X * Math.Abs(obbTransform.M32) +
aabbExtents.Z * Math.Abs(obbTransform.M12);
rb =
obbExtents.X * Math.Abs(obbTransform.M23) +
obbExtents.Z * Math.Abs(obbTransform.M21);
t = Math.Abs(
obbTransform.M41 * obbTransform.M32 - obbTransform.M43 * obbTransform.M12
);
if(t > ra + rb)
return false;
// L = A1 x B2
ra =
aabbExtents.X * Math.Abs(obbTransform.M33) +
aabbExtents.Z * Math.Abs(obbTransform.M13);
rb =
obbExtents.X * Math.Abs(obbTransform.M22) +
obbExtents.Y * Math.Abs(obbTransform.M21);
t = Math.Abs(
obbTransform.M41 * obbTransform.M33 - obbTransform.M43 * obbTransform.M13
);
if(t > ra + rb)
return false;
// L = A2 x B0
ra =
aabbExtents.X * Math.Abs(obbTransform.M21) +
aabbExtents.Y * Math.Abs(obbTransform.M11);
rb =
obbExtents.Y * Math.Abs(obbTransform.M33) +
obbExtents.Z * Math.Abs(obbTransform.M32);
t = Math.Abs(
obbTransform.M42 * obbTransform.M11 - obbTransform.M41 * obbTransform.M21
);
if(t > ra + rb)
return false;
// L = A2 x B1
ra =
aabbExtents.X * Math.Abs(obbTransform.M22) +
aabbExtents.Y * Math.Abs(obbTransform.M12);
rb =
obbExtents.X * Math.Abs(obbTransform.M33) +
obbExtents.Z * Math.Abs(obbTransform.M31);
t = Math.Abs(
obbTransform.M42 * obbTransform.M12 - obbTransform.M41 * obbTransform.M22
);
if(t > ra + rb)
return false;
// L = A2 x B2
ra =
aabbExtents.X * Math.Abs(obbTransform.M23) +
aabbExtents.Y * Math.Abs(obbTransform.M13);
rb =
obbExtents.X * Math.Abs(obbTransform.M32) +
obbExtents.Y * Math.Abs(obbTransform.M31);
t = Math.Abs(
obbTransform.M42 * obbTransform.M13 - obbTransform.M41 * obbTransform.M23
);
if(t > ra + rb)
return false;
// No separating axis found, the two boxes overlap
return true;
}
/// <param name="aabbExtents">Extents of the AABB</param>
/// <param name="obbTransform">Orientation and position of the OBB</param>
/// <param name="obbExtents">Extents of the OBB</param>
/// <returns>True if the two boxes are overlapping</returns>
/// <remarks>
/// <para>
/// This method is a helper method for the other intersection checks. It assumes the
/// AABB is sitting right in the center of the coordinate frame. In other words,
/// that the OBB has been transformed into the AABB's local coordinate frame.
/// </para>
/// <para>
/// Idea taken from the "Simple Intersection Tests for Games" article
/// on gamasutra by Gomez. The algorithm uses the separating axis test for
/// all 15 potential separating axes. If a separating axis can not be found,
/// the two boxes are overlapping.
/// (http://www.gamasutra.com/features/19991018/Gomez_1.htm)
/// </para>
/// </remarks>
public static bool CheckContact(
Vector3 aabbExtents, Matrix obbTransform, Vector3 obbExtents
) {
double ra, rb, t;
// A's basis vectors
for(int i = 0; i < 3; ++i) {
ra = VectorHelper.Get(ref aabbExtents, i);
rb =
obbExtents.X * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 0)) +
obbExtents.Y * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 1)) +
obbExtents.Z * Math.Abs(MatrixHelper.Get(ref obbTransform, i, 2));
//t = Math.Abs(VectorHelper.Get(ref obbPosition, i));
t = Math.Abs(MatrixHelper.Get(ref obbTransform, 3, i));
if(t > ra + rb)
return false;
}
// B's basis vectors
for(int k = 0; k < 3; ++k) {
ra =
aabbExtents.X * Math.Abs(MatrixHelper.Get(ref obbTransform, 0, k)) +
aabbExtents.Y * Math.Abs(MatrixHelper.Get(ref obbTransform, 1, k)) +
aabbExtents.Z * Math.Abs(MatrixHelper.Get(ref obbTransform, 2, k));
rb = VectorHelper.Get(ref obbExtents, k);
t = Math.Abs(
obbTransform.M41 * MatrixHelper.Get(ref obbTransform, 0, k) +
obbTransform.M42 * MatrixHelper.Get(ref obbTransform, 1, k) +
obbTransform.M43 * MatrixHelper.Get(ref obbTransform, 2, k)
);
if(t > ra + rb)
return false;
}
// L = A0 x B0
ra =
aabbExtents.Y * Math.Abs(obbTransform.M31) +
aabbExtents.Z * Math.Abs(obbTransform.M21);
rb =
obbExtents.Y * Math.Abs(obbTransform.M13) +
obbExtents.Z * Math.Abs(obbTransform.M12);
t = Math.Abs(
obbTransform.M43 * obbTransform.M21 - obbTransform.M42 * obbTransform.M31
);
if(t > ra + rb)
return false;
// L = A0 x B1
ra =
aabbExtents.Y * Math.Abs(obbTransform.M32) +
aabbExtents.Z * Math.Abs(obbTransform.M22);
rb =
obbExtents.X * Math.Abs(obbTransform.M13) +
obbExtents.Z * Math.Abs(obbTransform.M11);
t = Math.Abs(
obbTransform.M43 * obbTransform.M22 - obbTransform.M42 * obbTransform.M32
);
if(t > ra + rb)
return false;
// L = A0 x B2
ra =
aabbExtents.Y * Math.Abs(obbTransform.M33) +
aabbExtents.Z * Math.Abs(obbTransform.M23);
rb =
obbExtents.X * Math.Abs(obbTransform.M12) +
obbExtents.Y * Math.Abs(obbTransform.M11);
t = Math.Abs(
obbTransform.M43 * obbTransform.M23 - obbTransform.M42 * obbTransform.M33
);
if(t > ra + rb)
return false;
// L = A1 x B0
ra =
aabbExtents.X * Math.Abs(obbTransform.M31) +
aabbExtents.Z * Math.Abs(obbTransform.M11);
rb =
obbExtents.Y * Math.Abs(obbTransform.M23) +
obbExtents.Z * Math.Abs(obbTransform.M22);
t = Math.Abs(
obbTransform.M41 * obbTransform.M31 - obbTransform.M43 * obbTransform.M11
);
if(t > ra + rb)
return false;
// L = A1 x B1
ra =
aabbExtents.X * Math.Abs(obbTransform.M32) +
aabbExtents.Z * Math.Abs(obbTransform.M12);
rb =
obbExtents.X * Math.Abs(obbTransform.M23) +
obbExtents.Z * Math.Abs(obbTransform.M21);
t = Math.Abs(
obbTransform.M41 * obbTransform.M32 - obbTransform.M43 * obbTransform.M12
);
if(t > ra + rb)
return false;
// L = A1 x B2
ra =
aabbExtents.X * Math.Abs(obbTransform.M33) +
aabbExtents.Z * Math.Abs(obbTransform.M13);
rb =
obbExtents.X * Math.Abs(obbTransform.M22) +
obbExtents.Y * Math.Abs(obbTransform.M21);
t = Math.Abs(
obbTransform.M41 * obbTransform.M33 - obbTransform.M43 * obbTransform.M13
);
if(t > ra + rb)
return false;
// L = A2 x B0
ra =
aabbExtents.X * Math.Abs(obbTransform.M21) +
aabbExtents.Y * Math.Abs(obbTransform.M11);
rb =
obbExtents.Y * Math.Abs(obbTransform.M33) +
obbExtents.Z * Math.Abs(obbTransform.M32);
t = Math.Abs(
obbTransform.M42 * obbTransform.M11 - obbTransform.M41 * obbTransform.M21
);
if(t > ra + rb)
return false;
// L = A2 x B1
ra =
aabbExtents.X * Math.Abs(obbTransform.M22) +
aabbExtents.Y * Math.Abs(obbTransform.M12);
rb =
obbExtents.X * Math.Abs(obbTransform.M33) +
obbExtents.Z * Math.Abs(obbTransform.M31);
t = Math.Abs(
obbTransform.M42 * obbTransform.M12 - obbTransform.M41 * obbTransform.M22
);
if(t > ra + rb)
return false;
// L = A2 x B2
ra =
aabbExtents.X * Math.Abs(obbTransform.M23) +
aabbExtents.Y * Math.Abs(obbTransform.M13);
rb =
obbExtents.X * Math.Abs(obbTransform.M32) +
obbExtents.Y * Math.Abs(obbTransform.M31);
t = Math.Abs(
obbTransform.M42 * obbTransform.M13 - obbTransform.M41 * obbTransform.M23
);
if(t > ra + rb)
return false;
// No separating axis found, the two boxes overlap
return true;
}
The MatrixHelper class used in this article is just a small simple
class to alleviate the problems rooted in the XNA frameworks omission of
indexed access to the fields of a matrix :)
Here's the source:
/// <summary>Provides helper methods for working with matrices</summary>
internal static class MatrixHelper {
/// <summary>Retrieves an element of the matrix by its column and row index</summary>
/// <param name="matrix">Matrix of which to retrieve an element</param>
/// <param name="row">Index of the row from which to retrieve the element</param>
/// <param name="col">Index of the column to retrieve</param>
/// <returns>The element at the given row and column</returns>
public static float Get(ref Matrix matrix, int row, int col) {
switch(row << 4 | col) {
case 0x00: { return matrix.M11; }
case 0x01: { return matrix.M12; }
case 0x02: { return matrix.M13; }
case 0x03: { return matrix.M14; }
case 0x10: { return matrix.M21; }
case 0x11: { return matrix.M22; }
case 0x12: { return matrix.M23; }
case 0x13: { return matrix.M24; }
case 0x20: { return matrix.M31; }
case 0x21: { return matrix.M32; }
case 0x22: { return matrix.M33; }
case 0x23: { return matrix.M34; }
case 0x30: { return matrix.M41; }
case 0x31: { return matrix.M42; }
case 0x32: { return matrix.M43; }
case 0x33: { return matrix.M44; }
default: {
throw new ArgumentOutOfRangeException(
"Matrix row and/or column index out of range"
);
}
}
}
} // class MatrixHelper
internal static class MatrixHelper {
/// <summary>Retrieves an element of the matrix by its column and row index</summary>
/// <param name="matrix">Matrix of which to retrieve an element</param>
/// <param name="row">Index of the row from which to retrieve the element</param>
/// <param name="col">Index of the column to retrieve</param>
/// <returns>The element at the given row and column</returns>
public static float Get(ref Matrix matrix, int row, int col) {
switch(row << 4 | col) {
case 0x00: { return matrix.M11; }
case 0x01: { return matrix.M12; }
case 0x02: { return matrix.M13; }
case 0x03: { return matrix.M14; }
case 0x10: { return matrix.M21; }
case 0x11: { return matrix.M22; }
case 0x12: { return matrix.M23; }
case 0x13: { return matrix.M24; }
case 0x20: { return matrix.M31; }
case 0x21: { return matrix.M32; }
case 0x22: { return matrix.M33; }
case 0x23: { return matrix.M34; }
case 0x30: { return matrix.M41; }
case 0x31: { return matrix.M42; }
case 0x32: { return matrix.M43; }
case 0x33: { return matrix.M44; }
default: {
throw new ArgumentOutOfRangeException(
"Matrix row and/or column index out of range"
);
}
}
}
} // class MatrixHelper