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). Masalahnya garis atau permukaan mana yang harus dihilangkan?
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; }
Terdapat beberapa cara atau metode untuk mendeteksi suatu permukaan yang terlihat ini, yaitu:
** 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 A-Buffer
Metode A-Buffer mewakili antialiased, daerah rata-rata, metode buffer akumulasi. Setiap posisi dari A-buffer memiliki 2 bidang, yakni:
- Depth field (Kedalaman bidang) memberikan nilai yag positif atau negative.
- Intensity filed (Intensitas diajukan) memberikan informasi intensitas dari permukaan atau merupkan nilai pointer.
** Metode Pohon BSP (Binary Space Partitioning)
Polygon akan scan-converted dengan benar, jika menyediakan pemesanan oklusi front-to-back, semua poligon yang ada di sisi lain dari viewer,dikonversi pertama kali dan diikuti oleh polygon tersebut, kemudian semua sisi yang sama dari viewer. Bentuk (construct) dari pohon BSP adalah:
Daun dari suatu pohon BSP merepresentasikan sebuah subspace cembung, dengan simpul yang mengikat daun dan setiap simpul dalam sebuah pohon BSP menggambarkan subspace – subspace yang terdiri dari semua node anak-anak,
Keuntugan dari metode adalah cocok untuk aplikasi yang berhubungan dengan perubahan sudut pandang tapi tidak untuk suatu objek. Kerugiannya adalah mememrlukan preprocessing (banyak polygon yang membelah (split) daripada depth-sort), penghitungan dalam pembuatan bayangan dapat terjadi lebih dari satu kali.
** Metode Octree
Metode direpensentasikan pada benda yang bervolume. Permukaaan yang terlihat ditentukan dengan mencari node (simpul) octree dari depan ke belakang.
Terdapat 2 octree traversal, yaitu:
– Hierarchically recursive traversal (traversal hirarki recursif)
– Test octants by OQ test accelerated by GPU (Uji tes octants oleh OQ dipercepat oleh GPU
** Metode Ray-Casting
Ray-Casting atau dikenal juga dengan ray-tracing merupakan metode untuk menghitung jalan gelombang atau partikel melalui suatu system. Dalam grafik computer ray–casting adalah teknik untuk menghasilkan suatu gambar dangan menelusuri jalan cahaya melalui pixel dalam gambar pesawat. Terdapat 2 bentuk metode yang berbeda, yaitu:
- Ray-tracing(physics) menganalisis system optic, contohnya pada sinyal radio, samudera akustik, dan dewsain optis
- Ray-tracing(graphics)digunakan untuk generasi gambar 3D, yang mampu menghasilkan tingkat ketajaman yang tinggi.
Contoh algoritmanya dari suatu metode Ray-Casting adalah:
select center of projection and window on viewplane;
for( each scan line in image) {
for (each pixel in scan line) {
determine ray from center of projection through pixel;
for (each object in scene) {
if (object is intersected and is closest considered thus far)
record intersection and object name; }
set pixel color to that at closest object intersection; } }
** Metode Curved Surfaces
Ada 2 cara dalam metode ini, yaitu:
• Catmull 74, 75
Dia menerangkan bahwa potongan kecil (patch) akan dibagi menjadi 4 potonga keci lagi secara rekursif ke dalam s dan t hingga proyeksny dapat mencakup tidak lebih dari 1 pixel. Setelah itu, metode z-buffer diterapkan.
• Subdivisi adaptif
Pembagian patch hanya terjadi pada direksinya (arahnya), jika patch tesebut sudah cukup datar terhadap yang lainnya. Setelah pembagiannya sudah cukup, maka tiap patch dijadijkan/diperlakukan menjadi segiempat.Terakhir diterapkannya algoritma scan-line.
** Metode Wireframe
Metode ini merupakan penyesuaian dari metode z-buffer, dimana permukaan dapat dilukiskan/digambarkan ke dalam refresh buffer sehingga permukaan interior menjadi warna latar belakangnya dan batas-batasnya menjadi warna di latar depan.
Selain itu, terdapat juga beberapa teknik untuk mengefisiensikan algoritma dari permukaan terlihat. Di antaranya adalah sebagai berikut:
a. Koheren (Coherence) == > Objek, Face, Edge, Scan-line, Luas(Daerah), Kedalaman dan Frame
b. Extents and Bounding Volumes
Contoh:
Gambar di samping menampilkan gambar segitiga dan bounding volumenya.
c Hierarchy
Testing dimulai dari akar atau puncak dari node, yaitu:
1. Jika terletak di luar, maka semua objek ditolak.
2. Sebaliknya, sub-node dites berulang
.
d. Spatial Partitioning
Contoh gambar:
(b)
(a)
e. Back-Face Culling
Merupakan back-face penghapusan yang akan membuat tidak akan ada lagi faces (gambaran) di belakang objek yang akan ditampilkan. Batasan dari algoritma ini adalah:
- Hanya dapat digunakan pada benda padat yang dimodelkan sebagai polygon mesh. Ini merupakan model yang paling umum untuk membangun system grafis line-scan.
- Bekerja baik pada polyhedral cembung, tapi belum tentu pada polyhedral cekung. Contohnya pada gambar di bawah ini, dimana bagian dari hidden face tidak akan dihapuskan oleh penghapusan back-face (pengolahan yang lebih lanjut).
Titik-titik yang terdapat pada permukaan normal dapat dikategorikan bebrapa jika dilihat dari suatu pusat proyeksi pada poligonnya.
– Positive : poligon back-face
– Zero : jika dilihat dari tepi
– Negative : poligon front-face