Visual Surface Determination (VSD)

VSD (VISUAL SURFACE DETERMINATION)

KELAS CONSERVATIVE : BOUNDING VOLUME

DISUSUN OLEH      :

Kelompok 3

Nama Anggota :

1.      Andry Darsono ( 51414172 )

2.      Danty Nurachmah S ( 52414531 )

3.      Hamda Prayogo ( 54414716 )

4.      Muhammad Fadhiil (  )

5.      Rizma Dwi Cahyaningsih ( 59414734 )

Kelas : 3IA09

FAKULTAS TEKNOLOGI INDUSTRI / TEKNIK INFORMATIKA

UNIVERSITAS GUNADARMA

2017

Visual Surface Determination (VSD)

            Visual Surface Determination (VSD) atau disebut juga dengan Hidden Surface Removal (HSR) merupakan suatu cara untuk menentukan garis atau permukaan yang terlihat pada suatu objek 3D dan spesifikasi pandangan (kamera). 

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 terlihat ditentukan dengan point-point pada setiap posisis pixelnya pada bidang proyeksi. Contohnya pada raytracing, atau Z-buffer.

3.      Ketelitian objek (object-precission) è menentukan bagian mana yang terlihat dengan membandingkan objek dan bagian-bagiannya dalam layar. Contohnya

A.         Boundering Volume

Bounding Volume Hierarchy (BVH) adalah sebuah struktur data berupa tree yang terdiri dari container yang melingkupi objek atau container lainnya. Dengan menggunakan BVH, kita dapat mengabaikan objek yang parent-nya tidak berpotongan dengan garis yang ditembakkan. Dengan mengabaikan objek-objek yang tidak relevan, kita dapat mempercepat proses Ray Tracing secara signifikan. Gambar (a,b) Menunjukkan ilustrasi BVH pada scene 2 dimensi dan representasi BVH pada tree

Bounding Volume Hierarchy (BVH) dapat mempercepat proses rendering dengan mengabaikan objek yang tidak perlu diperhitungkan. Sayangnya konstruksi BVH bukan hal yang mudah dan konstruksi BVH secara manual tidak praktikal jika dibandingkan dengan kompleksitas scene yang akan di-render. Dalam tugas akhir ini penulis ingin menerapkan Agglomerative Clustering dengan optimalisasi untuk konstruksi BVH secara otomatis.

Dibawah ini ada gambar kelinci yang merupakan contoh dari BVH, gambar yang dibawah ini adalah gambar yg sudah dirender .

Dibawah ini merupakan tampilan yg belum di render , bisa dilihat bawa ada bagian yang tidak perlu difikirkan saat melakukan proses rendering.

B.     Ray Tracing dengan BVH

Pada algoritma Ray Tracing, kita memerlukan perhitungan persilangan ray-object sebanyak jumlah objek per pixel. BVH tersusun dari container dalam bentuk 3 dimensi yang membentuk sebuah tree. Dengan memanfaatkan BVH, objek yang parent-nya tidak bersilangan dengan objek tidak perlu diperhitungkan persilangannya Pada penelitian kali ini diimplementasikan BVH dalam bentuk binary tree.

C.    Approximate Agglomerative Clustering

Digunakan Approximate Agglomerative Clustering sebagai metode untuk membangun BVH. Secara garis besar AAC adalah Agglomerative Clustering dengan tahapan preprocessing yang membagi list cluster menjadi beberapa sub-list hingga perhitungan jarak tidak dilakukan secara global. Fitur utama dari AAC adalah pembagian subset di mana sebuah node hanya perlu mencari tetangga terdekat dari subset tersebut. Dengan node yang sudah tersortir, pembagian subset dapat dilakukan dengan cepat dan tidak akan mengurangi kualitas cluster secara signifikan. Sub-list tersebut lalu di satukan dengan menggunakan Agglomerative Clustering

Tahapan pertama AAC adalah tahap preprocessing data poligon. Proses yang dilakukan adalah menghitung Morton Code masing-masing poligon dan melakukan sorting dengan Radix Sort yang dijalankan pada awal build BVH. Morton Code digunakan untuk memudahkan proses sorting dengan menjaga lokalitas data. Radix Sort digunakan karena cocok digunakan untuk tipe data Morton Code.

Setelah tahapan preprocessing, cluster akan dibentuk pada metode buildTree yang akan menghasilkan cluster sesuai parameter algoritma. Proses ini akan membagi list poligon secara rekursif hingga memenuhi threshold tertentu. Tahap pembagian list memanfaatkan Morton Code sehingga hanya perlu mencari perubahan bit di posisi tertentu. Dikarenakan Morton Code menjaga locality data, hasil pembagian list tidak akan merusak kualitas tree.

Setelah jumlah node dalam suatu subset memenuhi kriteria, akan dilakukan Agglomerative Clustering dengan metode combineCluster yang merupakan implementasi Agglomerative Clustering dengan optimalisasi memoization. Tahap terakhir adalah menggabungkan seluruh cluster yang tersisa menjadi satu cluster (root). Tahap penggabungan cluster pada BVH bersifat non-decremental sehingga kita dapat menerapkan beberapa optimalisasi seperti menghitung jarak di awal pemanggilan loop dan tidak menghitung ulang jarak kecuali pada node yang membutuhkan.