Tutorial Fisika Video Game - Bagian II: Deteksi Tabrakan untuk Benda Padat

Ini adalah Bagian II dari seri tiga bagian kami tentang fisika video game. Untuk sisa seri ini, lihat:

Bagian I: Pengantar Dinamika Tubuh Kaku
Bagian III: Simulasi Tubuh Kaku Terkendala

Di Bagian I dari seri ini, kami menjelajahi benda tegar dan gerakannya. Dalam diskusi itu, bagaimanapun, objek tidak berinteraksi satu sama lain. Tanpa beberapa pekerjaan tambahan, benda tegar yang disimulasikan dapat menembus satu sama lain, atau "saling menembus", yang tidak diinginkan dalam sebagian besar kasus.

Untuk mensimulasikan perilaku benda padat secara lebih realistis, kita harus memeriksa apakah mereka bertabrakan satu sama lain setiap kali bergerak, dan jika mereka bergerak, kita harus melakukan sesuatu, seperti menerapkan gaya yang mengubah kecepatannya, jadi bahwa mereka akan bergerak ke arah yang berlawanan. Di sinilah pemahaman fisika tabrakan sangat penting bagi pengembang game.

Di Bagian II, kita akan membahas langkah deteksi tabrakan, yang terdiri dari menemukan pasangan benda yang bertabrakan di antara sejumlah besar benda yang mungkin tersebar di dunia 2D atau 3D. Dalam angsuran berikutnya, dan terakhir, kita akan berbicara lebih banyak tentang "menyelesaikan" tabrakan ini untuk menghilangkan interpenetrasi.

Untuk tinjauan konsep aljabar linier yang dirujuk dalam artikel ini, Anda dapat merujuk ke kursus kilat aljabar linier di Bagian I.

Fisika Tabrakan di Video Game

Dalam konteks simulasi benda tegar, tumbukan terjadi ketika bentuk dua benda tegar berpotongan, atau ketika jarak antara bentuk-bentuk ini turun di bawah toleransi yang kecil.

Jika kita memiliki n benda dalam simulasi kita, kompleksitas komputasi untuk mendeteksi tabrakan dengan tes berpasangan adalah O ( n 2 ) , angka yang membuat ilmuwan komputer ngeri. Jumlah tes berpasangan meningkat secara kuadrat dengan jumlah tubuh, dan menentukan apakah dua bentuk, dalam posisi dan orientasi yang sewenang-wenang, bertabrakan sudah tidak murah. Untuk mengoptimalkan proses deteksi tabrakan, kami biasanya membaginya menjadi dua fase: fase luas dan fase sempit .

Fase luas bertanggung jawab untuk menemukan pasangan benda tegar yang berpotensi bertabrakan, dan mengecualikan pasangan yang tentu saja tidak bertabrakan, dari seluruh rangkaian benda yang ada dalam simulasi. Langkah ini harus dapat menskalakan dengan sangat baik dengan jumlah benda tegar untuk memastikan kita tetap baik di bawah kompleksitas waktu O ( n 2 ) . Untuk mencapai itu, fase ini umumnya menggunakan partisi ruang yang digabungkan dengan volume pembatas yang menetapkan batas atas untuk tumbukan.

Fase sempit beroperasi pada pasangan benda tegar yang ditemukan oleh fase luas yang mungkin bertabrakan. Ini adalah langkah penyempurnaan di mana kami menentukan apakah tabrakan benar-benar terjadi, dan untuk setiap tabrakan yang ditemukan, kami menghitung titik kontak yang akan digunakan untuk menyelesaikan tabrakan nanti.

Pada bagian selanjutnya kita akan berbicara tentang beberapa algoritma yang dapat digunakan dalam fase luas dan fase sempit.

Fase Luas

Dalam fase fisika tumbukan yang luas untuk video game, kita perlu mengidentifikasi pasangan benda tegar mana yang mungkin bertabrakan. Benda ini mungkin memiliki bentuk kompleks seperti poligon dan polihedron, dan yang dapat kita lakukan untuk mempercepatnya adalah dengan menggunakan bentuk yang lebih sederhana untuk mencakup objek. Jika volume pembatas ini tidak berpotongan, maka bentuk sebenarnya juga tidak berpotongan. Jika mereka berpotongan, maka bentuk sebenarnya mungkin berpotongan.

Beberapa jenis volume pembatas yang populer adalah kotak pembatas berorientasi (OBB), lingkaran dalam 2D, dan bola dalam 3D. Mari kita lihat salah satu volume pembatas paling sederhana: kotak pembatas sumbu-selaras (AABB) .

AABB mendapatkan banyak cinta dari programmer fisika karena sederhana dan menawarkan pengorbanan yang baik. AABB 2 dimensi dapat diwakili oleh struct seperti ini dalam bahasa C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Bidang min mewakili lokasi sudut kiri bawah kotak dan bidang max mewakili sudut kanan atas.

Untuk menguji apakah dua AABB berpotongan, kita hanya perlu mengetahui apakah proyeksinya berpotongan pada semua sumbu koordinat:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Kode ini memiliki logika yang sama dengan fungsi b2TestOverlap dari mesin Box2D (versi 2.3.0). Ini menghitung perbedaan antara min dan max dari kedua AABB, di kedua sumbu, di kedua pesanan. Jika salah satu dari nilai ini lebih besar dari nol, AABB tidak berpotongan.

Meskipun tes tumpang tindih AABB murah, itu tidak akan banyak membantu jika kita masih melakukan tes berpasangan untuk setiap pasangan yang mungkin karena kita masih memiliki kompleksitas waktu O ( n 2 ) yang tidak diinginkan. Untuk meminimalkan jumlah uji tumpang tindih AABB, kita dapat menggunakan semacam partisi ruang , yang bekerja dengan prinsip yang sama seperti indeks basis data yang mempercepat kueri. (Basis data geografis, seperti PostGIS, sebenarnya menggunakan struktur data dan algoritme yang serupa untuk indeks spasialnya.) Namun, dalam kasus ini, AABB akan bergerak terus-menerus, jadi umumnya, kita harus membuat ulang indeks setelah setiap langkah simulasi.

Ada banyak algoritme partisi ruang dan struktur data yang dapat digunakan untuk ini, seperti grid seragam, quadtree dalam 2D, octrees dalam 3D, dan hashing spasial. Mari kita lihat lebih dekat dua algoritma partisi spasial yang populer: sort and sweep, dan bounding volume hierarchies (BVH).

Algoritma Sortir dan Sapu

Metode sort and sweep (atau dikenal sebagai sweep and prune ) adalah salah satu pilihan favorit di antara programmer fisika untuk digunakan dalam simulasi benda tegar. Mesin Bullet Physics, misalnya, memiliki implementasi metode ini di kelas btAxisSweep3 .

Proyeksi satu AABB ke sumbu koordinat tunggal pada dasarnya adalah interval [ b , e ] (yaitu, awal dan akhir). Dalam simulasi kita, kita akan memiliki banyak benda tegar, dan dengan demikian, banyak AABB, dan itu berarti banyak interval. Kami ingin mencari tahu interval mana yang berpotongan.

Dalam algoritma sort and sweep, kami memasukkan semua nilai b dan e dalam satu daftar dan mengurutkannya secara menaik berdasarkan nilai skalarnya. Kemudian kami menyapu atau melintasi daftar. Setiap kali nilai b ditemukan, interval yang sesuai disimpan dalam daftar interval aktif yang terpisah , dan setiap kali nilai e ditemukan, interval yang sesuai akan dihapus dari daftar interval aktif. Setiap saat, semua interval aktif berpotongan. (Lihat Tesis Ph. D David Baraff, hlm. 52 untuk detailnya. Saya sarankan menggunakan alat online ini untuk melihat file postscript.) Daftar interval dapat digunakan kembali pada setiap langkah simulasi, di mana kita dapat menyortir ulang secara efisien daftar ini menggunakan pengurutan penyisipan, yang pandai menyortir daftar yang hampir diurutkan.

Dalam dua dan tiga dimensi, menjalankan sortir dan sapuan, seperti dijelaskan di atas, pada satu sumbu koordinat akan mengurangi jumlah pengujian persimpangan AABB langsung yang harus dilakukan, tetapi hasilnya mungkin lebih baik pada satu sumbu koordinat daripada yang lain. Oleh karena itu, variasi yang lebih canggih dari algoritma sort and sweep diimplementasikan. Dalam bukunya Real-Time Collision Detection (halaman 336), Christer Ericson menyajikan variasi yang efisien di mana ia menyimpan semua AABB dalam satu larik, dan untuk setiap lari pengurutan dan sapuan, satu sumbu koordinat dipilih dan larik diurutkan berdasarkan nilai min AABB di sumbu yang dipilih, menggunakan quicksort. Kemudian, array dilintasi dan uji tumpang tindih AABB dilakukan. Untuk menentukan sumbu berikutnya yang harus digunakan untuk pengurutan, varians dari pusat AABBs dihitung, dan sumbu dengan varians yang lebih besar dipilih untuk langkah berikutnya.

