Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Bagaimana untuk Mengecilkan Bentuk Convex secara dinamik

by
Difficulty:AdvancedLength:LongLanguages:

Malay (Melayu) translation by Meyria (you can also view the original English article)

Keupayaan untuk memecah bentuk cembung secara dinamik ke dalam dua bentuk berasingan adalah kemahiran atau alat yang sangat berharga untuk digunakan dalam gamedev senjata anda. Pemisahan ini membolehkan simulasi jenis lanjutan seperti ruang perduaan untuk grafik atau fizik, persekitaran yang merosakkan secara dinamik (fracturing rapuh!), Lautan atau simulasi air, resolusi perlanggaran untuk enjin fizik, perduaan ruang binari, dan senarai hanya berlaku. Salah satu contoh yang hebat ialah permainan Ninja Fruit for Kinect.

Apa sebenarnya maksudnya untuk membahagikan bentuk cembung? Dalam dua dimensi, kita merujuk kepada bentuk sebagai poligon; dalam tiga dimensi, kita merujuk kepada bentuk sebagai polyhedron. (Polyhedra adalah perkataan yang digunakan untuk merujuk lebih daripada satu polyhedron.)

Petua: Secara umum, poligon cembung dan polyhedra memudahkan banyak aspek volum atau manipulasi dan pengurusan mesh. Disebabkan pemudahan ini, artikel keseluruhan menganggap poligon cembung dan cembung polyhedra. Bentuk cekung tidak terlepas dari apa-apa perbincangan di sini. Secara umum bentuk cekung disimulasikan sebagai koleksi gabungan bentuk cembung.


Prasyarat

Untuk memahami idea-idea yang dibentangkan dalam artikel ini, anda memerlukan pengetahuan tentang beberapa bahasa pengaturcaraan, dan pemahaman yang mudah tentang produk titik.

Satu cara yang baik untuk memecah bentuk dalam kedua-dua dua dimensi ini adalah untuk menggunakan  kliping rutin Sutherland-Hodgman. Rutin ini agak mudah dan sangat cekap, dan boleh juga diperluaskan sedikit demi sedikit untuk mempertahankan kekukuhan angka. Sekiranya anda tidak mengetahui dengan algoritma ini, lihat artikel saya sebelum ini mengenai subjek.

Pemahaman tentang pesawat dalam kedua-dua dua dimensi juga mesti. Harus diingat bahawa satah dua dimensi dapat dianggap sebagai unjuran satah tiga dimensi menjadi dua dimensi - atau, dengan kata lain, garis.

Sila faham bahawa satah juga boleh dianggap sebagai ruang setengah. Mengira jarak atau persimpangan mata ke separuh ruang adalah prasyarat yang diperlukan: lihat bahagian terakhir Cara Membuat Enjin Fizik 2D Kustom: Enjin Teras untuk mendapatkan maklumat mengenai perkara ini.


Sumber Demo

Sila rujuk sumber demonstrasi (juga pada Bitbucket) yang telah saya buat semasa anda membaca tutorial ini. Saya menggunakan demo ini untuk mencipta semua imej GIF dalam artikel itu. Kod sumber berada dalam C (dan harus serasi merentas platform), tetapi ditulis dengan cara yang mudah dipindahkan ke bahasa pengaturcaraan.


Pemisahan Segitiga

Sebelum menangani masalah membelah poligon keseluruhan, mari kita lihat masalah membelah segitiga melalui pesawat pemotongan. Ini akan membentuk asas pemahaman untuk bergerak ke penyelesaian yang kukuh dan umum.

Perkara yang baik mengenai pemisahan bentuk ialah, selalunya, algoritma dalam 2D ​​boleh dilanjutkan tanpa banyak masalah langsung ke dalam 3D. Di sini, saya akan mengemukakan algoritma pemisah segi tiga yang sangat mudah untuk kedua-dua dua dan tiga dimensi.

Apabila segitiga bersilang dengan satah membelah, tiga segitiga baru harus dihasilkan. Berikut adalah imej yang menunjukkan segitiga sebelum dan selepas berpisah di sepanjang satah:

TriangleSplit

Memandangkan satah berpecah, tiga segitiga baru dikeluarkan semasa operasi mengiris. Let's throw some code into the open, dengan asumsi bahawa tiga simpul segitiga adalah {a, b, c} dalam urutan berlawanan arah jarum jam (CCW), dan kita tahu bahawa kelebihan ab (tepi simpang a hingga b) berpotongan pesawat berpecah:

Semoga kod di atas menakutkan anda sedikit. Tetapi jangan takut; semua yang kita lakukan di sini adalah mengira beberapa mata persimpangan untuk mengetahui bagaimana untuk menghasilkan tiga segitiga baru. Sekiranya seseorang telah meneliti imej terdahulu dengan teliti, lokasi titik persilangan mungkin jelas: di mana garis putus-putusnya memenuhi satah pemisahan, dan di mana pinggir ab memotong pesawat berpecah. Inilah gambarajah untuk kemudahan:

