軸の定理を分けていると、ナッツが動いている！

Question

私は2Dゲームで使用するためにSeparting Axis Theoremの実装を進めています。それは作品のようなものですが、まあまあです。

私はこのようにそれを使用する：

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である）：

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

c1とc2はとして定義され、タイプConvexでありますポイントは時計回りに入力されます。

私の現在のコード（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; 
} 

私は間違って何をしているのですか？それは完全に衝突を登録するが、1つのエッジ（私のテストでは、三角形とダイヤモンドを使用して）に敏感な上にある：私はこの上で、このメガADHDを取得しています

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

Answer 1

OK、私は初めて間違っていました。失敗事例のあなたの写真を見ると、分離軸が存在し、法線（三角形の長い辺の法線）の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表現。実際には次のものが必要です。

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; 

ため

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

またはより良いあなたはおそらく軸上に負の投影を見ているので。