c++ - 分离轴定理快把我逼疯了!

Question

我正在研究用于 2D 游戏的分离轴定理的实现。它有点管用，但只是有点。

我是这样使用的:

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

其中c1和c2都是Convex类型，定义为:

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

我为此患上了 super 多动症，请帮帮我 :)

http://u8999827.fsdata.se/sat.png

Answer 1

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

我认为错误在这里:

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

FLT_MIN is the smallest normal positive number可以用 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;

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