c++ - 碰撞 : Separating Axis Theorem Bug

Question

问题:

我的碰撞函数的某些输入似乎没有给出正确的结果。我实现了 SAT 算法来测试边界框和三角形的碰撞。当边界框处于负坐标并且三角形的 1 个点伸入其中时，输入不起作用。

示例输入:

这个输入没有发生冲突，但它应该发生冲突!

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

这个输入像它应该的那样发生碰撞。请注意，唯一的变化是它现在是一个不同形状的三角形。它仍然与同一点相交。

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

除了边界框和三角形位于正象限之外，此输入与第一个输入相同。稍微移动一下它们就会发生碰撞。

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

这些输入将三角形的点直接放在边界框的平面上，但是对于第一个输入，用三角形多刺一点是行不通的，除非你刺很多。例如，值 1.0f 到 0.7f 不会发生碰撞，即使它穿过平面也是如此。

碰撞代码:

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

想通了。我需要对叉积进行标准化以提高准确性，并且需要针对边界框上的其余点进行测试。我忘记了，只测试了最小值和最大值。

...

希望我知道为什么我被否决了。 =(