Rancang Bangun Ray Tracing Pipeline Pada Platform CUDA Reza Fuad R1 , Mochamad Hariadi2 Game Technology Research Group, Department of Electrical Engineering Sepuluh Nopember Institute of Technology, Surabaya email:
[email protected] ,
[email protected]
Abstrak Ray tracing adalah algoritma penggambaran tiga dimensi yang banyak digunakan untuk memproduksi gambar berkualitas foto realistik. Permasalahan terbesar pada algoritma ray tracing adalah kebutuhan daya komputasi yang sanga besar untuk melakukan penggambaran. Pada penelitian ini akan dilakukan perancangan sistem ray tracing pada platform CUDA dengan menggunakan struktur uniform grid. Platform CUDA merupakan standar parallel processing pada GPU dan dapat digunakan untuk berbagai keperluan komputasi. Hasil penelitian berupa sistem yang dapat berjalan pada interaktif frame rate dengan teknik pencahayaan yang sederhana.
Gambar 1: Struktur uniform grid
Kata kunci: ray tracing, uniform grid, foto realistik, parallel processing
baran adalah dengan menggunakan accelerated structure yang membagi scene menjadi sebuah data spasial. Salah satu accelerated structure yang banyak digunakan adalah uniform grid. Gambar 1 merupakan gambaran struktur uniform grid yang digunakan. Uniform grid telah dikembangkan dan dipublikasikan pada makalah [2, 4, 6, 7, ?]. Secara sederhana struktur uniform grid dapat diumpamakan sebagai sebuah bidang koordinat baru dengan skala satu pixelnya adalah sama dengan besar satu cell pada uniform grid.
1 PENDAHULUAN Penggambaran grafik tiga dimensi telah menjadi tulang punggung untuk beberapa bidang seperti film, arsitektur, grafik desain, dan game. Penggambaran grafik tiga dimensi terdiri dari dua jenis yaitu rasterzation dan PBRT (Physically Based Rendering Technique). Teknik rasterzation biasa digunakan pada game dan aplikasi yang bersifat real-time sedangkan PBRT lebih digunakan untuk aplikasi yang membutuhkan ketepatan penggambaran sesuai dengan sifat-sifat cahaya yang ada di alam. Salah satu contoh aplikasi yang menggunakan PBRT adalah [5] yang menggunakan metode ray tracing untuk penggambaran film “Cars”. Ray tracing merupakan suatu metode penggambaran dengan cara mensimulasikan perjalanan partikel cahaya dari sumber cahaya ke mata penglihat. Pada perkembangannya metode ray tracing kemudian sedikit berubah dari pengertian asalnya yaitu mensimulasikan perjalanan partikel cahaya dari mata penglihat ke sumber cahaya. Perubahan tersebut digunakan untuk mengefisienkan proses perhitungan dan pengertian tersebut hanya digunakan pada bidang keilmuan komputer grafik. Ray tracing diperkenalkan pada makalah [13] dan masih dilakukan dengan bentuk-bentuk geometri yang sederhana seperti bidang datar dan bola. Permasalahan utama pada metode ray tracing adalah kebutuhan komputasi yang sangat besar untuk dapat menggambar satu gambar dengan jumlah polygon yang banyak. Salah satu cara untuk mempercepat penggam-
2 DESAIN SISTEM Perhitungan ray tracing dengan menggunakan struktur uniform grid memerlukan dua tahapan dasar yaitu konstruksi struktur uniform grid dan traversing struktur uniform grid. Tahapan pertama diperlukan untuk membentuk struktur uniform grid sesuai dengan keadaan scene sedangkan tahapan kedua dilakukan pada saat penggambaran yaitu bagaimana program secara selektif melakukan perhitungan perpotongan antara garis perjalanan partikel cahaya dengan polygon yang ada pada scene.
2.1
Pembuatan Struktur Uniform Grid
Secara skematik, rancangan struktur data uniform grid yang digunakan terdapat pada gambar 2. Pada gambar tersebut, pada kiri atas adalah struktur uniform grid yang berkolerasi dengan struktur triangle offset. Pada kiri bawah terdapat struktur triangle offset yang berkolerasi dengan struktur triangle data. Panah dan kolom berwar1
dari input model. Metode perhitungannya menggunakan pemetaan dari AABB suatu polygon ke koordinat uniform grid (koordinat dengan x, y, dan z adalah cell index dan (0,0,0) berada di AABB uniform grid yang paling minimum). Total perhitungan yang dilakukan pada proses ini akan digunakan untuk memesan memori yang dibutuhkan oleh struktur data triangle offset. Paralel Prefix Sum Proses berikut adalah melakukan penambahan terhadap semua hasil yang didapatkan pada proses overlapped polygon untuk mencari total memori yang dibutuhkan untuk struktur triangle offset. Pada proses sebelumnya, data hasil keluaran disimpan dalam array dan proses selanjutnya adalah melakukan penambahan untuk setiap elemen pada array tersebut. Proses penambahan tersebut dinamakan prefix sum. Persamaan 2 merupakan persamaan inclusive scan yang digunakan pada proses ini dengan menggunakan pustaka CUDPP (CUDA Data Parallel Processing) [10, 11].
Gambar 2: Rancangan struktur data
[a0 , a1 , . . . , an−1 ] ⇒ [a0 , (a0 + a1 ), . . . , (a0 + . . . + an−1 )] (2)
na hijau merupakan kolerasi yang terbentuk antara satu struktur dengan struktur lainnya. Rancangan struktur data tersebut mirip dengan rancangan struktur data yang digunakan pada makalah [6, 4] yang melakukan penelitian yang bertujuan sama yaitu penggambaran tiga dimensi dengan metode ray tracing dan struktur data uniform grid. Konstruksi struktur uniform grid mempunyai 6 proses yang dilakukan secara serial dan masing-masing proses berjalan secara paralel. Proses-proses tersebut adalah inisialisasi, overlapped polygon, parallel prefix sum, perhitungan perpotongan cell pada uniform grid, paralel sort, dan scanning data. Proses dan metode yang digunakan pada proses konstruksi struktur uniform grid diambil dari makalah [3].
Perhitungan Perpotongan Cell Perhitungan perpotongan cell adalah proses mencatatan cell mana saja yang berpotongan dengan polygon. Proses ini mirip dengan proses kedua, yaitu overlapped polygon, tetapi pada proses ini bukan menghitung tetapi mencatat cell mana saja yang berpotongan dengan polygon dari model input. Paralel Sort Langkah berikutnya adalah melakukan sorting berdasarkan index cell sehingga membentuk data yang urut dari index cell terkecil ke yang terbesar. Proses pengurutan dilakukan dengan menggunakan algoritma paralel radix sort yang terdapat pada makalah [9], yang sampai saat ini merupakan algoritma paralel sorting yang paling cepat yang pernah diimplementasikan pada platform CUDA. Algoritma dari paralel radix sort tersebut telah diimplementasikan pada pustaka CUDPP dan pustaka tersebut digunakan pada proses ini.
Inisialisasi Proses inisialisasi adalah proses menentukan resolusi uniform grid yang digunakan dan memesan memori yang dibutuhkan untuk menyimpan struktur uniform grid . Persamaan 1 digunakan untuk menentukan resolusi uniform grid dengan nilai variabel k = 5. Nilai k = 5 diambil dari percobaan pada makalah [12] yang menghasilkan nilai k = 5 adalah nilai k terbaik untuk digunakan pada penentuan struktur uniform grid. Proses ini berjalan secara serial pada CPU karena hanya terdiri dari beberapa perhitungan dan pemesanan memori untuk struktur data uniform grid sehingga tidak diperlukan proses paralel. r Nx = dx
3
kP , Ny = dy V
r 3
kP , Nz = dz V
r 3
kP V
Scanning Data Scanning data adalah proses mencatatan index awal dan index akhir yang menyimpan data polygon yang berpotongan dengan index cell. Proses scanning data dilakukan secara paralel dengan thread sebanyak jumlah overlapped polygon yang telah dihitung pada proses kedua. Pada proses scanning data ditekankan bahwa setelah melakukan proses sorting maka data dianggap akan urut dari index cell terkecil ke index cell terbesar sehingga yang diperlukan adalah melihat data pada index cell sekarang dengan data pada index cell sebelumnya dan data pada index cell selanjutnya, jika data index cell sekarang dengan data index cell sebelumnya tidak sama maka berarti index triangle offset sekarang adalah index awal dari cell sedangkan jika data index cell sekarang tidak sama dengan data index cell selanjutnya maka index
(1)
Overlapped Polygon Overlapped polygon merupakan proses untuk mencatat berapa cell yang berpotongan dengan polygon dari model input serta proses perhitungannya bersifat independen pada satu polygon. Proses perhitungan berjalan secara paralel dengan thread berjumlah banyaknya polygon 2
Perpotongan Ray-AABB Scene Perhitungan perpotongan ray dengan AABB dari scene digunakan untuk mengetahui koordinat uniform grid pertama yang digunakan untuk memulai traversal pada struktur uniform grid. Metode deteksi perpotongan antara ray dengan AABB yang digunakan adalah metode slabs. Hasil keluaran dari proses ini adalah koordinat dalam sistem koordinat uniform grid yang pertama kali berpotongan dengan ray. Traversal Proses terakhir adalah melakukan proses traversal dari koordinat uniform grid yang pertama kali berpotongan dengan ray sampai didapatkan ray yang berpotongan dengan suatu polygon atau koordinat uniform grid telah keluar dari AABB scene. Metode traversal yang digunakan adalah metode yang dipaparkan pada makalah [1]. Setiap berganti koordinat, dilakukan perhitungan perpotongan antara ray dengan segitiga yang masuk dalam kelompok segitiga yang berpotongan dengan cell pada uniform grid. Metode deteksi perpotongan antara ray dengan segitiga yang digunakan adalah metode yang dipaparkan pada makalah [8].
Gambar 3: Perhitungan vektor arah ray
triangle offset sekarang merupakan index terakhir pada triangle offset dari cell.
2.2
Ray Tracing Traversal
Tahapan ray tracing traversal dibagi menjadi 3 proses besar yaitu inisialisasi, deteksi perpotongan ray dengan AABB dari scene dan traversal. Metode yang digunakan untuk proses traversal adalah metode yang dipaparkan pada makalah [1]
3 Hasil Percobaan Pada pengujian yang akan dilakukan, digunakan spesifikasi perangkat keras dan perangkat lunak dengan rincian sebagai berikut
Inisialisasi
• Kartu grafik NVIDIA GeForce GTX 260 896 MB DDR3 • Sistem operasi Linux Debian squeeze • NVIDIA CUDA Toolkit 2.3 dan NVIDIA CUDA SDK 2.3
Proses inisialisasi adalah proses perhitungan komponen arah primary ray yang ditembakkan dari kamera ke dalam scene. Terdapat dua proses dalam tahapan inisialisasi yaitu mengorthogonalkan vektor kamera dan menentukan vektor arah dari pusat kamera pada setiap titik pada gambar hasil dengan resolusi yang diinginkan. Pencarian tiga vektor kamera yang orthogonal digunakan metode gram-schmidt orthonormalization. Pada gambar 3 merupakan skema dari kamera yang digunakan untuk menghitung ll, yaitu vektor yang digunakan sebagai acuan titik (0,0) pada gambar yang dihasilkan. Vektor l, v, dan u merupakan vektor arah kamera yang saling orthogonal yang dihasilkan pada proses sebelumnya sedangkan variabel a adalah aspek rasio dari resolusi gambar (panjang/tinggi) dan variabel d dihasilkan dari d = tan( f 1ovy/2) , parameter f ovy adalah sudut kebebasan dari kamera. ll = campos + dl − av − u
Data yang diambil dalam pengujian ini adalah waktu pembuatan/konstruksi struktur uniform grid (tidak termasuk pengiriman data ke memori GPU) dan waktu ray tracing traversal pada saat penggambaran.
(3)
Proses selanjutnya seletah melakukan perhitungan vektor ll adalah menghitung vektor arah sesungguhnya untuk setiap titik pada gambar. Persamaan 4 digunakan untuk perhitungan vektor arah untuk setiap titik pada gambar.
p = ll + 2av
x y + 2u resx resy
(4)
Gambar 4: conference dengan shadow 3
Model / Scene
Sistem yang
Waktu Konstruksi (ms) Sistem pada Sistem pada
Sistem yang
Waktu Traversal (ms) Sistem pada Sistem pada
dirancang
makalah [6]
makalah [7]
dirancang
makalah [6]
makalah [7]
Wood Doll
2,45
n/a
n/a
34,25
n/a
n/a
Bunny
6,14
n/a
10
61.39
n/a
680
Sponza
10,80
13
80
179,84
n/a
1930
Horse
6,81
n/a
n/a
82,49
n/a
n/a
Fairy Forest
18,77
24
n/a
499,61
285
n/a
Conference
24,42
27
n/a
339,91
130
n/a
Hand
24,26
n/a
n/a
99,14
n/a
n/a
Dragon
34,82
n/a
110
133,54
n/a
800
Happy Budha
44,08
n/a
140
172,40
n/a
580
Blade
71,30
n/a
n/a
148,86
n/a
n/a
xyzrgb_dragon
193,51
n/a
800
n/a
n/a
1430
Tabel 1: Hasil pengujian pembuatan struktur uniform grid dan ray tracing traversal, serta perbandingannya dengan sistem yang sejenis pada makalah [6] dan [7]
5 Kesimpulan dan Saran
Hasil pengujian yang telah dilakukan serta perbandingannya dengan sistem yang sejenis pada makalah lain dapat dilihat pada tabel 1. Pada gambar 4 merupakan salah satu gambar hasil keluaran dari sistem. Resolusi gambar hasil keluaran yang digunakan adalah 1024x1024 dan jumlah thread per block yang digunakan adalah 8x8.
Dari hasil perancangan dan pengujian sistem penggambaran tiga dimensi dengan menggunakan algoritma ray tracing pada platform CUDA, maka dapat disimpulkan beberapa hal yaitu • Pada sistem, waktu yang digunakan untuk pembuatan struktur uniform grid tergantung pada dua hal yaitu banyaknya polygon pada scene dan besarnya struktur triangle offset. • Waktu traversal pada model / scene akan lebih lama jika banyak terdapat cell pada uniform grid yang kosong (density scene kecil). • Sistem yang dirancang dan dijalankan pada GPU memerlukan waktu penggambaran yang lebih cepat daripada sistem yang sejenis yang dijalankan pada CPU. • Sekitar 80 % sampai 95 % waktu penggambaran digunakan untuk traversal dan sisanya digunakan untuk pembuatan struktur uniform grid.
4 Diskusi dan Evaluasi Data hasil pengujian pembuatan struktur uniform grid pada tabel 1 memperlihatkan bahwa seiring dengan meningkatnya jumlah polygon yang ada pada model atau scene yang akan digambar, maka waktu pembuatan struktur uniform grid yang dibutuhkan semakin meningkat pula. Tetapi hal tersebut tidak terjadi pada model sponza dengan model horse. Model horse mempunyai jumlah polygon lebih banyak daripada jumlah polygon pada model sponza tetapi waktu pembuatan struktur uniform grid lebih singkat. Fenomena tersebut terjadi karena resolusi dan besar struktur triangle offset dari horse lebih kecil daripada model sponza sehingga banyaknya data yang harus diproses menjadi lebih sedikit. Hasil pengujian ray tracing traversal yang dilakukan dan direkap dalam tabel 1 menghasilkan waktu penggambaran sangat bervariasi dan tidak hanya bergantung pada banyaknya polygon. Model yang mempunyai banyak cell kosong pada struktur uniform gridnya, seperti sponza, conference, dan fairy forest, menghasilkan waktu penggambaran yang lebih besar daripada model yang mempunyai cell kosong sedikit. Pada tabel 1 terdapat perbandingan antara sistem yang dirancang dengan sistem yang sejenis yang dipaparkan pada makalah [7, 6] pada model / scene tertentu. Dari data terlihat bahwa sistem yang dirancang mempunyai waktu penggambaran (pembuatan struktur dan traversal) yang lebih cepat dari sistem yang dipaparkan pada makalah [7] tetapi sedikit lebih lambat dari sistem yang dipaparkan pada makalah [6] karena perangkat keras yang digunakan pada pengujian lebih rendah daripada yang digunakan pada makalah [6].
Sistem penggambaran ray tracing yang dirancang pada penelitian ini masih merupakan framework dasar dan bukan merupakan solusi yang lengkap sehingga diperlukan pengembangan yang lebih lanjut pada sistem. Penulis menyarankan beberapa topik pengembangan yang dapat dilakukan, yaitu: • Penggunaan material (texture dan warna) pada model sehingga didapatkan hasil yang lebih realistik. • Penggunaan metode anti-aliasing untuk menghilangkan aliasing yang terdapat pada hasil penggambaran. • Penambahan efek refleksi dan refraksi cahaya (dengan material tertentu) agar didapatkan hasil penggambaran yang lebih realistik. • Perancangan sistem lebih lanjut untuk dinamik scene (animated scene) sehingga dapat digunakan dengan model / scene yang terdapat animasi didalamnya. 4
Hasil Penggambaran
Pustaka [1] A MANATIDES , J., AND W OO , A. A fast voxel traversal algorithm for ray tracing. In Proc. Eurographics 1987 (August 1987). [2] C HRISTEN , M. Ray tracing on gpu. Master’s thesis, University of Applied Sciences Basel, 2005. [3] F UAD , R., AND H ARIADI , M. Gpu-based parallel algorithm for construction of uniform grid structure. In National Seminar on Applied Technology, Science, and Arts 2009 (2009). [4] I VSON , P., D UARTE , L., AND C ELES , W. Gpuaccelerated uniform grid construction for ray tracing dynamic scenes. Master’s thesis, PUC-Rio, 2009. [5] J ENSEN , H. W., AND C HRISTENSEN , P. H. Highquality rendering using ray tracing and photon mapping. In Siggraph course notes (2007). [6] K ALOJANOV, J., AND S LUSALLEK , P. A parallel algorithm for construction of uniform grids. In HPG ’09: Proceedings of the Conference on High Performance Graphics 2009 (New York, NY, USA, 2009), ACM, pp. 23–28. [7] L AGAE , A., AND D UTRÉ , P. Compact, fast and robust grids for ray tracing. In SIGGRAPH ’08: ACM SIGGRAPH 2008 talks (New York, NY, USA, 2008), ACM, pp. 1–1. [8] M ÖLLER , T., AND T RUMBORE , B. Fast, minimum storage ray-triangle intersection. J. Graph. Tools 2, 1 (1997), 21–28. [9] S ATISH , N., H ARRIS , M., AND G ARLAND , M. Designing efficient sorting algorithms for manycore gpus. In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on (2009), pp. 1–10. [10] S ENGUPTA , S., H ARRIS , M., AND G ARLAND , M. Efficient parallel scan algorithms for GPUs. Tech. Rep. NVR-2008-003, NVIDIA Corporation, Dec. 2008. [11] S ENGUPTA , S., H ARRIS , M., Z HANG , Y., AND OWENS , J. D. Scan primitives for gpu computing. In GH ’07: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware (Aire-la-Ville, Switzerland, Switzerland, 2007), Eurographics Association, pp. 97–106. [12] WALD , I., I ZE , T., K ENSLER , A., K NOLL , A., AND PARKER , S. G. Ray Tracing Animated Scenes using Coherent Grid Traversal. ACM Transactions on Graphics 25, 3 (Jul 2006), 485–493. (Proceedings of ACM SIGGRAPH 2006). [13] W HITTED , T. An improved illumination model for shaded display. Commun. ACM 23, 6 (1980), 343– 349. 5
