Saya sedang mengerjakan mesin fisika kontinu murni , dan saya perlu memilih algoritma untuk pendeteksian benturan fase luas dan sempit. "Murni terus menerus" berarti saya tidak pernah melakukan tes persimpangan, tetapi sebaliknya ingin menemukan cara untuk menangkap setiap tabrakan sebelum itu terjadi, dan menempatkan masing-masing ke dalam tumpukan "tabrakan yang direncanakan" yang dipesan oleh TOI.

Fase Luas Satu-satunya metode fase luas berkelanjutan yang dapat saya pikirkan adalah membungkus setiap tubuh dalam lingkaran dan menguji apakah setiap lingkaran akan tumpang tindih dengan yang lain. Namun ini tampaknya sangat tidak efisien, dan tidak memiliki pemusnahan apa pun.

Saya tidak tahu apa analog kontinu yang mungkin ada untuk metode penyisihan tabrakan diskrit hari ini seperti quad-tree. Bagaimana saya bisa mencegah pengujian luas yang tidak pantas dan tidak berguna seperti mesin diskrit lakukan? Saya juga ingin dapat melihat tabrakan lebih dari 1 frame di depan.

Fase Sempit
Saya telah berhasil mengadaptasi SAT yang sempit ke pemeriksaan kontinu daripada diskrit, tapi saya yakin ada algoritma lain yang lebih baik di luar sana di koran atau situs yang mungkin kalian temui.
Apa variasi algoritma cepat atau akurat yang Anda sarankan untuk saya gunakan dan apa kelebihan / kekurangan masing-masing?

Catatan Akhir:
Saya katakan teknik dan bukan algoritma karena saya belum memutuskan bagaimana saya akan menyimpan poligon yang berbeda yang mungkin cekung, cembung, bulat, atau bahkan memiliki lubang. Saya berencana untuk membuat keputusan berdasarkan apa yang dibutuhkan algoritma (misalnya jika saya memilih algoritma yang memecah poligon menjadi segitiga atau bentuk cembung, saya hanya akan menyimpan data poligon dalam formulir ini).

Saya benar-benar hanya melemparkan ide di sekitar sini. Dengan asumsi Anda memiliki (paling tidak) currentposisi dan nextposisi; untuk setiap bingkai.

Anda akan membutuhkan dua fase luas yang terpisah, diikuti oleh fase sempit Anda:

• Salah satu yang mengetahui bahwa tabrakan akan terjadi.
• Salah satu yang mencari tahu di mana tabrakan sebenarnya terjadi (misalnya fase luas / SAT tidak akurat)
• Akhirnya fase sempit Anda akan meningkatkan hasil fase luas kedua.

Fase Luas Awal

Anda bisa melihat hashing spasial (menggunakan nextposisi, bukan current) untuk fase luas awal. Ini akan mempartisi ruang masalah Anda dengan baik menjadi grup kandidat tabrakan.

Fase Luas Kedua

Lakukan multi-sampel biner menggunakan metode persimpangan lingkaran yang Anda jelaskan. Dengan kata lain:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Tweak akurasi itu juga bisa menjadi pertimbangan - saya pikir menggunakan 'panjang kuadrat' next - currentakan mendapatkan hasil pixel-sempurna.

Fase Sempit

Lakukan multi-sampel biner menggunakan sesuatu seperti PMask - logikanya akan persis sama seperti di atas; hanya menggunakan tabrakan rutin yang berbeda.

Akhirnya

Anda akan dapat menentukan waktu persimpangan pointOfCollision, currentdan arus Anda speeddan acceleration(dengan asumsi Anda memiliki integrator yang masuk akal).

Baiklah, saya telah melihat Anda memperbarui pertanyaan Anda sehingga menjadi lebih spesifik. Saya akan mencoba dan membantu Anda lagi.

Untuk pemeriksaan fase-lebar pertama Anda, saya akan sangat menyarankan hashing spasial .

Pada dasarnya, Anda membagi layar Anda menjadi kisi-kisi berukuran sama. Kemudian, jika suatu objek terletak di dalam kisi, Anda menambahkannya ke "ember" di tabel hash 1D.

Itu cek pertamamu selesai. Jika objek tidak berada di ember yang sama, tidak mungkin bagi mereka untuk berpotongan.

Melanjutkan dengan itu, Anda sekarang memiliki daftar ember dengan objek (berpotensi) di dalamnya. Anda dapat melakukan pemeriksaan fase luas lain di sini dengan:

A.) Membagi ember ini menjadi 4 ember lain, dan memeriksa tabel hash 1D yang dihasilkan. Jika mereka tidak berada di ember yang sama, tidak ada tabrakan.

Atau:

B.) Melakukan pemeriksaan jarak yang sederhana dan menjaga lebar dan / atau tinggi objek dalam pikiran untuk memastikan akurasi.

Tapi bagaimana dengan saat Anda berpotensi tabrakan?

Maka saya akan merekomendasikan sesuatu seperti ini . Ini pada dasarnya semacam campuran antara tabrakan poligon (untuk bentuk kompleks) atau persegi panjang / lingkaran untuk bentuk yang kurang kompleks.

Juga, jika Anda benar-benar ingin "menangkap tabrakan sebelum terjadi dan menyimpannya" maka Anda selalu dapat melakukan sesuatu seperti ini:

Jika dua benda berada di ember yang sama, maka mereka mungkin bertabrakan.

Lebih jauh lagi, apakah benda-benda itu cukup dekat sehingga dapat bertabrakan segera? (Memperhatikan kecepatan, ukuran objek dan jarak)

Jika jawaban untuk keduanya adalah ya, lanjutkan dan simpan untuk melakukan tes persimpangan nanti.

" Jawaban lama

Yah, sayangnya saya telah kehilangan jejak Buku Pegangan "Semua Jenis Tabrakan dan Untuk Apa Mereka Digunakan". :)

Namun, meskipun ini adalah pencarian yang sangat luas, saya akan membantu Anda memulai.

Ada pertanyaan (yang dijawab) yang bagus untuk hal seperti ini di sini .

Serta artikel oleh orang-orang yang membuat N dan N + di sini .

Belum lagi, Anda memiliki tabrakan Per-pixel fallback yang bagus .

Saya sungguh meragukan bahwa siapa pun akan memiliki daftar yang berguna untuk setiap jenis tabrakan, tetapi ini akan membantu Anda memulai.

Namun, saya harus menyebutkan bahwa jenis tabrakan yang Anda butuhkan (dan akan berakhir menggunakan) sangat tergantung pada jenis permainan yang Anda buat. Itu sebabnya Anda menemukan tutorial - kebanyakan orang menganggap Anda memiliki gagasan tentang apa yang Anda inginkan, sehingga mereka membantu Anda dalam bidang tertentu. Saya menyadari bahwa sebagian besar tautan saya adalah tutorial tentang topik tertentu, tetapi saya pikir tutorial akan lebih membantu Anda secara jujur. Daftar adalah satu hal, tetapi jika Anda membaca sendiri tentang masing-masing poin, Anda dapat mengambil keputusan yang lebih berpendidikan yang mungkin akan lebih sesuai dengan kebutuhan Anda.