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)= Ibackground
- Menghitung kedalaman z pada
setiap posisi (X,y) dalam polygon If z> depth(x,y), then set
depth (x,y) = z, refresh(x,y)=Isurface(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.
- Melakukan transformasi
kedalaman perspektif (untuk mempertahankan bidang).
- Menghitung persamaan bidang
(tidak sama seperti sebelum transformasi perspektif)
- Untuk setiap pixel di
PDC (xp, yp) menemukan x, nilai WDC y (menggunakan
titik inverse transform)
- Masukan x, y dalam persamaan
pesawat untuk menemukan z di WDC
- 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.
