Saya mengambil studi proses pengenalan tabrakan, dan ini membawa saya ke algoritma Gilbert-Johnson-Keerthi (GJK).

Semua contoh kode dalam posting ditulis dalam TypeScript. Contoh-contoh menggunakan struktur yang saya buat yang tidak dibahas secara rinci dalam posting. Mereka sederhana dan dapat dilihat di repositori GitHub:

• Vector
• IShape
• Collision

Semua kode dari pos disimpan di repositori GitHub:

https://github.com/jthomperoo/gjk-ts-implementation

Posting itu ditulis berdasarkan artikel ini dan video yang direkomendasikan di dalamnya:

• http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
• http://mollyrocket.com/849

Pendahuluan

GJK adalah algoritma yang dirancang untuk menentukan persimpangan dua bentuk cembung. Ini sederhana dan diimplementasikan menggunakan "fungsi bantu" umum yang memungkinkan Anda untuk menggunakan pendekatan yang lebih umum - dengan cara yang sama, Anda dapat memproses poligon dan bentuk yang terdiri dari kurva, misalnya, elips.

Informasi yang Diperlukan

Jumlah Minkowski

GJK menggunakan konsep yang disebut jumlah Minkowski. SM dihitung dengan menjumlahkan semua poin dari dua angka. Misalnya, ambil dua gambar yang ditunjukkan di bawah ini:


Gambar A (hijau):


Gambar B (ungu):


Mengambil nilai dari angka A dan angka B, kita dapat menghitung jumlah Minkowski:

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

Jika kita mengambil nilai-nilai ini dan membuat grafik darinya, kita akan melihat gambar mana yang akan menjadi hasilnya.

Jumlah Minkowski untuk angka A dan B:

Perhatikan bahwa AD dalam tabel dan grafik berhubungan dengan A + D



Untuk lebih memahami jumlah Minkowski, kita dapat membayangkan bahwa kita mengambil angka A dan memotongnya dengan garis besar huruf B. Angka yang dihasilkan adalah jumlah Minkowski.

Perbedaan Minkowski

GJK menggunakan variasi jumlah Minkowski, di mana A + B tidak diambil, tetapi A - B. Dalam sumber yang saya baca, ini disebut "Perbedaan Minkowski". Perbedaan Minkowski memiliki properti yang menarik: jika dua angka tumpang tindih / berpotongan, maka perbedaan Minkowski yang dihasilkan akan berisi asal. Dan ini adalah dasar dari algoritma GJK.

Mengambil nilai dari angka A dan B, kita dapat menghitung perbedaan Minkowski:

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

Jika kita mengambil nilai-nilai ini dan meletakkannya di grafik, kita akan melihat gambar yang dihasilkan.

Perbedaan Minkowski untuk angka A dan B:

Perhatikan bahwa AD dalam tabel dan grafik mengacu pada A - D

Algoritma

Berdasarkan konsep-konsep ini, algoritma GJK mengoptimalkannya. Menghitung jumlah Minkowski bisa memakan banyak waktu, terutama jika Anda memeriksa persimpangan dua angka yang terdiri dari banyak titik. Untuk menghindari hal ini, GJK menggunakan dua konsep utama: fungsi pembantu dan simpleks.

Fungsi Pembantu

Fungsi bantu adalah cara pengambilan sampel titik di tepi perbedaan Minkowski tanpa membangun keseluruhan gambar. Fungsi helper mendapat dua angka perbandingan, dan arah yang perlu diperiksa. Kemudian fungsi bantu menerima dari masing-masing gambar titik terjauh dari dua arah yang berlawanan. Dengan menggunakan dua titik paling jauh ini, Anda dapat menghitung titik tambahan pada gambar perbedaan Minkowski. Kami mengambil poin dari arah yang berlawanan karena kami mendapatkan poin pada perbedaan Minkowski, yang akan memberi kita area terbesar, yaitu, akan ada kemungkinan lebih tinggi bahwa kita akan menyertakan asal pada gambar. Karena perbedaan Minkowski adalah titik a - b , keberadaan titik gambar b yang diambil dari arah yang berlawanan akan memberi kita titik tambahan yang sejauh mungkin dalam arah ini.

Implementasi fungsi helper cukup sederhana:

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

