分离轴定理让我抓狂！

Question

我正在开发一个用于2D游戏的分离轴定理实现。它有点能用，但只是有点。

我使用它的方式如下：

bool penetration = sat(c1, c2) && sat(c2, c1);

其中和的类型为，定义如下：

class Convex
{
public:
    float tx, ty;
public:
    std::vector<Point> p;
    void translate(float x, float y) {
        tx = x;
        ty = y;
    }
};

“Point”是由“float x”和“float y”组成的结构体。

点按顺时针方向输入。

我的当前代码（忽略Qt调试信息）：

bool sat(Convex c1, Convex c2, QPainter *debug)
{
    //Debug
    QColor col[] = {QColor(255, 0, 0), QColor(0, 255, 0), QColor(0, 0, 255), QColor(0, 0, 0)};
    bool ret = true;

    int c1_faces = c1.p.size();
    int c2_faces = c2.p.size();

    //For every face in c1
    for(int i = 0; i < c1_faces; i++)
    {
        //Grab a face (face x, face y)
        float fx = c1.p[i].x - c1.p[(i + 1) % c1_faces].x;
        float fy = c1.p[i].y - c1.p[(i + 1) % c1_faces].y;

        //Create a perpendicular axis to project on (axis x, axis y)
        float ax = -fy, ay = fx;

        //Normalize the axis
        float len_v = sqrt(ax * ax + ay * ay);
        ax /= len_v;
        ay /= len_v;

        //Debug graphics (ignore)
        debug->setPen(col[i]);
        //Draw the face
        debug->drawLine(QLineF(c1.tx + c1.p[i].x, c1.ty + c1.p[i].y, c1.p[(i + 1) % c1_faces].x + c1.tx, c1.p[(i + 1) % c1_faces].y + c1.ty));
        //Draw the axis
        debug->save();
        debug->translate(c1.p[i].x, c1.p[i].y);
        debug->drawLine(QLineF(c1.tx, c1.ty, ax * 100 + c1.tx, ay * 100 + c1.ty));
        debug->drawEllipse(QPointF(ax * 100 + c1.tx, ay * 100 + c1.ty), 10, 10);
        debug->restore();

        //Carve out the min and max values
        float c1_min = FLT_MAX, c1_max = FLT_MIN;
        float c2_min = FLT_MAX, c2_max = FLT_MIN;

        //Project every point in c1 on the axis and store min and max
        for(int j = 0; j < c1_faces; j++)
        {
            float c1_proj = (ax * (c1.p[j].x + c1.tx) + ay * (c1.p[j].y + c1.ty)) / (ax * ax + ay * ay);
            c1_min = min(c1_proj, c1_min);
            c1_max = max(c1_proj, c1_max);
        }

        //Project every point in c2 on the axis and store min and max
        for(int j = 0; j < c2_faces; j++)
        {
            float c2_proj = (ax * (c2.p[j].x + c2.tx) + ay * (c2.p[j].y + c2.ty)) / (ax * ax + ay * ay);
            c2_min = min(c2_proj, c2_min);
            c2_max = max(c2_proj, c2_max);
        }

        //Return if the projections do not overlap
        if(!(c1_max >= c2_min && c1_min <= c2_max))
            ret = false; //return false;
    }
    return ret; //return true;
}

我做错了什么？它能完美地检测到碰撞，但在一个边缘上过于敏感（在我的测试中使用三角形和钻石）：

//Triangle
push_back(Point(0, -150));
push_back(Point(0, 50));
push_back(Point(-100, 100));

//Diamond
push_back(Point(0, -100));
push_back(Point(100, 0));
push_back(Point(0, 100));
push_back(Point(-100, 0));

我因此变得非常ADHD，拜托帮我一下 :) http://u8999827.fsdata.se/sat.png

- Alex

---

在您的编辑器中使用“101”按钮对代码进行格式化通常可以大大增加人们回答您问题的可能性。 - axel22

我进行了格式化，并且发布了一个问题图片的链接。 - Alex

有人能告诉我 c1.tx、c1.ty 和 c2.tx、c2.ty 是什么吗？感谢帮助。祝好。 - user427969

Answer 1

好的，我第一次说错了。看了你的失败案例图片后，很明显存在一个分离轴并且是三角形长边的法线。投影是正确的，但是你的边界不正确。

我认为错误在这里：

float c1_min = FLT_MAX, c1_max = FLT_MIN;
float c2_min = FLT_MAX, c2_max = FLT_MIN;

FLT_MIN是float类型能表示的最小正数，而不是最负数。事实上，你需要：

float c1_min = FLT_MAX, c1_max = -FLT_MAX;
float c2_min = FLT_MAX, c2_max = -FLT_MAX;

或者对于C++更好。

float c1_min = std::numeric_limits<float>::max(), c1_max = -c1_min;
float c2_min = std::numeric_limits<float>::max(), c2_max = -c2_min;

因为你可能会看到负投影到轴上。

- Adam Bowen

---

我真想亲吻你的屁股 :) 我一直以为 FLT_MIN 是浮点数可能具有的最小值？现在是时候进行游戏中的优化和采用了 :) - Alex

仅需通过调试器一次一步步执行代码，您就可以在几分钟内轻松查找到此错误，而无需患有注意力不足症:p - Emile Vrijdags