Visible Surface determination (VSD) : Image-Precission

Visible Surface determination (VSD) atau disebut juga dengan Hidden Surface Removal (HSR) merupakan suatu cara untuk menentukan garis atau permukaan yang terlihat pada suatu objeck 3D dan spesifikasi pandangan (kamera),sering juga di definisikan sebagai suatu algoritma yang digunakan untuk menghilangkan penampilan bagian yang tertutup oleh objek yang didepannya. Apabila ada dua bidang yang berpotongan ditampilkan biasa tanpa menggunakan algoritma Visible Surface Determination, maka bagian yang berpotongan itu tidak terlihat karena bidang yang satu ditutupi oleh bagian yang lain tanpa memotong.

Terdapat 3 pendekatan utama pada permukaan terlihat, yaitu:

1. Tes penampakan konservatif (conservative surface test)  hanya sebatas trivial reject saja, yang tidak memberikan jawaban, contohnya back-free culling. Untuk mendapat penyelesaiannya harus dilakukan dengan pendekatan yang lain.

2. Ketelitian gambar (image-precission)  bagian yang erlihat ditentukan dengan point-point pada setiap posisis pixelnya pada bidang proyeksi. Contohnya pada raytracing, atau Z-buffer

 

// Image or Pixel Precision – O(p) operations

for(each pixel) {

determine the object closest to the viewer that is

pierced by the projector through the pixel;

draw the pixel in the appropriate color;     }

3. Ketelitian objek (object-precission) menentukan bagian mana yang terlihat dengan membandingkan objek dan bagian-bagiannya dalam layar . Contohnya pada poly clipping, BSP trees,dll

// Object Precision – O(n2) operations

for(each object) {

determine those parts of the object whose view is

unobstructed by other parts of it or any other object;

draw those parts of appropriate color; }

Algoritma yang akan di bahas yang terdapat pada VSD, yaitu Image-Precision

• Z-Buffer
• Algoritma Painter

1. Z-Buffer

      Z-Buffer adalah Area dari memori grafis yang digunakan untuk menyimpan Z atau kedalaman informasi atau objek yang digambar. Nilai Z-buffer sebuah pixel digunakan untuk menentukan apakah ia terletak di belakang atau di depan pixel lainnya. Kalkulasi Z mencegah objek pada background menimpa objek yang berada di depannya dalam frame buffer.

Metode Depth-Buffer

Metode ini untuk menguji dari depth-z dari masing-masing permkaan untuk menentukan permukaan terlihat. Pertama kali ditemukan oleh Catmull 74. Algoritma dari Depth-Buffer (Z-Buffer), yaitu:

• Menginisialisas depth-buffer dan me-refeshnya sehingga untuk semua posisi penyangga (x, y) ==> depth(x,y)= 0, refresh(x,y)= I_background
• Menghitung kedalaman z pada setiap posisi (X,y) dalam polygon If  z> depth(x,y), then set depth (x,y) = z, refresh(x,y)=I_surface(x,y)
• Hitung nilai z untuk polygon planar. Dengan rumus Z = (-D-Ax-By)/ C. Lalu pada (x+ Dx,y), nilia dari z adalah z’=z-A/C 
• Jika polygon tidak planar, maka di-subdivide (dibagi lagi).

Keuntungan:

• Presorting tidak ada dan perbandingan objek-objek diperlukan
• Waktu yang diambil dari perhitungan permukaan terlihat adalah konstan
• Merupakan implementasi yang sederhana dan mudah pada hardware
• Baik untuk animasi dan sangat mudah untuk diterapkan

Kekurangan

• Membutuhkan memori yang besar untuk Z dan Frame buffer
• Merupakan subjek yang menggunakan nama lain.  == > Improved by A-buffer algorithm [CARP 84] 
• Dapat menggambarkan pixel yang sama beberapa kali.

Metode alternatif untuk menghitung nilai kedalaman z menggunakan persamaan bidang.

1. Melakukan transformasi kedalaman perspektif (untuk mempertahankan bidang).
2. Menghitung persamaan bidang (tidak sama seperti sebelum transformasi perspektif) 
3. Untuk setiap pixel di PDC (xp, yp) menemukan x, nilai WDC y (menggunakan titik inverse transform) 
4. Masukan x, y dalam persamaan pesawat untuk menemukan z di WDC 
5. Melakukan z buffer test pada z.