Salah satu kelebihan GJK adalah FarthestPointInDirection dapat diabstraksikan dan diterapkan pada poligon dan kurva. Berikut ini adalah implementasi dari FarthestPointInDirection untuk poligon.

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } } 

Jika Anda ingin melihat bagaimana bentuk lain akan diimplementasikan, maka periksa repositori Git dari posting ini , yang memperkenalkan implementasi untuk Circle .

Inilah cara titik bantu dalam arah (1,0) akan dihitung untuk angka A dan B:

1. Ambil titik paling jauh dari gambar A; ternyata menjadi titik B (1, -1) . (Anda dapat menghitungnya, seperti yang ditunjukkan oleh algoritma di atas, atau cukup melihatnya dengan melihat grafik).
2. Ambil titik paling jauh dari gambar B; ternyata menjadi titik F (-1, 1) .
3. Hitung B - F ; ternyata menjadi titik BF (2, -2) - itu akan menjadi tambahan .

Simpleks

Simpleks adalah contoh titik di sepanjang angka perbedaan Minkowski. Simpleks dapat memuat hingga tiga poin. GJK menggunakannya, mencoba membangun segitiga di sekitar titik asal untuk menentukan terjadinya tabrakan.

Konstruksi simpleks

Simpleks dibangun secara iteratif dengan menambahkan titik bantu dalam arah yang berbeda. Setiap titik bantu harus menunjuk ke arah yang baru, sehingga kita dapat secepat mungkin membangun simpleks yang mengandung titik asal. Kesulitannya terletak pada pemilihan arah untuk mendapatkan poin tambahan berikutnya.

Deteksi tabrakan dan pemilihan arah

Algoritme dasar hanya membangun simpleks dengan bantuan fungsi bantu, mencoba melampirkan titik asal pada gambar. Kita dapat memahami bahwa tidak ada tabrakan / persimpangan dengan memeriksa apakah titik bantu yang dihitung mencapai titik asal, dan jika tidak, maka titik asal harus berada di luar perbedaan Minkowski; oleh karena itu, kita dapat mengatakan bahwa tidak ada tabrakan / persimpangan.

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); } 

Semua kompleksitas dan operasi internal algoritma berada dalam simplex.CalculateDirection . Fungsi ini menentukan apakah asal dalam simpleks saat ini - jika demikian, itu akan kembali undefined ; jika tidak, itu akan mengembalikan arah baru untuk mendapatkan titik bantu, yang harus ditambahkan ke simpleks.

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } } 

Anda mungkin bertanya-tanya: mengapa kita tidak memeriksa segmen BC? Karena kita dapat dengan tanpa syarat mengecualikan bahwa asalnya adalah sepanjang tegak lurus. Karena titik B dan C sudah berada di simpleks, dan mereka tidak hanya ditambahkan, kita tahu bahwa mereka diperiksa dalam iterasi sebelumnya. Mereka dapat diperiksa sebagai bagian dari segitiga, atau sebagai segmen dari dua titik pertama dalam simpleks - tidak masalah. Oleh karena itu, kami dapat melewati pemeriksaan segmen BC dengan aman.

Penjelasan terperinci

Kami mendapat banyak kode, dan itu terlihat membingungkan. Di bawah ini saya akan menganalisis langkah-langkah algoritma untuk angka A dan B yang ditunjukkan di atas.

Poin angka A dan B:

1. Persiapan algoritma; kami mengambil (0,1) sebagai arah awal.
   
   

    // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); 

   
   
2. Kami mendapatkan poin tambahan pertama.
   
   

     // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); 

   
   Kami mendapatkan titik terjauh dari titik A di arah (0,1) dan dari titik B di arah (0,-1) .
   
   aFar: (0,1) dan bFar: (0,-1)
   
   Gunakan nilai-nilai ini untuk mendapatkan poin tambahan.
   
   Dukungan: aFar-bFar = (0,2)
   
   

     function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

   
   
3. Kami membalik arah untuk titik bantu berikutnya dan memulai iterasi, menghitung titik bantu baru.
   
   Dukungan: (0,-3)
   
   

     // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); 

