Bagaimana cara mendapatkan hasil yang akurat dengan algoritma Painter?

14

Beberapa waktu yang lalu saya bertanya bagaimana menentukan kapan wajah saling tumpang tindih. Sarannya adalah menggunakan Z-buffer.

Namun, saya tidak dapat menggunakan Z-buffer dalam proyek saya saat ini dan karenanya saya ingin menggunakan algoritma Painter. Saya tidak memiliki petunjuk yang baik tentang kapan permukaan berada di belakang atau di depan yang lain. Saya sudah mencoba banyak metode tetapi mereka semua gagal dalam kasus tepi, atau mereka gagal bahkan dalam kasus umum.

Ini adalah daftar metode penyortiran yang saya coba sejauh ini:

  • Jarak ke titik tengah setiap wajah
  • Jarak rata-rata ke setiap titik di setiap wajah
  • Nilai z rata-rata dari setiap simpul
  • Nilai z paling tinggi dari simpul setiap wajah dan gambarlah terlebih dahulu
  • Nilai z terendah simpul setiap wajah dan gambar yang terakhir

Masalahnya adalah bahwa wajah mungkin memiliki jarak yang lebih dekat tetapi masih jauh. Semua metode ini tampaknya tidak dapat diandalkan.

Sunting: Misalnya, pada gambar berikut permukaan dengan titik biru sebagai titik tengah dicat di atas permukaan dengan titik merah sebagai titik tengah, karena titik biru lebih dekat. Namun, ini karena permukaan titik merah lebih besar dan titik tengah lebih jauh. Permukaan dengan titik merah harus dicat di atas yang biru, karena lebih dekat , sementara jarak titik tengah mengatakan sebaliknya.

masukkan deskripsi gambar di sini

Apa sebenarnya yang digunakan dalam algoritma Painter untuk menentukan urutan objek yang harus diambil?

pimvdb
sumber
1
The algoritma pelukis yang hanya menggambar dari belakang ke depan.
Jonathan Connell
1
@ 3nixios: Ya, jelas, tetapi dengan cara apa saya bisa menentukan urutan 'kembali ke depan'?
pimvdb
1
Semua objek, segitiga, atau simpul Anda akan berjarak tertentu dari kamera saat Anda mulai menggambar. Menerapkan algoritma dasar (apakah Anda berhasil?) Akan menentukan jarak ini dari kamera untuk setiap segitiga dan menggambar mereka dalam urutan terjauh ke terdekat. Setelah selesai, Anda harus mulai mencari persimpangan dan memotong segitiga Anda, yang merupakan permainan bola yang sangat berbeda . Mengapa Anda tidak dapat menggunakan Z-Buffer? : P
Jonathan Connell
@ 3nixios: Anda sepenuhnya benar, tetapi masalah yang saya hadapi adalah menghitung jarak. Seperti yang saya nyatakan, saya sudah mencoba beberapa metode jarak tetapi semuanya tidak sempurna. Pesanan ini dihasilkan dari penyortiran jarak titik tengah: i.imgur.com/AcfCm.png .
pimvdb
1
Apakah semua poligon Anda berada di grid biasa seperti itu? Jika demikian, mungkin ada hal-hal khusus kisi yang dapat Anda lakukan untuk meningkatkan ini.
CiscoIPPhone

Jawaban:

14

Biasanya jarak titik tengah poligon ke kamera digunakan untuk menyortir z. Algoritma pelukis tidak bisa 100% akurat berdasarkan sifatnya. Akan selalu ada kasus di mana penyortiran akan gagal, tidak peduli titik referensi apa yang Anda gunakan.

Jika Anda ingin benar menyortir z dengan algoritma pelukis, Anda harus mengiris poligon yang tumpang tindih menjadi bagian-bagian yang lebih kecil (misalnya dengan menggunakan quad-tree) dan mengurutkan bagian-bagian ini secara terpisah. Ini bisa menjadi sangat berat pada CPU ..

Menemukan file Powerpoint ini yang menggambarkan masalah dengan baik ( Versi PDF ).

bummzack
sumber
Terima kasih untuk Powerpoint itu, ini membantu saya memecahkan masalah.
pimvdb
Tautan rusak. Adakah yang bisa menemukan salinannya?
Keavon
1
@Keavon Diedit. Saya menemukan tautan yang berfungsi untuk file tersebut.
bummzack
1

Dalam kasus seperti itu bagi saya itu selalu berhasil menggunakan pohon bsp. Membagi adegan sampai Anda memiliki set cembung poligon di node bsp-tree dan kemudian Anda dapat dengan mudah mengurutkan poligon dalam node. Perhatikan bahwa dengan menyortir poligon dari node bsp-tree sepertinya masalah yang sama seperti yang Anda jelaskan di atas, tetapi ada kondisi yang tidak begitu jelas - setelah membangun bsp-tree semua kasus bermasalah sudah diselesaikan - dalam node Anda harus mengakhiri dengan seperangkat poligon yang harus dilewati oleh tes konveksitas - jika Anda memilih sebuah pesawat dari satu poligon dari set ini, sisa poligon semuanya ada di depan pesawat atau di belakang pesawat. Menggunakan info itu membuat penyortiran menjadi mudah - functor penyortiran mengambil 2 poligon - periksa di mana setengah spasi adalah poligon 1 melawan poligon 2 dan juga periksa penempatan kamera terhadap poligon kedua.

Perhatikan juga bahwa tes untuk menentukan sisi penempatan kamera terhadap poligon dan melintasi bsp-tree sedikit berbeda ketika berhadapan dengan proyeksi ortografis dan perspektif.

Jika Anda tidak mampu memisahkan poligon input, saya pikir Anda kurang beruntung.

uskup
sumber