# Problem Implementing SAT Collision in 3D, OBB vs OBB

I am trying to implement SAT collision detection between 2 OBBs, however, I am getting a lot of false positives, can anyone help me figure out what I am doing wrong, thank you in advance.

This is my C++ code for reference, I am using GLM math library for all calculations:

uint MyRigidBody::SAT(MyRigidBody* const a_pOther)
{
//distance between two points
float offset = glm::distance(this->GetCenterGlobal(), a_pOther->GetCenterGlobal());

//corners of the first rigid body
std::vector<vector3> OBBPoints;

//back bottom left
vector3 backBottomLeft1 = m_v3MinG;
OBBPoints.emplace_back(backBottomLeft1);
//front up right
vector3 frontUpRight1 = m_v3MaxG;
OBBPoints.emplace_back(frontUpRight1);
//back bottom right point
vector3 backBottomRight1 = vector3(m_v3MaxG.x, m_v3MinG.y, m_v3MinG.z);
OBBPoints.emplace_back(backBottomRight1);
//back up right point
vector3 backUpRight1 = vector3(m_v3MaxG.x, m_v3MaxG.y, m_v3MinG.z);
OBBPoints.emplace_back(backUpRight1);
//back up left point
vector3 backUpLeft1 = vector3(m_v3MinG.x, m_v3MaxG.y, m_v3MinG.z);
OBBPoints.emplace_back(backUpLeft1);
//front bottom left
vector3 frontBottomLeft1 = vector3(m_v3MinG.x, m_v3MinG.y, m_v3MaxG.z);
OBBPoints.emplace_back(frontBottomLeft1);
//front bottom right point
vector3 frontBottomRight1 = vector3(m_v3MaxG.x, m_v3MinG.y, m_v3MaxG.z);
OBBPoints.emplace_back(frontBottomRight1);
//front up left point
vector3 frontUpLeft1 = vector3(m_v3MinG.x, m_v3MaxG.y, m_v3MaxG.z);
OBBPoints.emplace_back(frontUpLeft1);

//corners of the second rigid body
vector3 v3MinLOther = a_pOther->GetMinGlobal();
vector3 v3MaxLOther = a_pOther->GetMaxGlobal();

//corners of the first rigid body
std::vector<vector3> OtherOBBPoints;

vector3 backBottomLeft2 = v3MinLOther;
OtherOBBPoints.emplace_back(backBottomLeft2);
//front up right
vector3 frontUpRight2 = v3MaxLOther;
OtherOBBPoints.emplace_back(frontUpRight2);
//back bottom right point
vector3 backBottomRight2 = vector3(v3MaxLOther.x, v3MinLOther.y, v3MinLOther.z);
OtherOBBPoints.emplace_back(backBottomRight2);
//back up right point
vector3 backUpRight2 = vector3(v3MaxLOther.x, v3MaxLOther.y, v3MinLOther.z);
OtherOBBPoints.emplace_back(backUpRight2);
//back up left point
vector3 backUpLeft2 = vector3(v3MinLOther.x, v3MaxLOther.y, v3MinLOther.z);
OtherOBBPoints.emplace_back(backUpLeft2);
//front bottom left
vector3 frontBottomLeft2 = vector3(v3MinLOther.x, v3MinLOther.y, v3MaxLOther.z);
OtherOBBPoints.emplace_back(frontBottomLeft2);
//front bottom right point
vector3 frontBottomRight2 = vector3(v3MaxLOther.x, v3MinLOther.y, v3MaxLOther.z);
OtherOBBPoints.emplace_back(frontBottomRight2);
//front up left point
vector3 frontUpLeft2 = vector3(v3MinLOther.x, v3MaxLOther.y, v3MaxLOther.z);
OtherOBBPoints.emplace_back(frontUpLeft2);

vector3 v3OtherCenter = a_pOther->GetCenterLocal();

std::vector<vector3> normalList;

//normal of x axis of this body
vector3 A0 = vector3(GetModelMatrix()*vector4(AXIS_X,1.0f));
normalList.emplace_back(A0);
//normal of z axis of this body
vector3 A1 = vector3(GetModelMatrix()*vector4(AXIS_Y, 1.0f));
normalList.emplace_back(A1);
//normal of the y axis of this body
vector3 A2 = vector3(GetModelMatrix()*vector4(AXIS_Z, 1.0f))
normalList.emplace_back(A2);

//normal of x axis of other body
vector3 B0 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_X, 1.0f));
normalList.emplace_back(B0);
//normal of y axis of other body
vector3 B1 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_Y, 1.0f));
normalList.emplace_back(B1);
//normal of the z axis of other body
vector3 B2 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_Z, 1.0f));
normalList.emplace_back(B2);

//9 cross product axes
vector3 A0CrossB0 = glm::cross(A0, B0);
normalList.emplace_back(A0CrossB0);

vector3 A0CrossB1 = glm::cross(A0, B1);
normalList.emplace_back(A0CrossB1);

vector3 A0CrossB2 = glm::cross(A0, B2);
normalList.emplace_back(A0CrossB2);

