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

29

Wdrażam SAT w oparciu o:

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ą?

GriffinHeart
źródło

Odpowiedzi:

56

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ą.

wprowadź opis zdjęcia tutaj

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!

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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.

Rozpoznać
źródło
2
Niesamowite wyjaśnienie! I dzięki za zdjęcia. Jak zauważa @Acegikmo, jest to trochę mylące, gdy mówisz „9 osi składa się z iloczynu poprzecznego krawędzi A i krawędzi B”, ponieważ możemy po prostu użyć normalnych, a nie krawędzi.
5
@joeRocc W przypadku prostopadłościanów, które są poprawne, wystarczy użyć normalnych, ponieważ normalne i krawędzie są wyrównane, ale w przypadku innych kształtów (np. czworościanów, innych wielościanów) normalne nie są wyrównane z krawędziami.
Ken
Dzięki wielkie! Czytałem tę fajną książkę zatytułowaną „Rozwój silnika Game Physics” i natknąłem się na ten problem. Nie miałem pojęcia, dlaczego używamy 15 osi. Wielkie dzięki. Teraz jestem wystarczająco pewny siebie, aby się tym chwalić. ; D
Ankit singh kushwah
11

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
}
Acegikmo
źródło
1
Witamy na stronie. Proszę sprawdzić w centrum pomocy , aw szczególności zauważyć, że ta strona nie jest forum i że „odpowiadanie” na inne odpowiedzi nie jest dobrym pomysłem (ponieważ Twoja „odpowiedź” może nie pojawić się przed postem, na który odpowiadasz). Lepiej jest pisać odpowiedzi w sposób niezależny i używać komentarzy, jeśli chcesz wyjaśnić istniejący post.
Josh
Dzięki za wyjaśnienie Acegikmo! Byłem trochę zdezorientowany odniesieniem do krawędzi. @Josh Petrie, powinieneś umieścić uśmieszki na końcu swoich komentarzy, aby początkujący wiedzieli, że ich nie
patrz mój komentarz powyżej re edge vs. normals
Ken
2

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
 }
}
Bas Smit
źródło