Wie viele und welche Achsen sollen für die 3D-OBB-Kollision mit SAT verwendet werden?

Ich habe das SAT implementiert, basierend auf:

• Dynamische Kollisionserkennung mit orientierten Begrenzungsrahmen [PDF]

Auf Seite 7 in der Tabelle wird die 15-Achse zum Testen angegeben, damit wir eine Kollision finden können, aber mit nur Axe, Ay und Az bekomme ich bereits Kollisionen.

Warum muss ich alle anderen Fälle testen? Gibt es eine Situation, in der nur Axe, Ay und Az nicht ausreichen?

Möglicherweise erhalten Sie falsche Positive. Kollisionen erkannt, aber nicht wirklich kollidierend.

Die Nummer 15 kommt von

• 3 Achsen von Objekt A (Flächennormalen)
• 3 Achsen von Objekt B (Flächennormalen)
• 9 Achsen von allen Kantenpaaren von A und Kanten von B (3x3)
• = 15 insgesamt

Die 9 Achsen bestehen aus Kreuzprodukten der Kanten von A und Kanten von B

1. Ae1 x Be1 (Kante 1 von A, Kreuzkante 1 von B)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... und so weiter

Die ersten 6 Achsen (von den Flächennormalen) werden verwendet, um zu prüfen, ob eine Ecke eines Objekts eine Fläche des anderen Objekts schneidet. (oder genauer gesagt, um solche Kollisionen zu vermeiden)

Der Satz von 9 Achsen, der durch die Kreuzprodukte von Kanten gebildet wird, wird verwendet, um die Erkennung von Kanten auf Kanten zu berücksichtigen, wenn kein Scheitelpunkt das andere Objekt durchdringt. Wie die "fast" Kollision auf dem Foto unten. Nehmen wir für den Rest dieser Antwort an, dass die beiden Kästchen im Bild nicht tatsächlich kollidieren, sondern durch einen winzigen Abstand voneinander getrennt sind.

Schauen wir uns an, was passiert, wenn wir nur die 6-Gesichts-Normalen für SAT verwenden. Das erste Bild unten zeigt eine Achse aus der blauen Box und 2 Achsen aus der gelben Box. Wenn wir beide Objekte auf diese Achsen projizieren, erhalten wir eine Überlappung für alle drei. Das zweite Bild unten zeigt die verbleibenden zwei Achsen der blauen Box und die verbleibende Achse der gelben Box. Wenn Sie erneut auf diese Achsen projizieren, werden alle drei Achsen überlappt.

Wenn Sie also nur die 6-Flächen-Normalen überprüfen, werden Überlappungen auf allen 6 Achsen angezeigt, was laut SAT bedeutet, dass die Objekte kollidieren, da wir keinen Abstand finden konnten. Aber natürlich kollidieren diese Objekte nicht. Der Grund, warum wir keine Trennung gefunden haben, ist, dass wir nicht genau genug nachgesehen haben!

Wie können wir diese Lücke finden? Das Bild unten zeigt eine Achse, auf der die Projektion beider Objekte eine Trennung erkennen lässt.

Woher bekommen wir diese Achse?

Wenn Sie sich vorstellen, ein Stück steife Karte in die Lücke zu schieben, ist diese Karte Teil der Trennebene. Wenn wir auf die Normalen dieser Ebene projizieren (schwarzer Pfeil im Bild oben), sehen wir den Abstand. Wir wissen, was diese Ebene ist, weil wir zwei Vektoren haben, die auf dieser Ebene liegen.) Ein Vektor ist an der Kante von Blau ausgerichtet, und der andere Vektor ist an der Kante von Gelb ausgerichtet. Wie wir alle wissen, ist die Normale zu einer Ebene einfach die Kreuzprodukt zweier im Flugzeug liegender Vektoren.

Für OOBBs müssen wir also jede Kombination (9 von ihnen) von Kreuzprodukten der Kanten der beiden Objekte überprüfen, um sicherzustellen, dass keine Kanten-Kanten-Abstände fehlen.

Kens Antwortnotizen :

Die 9 Achsen bestehen aus Kreuzprodukten der Kanten von A und Kanten von B

Es ist etwas verwirrend, sich auf die Kanten zu beziehen, da es 12 Kanten im Vergleich zu 6 Normalen gibt, wenn Sie genauso gut die drei Hauptnormalen für die gleiche Ausgabe verwenden können - die Kanten sind alle an den Normalen ausgerichtet, daher empfehle ich, sie stattdessen zu verwenden !

Beachten Sie auch, dass Normalen, die auf dieselbe Achse, jedoch in eine andere Richtung zeigen, ignoriert werden und somit drei eindeutige Achsen übrig bleiben.

Eine andere Sache, die ich hinzufügen möchte, ist, dass Sie diese Berechnung optimieren können, indem Sie vorzeitig beenden, wenn Sie eine Trennachse finden, bevor Sie alle Achsen berechnen, die Sie testen möchten. Also, nein, Sie müssen nicht in jedem Fall alle Achsen testen, aber Sie müssen bereit sein, sie alle zu testen :)

Hier ist eine vollständige Liste der zu testenden Achsen mit zwei OBBs A und B, wobei sich x, y und z auf die Basisvektoren / drei eindeutigen Normalen beziehen. 0 = x-Achse, 1 = y-Achse, 2 = z-Achse

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

Es gibt auch eine kleine Einschränkung, die Sie beachten sollten.

Das Kreuzprodukt ergibt einen Nullvektor {0,0,0}, wenn zwei Achsen zwischen den Objekten in die gleiche Richtung zeigen.

Da dieser Teil weggelassen wurde, ist hier meine Implementierung, um zu prüfen, ob sich die Projektion überlappt oder nicht. Es gibt wahrscheinlich einen besseren Weg, aber das hat bei mir funktioniert! (Verwenden von Unity und seiner C # -API)

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

funktionierendes C # -Beispiel basierend auf Acegikmos Antwort (unter Verwendung einiger Unity-APIs):

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