Problem Implementing SAT Collision in 3D, OBB vs OBB

Question

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

DMGregory · Accepted Answer · 2019-05-20 20:55:58Z

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
– Shubham Sachdeva, Commented May 20, 2019 at 20:31
You saw the second point about your vertex positions also being incorrect? — DMGregory
– DMGregory ♦, Commented May 20, 2019 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
– Shubham Sachdeva, Commented May 20, 2019 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
– Shubham Sachdeva, Commented May 20, 2019 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
– DMGregory ♦, Commented May 20, 2019 at 20:57

Community · Accepted Answer · 2020-06-16 10:15:23Z

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).

Stack Exchange Network

Problem Implementing SAT Collision in 3D, OBB vs OBB

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Problem Implementing SAT Collision in 3D, OBB vs OBB

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions