Meningkatkan Simulasi dan Kinerja dengan Solver Fisika Tingkat Lanjut

Pada tahun 2016, kami menambahkan dukungan untuk serangkaian batasan fisika baru yang beragam, mendorong pengembang untuk beralih ke pemecah masalah baru dan memperluas kemampuan kreatif mesin fisika. Setiap tempat baru menggunakan pemecah masalah PGS secara default, dengan opsi untuk kembali ke pemecah masalah klasik.

Kami mengatasi beberapa masalah stabilitas yang terkait dengan perbedaan massa yang tinggi dan mekanisme yang kompleks melalui pengenalan pemecah masalah hibrida LDL-PGS pada pertengahan 2018. Hal ini membuat pemecah masalah lama menjadi usang, dan pemecah masalah tersebut dinonaktifkan sepenuhnya pada tahun 2019, sehingga secara otomatis memigrasi semua tempat ke PGS.

Pada 2019, kinerja ditingkatkan lebih lanjut dengan menggunakan multi-threading yang membagi simulasi menjadi tugas-tugas yang terdiri dari pulau-pulau terhubung dari bagian-bagian yang disimulasikan. Kami masih menghadapi masalah kinerja terkait LDL yang akhirnya kami selesaikan pada awal 2020.

Mesin fisika masih terus ditingkatkan dan dioptimalkan untuk kinerja, dan kami berencana menambahkan fitur-fitur baru di masa mendatang.

Menerapkan Hukum Fisika

Tujuan utama dari mesin fisika adalah mensimulasikan gerakan benda-benda dalam lingkungan virtual. Dalam mesin fisika kami, kami berfokus pada benda-benda yang kaku, yang bertabrakan, dan memiliki keterbatasan satu sama lain.

Mesin fisika disusun dalam dua fase: deteksi tabrakan dan pemecahan. Deteksi tabrakan menemukan persimpangan antara geometri yang terkait dengan benda-benda kaku, menghasilkan informasi tabrakan yang sesuai seperti titik tabrakan, normal, dan kedalaman penetrasi. Kemudian, pemecah memperbarui gerakan benda-benda kaku di bawah pengaruh tabrakan yang terdeteksi dan batasan yang diberikan oleh pengguna.

Gerakan tersebut merupakan hasil interpretasi pemecah masalah terhadap hukum fisika, seperti hukum kekekalan energi dan momentum. Namun, melakukan hal ini dengan akurasi 100% sangatlah mahal, dan trik untuk mensimulasikannya secara real-time adalah dengan melakukan perkiraan untuk meningkatkan kinerja, selama hasilnya tetap realistis secara fisik. Selama hukum dasar gerak tetap terjaga dalam toleransi yang wajar, kompromi ini sepenuhnya dapat diterima untuk simulasi permainan komputer.

Mengambil Langkah-Langkah Kecil

Ide utama dari mesin fisika adalah mendiskritisasi gerakan menggunakan langkah waktu. Persamaan gerak benda kaku yang terikat dan tidak terikat sangat sulit untuk diintegrasikan secara langsung dan akurat. Diskritisasi membagi gerakan menjadi peningkatan waktu kecil, di mana persamaan disederhanakan dan dilinearisasi sehingga memungkinkan untuk menyelesaikannya secara perkiraan. Ini berarti bahwa selama setiap langkah waktu, gerakan bagian-bagian relevan dari benda kaku yang terlibat dalam suatu ikatan diperkirakan secara linier.

Meskipun masalah yang dilinearkan lebih mudah diselesaikan, hal ini menyebabkan penyimpangan dalam simulasi yang mengandung perilaku non-linier, seperti gerak rotasi. Nanti kita akan melihat metode mitigasi yang membantu mengurangi penyimpangan dan membuat simulasi lebih masuk akal.

Pemecahan

