Ile i jakich osi użyć do kolizji OBB 3D z SAT

Wdrażam SAT w oparciu o:

• Dynamiczne wykrywanie kolizji za pomocą orientowanych ramek ograniczających [PDF]

Na stronie 7 w tabeli odnosi się do osi 15 do przetestowania, abyśmy mogli znaleźć kolizję, ale tylko Ax, Ay i Az już dostaję kolizje.

Dlaczego muszę testować wszystkie pozostałe przypadki? Czy jest jakaś sytuacja, w której same Axe, Ay i Az nie wystarczą?

Być może otrzymujesz fałszywe alarmy. Wykryto kolizje, ale tak naprawdę nie kolidują.

Liczba 15 pochodzi z

• 3 osie od obiektu A (normalne twarze)
• 3 osie od obiektu B (normalne twarze)
• 9 osi ze wszystkich par krawędzi A i krawędzi B (3x3)
• = 15 ogółem

9 osi składa się z iloczynu poprzecznego krawędzi A i krawędzi B

1. Ae1 x Be1 (Krawędź 1 z A krzyżuje krawędź 1 z B)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... i tak dalej

Pierwsze 6 osi (z normalnych ścian twarzy) służy do sprawdzania, czy róg jednego obiektu przecina ścianę drugiego obiektu. (lub bardziej poprawnie, aby wyeliminować tego rodzaju kolizje)

Zbiór 9 osi utworzonych przez iloczyny poprzeczne krawędzi służy do rozważenia wykrywania kolizji między krawędziami, gdy nie ma wierzchołka penetrującego inny obiekt. Podobnie jak kolizja „prawie” na poniższym zdjęciu. Przyjmijmy do końca tej odpowiedzi, że dwa pola na zdjęciu tak naprawdę nie kolidują, ale są oddzielone niewielką odległością.

Przyjrzyjmy się, co się stanie, jeśli użyjemy 6 normalnych twarzy dla SAT. Pierwsze zdjęcie poniżej pokazuje jedną oś z niebieskiego pola i 2 osie z żółtego pola. Jeśli rzutujemy oba obiekty na te osie, otrzymamy nakładanie się na wszystkie trzy. Drugi obraz poniżej pokazuje pozostałe dwie osie niebieskiego pola i pozostałą oś żółtego pola. Ponownie rzutowanie na te osie będzie nakładać się na wszystkie 3.

Tak więc tylko sprawdzenie 6 normalnych twarzy pokaże nakładanie się na wszystkich 6 osiach, co według SAT oznacza, że ​​obiekty zderzają się, ponieważ nie byliśmy w stanie znaleźć separacji. Ale oczywiście te obiekty nie kolidują. Powodem, dla którego nie znaleźliśmy separacji, jest to, że nie spojrzeliśmy wystarczająco mocno!

Jak więc znaleźć tę lukę? Poniższy obraz pokazuje oś, na której rzut obu obiektów ujawni separację.

Skąd mamy tę oś?

Jeśli wyobrażasz sobie wsunięcie kawałka sztywnej karty w szczelinę, karta ta będzie częścią płaszczyzny oddzielającej. Jeśli rzutujemy na normalną płaszczyznę (czarna strzałka na zdjęciu powyżej), zobaczymy separację. Wiemy, czym jest ta płaszczyzna, ponieważ mamy dwa wektory, które leżą na tej płaszczyźnie. Jeden wektor jest wyrównany z krawędzią niebieskiego, a drugi wektor jest wyrównany z krawędzią żółtej, a jak wszyscy wiemy, normalna do płaszczyzny jest po prostu iloczyn krzyżowy dwóch wektorów leżących na płaszczyźnie.

Dlatego w przypadku OOBB musimy sprawdzić każdą kombinację (9 z nich) iloczynu krzyżowego krawędzi dwóch obiektów, aby upewnić się, że nie brakuje nam żadnych separacji krawędzi.

Notatki odpowiedzi Kena :

9 osi składa się z iloczynu poprzecznego krawędzi A i krawędzi B

Odwoływanie się do krawędzi jest nieco mylące, ponieważ istnieje 12 krawędzi w porównaniu do 6 normalnych, gdy równie dobrze możesz użyć trzech głównych normalnych do tego samego wyniku - wszystkie krawędzie są wyrównane z normalnymi, więc zalecam ich użycie zamiast tego !

Zauważ też, że normalne wskazujące wzdłuż tej samej osi, ale w innym kierunku, są ignorowane, dlatego mamy trzy unikalne osie.

Inną rzeczą, którą chciałbym dodać, jest to, że możesz zoptymalizować to obliczenie, wychodząc wcześniej, jeśli znajdziesz oś oddzielającą, przed obliczeniem wszystkich osi, które chcesz przetestować. Więc nie, nie musisz testować wszystkich osi w każdym przypadku, ale musisz być gotowy do przetestowania ich wszystkich :)

Oto pełna lista osi do przetestowania, z dwoma OBB, A i B, gdzie x, y i z odnoszą się do wektorów podstawowych / trzech unikalnych normalnych. 0 = oś x, 1 = oś y, 2 = oś z

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

Jest też małe zastrzeżenie, o którym powinieneś wiedzieć.

Iloczyn krzyżowy da wektor zerowy {0,0,0}, gdy dowolne dwie osie między obiektami wskażą ten sam kierunek.

Ponadto, ponieważ ta część została pominięta, oto moja implementacja, aby sprawdzić, czy projekcja się pokrywa. Prawdopodobnie jest lepszy sposób, ale to zadziałało dla mnie! (Korzystanie z Unity i jego 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
}

działający przykład c # oparty na odpowiedzi Acegikmo (przy użyciu niektórych interfejsów API jedności):

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