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

29

Estou implementando o SAT com base em:

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?

GriffinHeart
fonte

Respostas:

56

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.

insira a descrição da imagem aqui

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!

insira a descrição da imagem aqui insira a descrição da imagem aqui

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.

insira a descrição da imagem aqui

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.

Ken
fonte
2
Explicação impressionante! E obrigado pelas fotos. Como o @Acegikmo observa, é um pouco confuso quando você diz que "9 eixos são compostos de produtos cruzados das arestas de A e arestas de B", pois podemos usar apenas os normais, e não as arestas. Obrigado novamente :)
5
@joeRocc Para cuboides, você está correto, basta usar os normais, porque os normais e as arestas estão alinhados, mas para outras formas (por exemplo, tetraedros, outros poliedros), os normais não estão alinhados com as arestas.
Ken
Valeu mesmo, cara! Eu estava lendo este belo livro chamado "Game Engine engine development" e me deparei com esse problema. Não sabia por que estamos usando 15 eixos. Muito obrigado. Agora estou confiante o suficiente para me gabar. ; D
Ankit singh kushwah 16/01
11

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
}
Acegikmo
fonte
1
Bem vindo ao site. Verifique a Central de Ajuda e observe, em particular, que este site não é um fórum e que "responder" a outras respostas não é uma boa ideia (porque sua "resposta" pode não aparecer antes da postagem para a qual você está respondendo). É melhor escrever suas respostas de maneira autônoma e usar comentários se você quiser especificamente esclarecer uma postagem existente.
Josh
Obrigado pelo esclarecimento Acegikmo! Fiquei um pouco confuso com a referência às arestas também. @ Josh Petrie você deve colocar smilies no final de seus comentários tão novatos sabe que não desligá-los :)
ver o meu comentário acima re bordas vs normais
Ken
2

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
 }
}
Bas Smit
fonte