Pohon Volume Batas Dinamis

Metode partisi spasial lain yang berguna adalah pohon volume pembatas dinamis , juga dikenal sebagai Dbvt . Ini adalah jenis hierarki volume pembatas .

Dbvt adalah pohon biner di mana setiap node memiliki AABB yang mengikat semua AABB dari anak-anaknya. AABB dari benda tegar itu sendiri terletak di simpul daun. Biasanya, Dbvt "ditanyakan" dengan memberikan AABB yang ingin kami deteksi persimpangannya. Operasi ini efisien karena anak-anak dari node yang tidak memotong AABB yang ditanyakan tidak perlu diuji tumpang tindih. Dengan demikian, kueri tabrakan AABB dimulai dari akar, dan berlanjut secara rekursif melalui pohon hanya untuk node AABB yang berpotongan dengan AABB yang ditanyakan. Pohon dapat diseimbangkan melalui rotasi pohon, seperti pada pohon AVL.

Box2D memiliki implementasi Dbvt yang canggih di kelas b2DynamicTree . Kelas b2BroadPhase bertanggung jawab untuk melakukan fase luas, dan menggunakan instance b2DynamicTree untuk melakukan kueri AABB.

Fase Sempit

Setelah fase luas fisika tabrakan video game, kami memiliki satu set pasangan benda tegar yang berpotensi bertabrakan. Jadi, untuk setiap pasangan, mengingat bentuk, posisi, dan orientasi kedua benda, kita perlu mencari tahu apakah mereka memang bertabrakan; jika mereka berpotongan atau jika jaraknya berada di bawah nilai toleransi yang kecil. Kita juga perlu mengetahui titik kontak antara benda yang bertabrakan, karena ini diperlukan untuk menyelesaikan tumbukan nanti.

Bentuk Cembung dan Cekung

Sebagai aturan umum fisika video game, tidak mudah untuk menentukan apakah dua bentuk sembarang berpotongan, atau menghitung jarak di antara keduanya. Namun, satu sifat yang sangat penting dalam menentukan seberapa sulitnya, adalah kecembungan bentuknya. Bentuk dapat berupa cembung atau cekung dan bentuk cekung lebih sulit untuk dikerjakan, jadi kami memerlukan beberapa strategi untuk menghadapinya.

Dalam bentuk cembung, segmen garis antara dua titik dalam bentuk selalu jatuh sepenuhnya di dalam bentuk. Namun untuk bentuk cekung (atau "tidak cembung"), hal yang sama tidak berlaku untuk semua segmen garis yang mungkin menghubungkan titik-titik dalam bentuk. Jika Anda dapat menemukan setidaknya satu segmen garis yang berada di luar bentuk sama sekali, maka bentuknya cekung.

Secara komputasi, diinginkan bahwa semua bentuk cembung dalam simulasi, karena kami memiliki banyak algoritma uji jarak dan persimpangan yang kuat yang bekerja dengan bentuk cembung. Tidak semua objek akan menjadi cembung, dan biasanya kita mengatasinya dengan dua cara: lambung cembung dan dekomposisi cembung.

Lambung cembung suatu bentuk adalah bentuk cembung terkecil yang sepenuhnya memuatnya. Untuk poligon cekung dalam dua dimensi, itu akan seperti memalu paku di setiap titik dan melilitkan karet gelang di sekitar semua paku. Untuk menghitung convex hull untuk poligon atau polihedron, atau lebih umum, untuk sekumpulan titik, algoritma yang baik untuk digunakan adalah algoritma quickhull , yang memiliki kompleksitas waktu rata-rata O ( n log n ) .

Jelas, jika kita menggunakan lambung cembung untuk mewakili objek cekung, itu akan kehilangan sifat cekungnya. Perilaku yang tidak diinginkan, seperti tabrakan "hantu" dapat menjadi jelas, karena objek akan tetap memiliki representasi grafis cekung. Sebagai contoh, sebuah mobil biasanya memiliki bentuk cekung, dan jika kita menggunakan lambung cembung untuk menggambarkannya secara fisik dan kemudian meletakkan sebuah kotak di atasnya, kotak itu mungkin tampak mengambang di ruang atas.

