Deteksi tabrakan dengan kurva

12

Saya sedang mengerjakan game 2D di mana saya ingin melakukan deteksi tabrakan antara lingkaran bergerak dan beberapa jenis kurva statis (mungkin kurva Bezier).

Saat ini permainan saya hanya menampilkan garis lurus sebagai geometri statis dan saya melakukan deteksi tabrakan dengan menghitung jarak dari lingkaran ke garis, dan memproyeksikan lingkaran keluar dari garis jika jaraknya kurang dari jari-jari lingkaran.

Bagaimana saya bisa melakukan deteksi tabrakan semacam ini secara relatif langsung? Saya tahu misalnya bahwa fitur Box2D mendeteksi tabrakan dengan kurva Bezier. Saya tidak memerlukan mekanisme pendeteksian tabrakan berfitur lengkap, hanya sesuatu yang dapat melakukan apa yang telah saya jelaskan.


UPDATE: Terima kasih banyak atas jawaban yang bagus! Saya harus membaca kurva Bezier untuk memahami metode yang telah Anda jelaskan. Maka saya akan kembali kepada Anda.

paldepind
sumber

Jawaban:

6

29/09/2012 - 23:20

Saya membuat Repo git di sini: https://github.com/ArthurWulfWhite/Bezier-Distance/

Anda dipersilakan untuk mengunduh file sumber sebagai zip dari sana. Ini juga termasuk demo yang dapat Anda kompilasi menggunakan FlashDevelop. Untuk menggunakan demo, buka proyek di Flash Develop dan klik 'Test Project'. Saat menjalankan demo, klik LMB untuk mengacak kurva Bezier baru dan Lingkaran baru.

Semoga berhasil!

Tautan zip sulit dilihat - cukup gunakan Ctrl + F dan ketik zip. Sumber ini mewakili beberapa minggu penelitian dan pemrograman, saya harap Anda menikmatinya.


Jika Anda berencana membagi bezier secara rekursif menjadi segmen dan memeriksa tabrakan dengan mereka, saya sarankan membuat 100.100 array (kisi) dan menempatkan setiap segmen dalam empat kotak terdekat, jadi Anda hanya perlu memeriksa tabrakan dengan 4 / 10.000 dari segmen setiap frame.

Saya pikir Anda akan mendapat manfaat dari box2d baik sebagai programmer dan sebagai pencipta permainan, karena ada banyak rintangan kecil tersembunyi dalam membuat mesin fisika 'sederhana' yang membuat gerakan itu tampak sedikit bergelombang dan kurang cairan daripada yang seharusnya.

Jawaban lama: Cara murni.

Anda benar-benar dapat melihat apakah sebuah lingkaran bertabrakan dengan kurva Bezier, dengan memeriksa jarak antara jarak antara pusat lingkaran dan titik terdekat pada kurva.

Persamaan untuk jarak (secara umum)

menjelaskan:

Persamaan Bezier:

q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Ini dapat disimpulkan hingga (dengan beberapa aljabar) - Saya akan menghilangkan. (X, y) untuk keterbacaan (mereka masih poin, bukan satu nomor)

q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start

Jarak dari titik (x, y) adalah:

sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)

Untuk menemukan titik terdekat pada bezier ke bola, Anda harus menurunkan dan menemukan semua titik di mana turunannya sama dengan nol (akar). Ini adalah polinomial tingkat ketiga sehingga Anda dapat menggunakan rumus tertutup tetapi bisa jadi tidak dapat diandalkan karena ketepatan titik mengambang komputer yang diwakili fraksi mungkin tidak cukup. Jauh lebih baik menggunakan Newton atau semacamnya.

Turunan yang perlu Anda temukan adalah:

Dengan asumsi: a = mulai b = kontrol c = akhir d = titik pusat berputar

Turunannya menggunakan wolfram alpha

Bagian yang sulit adalah mengalikan poin ini, Anda harus menggunakan produk titik.

Jika Anda suka, saya punya kode untuk ini dan saya bisa membagikannya di sini dalam bentuk fungsi yang hanya mengembalikan boolean jika ada tabrakan atau tidak dan sudut tabrakan. Beberapa masalah bisa muncul dalam implementasi naif dari mesin tabrakan seperti ini misalnya bola yang bergerak cepat bisa terjebak di antara dua kurva.

Saya merekomendasikan untuk menghindarinya untuk saat ini, cukup jumlah koefisien untuk sumbu x dan untuk sumbu y dan tambahkan.

Gunakan metode apa pun yang dapat Anda pilih seperti Newton untuk menemukan akar, periksa jarak dari titik akar di bezier, 0 <= t <= 1 ke pusat lingkaran dan periksa jarak untuk dua ujung bezier (mulai dan ujung) ke pusat lingkaran, mana pun yang terdekat, akan memberi tahu Anda jika ada tabrakan.

Jika jari-jari lebih kecil dari jarak minimal, ada tabrakan.

Sudutnya kira-kira satu antara pusat lingkaran dan titik terdekat pada bezier.

Yang sedang berkata, jika Anda benar-benar ingin membuat game dengan fisika tabrakan, saya sarankan Anda beralih ke bezier

    q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Bagi setiap bagian di tengah secara rekursif hingga cukup kecil, katakanlah 10 piksel atau kurang, lalu buat bezier secara kasar dari kotak dan gunakan Box2d untuk fisika karena ada kemungkinan bahwa menulis semua kode deteksi tabrakan ini akan terbukti hebat time sink yang tidak banyak meningkatkan gameplay. Menggunakan Box2d telah membuktikan dirinya dalam banyak sekali proyek di masa lalu.