2. Algoritma Painter

      Algoritma Painter atau Algoritma pelukis yang juga dikenal sebagai fill prioritas, adalah salah satu solusi yang paling sederhana untuk masalah visibilitas pada grafis komputer 3D. Saat memproyeksikan adegan 3D ke bidang 2D, perlu beberapa titik untuk menentukan poligon mana yang terlihat, dan mana yang tersembunyi.

     Nama "Algoritma Pelukis" mengacu pada teknik yang digunakan oleh banyak pelukis untuk mengecat bagian jauh dari sebuah adegan sebelum bagian yang lebih dekat sehingga menutupi beberapa area bagian yang jauh. Algoritma pelukis memilah semua poligon dalam pemandangan dengan kedalamannya dan kemudian melukisnya dalam urutan ini, paling jauh ke terdekat. Ini akan melukis bagian-bagian yang biasanya tidak terlihat - sehingga memecahkan masalah visibilitas - dengan biaya untuk melukis area tak terlihat dari benda-benda yang jauh. Pengurutan yang digunakan oleh algoritma ini disebut 'tatanan kedalaman', dan tidak harus menghormati jarak numerik ke bagian-bagian adegan: properti penting dari pemesanan ini adalah, sebaliknya, jika satu objek mengaburkan bagian dari yang lain maka Objek pertama dilukis setelah objek yang dikaburkannya. Dengan demikian, pemesanan yang valid dapat digambarkan sebagai urutan topologi dari grafik asiklik yang diarahkan yang mewakili oklusi antara objek. 

     Pegunungan yang jauh dilukis terlebih dahulu, diikuti oleh padang rumput yang lebih dekat; Akhirnya, pepohonannya dilukis. Meskipun beberapa pohon lebih jauh dari sudut pandang daripada beberapa bagian padang rumput, pemesanan (pegunungan, padang rumput, pepohonan) membentuk urutan kedalaman yang valid, karena tidak ada objek dalam pemesanan yang mengaburkan bagian dari objek selanjutnya.

(Poligon yang tumpang tindih dapat menyebabkan algoritma gagal)

     Algoritma ini bisa gagal dalam beberapa kasus, termasuk siklik siklik siklik atau menusuk. Dalam kasus tumpang tindih siklik, seperti yang ditunjukkan pada gambar di sebelah kanan, Poligon A, B, dan C saling tumpang tindih sedemikian rupa sehingga tidak mungkin menentukan poligon mana yang berada di atas yang lain. Dalam kasus ini, poligon yang menyinggung harus dipotong agar memungkinkan pemilahan. Algoritma Newell, yang diusulkan pada tahun 1972, menyediakan metode untuk memotong poligon semacam itu. Berbagai metode juga telah diusulkan di bidang komputasi geometri.

     Kasus poligon menusuk muncul saat satu poligon memotong yang lain. Seperti tumpang tindih siklik, masalah ini dapat diatasi dengan memotong poligon yang menyinggung. Dalam implementasi dasar, algoritma pelukis bisa menjadi tidak efisien. Ini memaksa sistem untuk membuat setiap titik pada setiap poligon dalam set yang terlihat, bahkan jika poligon itu tersumbat dalam adegan selesai. Ini berarti bahwa, untuk detail adegan, algoritma pelukis bisa terlalu menekan perangkat keras komputer.

     Algoritma pelukis reverse terkadang digunakan, di mana objek yang paling dekat dengan penampil dicat terlebih dahulu - dengan aturan bahwa cat tidak boleh diterapkan pada bagian gambar yang sudah dicat (kecuali jika sebagian transparan). Dalam sistem grafis komputer, ini bisa sangat efisien, karena tidak perlu menghitung warna (menggunakan pencahayaan, tekstur dan semacamnya) untuk bagian pemandangan jauh yang tersembunyi oleh benda-benda di dekatnya. Namun, algoritma sebaliknya menderita banyak masalah yang sama dengan versi standarnya.     

     Kelemahan ini dan kekurangan lainnya dengan algoritma menyebabkan pengembangan teknik penyangga Z, yang dapat dipandang sebagai pengembangan algoritma pelukis, dengan menyelesaikan konflik mendalam berdasarkan basis piksel demi pixel, mengurangi kebutuhan akan basis berbasis kedalaman. Rendering order Bahkan dalam sistem seperti itu, varian algoritma pelukis kadang dipekerjakan. Karena implementasi Z-buffer umumnya bergantung pada register buffer kedalaman presisi tetap yang diterapkan pada perangkat keras, ada cakupan untuk masalah keterlihatan karena kesalahan pembulatan. Ini adalah tumpang tindih atau kesenjangan pada sendi antara poligon. Untuk menghindari hal ini, beberapa implementasi mesin grafis "overrender" [rujukan?], Menarik tepi kedua poligon yang terpengaruh sesuai urutan algoritma pelukis. Ini berarti bahwa beberapa piksel benar-benar ditarik dua kali (seperti algoritma pelukis penuh) tapi ini hanya terjadi pada sebagian kecil gambar dan memiliki efek kinerja yang dapat diabaikan.