OBB vs OBB Detección de colisión

20

Supongamos que tiene dos objetos Bounding Box cada uno de ellos almacenando los vértices actuales del cuadro en un vector con todos los vértices del objeto rotados y traducidos en relación con un eje común.

Aquí hay una imagen para ilustrar mi problema:

¿Cómo puedo resolver si los dos OBB se superponen a algún enlace para ayudar a explicar la solución al problema? Nada demasiado complicado por favor ...

Joshua Barnett
fuente

Respuestas:

16

Un OBB es un casco convexo. Un casco convexo es una forma 3D que no tiene "grietas" en su superficie. Cada "protuberancia" (vértice) en el casco convexo sobresale hacia afuera , nunca hacia adentro. Si corta un plano a través de un casco convexo obtendrá (solo uno) polígono convexo. Si está dentro de un casco convexo y dispara un láser que apunta hacia afuera, solo atravesará la superficie del casco una vez (nunca dos veces).

La prueba del Teorema del eje de separación se puede utilizar para detectar la colisión de cascos convexos. El examen SAT es simple. Funciona en 2D y 3D. Aunque las imágenes a continuación estarán en 2D, podrían aplicarse fácilmente a 3D.

Concepto

Este es el concepto clave que está utilizando con SAT:

  • Dos formas solo se cruzan si se solapan cuando se "proyectan" en cada eje normal de ambas formas .

La "proyección" de una forma en un vector 1D se ve así (lo que yo llamo "aplastamiento")

Una forma con verts rojos y un eje.

ingrese la descripción de la imagen aquí

"Proyectar la forma en el eje" significa dejar caer una perpendicular desde cada punto de la forma solo para aterrizar en el eje. Puedes pensar en esto como "aplastar" los puntos con una mano que recoge todo y lo aplasta perpendicularmente hacia el eje.

ingrese la descripción de la imagen aquí

Lo que te queda: puntos en un eje

ingrese la descripción de la imagen aquí

SAT dice:

Para que 2 cascos convexos se crucen, tienen que superponerse en cada eje (donde cada normal en cualquier forma cuenta como un eje que debemos verificar).

Toma estas 2 formas:

ingrese la descripción de la imagen aquí

Verá que no se cruzan, así que intentemos con algunos ejes para mostrar si no se produce una superposición .

Probar la parte superior normal del pentágono:

ingrese la descripción de la imagen aquí

Estas son las extensiones. Se superponen.

ingrese la descripción de la imagen aquí

Intenta con el lado izquierdo del rectángulo. Ahora no se superponen en este eje, por lo tanto, NO HAY INTERSECCIÓN.

ingrese la descripción de la imagen aquí

Algoritmo:

Para cada cara normal en ambas formas:

  • Encuentre las extensiones mínima y máxima (valor mayor y menor) de la proyección de todos los puntos de esquina de vértice de ambas formas en ese eje
  • Si no se superponen, no hay intersección .

Y eso es todo. El código para hacer que SAT funcione es muy corto y simple.

Aquí hay un código que muestra cómo hacer una proyección del eje SAT:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Código de llamada:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}
bobobobo
fuente
Hullinator implementa la prueba SAT para cascos convexos
bobobobo
¡explicación asombrosa! Gracias. Creo que es posible que tenga un error tipográfico en la línea: "así que vamos a probar un par de ejes para mostrar una superposición eran no sucede.", Porque entonces se procede a dar ejemplos en los que hacen solapamiento. ¡gracias de nuevo!
¿No necesita hacer las pruebas también para todos los productos cruzados de las normales? Este artículo geometrictools.com/Documentation/DynamicCollisionDetection.pdf lo dice.
iNFINITEi
Vale la pena decir que este método específico de SAT solo funciona en 2D. En 3D, necesitas obtener más que las normales de cada cara. Sin embargo, una vez que tiene las normales correctas, el resto del proceso (proyecto, comparación) es exactamente el mismo.
Financia la demanda de Mónica el
De tus imágenes 2D es muy difícil saber en qué dirección van las flechas.
WDUK
7

Definitivamente deberías buscar el teorema del eje de separación . Es para objetos convexos. Hay una regla: "Si dos objetos convexos no se cruzan, entonces hay un plano donde la proyección de estos dos objetos no se intersecará".

Puedes encontrar algunos ejemplos en la wiki . Pero es un poco más complicado que para su caso.

Algo más adecuado para su problema se puede encontrar aquí (dos autos colisionando).

zacharmarz
fuente
1

Más artículos del SAT .

El último artículo en este sitio viene con un código completo, creo que está en FLASH, no tengo idea, pero tuve exactamente 0 problemas al convertirlo a C ++ cuando tuve que usar SAT por primera vez, no debería ser difícil haz lo mismo para otros idiomas. Lo único que tendrá que agregar es almacenar el vector de desplazamiento en cada cálculo (si es el más pequeño, por supuesto, lo entenderá cuando aprenda sobre SAT), el código en este tutorial no lo hace, así que terminas con el último vector calculado.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Buenos, viejos tutoriales de N-Game. La mejor teoría SAT en la web.

http://www.metanetsoftware.com/technique/tutorialA.html

dreta
fuente
Es tan irritante que nadie publica la fuente de trabajo completa con todas las clases requeridas. Porté su código en una demostración propia, pero simplemente no funciona. :( Este es mi proyecto hasta ahora si alguien pudiera ayudarme a depurarlo sería genial. Enlace
Joshua Barnett
¿Qué quieres decir con que no funciona? preste atención a cómo está almacenando sus vértices, en la imagen los tiene en un sistema de coordenadas cartesianas, en el tutorial almacena los vértices como vectores relativos al centroide (todo lo que tiene que hacer es restar el centroide de sus propios vértices o elimina las líneas donde modifica sus propios vértices), funciona como un producto de puntos que puedes crear tú mismo, no necesitas una guía para eso, el resto debe ser sencillo, no es un material de copiar y pegar, aprende SAT antes de intentar implementarlo
Dreta
Así es como lo he implementado: SAT.as , Shape2D.as , ¿Qué quieres decir con centroide? ¿El centro del polígono como (x, y)?
Joshua Barnett
Por el momento tengo una función getOBB () que devuelve vértices como se detalla en mi imagen original. Esto se calcula a partir de un Vector <b2Vec2> que contiene los vértices de la forma, una variable de ángulo y una variable de posición.
Joshua Barnett
sí, el centro, la forma en que este tipo crea sus polígonos es dando desplazamientos desde el centro, idk AS3, pero por lo que veo proyectas tus vértices tal como están, al calcular el producto de puntos intenta restar el centroide de los vértices (subracción vectorial ), además de esto, no está comprobando qué vector de separación es el más pequeño todavía, solo almacena el último calculado
dreta