Secara umum, lambung cembung seringkali cukup baik untuk mewakili objek cekung, baik karena tumbukan yang tidak realistis tidak terlalu terlihat, atau sifat cekungnya tidak penting untuk apa pun yang sedang disimulasikan. Namun, dalam beberapa kasus, kita mungkin ingin objek cekung berperilaku seperti bentuk cekung secara fisik. Misalnya, jika kita menggunakan lambung cembung untuk mewakili mangkuk secara fisik, kita tidak akan bisa memasukkan apa pun ke dalamnya. Objek hanya akan mengapung di atasnya. Dalam hal ini, kita dapat menggunakan dekomposisi cembung dari bentuk cekung.

Algoritma dekomposisi cembung menerima bentuk cekung dan mengembalikan satu set bentuk cembung yang penyatuannya identik dengan bentuk cekung asli. Beberapa bentuk cekung hanya dapat diwakili oleh sejumlah besar bentuk cembung, dan ini mungkin menjadi sangat mahal untuk dihitung dan digunakan. Namun, pendekatan seringkali cukup baik, dan karenanya, algoritma seperti V-HACD menghasilkan satu set kecil polihedron cembung dari polihedron cekung.

Namun, dalam banyak kasus fisika tumbukan, dekomposisi cembung dapat dibuat dengan tangan, oleh seorang seniman. Ini menghilangkan kebutuhan untuk memajaki kinerja dengan algoritma dekomposisi. Karena kinerja adalah salah satu aspek terpenting dalam simulasi waktu nyata, biasanya ide yang baik untuk membuat representasi fisik yang sangat sederhana untuk objek grafik yang kompleks adalah ide yang bagus. Gambar di bawah menunjukkan satu kemungkinan dekomposisi cembung dari mobil 2D menggunakan sembilan bentuk cembung.

Pengujian untuk Persimpangan - Teorema Sumbu Pemisah

Teorema sumbu pemisah (SAT) menyatakan bahwa dua bentuk cembung tidak berpotongan jika dan hanya jika ada setidaknya satu sumbu di mana proyeksi ortogonal bentuk pada sumbu ini tidak berpotongan.

Biasanya lebih intuitif secara visual untuk menemukan garis dalam 2D ​​atau bidang dalam 3D yang memisahkan kedua bentuk, yang secara efektif merupakan prinsip yang sama. Vektor ortogonal terhadap garis dalam 2D, atau vektor normal bidang dalam 3D, dapat digunakan sebagai “sumbu pemisah”.

Mesin fisika permainan memiliki sejumlah kelas bentuk yang berbeda, seperti lingkaran (bola dalam 3D), tepi (segmen garis tunggal), dan poligon cembung (polihedron dalam 3D). Untuk setiap pasangan tipe bentuk, mereka memiliki algoritma pendeteksian tabrakan yang spesifik. Yang paling sederhana mungkin adalah algoritma lingkaran-lingkaran:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Meskipun SAT berlaku untuk lingkaran, lebih mudah untuk memeriksa apakah jarak antara pusatnya lebih kecil daripada jumlah jari-jarinya. Oleh karena itu, SAT digunakan dalam algoritme deteksi tumbukan untuk pasangan kelas bentuk tertentu, seperti poligon cembung melawan poligon cembung (atau polihedron dalam 3D).

Untuk pasangan bentuk apa pun, ada jumlah sumbu tak terbatas yang dapat kita uji untuk pemisahan. Dengan demikian, menentukan sumbu mana yang akan diuji terlebih dahulu sangat penting untuk implementasi SAT yang efisien. Untungnya, ketika menguji jika sepasang poligon cembung bertabrakan, kita dapat menggunakan normal tepi sebagai sumbu pemisah potensial. Vektor normal n dari sebuah tepi tegak lurus terhadap vektor tepi, dan menunjuk di luar poligon. Untuk setiap sisi dari setiap poligon, kita hanya perlu mencari tahu apakah semua simpul dari poligon lain berada di depan tepi.

Jika ada tes yang lolos – yaitu, jika, untuk sembarang sisi, semua simpul dari poligon lain berada di depannya – maka poligon tidak berpotongan. Aljabar linier memberikan rumus mudah untuk pengujian ini: diberikan sisi pada bentuk pertama dengan simpul a dan b dan simpul v pada bentuk lainnya, jika ( v - a ) · n lebih besar dari nol, maka simpul tersebut berada di depan dari tepi.