Animasi ini menunjukkan bagaimana pemecah PGS mengubah posisi benda-benda pada setiap langkah proses iterasi, dengan tujuan menemukan posisi yang mematuhi batasan bola dan soket sambil mempertahankan pusat massa pada setiap langkah (ini adalah jenis pemecah posisi yang digunakan oleh IK dragger). Meskipun contoh ini memiliki solusi analitis yang sederhana, ini merupakan demonstrasi yang baik dari konsep di balik PGS. Pada setiap langkah, solver mengunci salah satu batasan dan membiarkan batasan lainnya dilanggar. Setelah beberapa iterasi, benda-benda tersebut sudah sangat dekat dengan posisi yang benar. Ciri khas metode ini adalah bagaimana beberapa benda kaku tampak bergetar di sekitar posisi akhir mereka, terutama saat berinteraksi dengan benda-benda yang lebih berat. Jika kita tidak melakukan iterasi yang cukup, bagian kuning mungkin tertinggal dalam keadaan yang jelas-jelas tidak valid di mana salah satu dari dua batasan tersebut dilanggar secara drastis. Ini disebut masalah rasio massa tinggi, dan telah menjadi momok bagi mesin fisika karena menyebabkan ketidakstabilan dan ledakan. Jika kita melakukan terlalu banyak iterasi, pemecah masalah menjadi terlalu lambat; jika tidak, ia menjadi tidak stabil. Menyeimbangkan kedua sisi ini telah menjadi proses yang menyakitkan dan memakan waktu.

Strategi Mitigasi

Sebuah solver memiliki dua sumber utama ketidakakuratan: langkah waktu dan pemecahan iteratif (ada juga penyimpangan bilangan floating point, tetapi hal ini minor dibandingkan dengan dua yang pertama). Ketidakakuratan ini menimbulkan kesalahan dalam simulasi yang menyebabkan simulasi menyimpang dari jalur yang benar. Beberapa penyimpangan ini dapat ditoleransi seperti kecepatan yang sedikit berbeda atau kehilangan energi, tetapi beberapa tidak dapat ditoleransi seperti ketidakstabilan, perolehan energi yang besar, atau batasan yang terlepas.

Oleh karena itu, sebagian besar kompleksitas dalam pemecah masalah berasal dari implementasi metode untuk meminimalkan dampak ketidakakuratan komputasi. Implementasi akhir kami menggunakan beberapa strategi mitigasi tradisional dan beberapa strategi baru:

1. Warm starting: memulai dengan solusi dari langkah waktu sebelumnya untuk meningkatkan laju konvergensi pemecah iteratif
2. Post-stabilization: memproyeksikan ulang sistem kembali ke manifold konstrain untuk mencegah pergeseran konstrain
3. Regularisasi: menambahkan kepatuhan pada batasan untuk memastikan adanya solusi dan keunikannya
4. Pre-conditioning: menggunakan solusi eksak untuk subsistem linier, meningkatkan stabilitas mekanisme kompleks

Strategi 1, 2, dan 3 cukup tradisional, tetapi strategi 3 telah kami perbaiki dan sempurnakan. Selain itu, meskipun strategi 4 bukan hal yang belum pernah terdengar, kami belum melihat implementasi praktisnya. Kami menggunakan metode faktorisasi asli untuk matriks batasan langka yang besar dan cara baru yang efisien untuk menggabungkannya dengan PGS. Implementasi yang dihasilkan hanya sedikit lebih lambat dibandingkan dengan PGS murni, tetapi memastikan bahwa sistem linier yang berasal dari batasan kesetaraan diselesaikan secara tepat. Akibatnya, batasan kesetaraan hanya mengalami pergeseran yang berasal dari diskritisasi waktu. Rincian mengenai metode kami terdapat dalam presentasi GDC 2020 saya. Saat ini, kami sedang meneliti metode langsung yang diterapkan pada batasan ketidaksetaraan dan tabrakan.

Mendapatkan Detail Lebih Lanjut

Secara tradisional, terdapat dua model matematis untuk mekanisme artikulasi: metode koordinat tereduksi yang dipelopori oleh Featherstone, yang memarametrisasi derajat kebebasan di setiap sendi, dan metode koordinat penuh yang menggunakan formulasi Lagrangian.

Kami menggunakan formulasi kedua karena lebih fleksibel dan memerlukan matematika serta implementasi yang jauh lebih sederhana.

Mesin Roblox menggunakan metode analitis untuk menghitung respons dinamis batasan, berbeda dengan metode penalti yang digunakan sebelumnya. Metode analitis pertama kali diperkenalkan dalam Baraff 1989, di mana metode ini digunakan untuk menangani batasan kesetaraan dan non-kesetaraan secara konsisten. Baraff mengamati bahwa model kontak dapat diformulasikan menggunakan pemrograman kuadratik, dan ia menyediakan metode solusi heuristik (yang bukan metode yang kami gunakan dalam pemecah kami).