TriangleSplitDiagram

Daripada rajah ini, mudah untuk melihat bahawa segitiga output harus mengandungi simpul {a, ac, ab}, {ac, c, b}, dan {ab, ac, b}. (Tetapi tidak semestinya dalam format yang tepat ini, sebagai contoh, {a, b, c} adalah segitiga yang sama seperti {c, b, a} kerana simpang hanya berpindah ke kanan.)

Untuk menentukan sudut mana yang menyumbang kepada mana dari tiga segitiga baru, kita mesti menentukan sama ada titik a dan titik c terletak di atas atau di bawah satah. Oleh kerana kita mengandaikan bahawa kelebihan ab diketahui bersilang, kita boleh menyimpulkan secara tersirat bahawa b adalah di sebalik satah keratan dari a.

Sekiranya konvensyen jarak negatif dari satah membelah bermaksud menembusi kapal terbang, kita boleh merumuskan predikat untuk menentukan sama ada satu titik memotong ruang setengah: mentakrifkan HitHalfspace (jarak) ((jarak) <0.0f). Predikat ini digunakan dalam setiap pernyataan jika menyemak dan melihat sama ada satu titik berada dalam ruang separuh dari pesawat kliping.

Terdapat empat kes yang wujud dari kombinasi a dan b memukul ruang setengah dari pesawat keratan:

Oleh kerana fungsi kami memerlukan kedua-dua a dan b pada sisi bertentangan pesawat, dua kes ini dijatuhkan. Semua yang tersisa adalah melihat di sebelah mana c yang disediakan. Dari sini, orientasi semua tiga titik diketahui; titik persilangan dan simpulan output boleh dikira secara langsung.

Mencari Edge Awal

Untuk menggunakan fungsi SliceTriangle (), kita mesti mencari pinggir segi tiga bersilang. Pelaksanaan di bawah adalah cekap, dan boleh digunakan apabila semua segitiga dalam simulasi berpotensi berpecah:

Setelah mengira jarak yang ditandatangani dari setiap sudut segitiga ke satah pemisahan, pendaraban boleh digunakan untuk melihat sama ada dua titik berbeza terletak pada sisi bertentangan satah. Oleh kerana jarak akan terapung positif dan negatif dalam sepasang, hasil dari dua yang didarabkan bersama mestilah negatif. Ini membolehkan penggunaan predikat mudah untuk melihat jika dua titik terletak di kedua-dua sisi pesawat: #mentakrifkan OnOppositeSides (distanceA, distanceB) ((distanceA) * (distanceB) <0.0f).

Sebaik sahaja kelebihan didapati berpotongan dengan satah pemisahan, simpang segitiga dinamakan semula dan beralih dan segera diserahkan kepada fungsi SliceTriangle pedalaman. Dengan cara ini, kelebihan tepi yang pertama dijumpai dinamakan semula kepada ab.

Berikut adalah apa produk akhir mungkin kelihatan seperti:

Splitting triangles along cutting planes dynamically via user interaction.
Memecahkan segitiga sepanjang pelantar pesawat secara dinamik melalui interaksi pengguna.

Pemisahan segitiga dengan cara ini menyumbang kepada setiap segitiga secara berasingan, dan algoritma yang dibentangkan di sini meluas, tanpa sebarang pengarang tambahan, dari dua hingga tiga dimensi. Bentuk segitiga clipping ini adalah ideal apabila maklumat bersebelahan segitiga tidak diperlukan, atau apabila segitiga dipotong tidak disimpan di mana-mana sahaja dalam ingatan. Ini sering terjadi ketika pengiraan jumlah persimpangan, seperti dalam simulasi apungan.

Satu-satunya masalah dengan memisahkan segitiga secara berasingan adalah bahawa tidak ada maklumat mengenai segi tiga yang bersebelahan antara satu sama lain. Sekiranya anda memeriksa GIF di atas dengan berhati-hati, anda dapat melihat bahawa banyak segitiga berkongsi simpul collinear, dan sebagai hasilnya dapat runtuh menjadi segitiga tunggal untuk diberikan dengan cekap. Bahagian seterusnya artikel ini membahas masalah ini dengan satu lagi, algoritma yang lebih kompleks, yang menggunakan semua taktik yang terdapat dalam bahagian ini).


Sutherland-Hodgman

Sekarang untuk topik akhir. Dengan mengandaikan pemahaman kerja tentang algoritma Sutherland-Hodgman, agak mudah untuk memperluas pemahaman ini untuk memisahkan bentuk dengan satah dan simpang keluaran pada kedua-dua belah pesawat. Ketahanan berangka boleh (dan harus) juga dipertimbangkan.