Untuk polihedron, kita dapat menggunakan normal wajah dan juga perkalian silang dari semua kombinasi tepi dari setiap bentuk. Kedengarannya seperti banyak hal untuk diuji; namun, untuk mempercepat, kita dapat menyimpan sumbu pemisah terakhir yang kita gunakan dan mencoba menggunakannya lagi dalam langkah simulasi berikutnya. Jika sumbu pemisah yang di-cache tidak memisahkan bentuk lagi, kita dapat mencari sumbu baru mulai dari face atau edge yang berdekatan dengan face atau edge sebelumnya. Itu berhasil karena tubuh sering kali tidak banyak bergerak atau berputar di antara langkah-langkah.

Box2D menggunakan SAT untuk menguji apakah dua poligon cembung berpotongan dalam algoritma deteksi tabrakan poligon-poligonnya di b2CollidePolygon.cpp.

Komputasi Jarak - Algoritma Gilbert-Johnson-Keerthi

Dalam banyak kasus fisika tumbukan, kita ingin menganggap benda-benda bertabrakan tidak hanya jika mereka benar-benar berpotongan, tetapi juga jika mereka sangat dekat satu sama lain, yang mengharuskan kita untuk mengetahui jarak di antara mereka. Algoritma Gilbert-Johnson-Keerthi (GJK) menghitung jarak antara dua bentuk cembung dan juga titik terdekatnya. Ini adalah algoritma elegan yang bekerja dengan representasi implisit dari bentuk cembung melalui fungsi pendukung, jumlah Minkowski, dan simpleks, seperti yang dijelaskan di bawah ini.

Fungsi Dukungan

Fungsi pendukung s A ( d ) mengembalikan sebuah titik pada batas bentuk A yang memiliki proyeksi tertinggi pada vektor d . Secara matematis, ia memiliki hasil kali titik tertinggi dengan d . Ini disebut titik dukungan , dan operasi ini juga dikenal sebagai pemetaan dukungan . Secara geometris, titik ini merupakan titik terjauh pada bentuk pada arah d .

Menemukan titik dukungan pada poligon relatif mudah. Untuk titik dukungan untuk vektor d , Anda hanya perlu mengulang simpulnya dan menemukan simpul yang memiliki produk titik tertinggi dengan d , seperti ini:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Namun, kekuatan sebenarnya dari fungsi pendukung adalah membuatnya mudah untuk bekerja dengan bentuk seperti kerucut, silinder, dan elips, antara lain. Agak sulit untuk menghitung jarak antara bentuk-bentuk tersebut secara langsung, dan tanpa algoritma seperti GJK Anda biasanya harus mendiskritkannya menjadi poligon atau polihedron untuk menyederhanakannya. Namun, hal itu dapat menyebabkan masalah lebih lanjut karena permukaan polihedron tidak semulus permukaan, katakanlah, bola, kecuali jika polihedron sangat detail, yang dapat menyebabkan kinerja yang buruk selama deteksi tabrakan. Efek samping lain yang tidak diinginkan mungkin muncul juga; misalnya, bola "polihedral" mungkin tidak menggelinding dengan mulus.

Untuk mendapatkan titik tumpuan bola yang berpusat di titik asal, kita hanya perlu menormalkan d (yaitu, hitung d / || d || , yaitu vektor dengan panjang 1 (satuan panjang) yang masih menunjuk ke arah yang sama dari d ) dan kemudian kita kalikan dengan jari-jari bola.

Periksa makalah Gino van den Bergen untuk menemukan lebih banyak contoh fungsi pendukung untuk silinder, dan kerucut, di antara bentuk lainnya.

Objek kita tentu saja akan dipindahkan dan diputar dari titik asal di ruang simulasi, jadi kita harus mampu menghitung titik dukungan untuk bentuk yang diubah. Kami menggunakan transformasi affine T ( x ) = R x + c untuk memindahkan dan memutar objek kami, di mana c adalah vektor perpindahan dan R adalah matriks rotasi . Transformasi ini pertama memutar objek tentang asal, dan kemudian menerjemahkannya. Fungsi pendukung untuk bentuk transformasi A adalah:

Jumlah Minkowski

Jumlah Minkowski dari dua bentuk A dan B didefinisikan sebagai:

Itu berarti kita menghitung jumlah untuk semua titik yang terdapat di A dan B . Hasilnya seperti menggembungkan A dengan B .

Demikian pula, kami mendefinisikan perbedaan Minkowski sebagai:

yang juga dapat kita tulis sebagai jumlah Minkowski dari A dengan -B :

