Memisahkan teorema sumbu dengan beberapa poligon?

9

Saya mencoba menerapkan teorema sumbu pemisah di C #. Saya memiliki fungsi yang dapat menghitung vektor terjemahan minimum antara dua poligon. Namun, sepertinya saya tidak dapat membuat fungsi yang menghitung vektor terjemahan minimum antara satu poligon dan beberapa poligon lainnya. Jujur, saya sudah mengerjakan ini selama berbulan-bulan dan saya tidak mendekati solusi dan belum dapat menemukan solusi online. Selalu ada beberapa kasus tepi yang tidak mengembalikan hasil yang benar, yang mengarah ke bug prioritas tinggi di permainan saya.

Berikut adalah kasus tepi umum yang tidak berfungsi dengan benar:

kasus tepi

Apakah ada solusi terkenal untuk masalah ini? Yang bisa saya temukan adalah orang-orang mengatakan "cukup lakukan SAT pada setiap poligon" tetapi ini jarang menghasilkan vektor terjemahan minimum .

Bantuan apa pun akan sangat dihargai.

collision-detection separating-axis-theorem pengguna40698
sumber
Satu ide, yang sebenarnya tidak pernah saya uji, adalah bahwa beberapa sumbu pemisah - sumbu pemisah yang akan membuat Anda menyamping menjadi poligon yang berdekatan - dapat ditandai untuk tidak pernah dianggap sebagai minimum. Kemudian beberapa jenis tes berulang akan memberikan hasil yang baik (mungkin dengan beberapa jenis FIFO dan / atau batas iterasi untuk mencegah terjebak dalam satu lingkaran).
Andrew Russell
Versi yang lebih sulit untuk dipecahkan adalah ketika ujung bentuknya hanya sebagian ditutupi oleh annother. Misalnya pada gambar kanan atas, jika kotak tengah melebar ke kanan, menjadi persegi panjang yang lebih besar. Ini mirip dengan keluaran dari beberapa kode yang saya gunakan yang mengambil puluhan ribu sel yang ditempati / tidak ditempati dan menguranginya menjadi di bawah seratus bentuk benturan yang lebih besar
Richard Tingle

Jawaban:

2

Idealnya, Anda tidak membangun lingkungan Anda dari poligon. Anda membuatnya dari tepi (yang mungkin Anda hitung dari serangkaian poligon). Dalam contoh pertama Anda, misalnya, ada tepi diagonal tunggal; pada contoh terakhir, kotak diletakkan pada satu sisi horisontal tunggal.

Fakta bahwa editor atau alat Anda menggunakan bentuk individual yang lebih kecil untuk membangun level seharusnya tidak memengaruhi runtime.

Pendekatan yang sedikit lebih sederhana hanya akan menghilangkan tepi "bagian dalam" dari bentuk dasar. Untuk contoh terakhir Anda, ada dua sisi antara kotak "lantai"; abaikan ini selama deteksi tabrakan.

Anda dapat menemukan beberapa gambar yang lebih baik dan beberapa ide implementasi dengan membaca bagian 4.5 (tepi dan rantai tepi) dalam dokumentasi Box2D .

Sean Middleditch
sumber
2
Menggunakan edge (terutama edge, sedikit lebih baik dengan edge chains) memiliki kelemahan utama yaitu menjadi sangat mudah bagi objek fisika untuk mengalami kesalahan di dalam geometri level.
Andrew Russell
1
@AndrewRussell: masalah-masalah itu dihindari dengan perbaikan tunneling biasa. Pastikan objek bergerak Anda memiliki volume / area yang cukup baik, jaga kecepatan maksnya per frame cukup rendah sehingga mereka tidak dapat memindahkan lebih dari ~ setengah dimensi terpendeknya (atau langkah beberapa kali jika Anda membutuhkannya untuk bergerak lebih cepat), hindari celah-celah yang sangat tajam dan demikian dalam geometri level Anda, iterate resolusi beberapa kali sampai Anda bertemu di lokasi akhir "aman", dll.
Sean Middleditch