Alih-alih menggunakan formulasi berbasis gaya, kami menggunakan formulasi berbasis impuls di ruang kecepatan, yang awalnya diperkenalkan oleh Mirtich-Canny 1995 dan diperbaiki lebih lanjut oleh Stewart-Trinkle 1996, yang menyatukan penanganan berbagai jenis kontak dan menjamin keberadaan solusi untuk kontak dengan gesekan. Pada setiap langkah waktu, batasan dan tabrakan dipertahankan dengan menerapkan perubahan kecepatan instan akibat impuls batasan. Penjelasan yang sangat baik mengenai mengapa simulasi berbasis impuls lebih unggul terdapat dalam presentasi GDC oleh Catto 2014.

Kontak tanpa gesekan dimodelkan menggunakan masalah komplementaritas linier (LCP) sebagaimana dijelaskan dalam Baraff 1994. Gesekan ditambahkan sebagai proyeksi non-linier ke kerucut gesekan, yang diselingi dengan iterasi Projected Gauss-Seidel.

Pergeseran numerik yang menyebabkan kesalahan posisi pada batasan diselesaikan menggunakan teknik post-stabilisasi dengan kecepatan palsu yang diperkenalkan oleh Cline-Pai 2003. Hal ini melibatkan penyelesaian LCP kedua di ruang posisi, yang memproyeksikan sistem kembali ke manifold batasan.

LCP diselesaikan menggunakan PGS / Impulse Solver yang dipopulerkan oleh Catto 2005 (lihat juga Catto 2009). Metode ini bersifat iteratif dan mempertimbangkan setiap batasan secara berurutan serta menyelesaikannya secara independen. Melalui banyak iterasi, dan dalam kondisi ideal, sistem konvergen ke solusi global.

Selain itu, masalah rasio massa yang tinggi pada batasan kesetaraan diatasi dengan melakukan prakondisi pada PGS menggunakan dekomposisi LDL langka dari matriks batasan kesetaraan. Submatriks padat dari matriks batasan tersebut dilangka-kan menggunakan metode yang kami sebut Body Splitting. Metode ini mirip dengan dekomposisi LDL yang digunakan dalam Baraff 1996, namun memungkinkan sistem mekanik yang lebih umum, dan memecahkan sistem di ruang batasan. Untuk informasi lebih lanjut, Anda dapat melihat presentasi GDC 2020 saya.

Arsitektur pemecah masalah kami mengikuti gagasan Guendelman-Bridson-Fedkiw, di mana langkah kecepatan dan posisi dipisahkan oleh resolusi batasan. Urutan waktu kami adalah:

1. Maju kecepatan
2. Resolusi batasan dalam ruang kecepatan dan ruang posisi
3. Maju posisi

Skema ini memiliki keunggulan dalam mengintegrasikan hanya kecepatan yang valid, serta membatasi latensi dalam penerapan gaya eksternal, namun memungkinkan adanya pelanggaran batasan yang terdeteksi dalam jumlah kecil akibat drift numerik.

Referensi yang sangat baik untuk simulasi benda kaku adalah buku Erleben 2005 yang baru-baru ini tersedia secara gratis. Anda dapat menemukan kuliah daring tentang animasi berbasis fisika, blog oleh Nilson Souto tentang pembuatan mesin fisika, presentasi GDC yang sangat bagus oleh Erin Catto tentang metode pemecah masalah modern, serta forum seperti Bullet Physics Forum dan GameDev yang merupakan tempat yang sangat baik untuk mengajukan pertanyaan.

Kesimpulan

Bidang simulasi fisika game menyajikan banyak masalah menarik yang sekaligus menantang dan mengasyikkan. Ada peluang untuk mempelajari matematika dan fisika yang menarik serta menggunakan teknik optimasi modern. Ini adalah bidang pengembangan game yang erat mengintegrasikan matematika, fisika, dan rekayasa perangkat lunak.

Meskipun Roblox memiliki mesin fisika benda kaku yang baik, masih ada area yang dapat ditingkatkan dan dioptimalkan. Selain itu, kami sedang mengerjakan proyek-proyek baru yang menarik seperti pemecahan, deformasi, benda lunak, kain, aerodinamika, dan simulasi air.

Baik Roblox Corporation maupun blog ini tidak mendukung atau merekomendasikan perusahaan atau layanan apa pun. Selain itu, tidak ada jaminan atau janji yang diberikan terkait keakuratan, keandalan, atau kelengkapan informasi yang terkandung dalam blog ini.

Postingan blog ini awalnya diterbitkan di Roblox Tech Blog.