Untuk cembung A dan B , A⊕B juga cembung.

Salah satu properti yang berguna dari perbedaan Minkowski adalah bahwa jika mengandung asal ruang, bentuk berpotongan, seperti yang dapat dilihat pada gambar sebelumnya. Mengapa demikian? Karena jika dua bentuk berpotongan, mereka memiliki setidaknya satu titik yang sama, yang terletak di lokasi yang sama dalam ruang, dan perbedaannya adalah vektor nol, yang sebenarnya adalah titik asal.

Fitur bagus lainnya dari perbedaan Minkowski adalah jika tidak mengandung asal, jarak minimum antara asal dan perbedaan Minkowski adalah jarak antara bentuk.

Jarak antara dua bentuk didefinisikan sebagai:

Dengan kata lain, jarak antara A dan B adalah panjang vektor terpendek dari A ke B . Vektor ini terdapat dalam A⊖B dan merupakan vektor dengan panjang terkecil, yang akibatnya paling dekat dengan titik asal.

Umumnya tidak mudah untuk secara eksplisit membangun jumlah Minkowski dari dua bentuk. Untungnya, kami juga dapat menggunakan pemetaan dukungan di sini, karena:

Simpleks

Algoritma GJK secara iteratif mencari titik pada selisih Minkowski yang paling dekat dengan titik asal. Ia melakukannya dengan membangun serangkaian simpleks yang lebih dekat ke titik asal di setiap iterasi. Simpleks – atau lebih spesifik lagi, k-simpleks untuk bilangan bulat k – adalah lambung cembung dari k + 1 titik yang saling bebas dalam ruang k-dimensi. Artinya, jika untuk dua titik mereka tidak boleh bertepatan, untuk tiga titik mereka juga tidak boleh terletak pada garis yang sama, dan jika kita memiliki empat titik, mereka juga tidak boleh terletak pada bidang yang sama. Oleh karena itu, simpleks 0 adalah titik, simpleks 1 adalah ruas garis, simpleks 2 adalah segitiga, dan 3 simpleks adalah tetrahedron. Jika kita menghapus sebuah titik dari sebuah simpleks, kita mengurangi dimensinya satu per satu, dan jika kita menambahkan sebuah titik ke sebuah simpleks, kita menambah dimensinya satu per satu.

GJK beraksi

Mari kita gabungkan ini semua untuk melihat bagaimana GJK bekerja. Untuk menentukan jarak antara dua bangun A dan B , kita mulai dengan mengambil selisih Minkowski A⊖B . Kami mencari titik terdekat ke titik asal pada bentuk yang dihasilkan, karena jarak ke titik ini adalah jarak antara dua bentuk asli. Kami memilih beberapa titik v di A⊖B , yang akan menjadi perkiraan jarak kami. Kami juga mendefinisikan himpunan titik kosong W , yang akan berisi titik-titik dalam simpleks pengujian saat ini.

Kemudian kita memasuki lingkaran. Kita mulai dengan mendapatkan titik tumpuan w = s A⊖B (- v ) , titik pada A⊖B yang proyeksinya ke v paling dekat dengan titik asal.

Jika || w || tidak jauh berbeda dengan || v || dan sudut di antara mereka tidak banyak berubah (menurut beberapa toleransi yang telah ditentukan), itu berarti algoritme telah konvergen dan kami dapat kembali || v || sebagai jarak.

Jika tidak, kita tambahkan w ke W . Jika lambung cembung dari W (yaitu, simpleks) berisi titik asal, bentuknya berpotongan, dan ini juga berarti kita selesai. Jika tidak, kami menemukan titik dalam simpleks yang paling dekat dengan titik asal dan kemudian kami mengatur ulang v menjadi pendekatan terdekat yang baru ini. Akhirnya, kami menghapus titik apa pun di W yang tidak berkontribusi pada perhitungan titik terdekat. (Misalnya, jika kita memiliki sebuah segitiga, dan titik terdekat ke titik asal terletak di salah satu sisinya, kita dapat menghapus titik dari W yang bukan titik dari sisi ini.) Kemudian kita ulangi langkah yang sama sampai algoritma konvergen.

Gambar berikut menunjukkan contoh empat iterasi dari algoritma GJK. Objek biru mewakili perbedaan Minkowski A⊖B dan vektor hijau adalah v . Anda dapat melihat di sini bagaimana v mengasah pada titik terdekat dengan titik asal.

