Quantos e quais eixos usar para colisão OBB 3D com SAT

Estou implementando o SAT com base em:

• Detecção dinâmica de colisões usando caixas delimitadoras orientadas [PDF]

Na página 7, na tabela, ele refere o eixo 15 a ser testado para que possamos encontrar uma colisão, mas com apenas Ax, Ay e Az, eu já estou tendo colisões.

Por que preciso testar todos os outros casos? Existe alguma situação em que apenas Ax, Ay e Az não são suficientes?

Você pode estar recebendo falsos positivos. Colisões detectadas, mas não realmente colidindo.

O número 15 vem de

• 3 eixos do objeto A (face normal)
• 3 eixos do objeto B (face normal)
• 9 eixos de todos os pares de arestas de A e arestas de B (3x3)
• = 15 no total

Os 9 eixos são compostos por produtos transversais das arestas de A e arestas de B

1. Ae1 x Be1 (Borda 1 de A borda cruzada 1 de B)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... e assim por diante

Os 6 primeiros eixos (das normais da face) são usados ​​para verificar se um canto de um objeto está cruzando uma face do outro objeto. (ou mais corretamente para eliminar esse tipo de colisão)

O conjunto de 9 eixos formado pelos produtos transversais das arestas é usado para considerar a detecção de colisão de arestas, onde não há um vértice penetrando no outro objeto. Como a colisão 'quase' na foto abaixo. Vamos supor, para o restante desta resposta, que as duas caixas da figura não estão colidindo, mas estão separadas por uma pequena distância.

Vamos ver o que acontece se apenas usarmos as 6 faces normais para o SAT. A primeira imagem abaixo mostra um eixo da caixa azul e 2 eixos da caixa amarela. Se projetarmos ambos os objetos nesses eixos, obteremos uma sobreposição nos três. A segunda imagem abaixo mostra os dois eixos restantes da caixa azul e o eixo restante da caixa amarela. Mais uma vez, projetar nesses eixos mostrará sobreposições em todos os 3.

Portanto, apenas a verificação das 6 normais de face mostrará sobreposições em todos os 6 eixos, o que, de acordo com o SAT, significa que os objetos estão colidindo, porque não conseguimos encontrar uma separação. Mas é claro que esses objetos não estão colidindo. A razão pela qual não encontramos uma separação é porque ainda não procuramos o suficiente!

Então, como vamos encontrar essa lacuna? A imagem abaixo mostra um eixo no qual a projeção de ambos os objetos revelará uma separação.

De onde tiramos esse eixo?

Se você imaginar deslizando um pedaço de cartão rígido no espaço, esse cartão fará parte do plano de separação. Se projetarmos para o normal desse plano (seta preta na figura acima), veremos a separação. Sabemos o que é esse plano porque temos dois vetores que se encontram nesse plano. Um vetor é alinhado com a borda do azul e o outro vetor é alinhado com a borda do amarelo e, como todos sabemos, o normal para um plano é simplesmente o produto cruzado de dois vetores no avião.

Portanto, para os OOBBs, precisamos verificar todas as combinações (9 delas) de produtos cruzados das bordas dos dois objetos para garantir que não faltem separações de bordas.

A resposta de Ken observa:

Os 9 eixos são compostos por produtos transversais das arestas de A e arestas de B

É um pouco confuso fazer referência às arestas, pois existem 12 arestas em comparação com 6 normais, quando você também pode usar os três principais normais para a mesma saída - as arestas estão todas alinhadas com as normais, então eu recomendo usá-las !

Observe também que os normais que apontam para o mesmo eixo, mas em uma direção diferente, são ignorados e, portanto, temos três eixos únicos.

Outra coisa que eu gostaria de acrescentar é que você pode otimizar esse cálculo saindo cedo se encontrar um eixo de separação antes de calcular todos os eixos que deseja testar. Portanto, não, você não precisa testar todos os eixos em todos os casos, mas precisa estar pronto para testá-los todos :)

Aqui está uma lista completa dos eixos a serem testados, dados dois OBBs, A e B, onde x, ye z se referem aos vetores base / três normais únicos. 0 = eixo x, 1 = eixo y, 2 = eixo 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)

Há também uma pequena ressalva, da qual você deve estar ciente.

O produto cruzado fornecerá um vetor zero {0,0,0} quando dois eixos entre os objetos apontarem na mesma direção.

Além disso, como essa parte foi deixada de fora, aqui está minha implementação para verificar se a projeção está sobreposta ou não. Provavelmente existe uma maneira melhor, mas isso funcionou para mim! (Usando o Unity e sua 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
}

exemplo c # de trabalho com base na resposta de Acegikmo (usando algumas APIs de unidade):

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