Correct box-box overlap tests

Many box-box overlap tests found on the internet are wrong. This classical Gamasutra article, in particular, has a bugged box-box function.

You need to pay attention to the edge-edge case, and tweak the “fabs matrix” as in the good old RAPID library.

The code below demonstrates the bug, and how the fixed code looks like.

Pierre Terdiman

// Gamasutra code

static bool Gamasutra_OBBOBBOverlap(const Point& e0, const Point& c0, const Matrix3x3& r0, const Point& e1, const Point& c1, const Matrix3x3& r1)

{

// Translation, in parent frame

Point v = c1 - c0;

// Translation, in A's frame

Point T(v|r0[0], v|r0[1], v|r0[2]);

// B's basis with respect to A's local frame

float R[3][3];

float ra, rb, t;

// Calculate rotation matrix

for(udword i=0;i<3;i++)

{

for(udword k=0;k<3;k++)

{

R[i][k] = r0[i] | r1[k];

}

}

// A's basis vectors

for(udword i=0;i<3;i++)

{

ra = e0[i];

rb = e1[0]*fabsf(R[i][0]) + e1[1]*fabsf(R[i][1]) + e1[2]*fabsf(R[i][2]);

t = fabsf(T[i]);

if(t > ra + rb) return false;

}

// B's basis vectors

for(udword k=0;k<3;k++)

{

ra = e0[0]*fabsf(R[0][k]) + e0[1]*fabsf(R[1][k]) + e0[2]*fabsf(R[2][k]);

rb = e1[k];

t = fabsf(T[0]*R[0][k] + T[1]*R[1][k] + T[2]*R[2][k]);

if( t > ra + rb ) return false;

}

if(1)

{

//9 cross products

//L = A0 x B0

ra = e0[1]*fabsf(R[2][0]) + e0[2]*fabsf(R[1][0]);

rb = e1[1]*fabsf(R[0][2]) + e1[2]*fabsf(R[0][1]);

t = fabsf(T[2]*R[1][0] - T[1]*R[2][0]);

if(t > ra + rb) return false;

//L = A0 x B1

ra = e0[1]*fabsf(R[2][1]) + e0[2]*fabsf(R[1][1]);

rb = e1[0]*fabsf(R[0][2]) + e1[2]*fabsf(R[0][0]);

t = fabsf(T[2]*R[1][1] - T[1]*R[2][1]);

if(t > ra + rb) return false;

//L = A0 x B2

ra = e0[1]*fabsf(R[2][2]) + e0[2]*fabsf(R[1][2]);

rb = e1[0]*fabsf(R[0][1]) + e1[1]*fabsf(R[0][0]);

t = fabsf(T[2]*R[1][2] - T[1]*R[2][2]);

if(t > ra + rb) return false;

//L = A1 x B0

ra = e0[0]*fabsf(R[2][0]) + e0[2]*fabsf(R[0][0]);

rb = e1[1]*fabsf(R[1][2]) + e1[2]*fabsf(R[1][1]);

t = fabsf(T[0]*R[2][0] - T[2]*R[0][0]);

if(t > ra + rb) return false;

//L = A1 x B1

ra = e0[0]*fabsf(R[2][1]) + e0[2]*fabsf(R[0][1]);

rb = e1[0]*fabsf(R[1][2]) + e1[2]*fabsf(R[1][0]);

t = fabsf(T[0]*R[2][1] - T[2]*R[0][1]);

if(t > ra + rb) return false;

//L = A1 x B2

ra = e0[0]*fabsf(R[2][2]) + e0[2]*fabsf(R[0][2]);

rb = e1[0]*fabsf(R[1][1]) + e1[1]*fabsf(R[1][0]);

t = fabsf(T[0]*R[2][2] - T[2]*R[0][2]);

if(t > ra + rb) return false;

//L = A2 x B0

ra = e0[0]*fabsf(R[1][0]) + e0[1]*fabsf(R[0][0]);

rb = e1[1]*fabsf(R[2][2]) + e1[2]*fabsf(R[2][1]);

t = fabsf(T[1]*R[0][0] - T[0]*R[1][0]);

if(t > ra + rb) return false;

//L = A2 x B1

ra = e0[0]*fabsf(R[1][1]) + e0[1]*fabsf(R[0][1]);

rb = e1[0] *fabsf(R[2][2]) + e1[2]*fabsf(R[2][0]);

t = fabsf(T[1]*R[0][1] - T[0]*R[1][1]);

if(t > ra + rb) return false;

//L = A2 x B2

ra = e0[0]*fabsf(R[1][2]) + e0[1]*fabsf(R[0][2]);

rb = e1[0]*fabsf(R[2][1]) + e1[1]*fabsf(R[2][0]);

t = fabsf(T[1]*R[0][2] - T[0]*R[1][2]);

if(t > ra + rb) return false;

}

return true;

}

// Fixed Gamasutra code

static bool Fixed_Gamasutra_OBBOBBOverlap(const Point& e0, const Point& c0, const Matrix3x3& r0, const Point& e1, const Point& c1, const Matrix3x3& r1)

