Komputasi Hull Convex Dan Pengurangan Segitiga

Convex hull dari satu set poin adalah objek cembung minimal yang merangkum obyek lain, baik cembung atau cekung. Akibatnya, convex hull dari objek cembung itu sendiri, dan lambung cembung cekung benda selalu lebih besar volume dari bentuk aslinya.

Solusi 2 Dimensi
Beberapa cara dapat digunakan untuk menghitung convex hull dari satu set poin. Dalam 2D, kita akan menggunakan “rubberband metode.” Metode sederhana menghitung convex hull dengan menggunakan kriteria sudut. Kita mulai dengan mencari titik di mesh yang memiliki Xvalue minimal. Jelas, simpul dengan minimal nilai koordinat selalu menjadi bagian dari convex hull. Kemudian, kita loop melalui simpul yang tersisa, mencari untuk vektor yang terletak (angularly berbicara) ke salah satu ekstrim yang lain.
Dengan kata lain, kita harus pilih vertex dari set sehingga segmen dari vertex asli dengan yang satu ini baru ditambahkan memiliki semua simpul lainnya terletak di hemispace sama. Kami kemudian menghilangkan titik baru dan seterusnya sampai kita tidak bisa menambahkan simpul lebih lanjut, dan kita mencapai titik awal lagi.

Solusi 3 Dimensi
Beberapa algoritma telah diusulkan untuk membuat lambung cembung 3D. Salah satu yang terbaik adalah yang Quickhull algoritma, yang menggunakan membagi-dan-menaklukkan pendekatan. Idenya sederhana: Mulailah dengan simpul yang merupakan bagian dari solusi dan rekursif menambahkan simpul baru ke solusi, pemurnian itu. Implementasi ini cukup kompleks.
1. Mengalokasikan polyhedron yang akan memegang solusi.
2. Hitung simpleks maksimal dari daftar titik 3D. Dalam kasus 3D, kita harus menemukan empat poin dari set yang mendefinisikan volume tetrahedron maksimal, yang akan menjadi bagian dari hasil kami. Untuk menghitung tetrahedron, ikuti langkah berikut:
a. Hitung poin dengan X maksimum dan minimum, Y, dan Z.
b. Membangun garis yang menghubungkan titik-titik jarak minimum dan maksimum di setiap arah: Xmin
untuk Xmax, dan sebagainya.
c. Pilih jalur terpanjang dari tiga. Itu salah satu tepi tetrahedron.
d. Sekarang, pilih titik (dari himpunan minimax) yang memiliki jarak terpanjang untuk baris. Bahwa
titik dan garis mendefinisikan segitiga yang merupakan bagian dari solusi.
e. Gunakan pesawat dukungan dari segitiga dan mendeteksi titik dari himpunan minimax yang terjauh
dari pesawat. Pesawat dan titik baru dihitung menentukan tetrahedron, dan dengan demikian
simpleks tersebut.
3. Urutkan poin menjadi orang-orang di dalam dan luar tetrahedron. Hapus di dalam mereka, karena mereka yang pasti bukan bagian dari solusi. Urutkan luar mereka menjadi empat kelompok, tergantung pada pesawat dari tetrahedron mereka berada di luar. Jika titik berada di luar lebih dari satu pesawat, tempatkan secara acak di salah satunya. Mari kita sebut keempat set yang OUTSIDEset mengenai wajah.
4. Walaupun ada wajah dalam convex hull yang luar himpunan tidak kosong:
a. Menemukan titik di set luar yang paling jauh dari pesawat dukungan.
b. Hitung cakrawala dari polyhedron seperti yang terlihat dari titik yang dipilih. Ini digunakan untuk
memperbaiki tepi dari kami polyhedron yang tidak benar-benar bagian dari convex hull.
Untuk membangun cakrawala, kita melakukan pencarian pertama kedalaman mulai dari segitiga titik calon terletak masuk Pada setiap langkah dalam proses, kami menyeberangi salah satu ujung dan mengunjungi segitiga tetangga. Jika terlihat, kita melintasi tepi lain, dan sebagainya. Setiap kali penyeberangan tepi mengarah ke nonvisible (dalam hal produk dot antara yang normal dan vektor sudut pandang, seperti dalam (pemusnahan) segitiga, kita menyimpan tepi menyinggung sebagai bagian dari cakrawala dan menghentikan pencarian.
Bila algoritma berakhir, kita memiliki daftar tepi yang semuanya bagian dari cakrawala.
c. Membangun sebuah kerucut dari titik baru ke simpul di cakrawala.
d. Bagilah set luar menjadi dua set baru. Titik-titik di dalam kerucut akan dihapus
(Karena mereka bukan bagian dari convex hull), sedangkan di luar mereka adalah LUAR baru
ditetapkan.
e. Iterate.
5. Sekarang tidak ada simpul di salah satu set luar, dan dengan demikian convex hull dihitung.
Quickhull adalah algoritma kompleks. Tetapi dalam kompleksitas terletak efisiensi. Quickhull berjalan dalam O (n2), Sedangkan biaya kasus rata-rata dekat dengan N * log N, yang akan menjadi solusi optimal untuk masalah seperti ini.
Pengurangan Segitiga
Keluarga lain dari algoritma geometris kami akan meninjau adalah metode pengurangan segitiga, yang digunakan untuk menciptakan variabel-resolusi dari jerat mesh dasar. Meskipun beberapa game tidak pernah menggunakan pengurangan segitiga atau menggunakannya pada tahap pemodelan, banyak orang lain merasa berguna untuk melakukan beberapa jenis pengurangan perangkat lunak segitiga.
Beberapa alasan populer untuk hal ini adalah
Kita Memilih tingkat detail untuk sebuah objek yang bisa sampai dekat atau jauh
Kita Menggunakan jerat resolusi yang lebih rendah untuk menghitung bayangan
kita membuat permainan untuk kemampuan perangkat keras pemain pada waktu yang
Apapun kasus Anda, kebijakan pengurangan segitiga dapat diimplementasikan baik sebagai preprocess pada waktu buka, dengan asumsi biaya komputasi relatif tidak penting, atau sebagai proses real-time, menghitung penurunan bertautan secara real time. Jelas, algoritma akan berbeda tergantung pada pilihan Anda. segitiga pengurangan bukanlah proses yang sederhana, dan dengan demikian mencoba untuk menghitung mesh multiresolusi baik secara real time pasti akan membutuhkan perencanaan yang cermat.