Apa algoritma yang baik untuk mendeteksi tabrakan antara bola bergerak?

27

Jika (untuk tujuan deteksi tabrakan) objek 3D direpresentasikan dalam game oleh spheres, apa algoritma yang baik untuk mendeteksi tabrakan antar spheres?

Jika setiap objek memiliki posisi pada frame terakhir dan posisi baru (yang diinginkan), apa itu algoritma yang baik yang akan mengidentifikasi tabrakan di mana bola tidak berpotongan di frame sebelumnya, dan mereka mungkin tidak berpotongan di frame kedua, tapi mereka berpotongan di suatu tempat di antara keduanya?

collision-detection kevin42
sumber

Jawaban:

18

Pada dasarnya Anda sedang mencari jejak.

Halaman ini mungkin akan membantu Anda: http://www.realtimerendering.com/intersections.html

Pindah Sphere / Sphere: (lokasi) Tambahkan jari-jari bola bergerak ke bola statis, dan perlakukan bola bergerak sebagai sinar. Gunakan sinar ini untuk melakukan persimpangan sinar / bola. Lihat Gomez; Schroeder untuk kode (artikel memiliki bug dalam derivasi, kode baik-baik saja); dan RTR2, hal. 622.

Tetrad
sumber
1
Itu tidak berfungsi jika kedua bola bergerak, (bahkan jika Anda melakukannya dua kali). Menurut saya, pertama-tama Anda harus melakukan pemeriksaan jarak antara garis yang merentang gerakan a dan satu gerakan merentang b, dan jika itu kurang dari jari-jari a + jari-jari b Anda memiliki kemungkinan tabrakan. Setelah itu saya akan melakukan pemeriksaan untuk melihat di mana titik itu dalam waktu untuk bola dan di mana untuk bola b untuk melihat apakah waktunya sudah dekat. Jika demikian saya akan memeriksa kecepatan terhadap jarak dalam waktu untuk titik itu, jika itu masih mungkin terjadi tabrakan, saya akan melakukan penyempurnaan bertahap.
Kaj
15
Sebenarnya itu benar, Anda hanya perlu membuat gerakan itu relatif. Jadi jika kedua bola bergerak Anda kurangi kecepatan salah satu bola dari keduanya sehingga Anda memiliki satu bola "bergerak" dan satu bola "stasioner". Maka Anda bisa menggunakan di atas.
Tetrad
8

Menggunakan tes menyapu seperti yang ditunjukkan dalam ini artikel Gamasutra.

Firas Assaad
sumber
4

Dari atas kepala saya:

  1. Buat dua segmen garis dari tengah masing-masing lingkaran dari tempat ia mulai ke tempat ia dipindahkan pada langkah waktu itu.
  2. Temukan jarak min antara kedua segmen garis tersebut; seperti yang dijelaskan di sini .
  3. Jika jarak itu kurang dari atau sama dengan jari-jari lingkaran pertama ditambah yang kedua maka mereka bertabrakan; kalau tidak, mereka tidak melakukannya.

Dan hanya itu yang ada di sana, saya berharap itu cukup cepat.

Robert Massaioli
sumber
1

Inilah artikel Gamasatura yang bagus .

Mateen Ulhaq
sumber
1
Saya menyadari ini 7 tahun kemudian, tetapi jawaban ini hanya tautan. Untungnya tautan itu masih hidup, tetapi jika tidak, jawaban Anda akan ... bukan menjadi jawaban.
Draco18s
0

Berbicara sebagai seseorang yang telah melakukan ini: tidak sepadan dengan kerumitannya . Kecuali jika desain game Anda benar-benar membutuhkannya, dan hampir pasti tidak, Anda akan menghabiskan lebih banyak usaha untuk menyapu pekerjaan daripada yang Anda harapkan. Dan itu akan lebih lambat dari yang Anda inginkan.

ZorbaTHut
sumber
Dia bisa membuat permainan biliar untuk semua yang Anda tahu.
Kaj
Jika dia membuat game biliar, "desain game-nya benar-benar membutuhkannya" .
deft_code
Anda benar, jangan menemukan kembali kemudi . Tapi hanya untuk olahraga mungkin layak.
user712092
4
Saya tidak setuju dengan keputusasaan langsung sebagai jawaban .
bobobobo
Saya setuju dengan @bobobobo, pertanyaannya bukan apakah ini sepadan dengan kerumitan atau tidak, pengguna di masa depan yang melihat utas ini mungkin benar-benar membutuhkan jawaban terlepas dari biaya. Ini akan lebih baik sebagai komentar.
TomTsagk
0

Ada artikel tentang mendapatkan deteksi tabrakan dengan matematika di Flipcode . Ini memiliki lingkaran-cirle. Ada cara untuk mendeteksi secara tepat titik tabrakan dan memeriksa apakah ada tabrakan sama sekali.

pengguna712092
sumber
Saya menyadari ini 7 tahun kemudian, tetapi jawaban ini hanya tautan. Untungnya tautan itu masih hidup, tetapi jika tidak, jawaban Anda akan ... bukan menjadi jawaban.
Draco18s
0

Deteksi tabrakan untuk objek bergerak biasanya disebut "Perhitungan volume Swept", berikut beberapa kode / artikel tentang subjek ini.

http://www.gpu-voxels.org/demos/ (Demo)

Pustaka kode sumber:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Artikel:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (Sayangnya tidak ada kode sumber)

http://www.realtimerendering.com/intersections.html (Koleksi tautan agak berat)

TarmoPikaro
sumber
1
Jawaban yang hanya berisi tautan (atau dalam hal ini, beberapa) tidak mengandung jawaban yang sebenarnya. Anda harus memasukkan informasi yang relevan di pos Anda sehingga jika tautan itu mati, pos Anda masih dapat dimengerti.
Draco18s
Informasi di balik tautan sedikit lebih menjelaskan daripada saya saat ini. Ada juga video demo di balik tautan, yang memberikan persepsi tentang apa yang terjadi secara real time.
TarmoPikaro
1
meta.stackexchange.com/a/8259/313685
Draco18s