# Implementing Separating Axis Theorem in 3D with C++/OpenGL

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;
for(int i = 0; i < 3; i++){
distS[i] = p2[i] - p1[i];   //minkowski sum
}
double dist;
NORMAL(dist, distS);

//normal1 = the X-vector
//normal1 = the Y-vector
//normal1 = 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)) > width1 + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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)) > height1 + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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)) > depth1 + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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)) > width2 + ABS((width1 * DOT(normal1, normal2))) + ABS((height1*DOT(normal1, normal2))) + ABS((depth1*DOT(normal1, normal2)))){
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)) > height2 + ABS((width1 * DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2)))){
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) << endl;
//cout << "PLANE CHECK " << depth2 + ABS((width1 * DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) << endl;
if(ABS(DOT(dist, normal2)) > depth2 + (width1 * ABS(DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2)))){
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;
double destination;
CROSS(destinationT, normal1, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((height1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((depth1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((depth2 * DOT(normal1, normal2)))){
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, normal2);
NORMAL(destination, destinationT);
if(ABS(DOT(dist, destination)) > ABS((width1 * DOT(normal1, normal2))) + ABS((height1 * DOT(normal1, normal2))) + ABS((width2 * DOT(normal1, normal2))) + ABS((height2 * DOT(normal1, normal2)))){
return false;
}
return true;


}

• 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. – JLC Dec 21 '15 at 15:28
• As they're macros, ensure that the results are sufficiently parenthesized to not accidentally have the wrong precedence. – Lars Viklund Dec 21 '15 at 15:49