Untuk penjelasan rinci dan mendalam tentang algoritma GJK, lihat makalah Implementasi GJK Cepat dan Kuat untuk Deteksi Tabrakan Objek Cembung , oleh Gino van den Bergen. Blog untuk mesin fisika dyn4j juga memiliki pos yang bagus di GJK.

Box2D memiliki implementasi algoritma GJK di b2Distance.cpp, dalam fungsi b2Distance . Itu hanya menggunakan GJK selama waktu perhitungan dampak dalam algoritmenya untuk deteksi tabrakan berkelanjutan (topik yang akan kita bahas lebih lanjut).

Mesin fisika Chimpunk menggunakan GJK untuk semua deteksi tabrakan, dan implementasinya ada di cpCollision.c, dalam fungsi GJK . Jika algoritma GJK melaporkan persimpangan, masih perlu diketahui titik kontaknya, beserta kedalaman penetrasinya. Untuk melakukan itu, ia menggunakan Algoritma Expanding Polytope, yang akan kita jelajahi selanjutnya.

Menentukan Kedalaman Penetrasi - Algoritma Expanding Polytope

Sebagaimana dinyatakan di atas, jika bentuk A dan B berpotongan, GJK akan menghasilkan simpleks W yang berisi titik asal, di dalam perbedaan Minkowski A⊖B . Pada tahap ini, kita hanya mengetahui bahwa bentuk-bentuk tersebut berpotongan, tetapi dalam desain banyak sistem pendeteksi tabrakan, diinginkan untuk dapat menghitung berapa banyak persimpangan yang kita miliki, dan titik apa yang dapat kita gunakan sebagai titik kontak, sehingga kami menangani tabrakan dengan cara yang realistis. Expanding Polytope Algorithm (EPA) memungkinkan kita untuk memperoleh informasi itu, mulai dari GJK tinggalkan: dengan simpleks yang berisi asal.

Kedalaman penetrasi adalah panjang vektor terjemahan minimum (MTV), yang merupakan vektor terkecil di mana kita dapat menerjemahkan bentuk berpotongan untuk memisahkannya dari bentuk lainnya.

Ketika dua bentuk berpotongan, perbedaan Minkowski mereka berisi titik asal, dan titik pada batas perbedaan Minkowski yang paling dekat dengan titik asal adalah MTV. Algoritme EPA menemukan titik itu dengan memperluas simpleks yang diberikan GJK kepada kita menjadi poligon; berturut-turut membagi tepinya dengan simpul baru.

Pertama, kita menemukan tepi simpleks yang paling dekat dengan titik asal, dan menghitung titik tumpuan dalam perbedaan Minkowski dalam arah yang normal terhadap tepi (yaitu tegak lurus dan menunjuk ke luar poligon). Kemudian kami membagi tepi ini dengan menambahkan titik dukungan ini padanya. Kami mengulangi langkah-langkah ini sampai panjang dan arah vektor tidak banyak berubah. Setelah algoritme konvergen, kami memiliki MTV dan kedalaman penetrasi.

Menggunakan GJK dalam kombinasi dengan EPA, kami mendapatkan deskripsi rinci tentang tabrakan, tidak peduli apakah objek sudah berpotongan, atau cukup dekat untuk dianggap tabrakan.

Algoritma EPA dijelaskan dalam makalah Proximity Query dan Penetration Depth Computation pada Objek Game 3D , juga ditulis oleh Gino van den Bergen. Blog dyn4j juga memiliki postingan tentang EPA.

Deteksi Tabrakan Terus Menerus

Teknik fisika video game yang disajikan sejauh ini melakukan deteksi tabrakan untuk snapshot statis dari simulasi. Ini disebut deteksi tabrakan diskrit , dan mengabaikan apa yang terjadi antara langkah sebelumnya dan saat ini. Untuk alasan ini, beberapa tabrakan mungkin tidak terdeteksi, terutama untuk objek yang bergerak cepat. Masalah ini dikenal sebagai tunneling .

Teknik deteksi tabrakan terus menerus mencoba menemukan ketika dua benda bertabrakan antara langkah simulasi sebelumnya dan saat ini. Mereka menghitung waktu tumbukan , sehingga kita dapat kembali ke masa lalu dan memproses tumbukan pada titik itu.

Waktu tumbukan (atau waktu kontak) t c adalah waktu saat jarak antara dua benda adalah nol. Jika kita dapat menulis sebuah fungsi untuk jarak antara dua benda sepanjang waktu, yang ingin kita cari adalah akar terkecil dari fungsi ini. Dengan demikian, waktu perhitungan dampak adalah masalah pencarian akar .

