Cuántos y qué ejes usar para la colisión OBB 3D con SAT

He estado implementando el SAT basado en:

• Detección dinámica de colisión utilizando cuadros delimitadores orientados [PDF]

En la página 7, en la tabla, hace referencia a los 15 ejes a probar para que podamos encontrar una colisión, pero con solo Ax, Ay y Az, ya estoy recibiendo colisiones.

¿Por qué necesito probar todos los demás casos? ¿Hay alguna situación en la que solo Axe, Ay y Az no sean suficientes?

Puede estar obteniendo falsos positivos. Colisiones detectadas pero no realmente colisiones.

El número 15 proviene de

• 3 ejes del objeto A (caras normales)
• 3 ejes del objeto B (caras normales)
• 9 ejes de todos los pares de aristas de A y aristas de B (3x3)
• = 15 en total

Los 9 ejes están formados por productos transversales de bordes de A y bordes de B

1. Ae1 x Be1 (Borde 1 de A, borde transversal 1 de B)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... y así

Los primeros 6 ejes (de las normales de la cara) se utilizan para verificar si una esquina de un objeto está intersectando una cara del otro objeto. (o más correctamente para eliminar este tipo de colisiones)

El conjunto de 9 ejes formados por los productos transversales de los bordes se usa para considerar la detección de colisión de borde sobre borde, donde no hay un vértice que penetre en el otro objeto. Como la colisión 'casi' en la foto de abajo. Supongamos para el resto de esta respuesta que los dos cuadros en la imagen no están realmente colisionando, sino que están separados por una pequeña distancia.

Veamos qué sucede si solo usamos las 6 normales de cara para SAT. La primera imagen a continuación muestra un eje del cuadro azul y 2 ejes del cuadro amarillo. Si proyectamos ambos objetos en estos ejes, obtendremos una superposición en los tres. La segunda imagen a continuación muestra los dos ejes restantes del cuadro azul y el eje restante del cuadro amarillo. Una vez más, proyectar en estos ejes mostrará superposiciones en los 3.

Entonces, solo al verificar las 6 normales de la cara se mostrarán superposiciones en los 6 ejes, lo que, según el SAT, significa que los objetos están colisionando, porque no hemos podido encontrar una separación. Pero, por supuesto, estos objetos no están colisionando. ¡La razón por la que no hemos encontrado una separación es porque no hemos buscado lo suficiente!

Entonces, ¿cómo vamos a encontrar esta brecha? La siguiente imagen muestra un eje en el que la proyección de ambos objetos revelará una separación.

¿De dónde obtenemos este eje?

Si imagina deslizar un trozo de tarjeta rígida en el espacio, esa tarjeta formará parte del plano de separación. Si proyectamos a la normalidad de ese plano (flecha negra en la imagen de arriba), veremos la separación. Sabemos cuál es ese plano porque tenemos dos vectores que se encuentran en ese plano) Un vector está alineado con el borde azul y el otro vector está alineado con el borde amarillo y, como todos sabemos, la normalidad de un plano es simplemente el producto cruzado de dos vectores que yacen en el plano.

Entonces, para los OOBBs necesitamos verificar cada combinación (9 de ellas) de productos cruzados de los bordes de los dos objetos para asegurarnos de que no faltan las separaciones de borde a borde.

La respuesta de Ken señala:

Los 9 ejes están formados por productos transversales de bordes de A y bordes de B

Es algo confuso referirse a los bordes, ya que hay 12 bordes en comparación con 6 normales, cuando también podría usar las tres normales principales para la misma salida: los bordes están todos alineados con las normales, por lo que recomiendo usarlos en su lugar !

También tenga en cuenta que las normales que apuntan a lo largo del mismo eje, pero en una dirección diferente, se ignoran y, por lo tanto, nos quedan tres ejes únicos.

Otra cosa que me gustaría agregar es que puede optimizar este cálculo saliendo temprano si encuentra un eje de separación, antes de calcular todos los ejes que desea probar. Entonces, no, no necesita probar todos los ejes en todos los casos, pero sí debe estar listo para probarlos a todos :)

Aquí hay una lista completa de ejes para probar, dados dos OBB, A y B, donde x, y y z se refieren a los vectores base / tres normales únicas. 0 = eje x, 1 = eje y, 2 = eje z

1. a0
2. a1
3. a2
4. b0
5. b1
6. b2
7. cruz (a0, b0)
8. cruz (a0, b1)
9. cruz (a0, b2)
10. cruz (a1, b0)
11. cruz (a1, b1)
12. cruz (a1, b2)
13. cruz (a2, b0)
14. cruz (a2, b1)
15. cruz (a2, b2)

También hay una pequeña advertencia, que debes tener en cuenta.

