Collisions: Separating Axis Theorem Bug

Question

The problem:

Certain inputs into my collision function don't seem to give the right result. I implement the SAT algorithm for testing the collision of a bounding box and a triangle. The input that doesn't work happens when the bounding box is in negative coordinates and 1 point of the triangle is poking into it.

Sample input:

This input does not collide, when it should!

BoundingBox bb;
// bb.value[0] is the minimum point
bb.value[0][0] = -1.0f;
bb.value[0][1] = -1.0f;
bb.value[0][2] = 0.0f;
// bb.value[1] is the maximum point
bb.value[1][0] = 0.0f;
bb.value[1][1] = 1.0f;
bb.value[1][2] = 0.0f;
ModelLocation v1 = {-0.5f, 1.0f, 0.0f};
ModelLocation v2 = {-0.4f, 1.2f, 0.0f};
ModelLocation v3 = {-0.6f, 1.2f, 0.0f};

 _______ 
 \     /
  \   /
   \ /
____x_____ <-- Would be collision.
|        |
|        |
|        |
|________|

This input collides like it should. Notice the only change is that its a different shaped triangle now. It still intersects the same point.

BoundingBox bb;
// bb.value[0] is the minimum point
bb.value[0][0] = -1.0f;
bb.value[0][1] = -1.0f;
bb.value[0][2] = 0.0f;
// bb.value[1] is the maximum point
bb.value[1][0] = 0.0f;
bb.value[1][1] = 1.0f;
bb.value[1][2] = 0.0f;
ModelLocation v1 = {-0.5f, 1.0f, 0.0f};
ModelLocation v2 = {-0.5f, 1.2f, 0.0f}; // <--- Small change here.
ModelLocation v3 = {-0.6f, 1.2f, 0.0f};

     _ _ 
    |   /
    |  /
    | /
____x_____ <-- Collision.
|        |
|        |
|        |
|________|

This input is the same as the first input except with the bounding box and the triangle are in a positive quadrant. Just moving them a little bit makes them collide.

BoundingBox bb;
// bb.value[0] is the minimum point
bb.value[0][0] = 0.0f;
bb.value[0][1] = 0.0f;
bb.value[0][2] = 0.0f;
// bb.value[1] is the maximum point
bb.value[1][0] = 1.0f;
bb.value[1][1] = 1.0f;
bb.value[1][2] = 0.0f;
ModelLocation v1 = {0.5f, 1.0f, 0.0f};
ModelLocation v2 = {0.4f, 1.2f, 0.0f};
ModelLocation v3 = {0.6f, 1.2f, 0.0f};

 _______ 
 \     /
  \   /
   \ /
____x_____ <-- Collision.
|        |
|        |
|        |
|________|

These inputs put the point of the triangle directly on the plane of the bounding box, however with the first input, stabbing it a little more with the triangle doesn't work unless you stab it a lot. For example values 1.0f through 0.7f will not collide even though it is stabbing through the plane.

Colision code:

U8 Math::collide(BoundingBox& bb, ModelLocation v1, ModelLocation v2, ModelLocation v3)
{
    // Test if inside
    if( bb.value[0][0] <= v1[0] && bb.value[0][1] <= v1[1] && bb.value[0][2] <= v1[2] &&
        bb.value[0][0] <= v2[0] && bb.value[0][1] <= v2[1] && bb.value[0][2] <= v2[2] &&
        bb.value[0][0] <= v3[0] && bb.value[0][1] <= v3[1] && bb.value[0][2] <= v3[2] &&
        bb.value[1][0] >= v1[0] && bb.value[1][1] >= v1[1] && bb.value[1][2] >= v1[2] &&
        bb.value[1][0] >= v2[0] && bb.value[1][1] >= v2[1] && bb.value[1][2] >= v2[2] &&
        bb.value[1][0] >= v3[0] && bb.value[1][1] >= v3[1] && bb.value[1][2] >= v3[2])
        return true;


    ModelLocation xAxis = {1.0f, 0.0f, 0.0f};
    ModelLocation yAxis = {0.0f, 1.0f, 0.0f};
    ModelLocation zAxis = {0.0f, 0.0f, 1.0f};

    // test the x, y, and z axes
    if(!i_collide(bb, v1, v2, v3, xAxis)) return false;
    if(!i_collide(bb, v1, v2, v3, yAxis)) return false;
    if(!i_collide(bb, v1, v2, v3, zAxis)) return false;

    // test the triangle normal
    ModelLocation axis;
    ModelLocation triedge1 = v2-v1;
    ModelLocation triedge2 = v3-v2;
    axis = triedge1.cross(triedge2).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;

    // test the 9 edge cross products
    ModelLocation triedge3 = v1-v3;

    axis = xAxis.cross(triedge1).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false; 
    axis = xAxis.cross(triedge2).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;
    axis = xAxis.cross(triedge3).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;

    axis = yAxis.cross(triedge1).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false; 
    axis = yAxis.cross(triedge2).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;
    axis = yAxis.cross(triedge3).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;

    axis = zAxis.cross(triedge1).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;  // <-- Fails test for input 1.
    axis = zAxis.cross(triedge2).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;
    axis = zAxis.cross(triedge3).normalized();
    if(!i_collide(bb, v1, v2, v3, axis)) return false;

    return true;
}

U8 Math::i_collide(BoundingBox& bb, ModelLocation& v1, ModelLocation& v2, ModelLocation& v3, ModelLocation& axis)
{
    if(i_getMin(bb, axis)>i_getMax(v1, v2, v3, axis)) return false;
    if(i_getMax(bb, axis)<i_getMin(v1, v2, v3, axis)) return false;  // <-- Fails test for input 1.
    return true;
}

F32 Math::i_getMin(BoundingBox& bb, ModelLocation& axis)
{
    F32 n1 = bb.value[0].dot(axis);
    F32 n2 = bb.value[1].dot(axis);
    if(n1<n2)
        return n1;
    return n2;
}

F32 Math::i_getMax(BoundingBox& bb, ModelLocation& axis)
{
    F32 n1 = bb.value[0].dot(axis);
    F32 n2 = bb.value[1].dot(axis);
    if(n1>n2)
        return n1;
    return n2;
}

F32 Math::i_getMin(ModelLocation& v1, ModelLocation& v2, ModelLocation& v3, ModelLocation& axis)
{
    F32 n1 = v1.dot(axis);
    F32 n2 = v2.dot(axis);
    F32 n3 = v3.dot(axis);
    F32 n = n1;
    if(n2 < n)
        n = n2;
    if(n3 < n)
        n = n3;
    return n;
}

F32 Math::i_getMax(ModelLocation& v1, ModelLocation& v2, ModelLocation& v3, ModelLocation& axis)
{
    F32 n1 = v1.dot(axis);
    F32 n2 = v2.dot(axis);
    F32 n3 = v3.dot(axis);
    F32 n = n1;
    if(n2 > n)
        n = n2;
    if(n3 > n)
        n = n3;
    return n;
}

Answer 1

Figured it out. I needed to normalize the cross products for accuracy and I needed to test against the rest of the points on the bounding box. I forgot and only tested the minimun and maximum points.

...

Wish I knew why I was downvoted. =(