vector3 A1CrossB0 = glm::cross(A1, B0);
normalList.emplace_back(A1CrossB0);

vector3 A1CrossB1 = glm::cross(A1, B1);
normalList.emplace_back(A1CrossB1);

vector3 A1CrossB2 = glm::cross(A1, B2);
normalList.emplace_back(A1CrossB2);

vector3 A2CrossB0 = glm::cross(A2, B0);
normalList.emplace_back(A2CrossB0);

vector3 A2CrossB1 = glm::cross(A2, B1);
normalList.emplace_back(A2CrossB1);

vector3 A2CrossB2 = glm::cross(A2, B2);
normalList.emplace_back(A2CrossB2);

int result = 0;

for (uint i = 1; i < normalList.size()+1; i++)
{
if (!IsOverlapping(normalList[i-1], OBBPoints, OtherOBBPoints,offset))
{
result = i;
break;
}
}

//there is no axis test that separates this two objects
return result;
}

bool MyRigidBody::IsOverlapping(vector3 axis, std::vector<vector3> thisPoints, std::vector<vector3> otherPoints,float offset)
{

bool overlap = false;

//vector to hold the dot products of the this rigid body's points to the given axis
std::vector<float> dots1;

//adding the dot products to a vector
for (int i = 0; i < thisPoints.size(); i++)
{
dots1.emplace_back(glm::dot(axis, thisPoints[i]));
}

//vector to hold the dot products of the other rigid body's points to the given axis
std::vector<float> dots2;

//adding the dot products of to a vector
for (int i = 0; i < otherPoints.size(); i++)
{
dots2.emplace_back(glm::dot(axis, otherPoints[i]));
}

//holding the min and max from the first set of dot products
float min1 = *std::min_element(dots1.begin(), dots1.end());
float max1 = *std::max_element(dots1.begin(), dots1.end());

//holding the min and max from the first set of dot products
float min2 = *std::min_element(dots2.begin(), dots2.end());
float max2 = *std::max_element(dots2.begin(), dots2.end());

if (min2<max1&&min1<max2)
{
overlap = true;
}

return overlap;

}


Here is an example of one false positive I get, with body B rotated -55.0 radians about the Z axis. For each axis, I list the axis vector and the min & max projection value of each object along that axis:

axis 0: (2.90000033, 1.40000010, 0.000000000)

    max1    3.31810808
max2    4.44125700
min1    2.17760968
min2    1.60608065


axis 1: (1.90000033, 2.40000010, 0.000000000)

    max1    3.76422477
max2    3.86839604
min1    2.19537735
min2    0.942635834


axis 2: (1.90000033, 1.40000010, 1.000000000)

    max1    3.45290613
max2    4.08557701
min1    1.92733908
min2    1.17654514


axis 3: (2.823576453, -0.819152057, 0.000000000)

    max1    1.77099395
max2    4.12324381
min1    0.837887466
min2    1.45174122


axis 4: (3.06915212, 0.573576450, 0.000000000)

    max1    2.76739883
max2    4.38953018
min1    1.97729456
min2    1.85467112


axis 5: (2.250000000, 0.000000000, 1.000000000)

    max1    2.20817542
max2    3.91630626
min1    1.44707108
min2    1.69250262


axis 6: (0.000000000, 0.000000000, -6.32854843)

    max1    0.374500990
max2    0.249922007
min1    -0.374500990
min2    -0.249922007


axis 7: (0.000000000, 0.000000000, -2.63344145)

    max1    0.374500990
max2    0.249922007
min1    -0.374500990
min2    -0.249922007


axis 8: (1.40000010, -2.90000033, -3.15000010)

    max1    0.0287668779
max2    1.71970975
min1    -1.70785379
min2    -0.592771530


axis 9: (0.000000000, 0.000000000, -8.33297253)

    max1    0.374500990
max2    0.249921992
min1    -0.374500990
min2    -0.249921992


axis 10: (0.000000000, 0.000000000, -6.27616978)

    max1    0.374500990
max2    0.249922007
min1    -0.374500990
min2    -0.249922007


axis 11: (2.40000010, -1.90000033, -5.40000010)

    max1    0.741111636
max2    1.95341909
min1    -0.620677114
min2    0.0398745090


axis 12: (0.819152057, 2.82357645, -5.50939655)

    max1    1.97528100
max2    1.45832372
min1    0.520946801
min2    -0.149432912


axis 13: (-0.573576450, 3.06915212, -3.20701790)

    max1    2.13298345
max2    1.00086546
min1    0.411477685
min2    -1.00041628


axis 14: (1.40000010, 0.349999666, 3.15000010)

    max1    1.47155154
max2    2.03141236
min1    0.468779355
min2    0.537880898


Thanks for sharing your axis values. It revealed that you have more parallel axes than we'd expect from two rotated boxes, suggesting that you're computing the projection axes incorrectly.

It looks like the problem is here:

//normal of x axis of this body
vector3 A0 = vector3(GetModelMatrix()*vector4(AXIS_X,1.0f));
normalList.emplace_back(A0);
//normal of z axis of this body
vector3 A1 = vector3(GetModelMatrix()*vector4(AXIS_Y, 1.0f));
normalList.emplace_back(A1);
//normal of the y axis of this body
vector3 A2 = vector3(GetModelMatrix()*vector4(AXIS_Z, 1.0f))
normalList.emplace_back(A2);

//normal of x axis of other body
vector3 B0 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_X, 1.0f));
normalList.emplace_back(B0);
//normal of y axis of other body
vector3 B1 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_Y, 1.0f));
normalList.emplace_back(B1);
//normal of the z axis of other body
vector3 B2 = vector3(a_pOther->GetModelMatrix()*vector4(AXIS_Z, 1.0f));
normalList.emplace_back(B2);


By appending a 1.0 to the end of the vector, you're telling GLM "this vector represents a position - please include the object's translation when you transform it"

But these normal vectors do not represent positions. They represent directions. So the fourth component should be zero.

(In fact, since you just want the axes of the matrix, you can read them straight out of the matrix's columns without doing a matrix multiplication at all)

It also looks like you're computing your vertex positions incorrectly. If one of the bodies is rotated, then the worldspace coordinates of its vertices are not simply interleaves of its min & max points. That will give you the vertices of its axis aligned bounding box, but since you're doing an OBB test you want the vertices of the box itself, transformed by its model matrix.

We can see the difference by drawing a simple example in 2D. Here the worldspace coordinates of the vertices we want to work with are (2, 1), (1, 4), (7, 6), (8, 3)

But if we take the worldspace min & max of all of these points to make two corners, and then form our remaining corners by interleaving values from that min & max, we get the box (1, 1) (1, 6), (8, 6), (8, 1), which as you can see sits considerably outside the real bounds of our object.

• I already tried to fix this problem by appending 0 instead of 1, which unfortunately gave the exact same results. And for your second suggestions, the GetGlobalMin and GetGlobalMax functions already multiplies the local space points by the model matrix to get the global space points. Finally, I am also getting this issue even when the second body is not rotated. Thank you – Shubham Sachdeva May 20 at 20:31
• You saw the second point about your vertex positions also being incorrect? – DMGregory May 20 at 20:32
• Even if those min and max are the min and max positions in the global space? Are you saying that I have to multiply the model matrix to the local vertices twice? – Shubham Sachdeva May 20 at 20:44
• I am doing the exact same thing for the OBB list and the OtherOBB list, its just that the other obb has a different set of vertices and model matrix. Maybe you are getting confused because I named my vector3 MinLOther, instead of MinGOther. – Shubham Sachdeva May 20 at 20:50
• I was being charitable and assuming you were deliberately working in object A's local space to skip one set of transformations. But if you're not, then yes you're right, you computed the wrong positions in BOTH cases. See the diagram for an explanation. – DMGregory May 20 at 20:57

It looks like you are computing the axes correctly, so I doubt that is your problem.

First, a couple of asides you may not be aware of:

It is possible for you to get degenerate cases in SAT, in the case of computing the cross product of two parallel axes.

In such a degenerate case, you do not attempt to compute the min/max, and just pass over the axis. This can be done easily using glm by simply checking it against itself:

vector3 A0CrossB0 = glm::cross(A0, B0);
if (A0CrossB0 == A0CrossB0)
{
normalList.emplace_back(A0CrossB0);
}


The reason this works, is that if the two input axes are parallel, the values in the output will be "NaN"(It works in glm, but don't assume it will work in other math libraries). You can check this in a debugger. Equality checks between two NaN values will always be evaluated as false.

I also noted the following:

if ( min2 < max1 && min1 < max2 )
{
overlap = true;
}


You have not addressed the possibility of "containment", where a much smaller projection can be contained within a larger one. See the image below for a number line representation of this case:

So I would change this to:

if ( min2 < max1 && min1 < max2 )
{
overlap = true;
}
if (min2 > min1 && max2 < max1 )
{
overlap = true;
}
if (min1 > min2 && max1 < max2 )
{
overlap = true;
}


But on to your question proper:

As DMGregory correctly stated in his answer, your use of the matrix is incorrect.

First I would suggest turning your model transform into a mat3:

glm::mat3 transformA = glm::mat3(A.GetModelMatrix());


This will strip out the scale and position components of the transform, making it a rotation only transform, from which you can get your principle axes for your OBB:

glm::vec3 localX = transformA[0];
glm::vec3 localY = transformA[1];
glm::vec3 localZ = transformA[2];


Then, you can compute the points using the OBB dimensions (halfwidth, halfheight, halflength), like so:

pointsA[0] = position + (localX * halfwidth) + (localY * halfheight) + (localZ * halflength);
pointsA[1] = position + (localX * halfwidth) - (localY * halfheight) + (localZ * halflength);
pointsA[2] = position + (localX * halfwidth) + (localY * halfheight) - (localZ * halflength);


and so on.

This will give you the world space coordinates for the vertices of your OBB. Repeat this for the other OBB, using it's own transform, position and dimensions, and you will get its worldspace coordinates and axes.

Computing the min/max projections in the same space along with the other changes I suggested, should prevent any false positives. (this is taken from my own working code btw).