¡Separar el teorema del eje me está volviendo loco!

Question

estoy trabajando en una implementación del Teorema del eje Separting para usar en juegos 2D. Funciona, pero funciona.

I utilizar de esta manera:

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

Dónde c1 y c2 son de tipo Convex, definido como:

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

(Point es una estructura de float x, float y)

Los puntos se escriben en el sentido de las agujas del reloj.

Mi código actual (ignorar Qt depuración):

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

¿Qué estoy haciendo mal? Se registra choque perfectamente, pero es más sensible en un borde (en mi prueba utilizando un triángulo y un diamante):

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

estoy recibiendo este mega-ADHD sobre esto, por favor me ayude :)

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

Answer 1

OK, me equivoqué la primera vez. Al observar su imagen de un caso de falla, es obvio que existe un eje de separación y es una de las normales (la normal al borde largo del triángulo). La proyección es correcta, sin embargo, tus límites no son correctos.

creo que el error es aquí:

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 representable por un flotador, no el número más negativo. De hecho lo necesario:

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

o incluso mejor para 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; 

porque es probable que ver proyecciones negativas sobre el eje.