分离轴定理让我疯狂！

我正致力于在2D游戏中使用Separting Axis定理的实现。它有点作品，但只是一种。分离轴定理让我疯狂！

我使用这样的：

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

我在这个得到这个巨型多动症，请帮我:)

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

来源

2010-12-07 Alex

使用编辑器中的“101”按钮格式化您的文章中的代码通常会大大增加人们回答您的问题的可能性。 – axel22 2010-12-07 10:59:42

我做了格式化，并发布了一个问题图片的链接 – Alex 2010-12-07 11:20:01

好的，我第一次错了。看看你的失败情况的图片，显然存在分离轴并且是法线之一（三角形的长边的法线）。投影是正确的，但是，你的界限不是。

我认为错误是在这里：

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

，因为你可能看到的负面预测到轴。

来源

2010-12-08 08:44:37

分离轴定理让我疯狂！

回答

相关问题