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
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.
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 memilikibinary tree
kotak pembatas dengan kotak pembatas kurva utama pada segmen akar dan garis pada daun. mencari di dalam pohon akan memberi AndaO(log n)
alih-alihO(n)
(di manan
= jumlah segmen garis untuk kurva)sumber
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.
sumber