Untuk perhitungan waktu tumbukan, kita mempertimbangkan keadaan (posisi dan orientasi) benda pada langkah sebelumnya pada waktu t i -1 , dan pada langkah saat ini pada waktu t i . Untuk mempermudah, kami mengasumsikan gerakan linier di antara langkah-langkah.

Mari kita sederhanakan masalahnya dengan menganggap bentuknya adalah lingkaran. Untuk dua lingkaran C 1 dan C 2 , dengan jari-jari r 1 dan r 2 , di mana pusat massanya x 1 dan x 2 berimpit dengan pusat massanya (yaitu, mereka secara alami berputar di sekitar pusat massanya), kita dapat menulis fungsi jarak sebagai:

Mengingat gerak linier antara langkah, kita dapat menulis fungsi berikut untuk posisi C 1 dari t i -1 ke t i

Ini adalah interpolasi linier dari x 1 ( t i -1 ) ke x 1 ( t i ) . Hal yang sama dapat dilakukan untuk x 2 . Untuk interval ini kita dapat menulis fungsi jarak lain:

Tetapkan ekspresi ini sama dengan nol dan Anda mendapatkan persamaan kuadrat pada t . Akar dapat ditemukan langsung menggunakan rumus kuadrat. Jika lingkaran tidak berpotongan, rumus kuadrat tidak akan memiliki solusi. Jika mereka melakukannya, itu mungkin menghasilkan satu atau dua akar. Jika hanya memiliki satu akar, nilai itu adalah waktu tumbukan. Jika memiliki dua akar, yang terkecil adalah waktu tumbukan dan yang lainnya adalah waktu ketika lingkaran terpisah. Perhatikan bahwa waktu tumbukan di sini adalah angka dari 0 hingga 1. Ini bukan waktu dalam detik; itu hanya angka yang dapat kita gunakan untuk menginterpolasi keadaan tubuh ke lokasi yang tepat di mana tabrakan terjadi.

Deteksi Tabrakan Berkelanjutan untuk Non-Lingkaran

Menulis fungsi jarak untuk jenis bentuk lain itu sulit, terutama karena jaraknya bergantung pada orientasinya. Untuk alasan ini, kami biasanya menggunakan algoritme iteratif yang memindahkan objek lebih dekat dan lebih dekat pada setiap iterasi hingga cukup dekat untuk dianggap bertabrakan.

Algoritme kemajuan konservatif menggerakkan benda ke depan (dan memutarnya) secara berulang. Dalam setiap iterasi itu menghitung batas atas untuk perpindahan. Algoritma asli disajikan dalam Tesis PhD Brian Mirtich (bagian 2.3.2), yang mempertimbangkan gerakan balistik benda. Makalah ini oleh Erwin Coumans (penulis Bullet Physics Engine) menyajikan versi yang lebih sederhana yang menggunakan kecepatan linier dan sudut konstan.

Algoritme menghitung titik terdekat antara bentuk A dan B , menggambar vektor dari satu titik ke titik lainnya, dan memproyeksikan kecepatan pada vektor ini untuk menghitung batas atas gerak. Ini menjamin bahwa tidak ada titik pada tubuh yang akan bergerak melampaui proyeksi ini. Kemudian ia memajukan tubuh ke depan dengan jumlah ini dan mengulangi sampai jarak jatuh di bawah nilai toleransi yang kecil.

Mungkin diperlukan terlalu banyak iterasi untuk konvergen dalam beberapa kasus, misalnya, ketika kecepatan sudut salah satu benda terlalu tinggi.

Menyelesaikan Tabrakan

Setelah tabrakan terdeteksi, perlu untuk mengubah gerakan objek yang bertabrakan dengan cara yang realistis, seperti menyebabkan mereka terpental satu sama lain. Dalam angsuran berikutnya dan terakhir dalam teori ini, kita akan membahas beberapa metode populer untuk menyelesaikan tabrakan dalam video game.

Referensi

Jika Anda tertarik untuk memperoleh pemahaman yang lebih mendalam tentang fisika tumbukan seperti algoritma dan teknik pendeteksian tumbukan, buku Real-Time Collision Detection , oleh Christer Ericson, adalah buku yang harus dimiliki.

Karena deteksi tabrakan sangat bergantung pada geometri, artikel Toptal's Computational Geometry in Python: From Theory to Application adalah pengantar yang sangat baik untuk topik ini.