El producto cruzado le dará un vector cero {0,0,0} cuando dos ejes cualesquiera entre los objetos apunten en la misma dirección.

Además, dado que esta parte se omitió, aquí está mi implementación para verificar si la proyección se superpone o no. Probablemente haya una mejor manera, ¡pero esto funcionó para mí! (Usando Unity y su API C #)

// aCorn and bCorn are arrays containing all corners (vertices) of the two OBBs
private static bool IntersectsWhenProjected( Vector3[] aCorn, Vector3[] bCorn, Vector3 axis ) {

    // Handles the cross product = {0,0,0} case
    if( axis == Vector3.zero ) 
        return true;

    float aMin = float.MaxValue;
    float aMax = float.MinValue;
    float bMin = float.MaxValue;
    float bMax = float.MinValue;

    // Define two intervals, a and b. Calculate their min and max values
    for( int i = 0; i < 8; i++ ) {
        float aDist = Vector3.Dot( aCorn[i], axis );
        aMin = ( aDist < aMin ) ? aDist : aMin;
        aMax = ( aDist > aMax ) ? aDist : aMax;
        float bDist = Vector3.Dot( bCorn[i], axis );
        bMin = ( bDist < bMin ) ? bDist : bMin;
        bMax = ( bDist > bMax ) ? bDist : bMax;
    }

    // One-dimensional intersection test between a and b
    float longSpan = Mathf.Max( aMax, bMax ) - Mathf.Min( aMin, bMin );
    float sumSpan = aMax - aMin + bMax - bMin;
    return longSpan < sumSpan; // Change this to <= if you want the case were they are touching but not overlapping, to count as an intersection
}

ejemplo de c # de trabajo basado en la respuesta de Acegikmo (usando algunos apis de la unidad)

using UnityEngine;

public class ObbTest : MonoBehaviour
{
 public Transform A;
 public Transform B;

 void Start()
 {
      Debug.Log(Intersects(ToObb(A), ToObb(B)));
 }

 static Obb ToObb(Transform t)
 {
      return new Obb(t.position, t.localScale, t.rotation);
 }

 class Obb
 {
      public readonly Vector3[] Vertices;
      public readonly Vector3 Right;
      public readonly Vector3 Up;
      public readonly Vector3 Forward;

      public Obb(Vector3 center, Vector3 size, Quaternion rotation)
      {
           var max = size / 2;
           var min = -max;

           Vertices = new[]
           {
                center + rotation * min,
                center + rotation * new Vector3(max.x, min.y, min.z),
                center + rotation * new Vector3(min.x, max.y, min.z),
                center + rotation * new Vector3(max.x, max.y, min.z),
                center + rotation * new Vector3(min.x, min.y, max.z),
                center + rotation * new Vector3(max.x, min.y, max.z),
                center + rotation * new Vector3(min.x, max.y, max.z),
                center + rotation * max,
           };

           Right = rotation * Vector3.right;
           Up = rotation * Vector3.up;
           Forward = rotation * Vector3.forward;
      }
 }

 static bool Intersects(Obb a, Obb b)
 {
      if (Separated(a.Vertices, b.Vertices, a.Right))
           return false;
      if (Separated(a.Vertices, b.Vertices, a.Up))
           return false;
      if (Separated(a.Vertices, b.Vertices, a.Forward))
           return false;

      if (Separated(a.Vertices, b.Vertices, b.Right))
           return false;
      if (Separated(a.Vertices, b.Vertices, b.Up))
           return false;
      if (Separated(a.Vertices, b.Vertices, b.Forward))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Forward)))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Forward)))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Forward)))
           return false;

      return true;
 }

 static bool Separated(Vector3[] vertsA, Vector3[] vertsB, Vector3 axis)
 {
      // Handles the cross product = {0,0,0} case
      if (axis == Vector3.zero)
           return false;

      var aMin = float.MaxValue;
      var aMax = float.MinValue;
      var bMin = float.MaxValue;
      var bMax = float.MinValue;

      // Define two intervals, a and b. Calculate their min and max values
      for (var i = 0; i < 8; i++)
      {
           var aDist = Vector3.Dot(vertsA[i], axis);
           aMin = aDist < aMin ? aDist : aMin;
           aMax = aDist > aMax ? aDist : aMax;
           var bDist = Vector3.Dot(vertsB[i], axis);
           bMin = bDist < bMin ? bDist : bMin;
           bMax = bDist > bMax ? bDist : bMax;
      }

      // One-dimensional intersection test between a and b
      var longSpan = Mathf.Max(aMax, bMax) - Mathf.Min(aMin, bMin);
      var sumSpan = aMax - aMin + bMax - bMin;
      return longSpan >= sumSpan; // > to treat touching as intersection
 }
}