Mahmuda, Arif Fathur (2017) Konstruksi Bounding Volume Hierarchy Dengan Metode Agglomerative Clustering Untuk Meningkatkan Performa Ray Tracing. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5112100118-Undergraduate-Theses.pdf - Published Version Download (2MB) | Preview |
Abstract
Ray Tracing Sebagai algoritma rendering yang menghasilkan citra realistis memiliki beberapa kekurangan. Salah satu di antaranya adalah perhitungan persilangan ray-object pada tiap pixel yang memakan 75% waktu dari keseluruhan proses.
Penulis menerapkan metode yang diharapkan dapat mempersingkat proses perhitungan persilangan ray-object dengan membangun struktur data berupa binary tree (Bounding Volume Hierarchy) di mana masing-masing node-nya adalah sebuah container. Container tersebut akan mencakup container lain atau sebuah poligon. Struktur data tersebut akan dibangun dengan metode Approximate Agglomerative Clustering (AAC) yang merupakan metode bottom-up clustering dengan top-down preprocessing.
Dengan Metode yang diterapkan, diharapkan performa Ray Tracing akan meningkat secara signifikan. Metode AAC dengan arameter yang baik dapat meningkatkan performa Ray Tracing. Metode-metode yang diterapkan sangat mudah diparalelkan sehingga performa algoritma meningkat jika dijalankan pada lingkungan paralel. Hasil uji coba penulis menunjukkan peningkatan kecepatan hingga 3 kali lipat dibandingkan tanpa menerapkan paralelisme. Pada hasil uji coba, penulis juga mendapatkan dua jenis parameter yang masingmasing memiliki karakteristik tersendiri (6= cepat, 12= HQ).
=========================================================================================
Ray tracing as a realistic rendering method has some limitation. One of them is expensive cost for ray-object intersection that takes 75% of the whole process. Bounding Volume Hierarchy will greatly improve this step by eliminating intersection calculation with irrelevant object. We could achieve this by designing a tree that contain nodes of containers. Each node will contains two other container or an object.
We implement some methods that will greatly improve the construction of bounding volume hierarchy’s efficiency. We implement a method based on Agglomerative Clustering with some preprocessing that will groups global nodes into smaller approximately close local groups, thus the name Approximate Agglomerative Clustering (AAC) given.
We later found optimal parameters for AAC algorithm such as container type and threshold. We also investigate some optimization to further boost AAC’s efficiency such as parallelism and thread pooling. Our implementation show 3 times boost in speed in parallel environment. We also run several scenarios to get optimum parameter (container type and threshold) values for AAC.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Ray Tracing; Rendering; Agglomerative Clustering; Grafika; BVH |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP Q Science > QA Mathematics > QA76 Computer software Q Science > QA Mathematics > QA278 Cluster Analysis. Multivariate analysis. Correspondence analysis (Statistics) |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | - ARIF FATHUR MAHMUDA |
| Date Deposited: | 11 Apr 2017 03:38 |
| Last Modified: | 08 Mar 2019 04:18 |
| URI: | http://repository.its.ac.id/id/eprint/3121 |
Actions (login required)
 |
View Item |