Cakupan - cacat dalam algoritma - bagaimana cara menghilangkan penggunaannya?

pengantar

Banyak mesin render grafis vektor arus utama memiliki kekurangan algoritmik di dalamnya. Mereka membuat setiap bentuk secara terpisah, dan antialias dengan menghitung cakupan piksel dan kemudian menyusunnya di atas satu sama lain. Ya itu sederhana tetapi solusi yang benar bahkan lebih sederhana.

Ini mengarah ke masalah penggabungan karena mengonfigurasi cakupan dengan transparansi. Alpha blending mengikuti aturan yang tidak mewakili situasi secara akurat misalnya mengambil piksel yang 50% tertutup yang bertetangga dengan piksel yang juga 50% saling melengkapi tidak berakhir dengan 100% cakupan itu berakhir dengan 75% cakupan . Bagaimana ini terlihat tergantung pada bagaimana algoritma disetel dan detail lainnya tetapi pada dasarnya ini adalah kesalahan yang diketahui. Seseorang bahkan mengalami kesulitan mendokumentasikan kesalahan mesin yang berbeda bersama dengan menulis makalah yang menunjukkan bagaimana hal itu dapat dilakukan dengan lebih baik.

Gambar 1 : Sampel yang benar-benar tidak representatif, dari render bentuk yang terbuat dari segitiga yang menunjukkan kesalahan diperbesar di baris atas. Sumber SVG

Masalahnya memiliki solusi naif sederhana * hanya sampel super tanpa perhitungan cakupan dan filter gambar ke bawah. Sebagai bonus Anda bisa menggunakan algoritma rekonstruksi gambar yang lebih baik daripada pemfilteran kotak (baca A Pixel is Not a Square ³ ). Bahkan ada solusi yang memiliki kecepatan yang sebanding dengan solusi saat ini dan solusi ini jauh lebih mudah dilakukan dalam pipa rasterisasi perangkat keras (dan Anda jarang melihat kesalahan ini pada GPU karena itu dibangun untuk menghindari hanya masalah ini).

Ini juga bukan masalah tanpa biaya. Ada banyak orang yang bekerja dalam desain grafis yang menghabiskan banyak waktu untuk menghindari masalah ini secara manual dengan memastikan ada tumpang tindih di sini dan tidak ada tumpang tindih di sana untuk memperbaiki masalah yang harus dilakukan komputer untuk mereka. Dan gagal secara spektakuler dalam banyak kasus. Tetapi klien mereka tidak peduli mengapa ada kesalahan, mereka harus memperbaikinya.

Pertanyaan

Bagaimana kesalahan menyebar? Karena mereka semua melakukan kesalahan yang sama, orang dapat menyimpulkan bahwa mereka menggunakan sumber yang sama untuk algoritma mereka. Apa yang bisa menyebabkan para desainer memilih algoritma ini? Mengapa hanya programmer 3D yang mengenali kesalahan ini dan bahkan mengkodifikasikan bagiannya dalam API dan pengajaran mereka sementara programmer 2D tidak melakukannya?

Bagaimana memastikan bahwa kesalahan ini berhenti merambat lebih lanjut?

Adendum (tetapi saya tidak bertanya tentang ini)

* Rupanya klaim saya bahwa super sampling bekerja tanpa cacat adalah luar biasa dan membutuhkan bukti luar biasa. Ok, jadi kunci untuk super sampling berfungsi adalah super sampling tidak melakukan pemrosesan cakupan. Intinya super sampler memperlakukan setiap sampel sebagai sampel titik. Karena sampel titik tidak membuat asumsi area yang mendasarinya, maka tidak menyebabkan perbandingan alfa jika tidak terjadi.