{

// Translation, in parent frame

Point v = c1 - c0;

// Translation, in A's frame

Point T(v|r0[0], v|r0[1], v|r0[2]);

// B's basis with respect to A's local frame

float R[3][3];

float FR[3][3];

float ra, rb, t;

// Calculate rotation matrix

for(udword i=0;i<3;i++)

{

for(udword k=0;k<3;k++)

{

R[i][k] = r0[i] | r1[k];

FR[i][k] = 1e-6f + fabsf(R[i][k]); // Precompute fabs matrix

}

}

// A's basis vectors

for(udword i=0;i<3;i++)

{

ra = e0[i];

rb = e1[0]*FR[i][0] + e1[1]*FR[i][1] + e1[2]*FR[i][2];

t = fabsf(T[i]);

if(t > ra + rb) return false;

}

// B's basis vectors

for(udword k=0;k<3;k++)

{

ra = e0[0]*FR[0][k] + e0[1]*FR[1][k] + e0[2]*FR[2][k];

rb = e1[k];

t = fabsf(T[0]*R[0][k] + T[1]*R[1][k] + T[2]*R[2][k]);

if( t > ra + rb ) return false;

}

if(1)

{

//9 cross products

//L = A0 x B0

ra = e0[1]*FR[2][0] + e0[2]*FR[1][0];

rb = e1[1]*FR[0][2] + e1[2]*FR[0][1];

t = fabsf(T[2]*R[1][0] - T[1]*R[2][0]);

if(t > ra + rb) return false;

//L = A0 x B1

ra = e0[1]*FR[2][1] + e0[2]*FR[1][1];

rb = e1[0]*FR[0][2] + e1[2]*FR[0][0];

t = fabsf(T[2]*R[1][1] - T[1]*R[2][1]);

if(t > ra + rb) return false;

//L = A0 x B2

ra = e0[1]*FR[2][2] + e0[2]*FR[1][2];

rb = e1[0]*FR[0][1] + e1[1]*FR[0][0];

t = fabsf(T[2]*R[1][2] - T[1]*R[2][2]);

if(t > ra + rb) return false;

//L = A1 x B0

ra = e0[0]*FR[2][0] + e0[2]*FR[0][0];

rb = e1[1]*FR[1][2] + e1[2]*FR[1][1];

t = fabsf(T[0]*R[2][0] - T[2]*R[0][0]);

if(t > ra + rb) return false;

//L = A1 x B1

ra = e0[0]*FR[2][1] + e0[2]*FR[0][1];

rb = e1[0]*FR[1][2] + e1[2]*FR[1][0];

t = fabsf(T[0]*R[2][1] - T[2]*R[0][1]);

if(t > ra + rb) return false;

//L = A1 x B2

ra = e0[0]*FR[2][2] + e0[2]*FR[0][2];

rb = e1[0]*FR[1][1] + e1[1]*FR[1][0];

t = fabsf(T[0]*R[2][2] - T[2]*R[0][2]);

if(t > ra + rb) return false;

//L = A2 x B0

ra = e0[0]*FR[1][0] + e0[1]*FR[0][0];

rb = e1[1]*FR[2][2] + e1[2]*FR[2][1];

t = fabsf(T[1]*R[0][0] - T[0]*R[1][0]);

if(t > ra + rb) return false;

//L = A2 x B1

ra = e0[0]*FR[1][1] + e0[1]*FR[0][1];

rb = e1[0] *FR[2][2] + e1[2]*FR[2][0];

t = fabsf(T[1]*R[0][1] - T[0]*R[1][1]);

if(t > ra + rb) return false;

//L = A2 x B2

ra = e0[0]*FR[1][2] + e0[1]*FR[0][2];

rb = e1[0]*FR[2][1] + e1[1]*FR[2][0];

t = fabsf(T[1]*R[0][2] - T[0]*R[1][2]);

if(t > ra + rb) return false;

}

return true;

}

static void TestEdgeEdgeBadCase()

{

bool success;

{

Matrix3x3 r0;

Matrix3x3 r1;

r0.SetCol(0, Point(1.000000e+00f, 0.000000e+00f, 0.000000e+00f));

r0.SetCol(1, Point(0.000000e+00f, 1.000000e+00f, 0.000000e+00f));

r0.SetCol(2, Point(0.000000e+00f, 0.000000e+00f, 1.000000e+00f));

r1.SetCol(0, Point(0.000000e+00f, 1.000000e+00f, 2.980232e-08f));

r1.SetCol(1, Point(2.980232e-08f, 0.000000e+00f, 1.000000e+00f));

r1.SetCol(2, Point(1.000000e+00f, 2.980232e-08f, 0.000000e+00f));

// Should return "0" (that's the bug)

success = Gamasutra_OBBOBBOverlap (Point (5.000000e-01f, 5.000000e-01f, 5.000000e-01f), Point (0.000000e+00f, 0.000000e+00f, 0.000000e+00f), r0, Point (5.000000e+02f, 5.000000e+01f, 2.000000e+02f), Point (8.792448e-27f, -3.507065e+00f, 3.621201e+02f), r1);

// Should return "1"

success = Fixed_Gamasutra_OBBOBBOverlap (Point (5.000000e-01f, 5.000000e-01f, 5.000000e-01f), Point (0.000000e+00f, 0.000000e+00f, 0.000000e+00f), r0, Point (5.000000e+02f, 5.000000e+01f, 2.000000e+02f), Point (8.792448e-27f, -3.507065e+00f, 3.621201e+02f), r1);

}

}