Berapa banyak dan sumbu mana yang akan digunakan untuk tabrakan OBB 3D dengan SAT

Saya telah mengimplementasikan SAT berdasarkan:

• Deteksi Tabrakan Dinamis menggunakan Oriented Bounding Boxes [PDF]

Pada halaman 7, dalam tabel, ini merujuk pada 15 sumbu untuk diuji sehingga kami dapat menemukan tabrakan, tetapi hanya dengan Ax, Ay dan Az, saya sudah mendapatkan tabrakan.

Mengapa saya perlu menguji semua kasus lainnya? Apakah ada situasi di mana hanya Ax, Ay dan Az tidak cukup?

Anda mungkin mendapatkan hasil positif palsu. Tabrakan terdeteksi tetapi tidak benar-benar bertabrakan.

Nomor 15 berasal

• 3 sumbu dari objek A (face normals)
• 3 sumbu dari objek B (face normals)
• 9 sumbu dari semua pasangan tepi A dan tepi B (3x3)
• = 15 total

9 sumbu terdiri dari produk silang tepi A dan tepi B

1. Ae1 x Be1 (Tepi 1 dari Tepi silang 1 dari B)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... dan seterusnya

6 sumbu pertama (dari face normals) digunakan untuk memeriksa apakah ada sudut dari satu objek yang memotong wajah dari objek lain. (atau lebih tepatnya untuk menghilangkan tabrakan semacam ini)

Himpunan 9 sumbu yang dibentuk oleh produk silang dari tepi digunakan untuk mempertimbangkan deteksi tumbukan tepi, di mana tidak ada titik menembus objek lain. Seperti tabrakan 'nyaris' di foto di bawah ini. Mari kita asumsikan untuk sisa jawaban ini bahwa dua kotak di gambar sebenarnya tidak bertabrakan, tetapi dipisahkan oleh jarak yang sangat kecil.

Mari kita lihat apa yang terjadi jika kita hanya menggunakan 6 face normals untuk SAT. Gambar pertama di bawah ini menunjukkan satu sumbu dari kotak biru dan 2 sumbu dari kotak kuning. Jika kita memproyeksikan kedua objek ke sumbu ini, kita akan mendapatkan tumpang tindih pada ketiganya. Gambar kedua di bawah ini menunjukkan sisa dua sumbu kotak biru dan sisa sumbu kotak kuning. Sekali lagi memproyeksikan pada sumbu ini akan menunjukkan tumpang tindih pada semua 3.

Jadi hanya memeriksa 6 muka normal akan menunjukkan tumpang tindih pada semua 6 sumbu, yang, menurut SAT, berarti benda bertabrakan, karena kita belum dapat menemukan pemisahan. Tapi tentu saja, benda ini tidak bertabrakan. Alasan kami belum menemukan pemisahan adalah karena kami belum terlihat cukup keras!

Jadi bagaimana kita menemukan celah ini? Gambar di bawah ini menunjukkan sumbu di mana proyeksi kedua objek akan mengungkapkan pemisahan.

Dari mana kita mendapatkan sumbu ini?

Jika Anda membayangkan memasukkan sepotong kartu kaku ke dalam celah, kartu itu akan menjadi bagian dari bidang pemisah. Jika kita memproyeksikan ke normal pesawat itu (panah hitam pada gambar di atas), kita akan melihat pemisahan. Kita tahu apa bidang itu karena kita memiliki dua vektor yang terletak pada bidang itu) Satu vektor disejajarkan dengan tepi biru dan vektor lainnya disejajarkan dengan tepi kuning dan seperti kita ketahui bahwa normal suatu bidang hanyalah produk silang dari dua vektor berbaring di pesawat.

Jadi untuk OOBB kita perlu memeriksa setiap kombinasi (9 dari mereka) produk silang dari tepi dua objek untuk memastikan kita tidak melewatkan pemisahan tepi-tepi.

Catatan jawaban Ken :

9 sumbu terdiri dari produk silang tepi A dan tepi B

Agak membingungkan untuk merujuk ke edge, karena ada 12 edge dibandingkan dengan 6 normals, ketika Anda mungkin juga menggunakan tiga normals utama untuk output yang sama - edge semuanya sejajar dengan normals, jadi saya sarankan untuk menggunakannya. !

Perhatikan juga bahwa normals yang menunjuk pada sumbu yang sama, tetapi dalam arah yang berbeda, diabaikan, dan dengan demikian kita dibiarkan dengan tiga sumbu unik.

Hal lain yang ingin saya tambahkan, adalah Anda dapat mengoptimalkan perhitungan ini dengan keluar lebih awal jika Anda menemukan sumbu pemisah, sebelum Anda menghitung semua sumbu yang ingin Anda uji. Jadi, tidak, Anda tidak perlu menguji semua sumbu dalam setiap kasus, tetapi Anda harus siap untuk menguji semuanya :)

Berikut adalah daftar lengkap sumbu untuk diuji, mengingat dua OBB, A dan B, di mana x, y dan z merujuk pada vektor basis / tiga normals unik. 0 = sumbu x, 1 = sumbu y, 2 = sumbu z

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

Ada juga sedikit peringatan, yang harus Anda waspadai.

Produk silang akan memberikan Anda vektor nol {0,0,0} ketika dua sumbu di antara objek menunjuk ke arah yang sama.

Juga, karena bagian ini ditinggalkan, inilah implementasi saya untuk memeriksa apakah proyeksi tumpang tindih atau tidak. Mungkin ada cara yang lebih baik, tetapi ini berhasil untuk saya! (Menggunakan Unity dan C # API-nya)

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

bekerja c # contoh berdasarkan jawaban Acegikmo (menggunakan api persatuan):

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