Konstruksi Bounding Volume Hierarchy dengan Metode Agglomerative Clustering untuk Meningkatkan Performa Ray Tracing

Arif Fathur Mahmuda, Anny Yuniarti, Wijayanti Nurul K
Submission Date: 2017-01-24 13:24:37
Accepted Date: 2018-01-25 10:42:49

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 rendering. Penelitian ini menerapkan metode yang diharapkan dapat mempersingkat proses perhitungan persilangan ray-object dengan membangun struktur data berupa binary tree. Tree yang dibangun sering juga disebut sebagai Bounding Volume Hierarchy (BVH) di mana masing-masing node-nya adalah sebuah container. Struktur data tersebut akan dibangun dengan metode Approximate Agglomerative Clustering (AAC) yang merupakan metode bottom-up clustering dengan top-down preprocessing. Metode AAC dengan parameter 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 menunjukkan peningkatan kecepatan hingga 3 kali lipat dibandingkan tanpa menerapkan paralelisme. Pada hasil uji coba,  juga didapatkan dua jenis parameter yang masing-masing memiliki karakteristik tersendiri (6= cepat, 12= kualitas baik).


Keywords


Ray Tracing; Rendering; Agglomerative Clustering; Grafika; BVH

References