Mari kita semak secara ringkas kes-kes keratan Sutherland-Hodgman lama:

Ketiga-tiga perkara ini berfungsi dengan baik, tetapi tidak benar-benar mengambil kira ketebalan pesawat yang berpecah. Akibatnya, ralat berangka boleh melayang ketika objek bergerak, menyebabkan koheren bingkai temporal yang rendah. Ketidakstabilan semacam ini boleh menyebabkan sudut yang dipotong satu bingkai dan tidak dalam bingkai yang lain, dan jittering seperti ini boleh menjadi agak buruk secara visual, atau tidak boleh diterima untuk simulasi fizikal.

Manfaat lain dari ujian pesawat tebal ini adalah bahawa titik-titik berbaring sangat dekat dengan pesawat itu sebenarnya boleh dipertimbangkan sebagai berada di pesawat, yang membuat geometri yang dipotong sedikit lebih berguna. Ia adalah mungkin untuk titik persilangan yang dikira secara numerik terletak di sebelah yang salah dari satah! Pesawat tebal mengelakkan masalah pelik seperti itu.

Dengan menggunakan pesawat yang tebal untuk ujian persimpangan, jenis kes baru boleh ditambah: satu titik meletakkan langsung pada satah.

Sutherland-Hodgman sepatutnya diubah suai seperti itu (dengan titik terapung EPSILON untuk menjelaskan pesawat tebal):

Walau bagaimanapun, bentuk Sutherland-Hodgman hanya menghasilkan simpang pada satu sisi pesawat berpecah. Lima perkara ini dapat dengan mudah diperluas ke satu set sembilan ke simpul output di kedua-dua sisi satah pemisah:

Pelaksanaan sembilan kes ini mungkin kelihatan seperti berikut (diperolehi daripada Pengesanan Perlanggaran Sebenarnya Ericson):

Berikut adalah contoh tindakan Sutherland-Hodgman:

Splitting a polygon via Sutherland-Hodgman by user interaction. Polygons are triangulated as a triangle fan.
Memisahkan poligon secara dinamik menerusi Sutherland-Hodgman dengan interaksi pengguna. Poligon adalah triangulasi sebagai kipas segitiga.

Perlu diperhatikan bahawa poligon akhir boleh diberikan sebagai senarai puncak dengan format kipas segitiga.

Kekuatan Numerikal

Terdapat satu masalah yang perlu anda ketahui: apabila mengira titik persimpangan ab dan satah pemisahan, titik ini menderita daripada kuantisasi berangka. Ini bermakna bahawa apa-apa nilai persilangan adalah penghampiran nilai persilangan sebenar. Ini juga bermakna bahawa titik persilangan ba tidak sama secara berangka; hanyut berangka kecil sebenarnya akan menghasilkan dua nilai yang berbeza!

Example of a visible crack between triangles as a result of inconsistent clipping (image inspired by Ericson's Real-Time Collision Detection book).
Contoh retakan yang kelihatan antara segitiga akibat keratan tidak konsisten (imej yang diilhami oleh buku Pengesanan Tebatan Sebenar Ericson).

Rutin kliping naif boleh membuat kesilapan besar titik persilangan pengkomputeran secara membuta tuli, yang boleh mengakibatkan T-persimpangan atau jurang lain dalam geometri. Untuk mengelakkan masalah sedemikian, orientasi persimpangan yang konsisten mesti digunakan. Dengan konvensyen, mata harus dipotong dari satu sisi ke pesawat lain. Pesanan persimpangan yang ketat memastikan bahawa titik persilangan yang sama dikira, dan akan menyelesaikan jurang yang berpotensi dalam geometri (seperti yang ditunjukkan dalam imej di atas, terdapat hasil keratan yang konsisten di sebelah kanan).


Koordinat UV

Untuk benar-benar membuat tekstur berbanding bentuk perpecahan (mungkin apabila memisahkan sprites), anda memerlukan pemahaman koordinat UV. Perbincangan lengkap mengenai koordinat UV dan pemetaan tekstur adalah jauh di luar skop artikel ini, tetapi jika anda sudah mempunyai pemahaman ini, mudah untuk mengubah titik persilangan ke ruang UV.

Sila faham bahawa transformasi dari ruang dunia ke ruang UV memerlukan perubahan asas mengubah. Saya akan meninggalkan transformasi UV sebagai latihan untuk pembaca!


Kesimpulan

Dalam tutorial ini, kami melihat beberapa teknik aljabar linear mudah untuk menangani masalah bentuk generik pemisahan secara dinamik. Saya juga membincangkan isu-isu mantap berangka. Anda kini dapat melaksanakan kod pemisah bentuk anda sendiri, atau menggunakan sumber demonstrasi, untuk mencapai banyak kesan dan ciri maju atau menarik untuk pengaturcaraan umum.

Rujukan

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.