necesita ayuda con la implementación de la detección de colisiones mediante el teorema de separación de ejes

Question

Así, después de horas de buscar en Google y la lectura, he encontrado que el proceso básico de la detección de una colisión utilizando SAT es:

for each edge of poly A 
    project A and B onto the normal for this edge 
    if intervals do not overlap, return false 
end for 

for each edge of poly B 
    project A and B onto the normal for this edge 
    if intervals do not overlap, return false 
end for 

Sin embargo, como muchos formas en que trato de implementar esto en el código, simplemente no logro que detecte la colisión. Mi código actual es la siguiente:

for (unsigned int i = 0; i < asteroids.size(); i++) { 
    if (asteroids.valid(i)) { 
     asteroids[i]->Update(); 

     // Player-Asteroid collision detection 
     bool collision = true; 
     SDL_Rect asteroidBox = asteroids[i]->boundingBox; 

     // Bullet-Asteroid collision detection 
     for (unsigned int j = 0; j < player.bullets.size(); j++) { 
      if (player.bullets.valid(j)) { 
       Bullet b = player.bullets[j]; 

       collision = true; 
       if (b.x + (b.w/2.0f) < asteroidBox.x - (asteroidBox.w/2.0f)) collision = false; 
       if (b.x - (b.w/2.0f) > asteroidBox.x + (asteroidBox.w/2.0f)) collision = false; 
       if (b.y - (b.h/2.0f) > asteroidBox.y + (asteroidBox.h/2.0f)) collision = false; 
       if (b.y + (b.h/2.0f) < asteroidBox.y - (asteroidBox.h/2.0f)) collision = false; 

       if (collision) { 
        bool realCollision = false; 

        float min1, max1, min2, max2; 

        // Create a list of vertices for the bullet 
        CrissCross::Data::LList<Vector2D *> bullVerts; 
        bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y + b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y - b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y - b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y + b.h/2.0f)); 
        // Create a list of vectors of the edges of the bullet and the asteroid 
        CrissCross::Data::LList<Vector2D *> bullEdges; 
        CrissCross::Data::LList<Vector2D *> asteroidEdges; 
        for (int k = 0; k < 4; k++) { 
         int n = (k == 3) ? 0 : k + 1; 
         bullEdges.insert(new Vector2D(bullVerts[k]->x - bullVerts[n]->x, 
               bullVerts[k]->y - bullVerts[n]->y)); 
         asteroidEdges.insert(new Vector2D(asteroids[i]->vertices[k]->x - asteroids[i]->vertices[n]->x, 
                asteroids[i]->vertices[k]->y - asteroids[i]->vertices[n]->y)); 
        } 

        Vector2D *vectOffset = new Vector2D(asteroids[i]->center.x - b.x, asteroids[i]->center.y - b.y); 

        for (unsigned int k = 0; k < asteroidEdges.size(); k++) { 
         Vector2D *axis = asteroidEdges[k]->getPerpendicular(); 
         axis->normalize(); 
         min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]); 
         for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) { 
          float test = axis->dotProduct(asteroids[i]->vertices[l]); 
          min1 = (test < min1) ? test : min1; 
          max1 = (test > max1) ? test : max1; 
         } 
         min2 = max2 = axis->dotProduct(bullVerts[0]); 
         for (unsigned int l = 1; l < bullVerts.size(); l++) { 
          float test = axis->dotProduct(bullVerts[l]); 
          min2 = (test < min2) ? test : min2; 
          max2 = (test > max2) ? test : max2; 
         } 
         float offset = axis->dotProduct(vectOffset); 
         min1 += offset; 
         max1 += offset; 
         delete axis; axis = NULL; 
         float d0 = min1 - max2; 
         float d1 = min2 - max1; 
         if (d0 > 0 || d1 > 0) { 
          realCollision = false; 
          break; 
         } else { 
          realCollision = true; 
         } 
        } 

        if (realCollision) { 
         for (unsigned int k = 0; k < bullEdges.size(); k++) { 
          Vector2D *axis = bullEdges[k]->getPerpendicular(); 
          axis->normalize(); 
          min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]); 
          for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) { 
           float test = axis->dotProduct(asteroids[i]->vertices[l]); 
           min1 = (test < min1) ? test : min1; 
           max1 = (test > max1) ? test : max1; 
          } 
          min2 = max2 = axis->dotProduct(bullVerts[0]); 
          for (unsigned int l = 1; l < bullVerts.size(); l++) { 
           float test = axis->dotProduct(bullVerts[l]); 
           min2 = (test < min2) ? test : min2; 
           max2 = (test > max2) ? test : max2; 
          } 
          float offset = axis->dotProduct(vectOffset); 
          min1 += offset; 
          max1 += offset; 
          delete axis; axis = NULL; 
          float d0 = min1 - max2; 
          float d1 = min2 - max1; 
          if (d0 > 0 || d1 > 0) { 
           realCollision = false; 
           break; 
          } else { 
           realCollision = true; 
          } 
         } 
        } 
        if (realCollision) { 
         player.bullets.remove(j); 

         int numAsteroids; 
         float newDegree; 
         srand (j + asteroidBox.x); 
         if (asteroids[i]->degree == 90.0f) { 
          if (rand() % 2 == 1) { 
           numAsteroids = 3; 
           newDegree = 30.0f; 
          } else { 
           numAsteroids = 2; 
           newDegree = 45.0f; 
          } 
          for (int k = 0; k < numAsteroids; k++) 
           asteroids.insert(new Asteroid(asteroidBox.x + (10 * k), asteroidBox.y + (10 * k), newDegree)); 
         } 
         delete asteroids[i]; 
         asteroids.remove(i); 
        } 
        while (bullVerts.size()) { 
         delete bullVerts[0]; 
         bullVerts.remove(0); 
        } 
        while (bullEdges.size()) { 
         delete bullEdges[0]; 
         bullEdges.remove(0); 
        } 
        while (asteroidEdges.size()) { 
         delete asteroidEdges[0]; 
         asteroidEdges.remove(0); 
        } 

        delete vectOffset; vectOffset = NULL; 
       } 
      } 
     } 
    } 
} 

