PDA

View Full Version : can someone explain me this Collition detection Test function



jmanuelexe
01-24-2013, 08:28 AM
Hello everyone


I saw the function bellow in the book, real time collision detection, and I have to say I don't understand a single thing (math is not my strong subjet) and I would like to understand it.
If someone could be kind enought to explain it to me in a simple way I would apreciate it.



// Region R = { x | x = c+r*u[0]+s*u[1]+t*u[2] }, |r|<=e[0], |s|<=e[1], |t|<=e[2]
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;

//if u[3] is the regular column the estracted rotation matrix why this dot product?


// Compute rotation matrix expressing b in a’s coordinate frame
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
R[i][j] = Dot(a.u[i], b.u[j]);

Why this dot product to.
I thought to convert a point P which is in the local space of B to local space of A, I would have to multiply P by the in worldspace of B then, multiply it by the inverse of the localmatrix of A.


// 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]));

Don't know what happend here either.


// 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 (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
AbsR[i][j] = Abs(R[i][j]) + EPSILON;

// Test axes L = A0, L = A1, L = A2
for (int i = 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 (int i = 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;
}

Here I know he is extracting all the points of A and B, but I thought they need to be projected on every axis using the the dot product, is that the reason he used the dot avobe?.



// Test axis L = A0 x B0
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;
// Test axis L = A0 x B1
ra = a.e[1] * AbsR[2][1] + a.e[2] * AbsR[1][1];
rb = b.e[0] * AbsR[0][2] + b.e[2] * AbsR[0][0];
if (Abs(t[2] * R[1][1] - t[1] * R[2][1]) > ra + rb) return 0;
// Test axis L = A0 x B2
ra = a.e[1] * AbsR[2][2] + a.e[2] * AbsR[1][2];
rb = b.e[0] * AbsR[0][1] + b.e[1] * AbsR[0][0];
if (Abs(t[2] * R[1][2] - t[1] * R[2][2]) > ra + rb) return 0;
// Test axis L = A1 x B0
ra = a.e[0] * AbsR[2][0] + a.e[2] * AbsR[0][0];
rb = b.e[1] * AbsR[1][2] + b.e[2] * AbsR[1][1];

if (Abs(t[0] * R[2][0] - t[2] * R[0][0]) > ra + rb) return 0;
// Test axis L = A1 x B1
ra = a.e[0] * AbsR[2][1] + a.e[2] * AbsR[0][1];
rb = b.e[0] * AbsR[1][2] + b.e[2] * AbsR[1][0];
if (Abs(t[0] * R[2][1] - t[2] * R[0][1]) > ra + rb) return 0;
// Test axis L = A1 x B2
ra = a.e[0] * AbsR[2][2] + a.e[2] * AbsR[0][2];
rb = b.e[0] * AbsR[1][1] + b.e[1] * AbsR[1][0];
if (Abs(t[0] * R[2][2] - t[2] * R[0][2]) > ra + rb) return 0;
// Test axis L = A2 x B0
ra = a.e[0] * AbsR[1][0] + a.e[1] * AbsR[0][0];
rb = b.e[1] * AbsR[2][2] + b.e[2] * AbsR[2][1];
if (Abs(t[1] * R[0][0] - t[0] * R[1][0]) > ra + rb) return 0;
// Test axis L = A2 x B1
ra = a.e[0] * AbsR[1][1] + a.e[1] * AbsR[0][1];
rb = b.e[0] * AbsR[2][2] + b.e[2] * AbsR[2][0];
if (Abs(t[1] * R[0][1] - t[0] * R[1][1]) > ra + rb) return 0;
// Test axis L = A2 x B2
ra = a.e[0] * AbsR[1][2] + a.e[1] * AbsR[0][2];
rb = b.e[0] * AbsR[2][1] + b.e[1] * AbsR[2][0];
if (Abs(t[1] * R[0][2] - t[0] * R[1][2]) > ra + rb) return 0;
// Since no separating axis is found, the OBBs must be intersecting
return 1;
}