1
\$\begingroup\$

Using an Octree data structure provided to me by an acquaintance that gives min/max bounding box values, I've been able to write an algorithm that takes the global centre points, face normals and half the height/width/depth of each box and calculates the possibility of an overlap.

However, the code behaves erratically in testing, behaving as if the bounding box on the second object is much larger than it should be.

Is there anything obvious I'm missing?

  /*
  normal1 is relative surface normals for obj1
  normal2 is relative surface normals for obj2
  p1 is the center point of obj1 (global space)
  p2 is center point of obj2 (global space)
  width1 is half width of obj1
  width2 is half width of obj2
  depth1 is half depth of obj1
  depth2 is half depth of obj2
  height1 is half height of obj1
  height2 is half height of obj2
*/
bool IntersectionTests::AABB_AABB_Intersect(double **normal1, double **normal2, double *p1, double *p2, double width1, double depth1, double height1, double width2, double depth2, double height2){
/* Two types of possible seperating axes, the first being face normals of either object, the second being edges */
double distS[3];
for(int i = 0; i < 3; i++){
    distS[i] = p2[i] - p1[i];   //minkowski sum
}
double dist[3];
NORMAL(dist, distS);

//normal1[0] = the X-vector
//normal1[1] = the Y-vector
//normal1[2] = the Z-vector
//NOTE DEPTH, HEIGHT ETC. MUST BE HALVED

/* --- Check face normals of each bounding box --- */
//L is our axis, width is X, height is Y and depth is Z
//Dot product of local x-axis and global co-ordinate difference T
//Local Axes for AABB 1
//X
//Project Points onto axis
if(ABS(DOT(dist, normal1[0])) > width1 + ABS((width2 * DOT(normal1[0], normal2[0]))) + ABS((height2 * DOT(normal1[0], normal2[1]))) + ABS((depth2 * DOT(normal1[0], normal2[2])))){
    cout << "X NORMAL TRIGGERED" << endl;
    return false;
}
//Y
//Project Points onto axis
//if(t . x2y > heightA + (widthB * Ay DOT Bx) + (heightB * Ay DOT By) + (depthB * Ay DOT Bz) 
if(ABS(DOT(dist, normal1[1])) > height1 + ABS((width2 * DOT(normal1[1], normal2[0]))) + ABS((height2 * DOT(normal1[1], normal2[1]))) + ABS((depth2 * DOT(normal1[1], normal2[2])))){
    cout << "Y NORMAL TRIGGERED" << endl;
    return false;
}
//Z
//Project Points onto axis
//if(t . x2z > depthA + (widthB * Az DOT Bx) + (heightB * Az DOT By) + (depthB * Az DOT Bz) 
if(ABS(DOT(dist, normal1[2])) > depth1 + ABS((width2 * DOT(normal1[2], normal2[0]))) + ABS((height2 * DOT(normal1[2], normal2[1]))) + ABS((depth2 * DOT(normal1[2], normal2[2])))){
    cout << "Z NORMAL TRIGGERED" << endl;
    return false;
}
//Local Axes for AABB 2
//X
//Project Points onto axis
//if(t . y2x > widthB + (widthA * Ax DOT Bx) + (heightA * Ay DOT Bx) + (depthA * Az DOT Bx) 
if(ABS(DOT(dist, normal2[0])) > width2 + ABS((width1 * DOT(normal1[0], normal2[0]))) + ABS((height1*DOT(normal1[1], normal2[0]))) + ABS((depth1*DOT(normal1[2], normal2[0])))){
    cout << "X NORMAL 2 TRIGGERED" << endl;
    return false;
}
//Y
//Project Points onto axis
//if(t . y2y > heightB + (widthA * Ax DOT By) + (heightA * Ay DOT By) + (depthA * Az DOT By) 
if(ABS(DOT(dist, normal2[1])) > height2 + ABS((width1 * DOT(normal1[0], normal2[1]))) + ABS((height1 * DOT(normal1[1], normal2[1]))) + ABS((depth1 * DOT(normal1[2], normal2[1])))){
    cout << "Y NORMAL 2 TRIGGERED" << endl;
    return false;
}
//Z
//Project Points onto axis
//if(t . y2z > depthB + (widthA * Ax DOT Bz) + (heightA * Ay DOT Bz) + (depthA * Az DOT Bz) 
//cout << "DOT OF DIST/NORMAL2 Z " << DOT(dist, normal2[2]) << endl;
//cout << "PLANE CHECK " << depth2 + ABS((width1 * DOT(normal1[0], normal2[2]))) + ABS((height1 * DOT(normal1[1], normal2[2]))) + ABS((depth1 * DOT(normal1[2], normal2[2]))) << endl;
if(ABS(DOT(dist, normal2[2])) > depth2 + (width1 * ABS(DOT(normal1[0], normal2[2]))) + ABS((height1 * DOT(normal1[1], normal2[2]))) + ABS((depth1 * DOT(normal1[2], normal2[2])))){
    cout << "Z NORMAL 2 TRIGGERED" << endl;
    return false;
}

/* --- Cross Product of 3*3 points on each bounding box --- */
//if((t . (x2x X y2x)) > (heightA * Az DOT Bx) + (depthA *  Ay DOT Bx) + (heightB * Ax DOT Bz) + (depthB * Ax DOT By))
double destinationT[3];
double destination[3];
CROSS(destinationT, normal1[0], normal2[0]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1[2], normal2[0]))) + ABS((depth1 * DOT(normal1[1], normal2[0]))) + ABS((height2 * DOT(normal1[0], normal2[2]))) + ABS((depth2 * DOT(normal1[0], normal2[1])))){
    return false;
}
//if((t . (x2x X y2y)) > (heightA * Az DOT By) + (depthA *  Ay DOT By) + (widthB * Ax DOT Bz) + (depthB * Ax DOT Bx))
CROSS(destinationT, normal1[0], normal2[1]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1[2], normal2[1]))) + ABS((depth1 * DOT(normal1[1], normal2[1]))) + ABS((width2 * DOT(normal1[0], normal2[2]))) + ABS((depth2 * DOT(normal1[0], normal2[0])))){
    return false;
}
//if((t . (x2x X y2z)) > (heightA * Az DOT Bz) + (depthA *  Ay DOT Bz) + (widthB * Ax DOT By) + (heightB * Ax DOT Bx))
CROSS(destinationT, normal1[0], normal2[2]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1[2], normal2[2]))) + ABS((depth1 * DOT(normal1[1], normal2[2]))) + ABS((width2 * DOT(normal1[0], normal2[1]))) + ABS((height2 * DOT(normal1[0], normal2[0])))){
    return false;
}
//if((t . (x2y X y2x)) > (widthA * Az DOT Bx) + (depthA *  Ax DOT Bx) + (heightB * Ay DOT Bz) + (depthB * Ay DOT By))
CROSS(destinationT, normal1[1], normal2[0]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[2], normal2[0]))) + ABS((depth1 * DOT(normal1[0], normal2[0]))) + ABS((height2 * DOT(normal1[1], normal2[2]))) + ABS((depth2 * DOT(normal1[1], normal2[1])))){
    return false;
}
//if((t . (x2y X y2y)) > (widthA * Az DOT By) + (depthA *  Ax DOT By) + (widthB * Ay DOT Bz) + (depthB * Ay DOT Bx))
CROSS(destinationT, normal1[1], normal2[1]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[2], normal2[1]))) + ABS((depth1 * DOT(normal1[0], normal2[1]))) + ABS((width2 * DOT(normal1[1], normal2[2]))) + ABS((depth2 * DOT(normal1[1], normal2[0])))){
    return false;
}
//if((t . (x2y X y2z)) > (widthA * Az DOT Bz) + (depthA *  Ax DOT Bz) + (widthB * Ay DOT By) + (heightB * Ay DOT Bx))
CROSS(destinationT, normal1[1], normal2[2]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[2], normal2[2]))) + ABS((depth1 * DOT(normal1[0], normal2[2]))) + ABS((width2 * DOT(normal1[1], normal2[1]))) + ABS((height2 * DOT(normal1[1], normal2[0])))){
    return false;
}
//if((t . (x2z X y2x)) > (widthA * Ay DOT Bx) + (heightA *  Ax DOT Bx) + (heightB * Az DOT Bz) + (depthB * Az DOT By))
CROSS(destinationT, normal1[2], normal2[0]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[1], normal2[0]))) + ABS((height1 * DOT(normal1[0], normal2[0]))) + ABS((height2 * DOT(normal1[2], normal2[2]))) + ABS((depth2 * DOT(normal1[2], normal2[1])))){
    return false;
}
//if((t . (x2z X y2y)) > (widthA * Ay DOT By) + (heightA *  Ax DOT By) + (widthB * Az DOT Bz) + (depthB * Az DOT Bx))
CROSS(destinationT, normal1[2], normal2[1]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[1], normal2[1]))) + ABS((height1 * DOT(normal1[0], normal2[1]))) + ABS((width2 * DOT(normal1[2], normal2[2]))) + ABS((depth2 * DOT(normal1[2], normal2[0])))){
    return false;
}
//if((t . (x2z X y2z)) > (widthA * Ay DOT Bz) + (heightA *  Ax DOT Bz) + (widthB * Az DOT By) + (heightB * Az DOT Bx))
CROSS(destinationT, normal1[2], normal2[2]);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1[1], normal2[2]))) + ABS((height1 * DOT(normal1[0], normal2[2]))) + ABS((width2 * DOT(normal1[2], normal2[1]))) + ABS((height2 * DOT(normal1[2], normal2[0])))){
    return false;
}
return true;

}

\$\endgroup\$
  • \$\begingroup\$ Should probably add that ABS, DOT and CROSS are pre-processor macros for working out the absolute value, dot and cross product of a vector. \$\endgroup\$ – JLC Dec 21 '15 at 15:28
  • \$\begingroup\$ As they're macros, ensure that the results are sufficiently parenthesized to not accidentally have the wrong precedence. \$\endgroup\$ – Lars Viklund Dec 21 '15 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.