4. Periksa apakah titik bantu telah mencapai titik asal; jika tidak, seharusnya tidak ada persimpangan. Jika dia mencapai titik asal, maka tambahkan titik ke simpleks.
   
   Dalam hal ini, titik bantu telah mencapai titik asal.
   
   arah: (0,-1)
   
   Dukungan: (0,-3)
   
   supportPoint.Dot (arah): 3
   
   

     // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); 

   
   
5. Pada tahap ini, simpleks adalah sebuah segmen, sehingga tidak dapat mengandung titik asal di dalam; tentukan arah baru untuk mencari titik bantu.
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. Kami mengambil titik terakhir yang ditambahkan ke simpleks dan menentukan arah ke asal, ini akan menjadi kebalikan dari titik ini.
      
      a: (0,-3) ao: (0,3)
      
      

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { 

   2. Karena simpleks adalah segmen, bukan segitiga, kami mengambil titik kedua segmen dan menghitung segmen simpleks.
      
      b: (0,2) ab: (0,5)
      
      

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); 

   3. Kami menghitung tegak lurus untuk segmen ini dan memverifikasi bahwa itu diarahkan ke asal. Ini akan menjadi arah baru untuk titik bantu berikutnya.
      
      abPerp: (5, 0)
      
      abPerp.Dot (ao) 0
      
      abPerp: (-5, 0)
      
      
      
      
      

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; 

6. Sekarang kita memiliki arahan untuk mencari titik tambahan berikutnya. Kami kembali ke awal siklus dan tidak keluar, karena sementara kami memiliki arah, dan persimpangan belum ditemukan.
   
   arah: (-5, 0)
   
   Dukungan: (-2,-2)
   
   supportPoint.Dot (arah): 10
   
   Titik bantu telah mencapai titik asal, jadi kita tidak bisa mengatakan bahwa tidak ada persimpangan.
   
   

     while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } 

7. Tambahkan titik bantu baru ke simpleks, membuat segitiga. Segitiga ini mungkin berisi asal, dan jika demikian, maka simpleks akan kembali undefined , dan bukan arah baru untuk pencarian.
   
   

     // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); 

   
   
   1. Ambil titik-titik simpleks segitiga.
      a: (-2,-2) b: (0,-3) c: (0,2) ao: (2,2)
      
      

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; 

   2. Ambil segmen ab dan ac.
      
      ab: (2,-1) ac: (2,4)
      
      

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); 

   3. Kami menghitung tegak lurus ke segmen ab, diarahkan dari simpleks.
      
      abperp: (-1,-2)
      
      

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } 

   4. Kami menentukan apakah asalnya berada di luar simpleks di luar ab.
      
      abPerp.Dot (ao): -6
      
      Asal tidak terletak di luar simpleks luar ab.
      
      
      
      
      

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } 

   5. Kami menghitung tegak lurus ke segmen ac yang diarahkan dari simpleks.
      
      acPerp: (-4,2) -4.2 (-4,2)
      
      

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } 

   6. Tentukan apakah asalnya berada di luar simpleks di luar ac.
      
      acPerp.Dot (ao): -4
      
      Asal bukan di luar simpleks luar ab.
      
      
      
      
      

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } 

   7. Karena AB dan AC diperiksa dalam iterasi ini, dan kita tahu bahwa BC diperiksa dalam iterasi sebelumnya, titik asal harus terletak di dalam simpleks, sehingga tabrakan / persimpangan terdeteksi - menginformasikan tentang ini, fungsi akan kembali undefined .
      
      
      
8. Karena tabrakan telah terdeteksi, loop keluar dan informasi Collision tentang tabrakan antara dua angka dikembalikan.
   
   

     direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); 

Kesimpulan

Saya harap artikel ini membantu Anda memahami algoritma GJK. Algoritme memberikan jawaban ya / tidak tentang adanya konflik antara kedua tokoh. Contoh yang berfungsi dengan poligon dan lingkaran dapat dilihat di repositori untuk posting ini . Anda dapat memperluas kode ini dengan algoritma dan teknik tambahan dengan mencoba untuk mendapatkan jarak penetrasi antara dua angka, tabrakan normal, dan titik kontak. Pos dyn4j memiliki tautan ke sumber daya yang baik pada berbagai algoritma pengenalan tabrakan / respons; jika Anda ingin memperluas GJK, maka Anda harus mempelajarinya.