AturSams
sumber
Metode yang Anda gambarkan untuk menghitung titik terpendek ke kurva adalah persis yang saat ini saya gunakan dengan garis, bukan kurva. Tetapi melakukan hal yang sama untuk kurva dengan metode yang Anda jelaskan terdengar agak terlalu rumit. Yang, seperti yang saya pahami, juga apa yang Anda pikirkan. Dan tentang Box2D. Saya yakin itu adalah pekerjaan yang hebat. Tetapi fisika dalam permainan saya sejujurnya sangat sederhana dan dengan demikian saya telah memutuskan bahwa mesin fisika penuh sesak nafas.
paldepind
Berapa banyak objek dalam gim Anda? Berapa banyak yang bisa saling bertabrakan? Terkadang menggunakan mesin Fisika dapat menghasilkan manfaat besar seperti menghitung waktu tabrakan secara akurat. (frame menyebabkan diskrit dan tabrakan adalah nyata (tidak terjadi tepat ketika Anda membuat bingkai)
AturSams
Seringkali daripada tantangan tak terduga ketika menerapkan sesuatu yang baru dan keindahan menggunakan api fisika 2d, adalah seperti halnya menggunakan bahasa pemrograman apa pun, itu tidak memerlukan upaya khusus dari pihak Anda selain menginvestasikan beberapa jam untuk mempelajarinya dan hasilnya sangat memuaskan.
AturSams
Saya menambahkan beberapa detail lagi sekarang, semoga berhasil. :)
AturSams
Saya membuat game seperti Elasto Mania sederhana. Hanya tiga lingkaran bergerak dan geometri statis. Seluruh mesin selesai dan bekerja dengan baik. Satu-satunya yang tersisa adalah untuk memungkinkan kurva yang akan saya selesaikan atm berkat bantuan dalam jawaban ini :) Jangan ragu untuk mengirim kode yang Anda sebutkan. Menurut Anda, seberapa tepat penggunaannya dalam kehidupan nyata? Lebih baik daripada mengubah bezier menjadi garis kecil?
paldepind
7

Untuk melakukan ini, saya akan:

  • Pecahkan kurva bezier menjadi beberapa segmen garis dan simpan.

  • Letakkan semua segmen ini dalam sumbu kotak pembatas selaras untuk seluruh kurva.

Deteksi tabrakan:

1) periksa apakah bola ada di dalam kotak pembatas utama. jika tidak, tidak ada tabrakan.

2) jika tidak, periksa apakah ada segmen individual yang dihitung di atas bertabrakan dengan bola. Lihat artikel persimpangan Line-sphere dari Wikipedia .

EDIT: jika Anda membutuhkan presisi tinggi dan menginginkan kinerja yang baik, Anda juga dapat membuat kotak pembatas utama untuk seluruh kurva, lalu membagi kurva menjadi dua segmen (mis:: [0.0 - 0.5]dan [0.5 - 1.0]). Buat kotak bouding untuk masing-masingnya, lalu bagi lagi masing-masing segmen ini menjadi dua segmen (sehingga memberi [0 - 0.25], [0.25 - 0.5]dan [0.5 - 0.75], [0.75 - 1.0]). Lanjutkan seperti ini sampai Anda mencapai cukup presisi. pada akhirnya Anda akan memiliki binary treekotak pembatas dengan kotak pembatas kurva utama pada segmen akar dan garis pada daun. mencari di dalam pohon akan memberi Anda O(log n)alih-alih O(n)(di mana n= jumlah segmen garis untuk kurva)

tigrou
sumber
Solusi ini masuk akal bagi saya dan jelas merupakan yang termudah untuk dipahami dan saya mungkin puas dengan itu. Tapi saya ingin tahu apakah ada pilihan yang lebih "murni".
paldepind
5

Perpotongan antara garis dan kurva Bezier dicapai secara matematis dengan membagi kurva. Ini berarti mengandalkan properti lambung cembung kurva dan membaginya menjadi busur yang lebih kecil dengan poligon kontrol yang berbeda dengan cara seperti divide-et-impera.

Artikel ini membahasnya hingga titik: http://students.cs.byu.edu/~tom/557/text/cic.pdf .

Bagian yang bagus adalah bahwa algoritma ini bekerja dengan garis apa pun, Anda hanya perlu menerapkan transformasi kaku pada kurva sehingga Anda dapat mempertimbangkan garis target Anda sejajar dengan sumbu Ox.

Demikian pula, Anda dapat memeriksa terhadap lingkaran dan poligon dari setiap busur bezier tersebut ketika Anda membagi busur Bezier menjadi dua sub-busur. Lingkaran harus memotong poligon kontrol busur untuk tes kurva-ke-lingkaran masuk akal.

Gabriel Conrad
sumber
Saya belum membaca artikelnya. Tapi bagaimana saya bisa dari persimpangan antara garis dan kurva Bezier ke persimpangan antara lingkaran dan Bezier? Memeriksa benturan dengan lingkaran dan poligon terdengar agak rumit bagi saya.
paldepind