Problems about oriented bounding boxes collision detection

Question

I get a question for the following code which detects if two OOBs collide by SAT. The OBBs struct is also listed below.

struct OBB {
Point c; // OBB center point
Vector u[3]; // Local x-, y-, and z-axes
Vector e;  // Positive halfwidth extents of OBB along each axis
}

int TestOBBOBB(OBB &a, OBB &b)
{
float ra, rb;
Matrix33 R, AbsR;
// Compute rotation matrix expressing b in a’s coordinate frame
for(inti=0;i<3;i++)
   for(intj=0;j<3;j++)
      R[i][j] = Dot(a.u[i], b.u[j]);
//Compute translation vector t
Vector t = b.c - a.c;
// Bring translation into a’s coordinate frame
t = Vector(Dot(t, a.u[0]), Dot(t, a.u[2]), Dot(t, a.u[2]));    

// Compute common subexpressions. Add in an epsilon term to
// counteract arithmetic errors when two edges are parallel and
// their cross product is (near) null (see text for details)
for(inti=0;i<3;i++)
    for(intj=0;j<3;j++)
        AbsR[i][j] = Abs(R[i][j]) + EPSILON;

// Test axes L=A0,L=A1,L=A2
for(inti=0;i<3;i++) {
    ra = a.e[i];
    rb = b.e[0] * AbsR[i][0] + b.e[1] * AbsR[i][1] + b.e[2] * AbsR[i][2];
    if (Abs(t[i]) > ra + rb) return 0;
}

// Test axes L=B0,L=B1,L=B2
for(inti=0;i<3;i++) {
    ra = a.e[0] * AbsR[0][i] + a.e[1] * AbsR[1][i] + a.e[2] * AbsR[2][i];
    rb = b.e[i];
    if (Abs(t[0] * R[0][i] + t[1] * R[1][i] + t[2] * R[2][i]) > ra + rb) return 0;
}

// Test axis L=A0xB0
ra = a.e[1] * AbsR[2][0] + a.e[2] * AbsR[1][0];
rb = b.e[1] * AbsR[0][2] + b.e[2] * AbsR[0][1];
if (Abs(t[2] * R[1][0] - t[1] * R[2][0]) > ra + rb) return 0;

//reset code are omitted

For the part "Test axes L=A0,L=A1,L=A2", why do we multiply each b.e[i] by the component from each axis in a's coordinate frame then add the result together? I know this part want to project the half positive extents onto each axis in a's coordinate frame, but it should do the dot product with the b.e vector and the projected axis, am I wrong? (that is b.e[0] * AbsR[0][i] + b.e[1] * AbsR[1][i] + b.e[2] * AbsR[2][i])

For the part "Test axes L=B0,L=B1,L=B2", It seems a.e vector is multiplied by each axis in a's coordinate frame, why don't transform the a.e vector into the b's coordinate frame since they are not at the same coordinate frame?

For the part "Test axis L=A0xB0", Why can we get ra and rb values by that arithmetic operation? What does Abs(t[2] * R[1][0] - t[1] * R[2][0] mean?

Answer 1

A good resource for answering your questions can be found here: http://www.stanford.edu/class/cs273/refs/obb.pdf

What you are talking about mostly is a change of 'basis' or as you say 'coordinate frame'. At the top of the function you see that there is a matrix multiply of basis A to the transpose of basis B, because in an orthonormal basis the inverse = transpose. 'Compute rotation matrix expressing b in a's coordinate frame' The entire set of equations are derived in A's basis.

The axis t is multiplied by the transpose of the relative matrix R in the 3 B's test because it was pretransformed at the top of the function into A's basis and why the A and B multiplied by AbsR are transposed (questions 1 and 2). The last 9 tests are edges of A cross product edges of B. There are lots of terms that cancel out in the derivation(question 1,2,3). I suggest you derive one A test, one B test, and one Edge Pair test so you are sure you understand what is going on.

Ps. In section 7.1 of the paper it specifically says the computation is numerically stable (the edge-on case is a non issue). The Epsilon term should be added to one side of the inequality, not the matrix elements. though it appears the effect is the same.

Essentially, your bug is in here:

t = Vector(Dot(t, a.u[0]), Dot(t, a.u[2]), Dot(t, a.u[2]));

Don't know about the rest but it looks about right.