Agar itu bekerja secara konsisten, seperti dijelaskan dalam salah satu jawaban. Kita perlu membuat untuk memproses sampel dengan integer sampling untuk konsistensi. Ini meyakinkan kita bahwa setiap titik yang pernah diubah menjadi ruang layar mendapatkan solusi yang persis sama untuk koordinat yang sama dan tidak ada sampel yang diarsir oleh batas piksel 2 kali. Untuk melakukan ini sampel tidak boleh memicu pixel atau tepat pada jika itu adalah contoh kiri bawah contoh (jadi kami membuat aturan bahwa tepi yang tepat diproses di> vs <=). Semua kecuali satu kartu grafis konsol berfungsi seperti ini. Ini memastikan bahwa tidak ada data tambahan yang perlu di-cache dan tidak ada pengujian tambahan di dekatnya yang perlu dilakukan. Solusi ini stabil, lebih umum dan konsisten daripada solusi berbasis cakupan.

Algoritma ini persis sama dengan aslinya dengan kode sedikit lebih sedikit dan sampel lebih sedikit. Dengan demikian sama konsisten jika tidak lebih dari algoritma berbasis cakupan. Kami mengetahui hal ini karena kami telah menggunakan metode tersebut untuk waktu yang lama di hampir semua bidang pemrosesan sinyal lainnya serta kartu grafis.

Jadi, apakah metode ini memiliki kelemahan? Yah itu sedikit lebih lambat jika Anda hanya akan membuat asumsi naif. Secara teori ia memiliki perilaku asimptotik yang lebih cepat daripada cakupan rasterizer, sedikit seperti raytracer, ia masih setara dengan adegan-adegan tertentu. Juga bisa membuat penggunaan efek berbasis konvolusi lebih menyakitkan untuk diterapkan.

Supersampling, ketika dilakukan secara naif, mahal secara komputasi, karena jika Anda menggunakan misalnya setengah ukuran piksel dari tampilan Anda, Anda memerlukan memori empat kali dan lebar pita. Wikipedia menyebutkan ini dan juga menyebut supersampling adaptif sebagai solusi yang memungkinkan. Tetapi itu mulai membuat algoritma jauh lebih canggih, kompleks dan sulit untuk diimplementasikan.

Dan saya kira itulah alasan yang Anda cari: jika Anda menginginkan suatu algoritma yang tidak membutuhkan banyak memori dan waktu yang berjalan, banyak hal menjadi jauh lebih rumit daripada dalam pendekatan "transparansi" yang naif.

Supersampling tidak akan menyelesaikan masalah secara umum: itu hanya akan membuatnya kurang terlihat. Dengan piksel setengah ukuran, masalahnya akan setengah terlihat tetapi tidak hilang.

Titik arsitektur di balik desain ini adalah bahwa kita ingin perintah "render triangle ABC" memiliki makna yang pasti. Kami tidak ingin itu menjadi ambigu kecuali jika dianggap sebagai bagian dari kumpulan perintah menggambar - misalnya, memiliki satu makna ketika "render triangle BCD" juga dalam koleksi (dengan warna yang sama atau berbeda) dan makna lain saat bukan itu.

Mempertimbangkan, misalnya, seribu segitiga, bahkan menemukan semua segitiga yang berbagi sisi atau bagian dari sisi dengan ABC adalah komputasi yang berat (mengingat bahwa itu harus dilakukan ulang seribu kali). Ada banyak masalah praktis lainnya juga: terutama bahwa semua permintaan render asli harus disimpan, bahkan jika mereka sudah ditarik sejak lama, jika mereka perlu ditinjau kembali karena permintaan baru tambahan.

Intinya adalah bahwa solusi yang sangat konsisten tidak praktis. Masih ada pertanyaan: haruskah kita mencoba memperbaiki situasi saat ini ketika kita bisa? Secara umum, jawaban untuk pertanyaan itu adalah Tidak . Implementasi model yang konsisten sempurna selalu lebih baik, bahkan jika model itu sendiri memiliki keterbatasan yang telah Anda ilustrasikan. Alternatifnya adalah implementasi yang terkadang lebih baik dan kadang tidak, tanpa programmer dapat mengetahui yang mana dari dua ini akan bertahan dalam kasus tertentu. Selain itu, dapat melompat dari "berbuat lebih baik" ke "tidak melakukan lebih baik" sebagai akibat dari perubahan kecil yang dibuat oleh programmer - atau bahkan sebagai akibat dari yang di luar kendali programmer. Prediktabilitas, dalam konteks pemrograman, jauh,