bullEdges es una lista de vectores de los bordes de una bala, asteroidEdges es similar, y bullVerts y asteroides [i] .vertices son, obviamente, las listas de vectores de cada vértice para la bala o asteroide respectivo.

Honestamente, no estoy buscando correcciones de código, solo un par de ojos nuevos.

Answer 1

Resulta que mi comprensión matemática del teorema estaba perfectamente bien.En cambio, el problema radicaba en el hecho de que no estaba incluyendo los puntos centrales de los polígonos en los vectores de vértice.

Gracias a todos por su tiempo.

Answer 2

Agregaste esto vectOffset parte incorrecta, los sistemas de coordenadas de tus asteroides y balas son los mismos, ¿no? (Debe ser, si la prueba de cuadro delimitador está funcionando.)

¿Son cuadrados sus asteroides? Si es así, entonces la prueba de cuadro delimitador siempre será exacta, y realCollision y collision siempre deben ser idénticos. Si no, entonces no está compilando asteroidEdges correctamente - necesita repetir el número de vértices, no 4.

Pero en serio, haga de este código un método diferente y escriba una prueba unitaria, es la única manera Puedo ejecutar tu código para ver qué está pasando.

Answer 3

bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y + b.h/2.0f)); bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y - b.h/2.0f)); bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y - b.h/2.0f)); bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y + b.h/2.0f));

Parece que va a crear un clon de asteroides, en cuyo caso se esperaría que la bala se puede girar, pero este código siempre se trata a la bala como si fuera completamente vertical. ¿Podria ese ser tu problema?

Answer 4

Algo que puede ayudar a encontrar el problema es hacer que la bala sea un punto. Podría iluminar problemas con otras partes de tu código. Además, si tu punto hace una colisión pero la bala no, obtendrás algo concreto para mirar.

En otras palabras, simplifique su problema hasta que surja una solución. ;)

Answer 5

Además de todo el desplazamiento, que es defectuoso, el resto del algoritmo parece OK. ¿Has intentado rastrearlo para detectar el problema?

Por cierto, hay varias peculiaridades estilísticas que hacen que el código sea difícil de leer de un vistazo:

• por qué los punteros en todas partes, en lugar de asignar todos esos Vector2Ds temporales en la pila?
• ¿Por qué CrissCross::Data::LList en lugar de "good old" std::vector?
• Seguramente Vector2D tiene un operador sobrecargado-?

Aquí hay una implementación autónoma rápida y sucia del algoritmo. Lo he probado un poco, pero no garantizo:

#include <vector> 
#include <limits> 

using namespace std; 

class Vector2D 
{ 
public: 
    Vector2D() : x(0), y(0) {} 
    Vector2D(double x, double y) : x(x), y(y) {} 

    Vector2D operator-(const Vector2D &other) const 
    { 
    return Vector2D(x - other.x, y - other.y); 
    } 

    double dot(const Vector2D &other) const 
    { 
    return x * other.x + y*other.y; 
    } 

    Vector2D perp() const 
    { 
    return Vector2D(-y, x); 
    } 

    double x,y; 
}; 

bool checkCollisionOneSided(vector<Vector2D> &object1, vector<Vector2D> &object2) 
{ 
    int nume = object1.size(); 
    for(int i=0; i<nume; i++) 
    { 
     Vector2D edge = object1[(i+1)%nume] - object1[i]; 
     Vector2D normal = edge.perp(); 

     double min1 = numeric_limits<double>::infinity(); 
     double min2 = min1; 
     double max1 = -numeric_limits<double>::infinity(); 
     double max2 = max1; 

     for(int j=0; j<object1.size(); j++) 
    { 
     double dot = normal.dot(object1[j]); 
     min1 = std::min(min1, dot); 
     max1 = std::max(max1, dot); 
    } 
     for(int j=0; j<object2.size(); j++) 
    { 
     double dot = normal.dot(object2[j]); 
     min2 = std::min(min2, dot); 
     max2 = std::max(max2, dot); 
    } 

     if(min2 > max1 || min1 > max2) 
    return false; 
    } 
    return true; 
} 

bool isColliding(vector<Vector2D> &object1, vector<Vector2D> &object2) 
{ 
    return checkCollisionOneSided(object1, object2) && checkCollisionOneSided(object2, object1); 
}