RANCANG BANGUN RAY TRACING PIPELINE PADA PLATFORM CUDA

TESIS TE2099

RANCANG BANGUN RAY TRACING PIPELINE PADA PLATFORM CUDA REZA FUAD RACHMADI 2208 205 740

DOSEN PEMBIMBING: Prof. Dr. Ir. Mauridhi Hery P., MEng.

PROGRAM MAGISTER BIDANG KEAHLIAN JARINGAN CERDAS MULTIMEDIA JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2010

Tesis ini disusun untuk memenuhi salah satu syarat memperoleh gelar Magister Teknik (MT) di Institut Teknologi Sepuluh Nopember oleh: REZA FUAD RACHMADI NRP. 2208 205 740 Tanggal Ujian : Periode Wisuda :

23 Januari 2010 Maret 2010

Disetujui oleh :

1.

Prof. Dr. Ir. Mauridhi Hery Purnomo, M.Eng.

(Pembimbing)

NIP: 195809161986011001

2.

Mochamad Hariadi, ST., MSc., PhD.

(Penguji)

NIP: 196912091997031002

3.

Dr. I Ketut Eddy Purnama, ST., MT.

(Penguji)

NIP: 196907301995121001

4.

Ahmad Zaini, ST., MT.

(Penguji)

NIP: 197504192002121003

5.

Diah Puspito Wulandari, ST., MSc.

(Penguji)

NIP: 198012192005012001

Direktur Program Pasca Sarjana,

Prof. Dr. Ir. Suparno, MSIE NIP: 194807101976031002

[Halaman ini sengaja dikosongkan]

RANCANG BANGUN RAY TRACING PIPELINE PADA PLATFORM CUDA Nama Mahasiswa : NRP : Pembimbing : Co-Pembimbing :

Reza Fuad Rachmadi 2208205740 Prof. Dr. Ir. Mauridhi Hery Purnomo, M.Eng.

-

ABSTRAK Penggambaran dengan menggunakan algoritma ray tracing banyak digunakan untuk pembuatan film-film animasi, desain arsitektur, dan simulasi teknik. Permasalahan terbesar pada penggambaran dengan algoritma ray tracing adalah kebutuhan daya komputasi yang sangat besar sehingga membutuhkan struktur data tambahan untuk menurunkan daya komputasi yang digunakan. Salah satu struktur data yang dapat mempercepat proses penggambaran pada algoritma ray tracing adalah struktur uniform grid. Pada penelitian ini akan dilakukan perancangan sistem penggambaran dengan menggunakan algoritma ray tracing pada platform CUDA dengan menggunakan struktur uniform grid sebagai strultur pemercepat. Platform CUDA merupakan standar parallel processing pada GPU dan dapat digunakan untuk berbagai keperluan komputasi. Hasil akhir penelitian berupa sistem penggambaran dengan menggunakan algoritma ray tracing yang dapat berjalan pada GPU dan lebih cepat 2 sampai 6 kali daripada sistem yang sama yang dijalankan pada CPU. Kata Kunci: ray tracing, parallel processing, CUDA, uniform grid

i


DESIGN AND IMPLEMENTATION RAY TRACING PIPELINE ON CUDA PLATFORM Student Name NRP Supervisor Co-Supervisor

: : : :

Reza Fuad Rachmadi 2208205740 Prof. Dr. Ir. Mauridhi Hery Purnomo, M.Eng.

-

ABSTRACT Rendering an image using ray tracing algorithm had been widely used for animation movie, architecture design, and simulation. Huge computational resource becomes the biggest and most challenging problem on implementing ray tracing algorithm, so it needs additional data structure to lower the resources needed. One of the data structure that mainly used to accelerate ray tracing algorithm is uniform grid. This research will develop a rendering system using ray tracing algorithm on CUDA platform and using uniform grid as accelerating structure. CUDA is a parallel processing standart in GPU and can be use to compute anything (general purpose). The research result is a 3d rendering system using ray tracing algorithm that run on GPU and run 2 to 6 time faster than other similiar system that run on CPU. Keywords: ray tracing, parallel processing, CUDA, uniform grid

iii


KATA PENGANTAR

Segala puji kahadirat Allah SWT karena hanya dengan rahmat-NYA-lah penyusunan tesis dengan judul “Rancang Bangun Ray Tracing Pipeline Pada Platform CUDA” ini dapat berjalan dengan lancar dan tanpa halangan yang berarti. Tesis ini disusun guna memenuhi persyaratan untuk memperoleh gelar magister teknik pada bidang konsentrasi Teknologi Permainan, bidang studi Jaringan Cerdas Multimedia, jurusan Teknik Elektro, Institut Teknologi Sepuluh Nopember Surabaya. Penentuan metode dan perancangan tesis menggunakan pedoman teori dan literatur penunjang pada beberapa konferensi internasional sehingga diharapkan dapat melahirkan tesis yang baik dan dapat dipertanggungjawabkan. Penulis memahami bahwa penyusunan tesisi tidak lepas dari bantuan pihakpihak tertentu, oleh karena itu penulis mengucapkan banyak terima kasih kepada seluruh pihak yang telah membantu proses penyuisunan tesisi ini, diantara: 1. Bapak Menteri Pendidikan Indonesia dan seluruh jajaran Depdiknas yang telah memberikan kesempatan kepada penulis untuk menerima beasiswa BU (Beasiswa Unggulan) dan menempuh kuliah magister di jurusan Teknik Elektro ITS hingga lulus. 2. Orang tuaku tercinta yang telah dengan sabar membimbing dan membesarkan penulis selama ini. 3. Anggit tercinta yang telah memberikan support dan semangat kepada penulis dalam proses penyusunan tesis ini. 4. Seluruh jajaran dosen lab B-201; pak Hariadi, pak Uki, pak Akok, pak Surya, dan pak Ketut; yang telah memberikan bimbingan dan pencerahan dalam penyusunan tesis ini. 5. Seluruh warga lab Common Computing yang telah memberikan semangat kebersamaan dan banyak berdiskusi sehingga menambah pengetahuan dari berbagai disiplin ilmu. 6. Warga lab B-201 yang telah meluangkan waktunya untuk kebutuhan mahasiswa S2 gamtech. Penulis menyadari bahwa masih banyak kekurangan dalam penyusunan tesis ini. Saran dan kritik yang membangun dari para pembaca sangat penulis hargai agar dapat dilakukan perbaikan di waktu yang akan datang, Selain itu, penulis mengharapkan akan ada mahasiswa lain yang akan melanjutkan penelitian ini sehingga v

didapatkan hasil yang lebih bagus lagi. Akhir kata, semoga tesis ini dapat menambah pemahaman dan pengetahuan pembaca tentang komputer grafik, khususnya ray tracing.

Penulis

vi

PENGHARGAAN

Model bunny, happy budha, dragon, dan xyzrgb_dragon adalah milik dari stanford university (stanford 3d scanning repository). Model hand, horse, dan blade adalah milik dari georgia institute of technology (large geometric model repository). Model wooddoll dan fairy forest adalah milik dari SCI Institute (the utah 3d animation repository). Model conference adalah milik dari Anat Grynberg dan Greg Ward. Model sponza atrium adalah milik dari Marko Dabrovic.

vii


DAFTAR ISI

ABSTRAK

i

KATA PENGANTAR

v

PENGHARGAAN 1

2

vii

PENDAHULUAN

1

1.1

Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4

Batasan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.5

Relevansi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.6

Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.7

Sistematika Penulisan . . . . . . . . . . . . . . . . . . . . . . . . .

4

TEORI PENUNJANG

7

2.1

Metode Penggambaran Tiga Dimensi . . . . . . . . . . . . . . . . .

7

2.1.1

Rasterization . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.2

Physically Based Rendering Technique . . . . . . . . . . . 11

2.2

2.3

2.4

2.5

2.6

Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1

Diffuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.2

Ambient

2.2.3

Specular . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

. . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Persamaan Parametrik Ray . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1

Perpotongan Ray-AABB . . . . . . . . . . . . . . . . . . . 18

2.3.2

Perpotongan Ray-Segitiga . . . . . . . . . . . . . . . . . . 19

Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1

Jenis Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.2

Tahapan Proses Pada Ray Tracing . . . . . . . . . . . . . . 24

Struktur Uniform Grid . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5.1

Resolusi Uniform Grid . . . . . . . . . . . . . . . . . . . . 29

2.5.2

Konstruksi Uniform Grid . . . . . . . . . . . . . . . . . . . 30

2.5.3

Uniform Grid Traversal . . . . . . . . . . . . . . . . . . . 31

GPGPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ix

2.7

3

2.6.2

SIMT Programming . . . . . . . . . . . . . . . . . . . . . 32

Parallel Random Access Machine . . . . . . . . . . . . . . . . . . 34 2.7.1

Dasar Desain Algoritma Pada PRAM . . . . . . . . . . . . 35

2.7.2

Parallel Prefix Sum . . . . . . . . . . . . . . . . . . . . . . 36 41

3.1

Rancangan Struktur Data . . . . . . . . . . . . . . . . . . . . . . . 41

3.2

Konstruksi Struktur Uniform Grid . . . . . . . . . . . . . . . . . . 44

3.4

3.2.1

Inisialisasi . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.2

Overlapped Polygon . . . . . . . . . . . . . . . . . . . . . 44

3.2.3

Paralel Prefix Sum . . . . . . . . . . . . . . . . . . . . . . 45

3.2.4

Perhitungan Perpotongan Cell . . . . . . . . . . . . . . . . 45

3.2.5

Paralel Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2.6

Scanning Data . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2.7

Flowchart Konstruksi Struktur Uniform Grid . . . . . . . . 46

Ray Tracing Traversal . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.1

Inisialisasi . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.2

Perpotongan Ray-AABB Scene . . . . . . . . . . . . . . . 50

3.3.3

Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Shadow Ray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

PENGUJIAN SISTEM 4.1

4.2

4.3

5

NVIDIA CUDA . . . . . . . . . . . . . . . . . . . . . . . 31

RANCANGAN SISTEM

3.3

4

2.6.1

53

Evaluasi Kinerja Pembuatan Struktur Uniform Grid . . . . . . . . . 53 4.1.1

Spesifikasi Pengujian . . . . . . . . . . . . . . . . . . . . . 53

4.1.2

Hasil Pengujian . . . . . . . . . . . . . . . . . . . . . . . . 54

4.1.3

Diskusi dan Evaluasi . . . . . . . . . . . . . . . . . . . . . 54

Evaluasi Kinerja Ray Tracing Traversal . . . . . . . . . . . . . . . 58 4.2.1

Spesifikasi Pengujian . . . . . . . . . . . . . . . . . . . . . 58

4.2.2

Hasil Pengujian

4.2.3


. . . . . . . . . . . . . . . . . . . . . . . 58

Optimasi Sistem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.1

Hasil Pengujian . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3.2


PENUTUP

69

5.1

Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2

Pengembangan Lebih Lanjut . . . . . . . . . . . . . . . . . . . . . 69 x

DAFTAR REFERENSI

71

LAMPIRAN HASIL PENGGAMBARAN

75

xi


DAFTAR GAMBAR

2.1

Penggambaran dengan rasterization . . . . . . . . . . . . . . . . .

8

2.2

Tipe proyeksi pada rasterization 1 . . . . . . . . . . . . . . . . . .

9

2

2.3

Clipping dengan metode sutherland-hodgeman

. . . . . . . . . . 10

2.4

Klasifikasi pada konstruksi photon map [Jen96] . . . . . . . . . . . 11

2.5

Ilustrasi BRDF secara geometri3 . . . . . . . . . . . . . . . . . . . 12

2.6

Persamaan penggambaran secara goemetri sederhana 4 . . . . . . . 13

2.7

Perbandingan radiosity dengan penggambaran dengan direct illumination 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.8

Pendekatan diffuse dan specular [SKSS08] . . . . . . . . . . . . . 15

2.9

Hasil penggambaran pendekatan cahaya diffuse6 . . . . . . . . . . . 16

2.10 Penggambaran dengan cahaya diffuse dan ambient7 . . . . . . . . . 17 2.11 Penggambaran dengan cahaya diffuse, ambient, dan specular7 . . . 17 2.12 Perpotongan Ray-AABB dengan metode slabs . . . . . . . . . . . . 19 2.13 Koordinat barycentric pada segitiga . . . . . . . . . . . . . . . . . 21 2.14 Proses perhitungan perpotongan ray-segitiga secara geometri [MT97] 22 2.15 Skema ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.16 Forward ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.17 Super sampling pada backward ray tracing8 . . . . . . . . . . . . . 25 2.18 Shadow ray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.19 Refleksi dan refraksi ray . . . . . . . . . . . . . . . . . . . . . . . 28 2.20 Struktur uniform grid . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.21 Uniform grid traversal . . . . . . . . . . . . . . . . . . . . . . . . 30 2.22 Operasi floating point antara CPU dan GPU [Nvi09a] . . . . . . . . 33 2.23 Thread, block, dan grid [Nvi09a] . . . . . . . . . . . . . . . . . . . 33 2.24 Hirarki memori pada CUDA [Nvi09a] . . . . . . . . . . . . . . . . 34 2.25 Contoh aliran data pada PRAM balanced trees [CP09] . . . . . . . 37 2.26 Tahapan up-sweep pada algoritma scan [HSO07] . . . . . . . . . . 39 2.27 Tahapan down-sweep pada algoritma scan [HSO07] . . . . . . . . . 39 3.1

Flowchart sistem secara sederhana . . . . . . . . . . . . . . . . . . 42

3.2

Rancangan struktur data . . . . . . . . . . . . . . . . . . . . . . . 43

3.3

Flowchart konstruksi struktur uniform grid . . . . . . . . . . . . . 47

3.4

Gram-Schmidt Orthonormalization . . . . . . . . . . . . . . . . . . 48 xiii

3.5 3.6

Perhitungan vektor arah ray . . . . . . . . . . . . . . . . . . . . . . 49 Ray tracing dengan shadow ray9 . . . . . . . . . . . . . . . . . . . 51

4.1 4.2 4.3 4.4 4.5 4.6 4.7

Visualisasi hasil konstruksi struktur uniform grid . . . . . . . Perbandingan jumlah polygon dengan besar triangle offset . . Beberapa hasil penggambaran . . . . . . . . . . . . . . . . . Perbandingan waktu penggambaran . . . . . . . . . . . . . . Persentase waktu yang digunakan pada GPU . . . . . . . . . . Grafik penggambaran dengan thread per block yang bervariasi Model eksekusi CUDA [Nvi09a] . . . . . . . . . . . . . . . .

xiv

. . . . . . .

. . . . . . .

. . . . . . .

55 57 59 60 63 65 67

DAFTAR TABEL

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8

Hasil Pengujian Pembuatan Struktur Uniform Grid . . . . . . . Struktur Triangle Offset . . . . . . . . . . . . . . . . . . . . . . Besar data paralel yang ditangani setiap tahapan . . . . . . . . . Perbandingan waktu konstruksi dengan sistem lain . . . . . . . Hasil pengujian ray tracing traversal . . . . . . . . . . . . . . . Perbandingan besar triangle offset dengan waktu penggambaran Perbandingan dengan sistem lainnya (dalam fps) . . . . . . . . . Hasil pengujian dengan jumlah thread per block bervariasi . . .

xv

. . . . . . . .

. . . . . . . .

55 56 56 56 61 61 61 65


DAFTAR ALGORITMA

2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4

Metode Slabs [KK86] . . . . . . . . . . . . . . . . . . Algoritma ray tracing [Hav00] . . . . . . . . . . . . . Voxel traversal, diambil dari [AW87] . . . . . . . . . . Algoritma paralel sederhana untuk sum scan [SHG08] Prefix sum dengan double buffer [SHG08] . . . . . . . Up-sweep pseudocode [HSO07] . . . . . . . . . . . . Down-sweep pseudocode [HSO07] . . . . . . . . . . . Pemetaan AABB ke koordinat uniform grid . . . . . . Perhitungan perpotongan cell . . . . . . . . . . . . . . Scanning data . . . . . . . . . . . . . . . . . . . . . . Algoritma perhitungan vektor arah ray . . . . . . . . .

xvii

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

20 26 32 37 38 39 39 44 45 46 50


BAB I PENDAHULUAN

Teknik penggambaran tiga dimensi telah menjadi ilmu yang sangat populer serta banyak diteliti oleh berbagai kalangan, instansi pendidikan maupun perusahaan. Hal terebut dikarenakan penggunaan teknologi penggambaran tiga dimensi diperlukan di hampir seluruh bidang-bidang keilmuan seperti arsitektur, grafik desain, CAD, film, game, dan simulasi teknik. Rasterization dan ray tracing merupakan dua buah jenis penggambaran tiga dimensi yang banyak digunakan untuk membuat gambar tiga dimensi. Teknik rasterization digunakan untuk penggambaran tiga dimensi yang membutuhkan waktu penggambaran yang minimal atau biasa disebut dengan penggambaran secara real-time sedangkan teknik ray tracing digunakan untuk penggambaran yang membutuhkan kualitas yang sama dengan foto (foto realistik) dan banyak digunakan untuk pembuatan film tiga dimensi serta aplikasi CAD dan arsitektur.

1.1 Latar Belakang Grafik tiga dimensi adalah bidang penelitian yang akan terus berkembang seiring dengan berkembangnya perangkat keras. Para peneliti maupun praktisi industri menggunakan grafik tiga dimensi untuk menvisualisasikan data yang ada sehingga lebih mudah untuk dianalisa. Selain untuk visualisasi data, grafik tiga dimensi juga banyak digunakan untuk efek film, simulasi, dan game. Ray tracing merupakan metode penggambaran tiga dimensi yang banyak digunakan untuk menvisualisasikan suatu bentuk atau objek sehingga mende-kati kualitas foto (foto realistik). Ray tracing merupakan metode penggambaran yang mudah dipahami secara konseptual tetapi pada implementasinya terdapat kelemahan. Salah satu kelemahan pada ray tracing adalah daya komputasi yang dibutuhkan untuk perhitungan sangat besar sehingga diperlukan metode-metode tambahan untuk mempercepat proses perhitungan.

1.2 Perumusan Masalah Permasalahan utama dalam melakukan penggambaran dengan menggunakan metode ray tracing adalah daya komputasi yang dibutuhkan sehingga dibutuhkan tambahan metode tertentu untuk dapat memperkecil daya komputasi yang dibu1

tuhkan. Dilain segi, perkembangan perangkat keras komputer sangat pesat terutama pada perangkat GPU (Graphics Processing Unit). Pada tahun 2008, NVIDIA mengeluarkan standar CUDA (Compute Unified Device Architecture) yang digunakan untuk melakukan perhitungan floting-point pada perangkat GPU sehingga dapat digunakan untuk berbagai keperluan komputasi. Pada penelitian ini, permasalahan yang diangkat adalah bagaimana menurunkan daya komputasi yang dibutuhkan oleh algoritma ray tracing dan bagaimana realisasi program penggambaran dengan menggunakan algoritma ray tracing pada lingkungan proses paralel dengan standar CUDA. Penyelesain kedua permasalahan tersebut menghasilkan eksekusi algoritma ray tracing yang cepat dan dapat berjalan pada interaktif frame rate dengan shading sederhana.

1.3 Tujuan Penelitian ini bertujuan untuk merancang ray tracing pipeline pada platform NVIDIA CUDA. Ray tracing pipeline yang dihasilkan adalah framework dasar untuk penggambaran tiga dimensi sehingga diharapkan dapat digunakan untuk menghasilkan penelitian-penelitian lanjutan untuk membuat efek tambahan yang membuat hasil penggambaran menjadi sama dengan kualitas foto, dari segi pencahayaan sampai efek lensa pada kamera.

1.4 Batasan Masalah Batasan masalah atau ruang lingkup yang digunakan selama penelitian berlangsung didefinisikan sebagai berikut. 1. Penelitian ini merancang dan mengimplementasikan framework dasar untuk melakukan penggambaran tiga dimensi dengan mengunakan metode ray tracing pada platform CUDA. 2. Media komputasi yang digunakan adalah platform NVIDIA CUDA. 3. Model tiga dimensi yang digunakan masih sederhana dan tidak menggunakan material apapun. 4. Metode shading yang digunakan adalah diffuse dan ambient.

1.5 Relevansi Penelitian Relevansi penelitian adalah industri-industri yang bergerak dibidang kreatif seperti pembuatan film tiga dimensi, arsitektur, dan simulasi CAD. Penelitian ini diharapkan dapat menumbuhkan sistem penggambaran tiga dimensi versi Indonesia 2

dimana tidak kalah cepat dengan sistem penggambaran yang dimiliki oleh studiostudio terkenal seperti Pixar, Dimension, dan Lucas Arts.

1.6 Metodologi Penelitian Metodologi penelitian pada penelitian ini dapat dibagi menjadi beberapa bagian, yaitu studi literatur, pemilihan perangkat keras, implementasi sistem, pemilihan model tiga dimensi yang dipakai untuk pengujian, dan pengujian. Studi Literatur Studi literatur digunakan untuk memahami teori-teori yang digunakan dalam penelitian ini. Literatur yang digunakan banyak berupa makalah-makalah yang diterbitkan pada beberapa seminar internasional yang berhubungan dengan bidang komputer grafik maupun bidang parallel processing. Penulis mengambil 2 makalah sebagai referensi utama dari seluruh referensi yang telah didapat, yaitu makalah Lagae [LD08] dan makalah Kolojanov [KS09]. Kedua makalah tersebut melakukan penelitian yang mirip dengan penelitian ini sehingga dapat dibandingkan kinerja antara sistem yang telah dirancang dengan sistem yang dijabarkan pada makalah tersebut. Selain studi literatur tentang komputer grafik dan parallel processing, literatur terakhir yang perlu dipelajari adalah user manual dan programming guide dari standar CUDA yang diterbitkan oleh NVIDIA. Pada makalah tersebut dijelaskan secara gamblang tentang teknik-teknik pemrograman dan batasannya untuk membuat program dengan menggunakan standar CUDA. Pemilihan Perangkat Keras Pemilihan perangkat keras menjadi pertimbangan mutlak karena menyangkut performansi dari sistem. Perangkat keras yang bagus akan meningkat performa sistem sehingga didapatkan hasil pengujian yang optimal. Pertimbangan utama pemilihan perangkat keras yang digunakan adalah versi dari standar CUDA yang didukung oleh perangkat keras tersebut. Pada penelitian ini, digunakan perangkat keras GPU NVDIA GTX 260 dengan memori 896 MB. Besar memori yang terbatas menyebabkan beberapa model atau scene yang mempunyai banyak polygon tidak dapat digambar karena keterbatasan memori.

3

Implementasi Sistem Implementasi sistem dilakukan dengan menggunakan beberapa pustaka lain, yaitu CUDPP, standar C++0.x (boost library), dan pustaka AntTweakBar. CUDPP digunakan untuk melakukan pengurutan dan prefix sum secara paralel pada standar CUDA. CUDPP sendiri merupakan singkatan dari CUDA Data Parallel Primitive. Boost library pada program digunakan untuk pengolahan parameter masukan dari user. Pustaka terakhir yaitu AntTweakBar digunakan untuk interaksi antara user dengan program pada saat program berjalan. Pemilihan Model Tiga Dimensi Yang Digunakan Pemilihan model tiga dimensi yang digunakan berhubungan dengan pengujian yang dilakukan pada sistem. Model tiga dimensi yang diujikan diambil dari beberapa repositori model tiga dimensi yang terkenal, yaitu stanford 3d repository, georgia university large goemetric repository, dan utah 3d animation repository. Beberapa model lain, yaitu conference room dan sponza atrium, digunakan untuk membandingkan antara sistem yang dirancang dengan sistem yang dijabarkan pada makalah lain yang menjadi referensi utama penulis. Pengujian Pengujian pada sistem yang dirancang dilakukan pada beberapa model tiga dimensi yang telah dipilih secara selektif agar kinerja sistem dapat dibandingkan dengan sistem lain yang dijabarkan pada beberapa makalah. Pengujian dibagi menjadi tiga yaitu pengujian waktu eksekusi untuk pembuatan struktur uniform grid, pengujian waktu eksekusi untuk ray tracing traversal, dan pengujian pengaruh konfigurasi thread per block pada sistem. Dua pengujian pertama merupakan pengujian yang dilakukan tanpa melakukan perubahan pada konfigurasi eksekusi dari sistem sedangkan pengujian terakhir dilakukan dengan melakukan perubahan terhadap konfigurasi sistem serta pengaruhnya terhadap hasil penggambaran.

1.7 Sistematika Penulisan Penulisan buku tesis ini terbagi menjadi 5 bab yaitu pendahuluan, teori penunjang, perancangan sistem, pengujian sistem, serta penutup. Penjelasan singkat tentang masing-masing bab adalah sebagai berikut.

4

BAB 1 PENDAHULUAN. Pada bab 1 diuraikan permasalahan yang menjadi landasan untuk melakukan penelitian serta tujuan dan batasan dari penlitian yang dilakukan. Selain itu, dijelaskan pula metodologi penelitian yang digunakan serta sistematik penulisan laporan ini. BAB 2 TEORI PENUNJANG. Bab 2 berisi tentang teori-teori dasar yang digunakan sebagai landasan dalam melakukan penelitian seperti ray traciug, GPGPU, PRAM, dan persamaan parametrik ray. Teori tentang parametrik ray digunakan antara lain, deteksi perpotongan ray dengan AABB (Axis Align Bounding Box) dan deteksi perpotongan ray dengan segitiga. Teori tentang PRAM (Parallel Random Access Machine) merupakan teori tentang perancangan suatu algoritma paralel dengan metode-metode tertentu. BAB 3 RANCANGAN SISTEM. Pada bab ini akan dibahas perancangan dari sistem penggambaran dengan menggunakan metode ray tracing serta teori-teori tambahan yang digunakan untuk mengimplementasikannya. Rancangan sistem dibagi menjadi dua yaitu rancangan sistem untuk pembentukan struktur uniform grid dan ray tracing traversal. BAB 4 PENGUJIAN SISTEM. Pengujian sistem dilakukan untuk melihat kehandalan serta evaluasi kinerja dari sistem yang telah dirancang dan diimplementasikan. Selain itu, pada pengujian juga dibandingkan antara sistem yang dirancang dengan sistem lain yang dijabarkan pada beberapa makalah. BAB 5 PENUTUP. Bab terakhir, dirumuskan beberapa kesimpulan yang didapatkan setelah melakukan pengujian pada sistem serta penelitian lanjutan yang disarankan untuk dilakukan.

5


BAB II TEORI PENUNJANG

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 rasterization dan PBRT (Physically Based Rendering Technique). Teknik rasterization 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 [JC07] yang menggunakan metode ray tracing untuk penggambaran film “Cars”. Teknik PBRT dibagi menjadi beberapa jenis, diantaranya adalah ray tracing, radiosity, dan photon-mapping. Pada bab ini akan dijelaskan semua teori tentang penggambaran tiga dimensi, persamaan parametrik ray, ray tracing, GPGPU (General Purpose GPU), dan PRAM (Parallel Random Access Machine) yang digunakan sebagai media komputasi pada lingkungan paralel yang digunakan untuk perhitungan ray tracing.

2.1 Metode Penggambaran Tiga Dimensi Seperti yang telah disinggung pada tulisan sebelumnya, metode penggambaran tiga dimensi dibagi menjadi dua jenis yaitu rasterization dan PBRT. Implementasi metode rasterization yang terkenal adalah OpenGL, Direct3D, dan Reyes. OpenGL dan Direct3D merupakan standar yang digunakan untuk pembuatan aplikasi-aplikasi yang berjalan secara real-time, sedangkan penggambaran dengan standar Reyes banyak diimplementasikan pada program-program permodelan tiga dimensi seperti Mental Ray, Pixar Render Man, dan NVIDIA Gelato. Implementasi PBRT banyak digunakan untuk pembuatan spesial efek seperti model transparant, subscattering, dan refleksi. PBRT dibagi menjadi beberapa jenis metode, antara lain ray tracing, photon mapping, dan radiosity. 2.1.1 Rasterization Metode rasterization merupakan metode penggambaran dengan mengasumsikan suatu objek merupakan vektor grafik. Proses-proses yang terjadi pada rasterization adalah melakukan transformasi objek dalam dunia tiga dimensi, proyeksi 7

Gambar 2.1: Penggambaran dengan rasterization

objek dari koordinat tiga dimensi ke koordinat dua dimensi, clipping, dan yang terakhir adalah melakukan scan conversion untuk mengisi objek sesuai dengan hasil proyeksi dua dimensi yang telah dilakukan dan warna yang telah ditentukan. Gambar 2.1 merupakan contoh penggambaran dengan menggunakan teknik rasterization pada sebuah segitiga. Transformasi Proses transformasi terbagi menjadi beberapa bagian yaitu transformasi lokal, transformasi global, transformasi camera, dan proyeksi. Transformasi lokal merupakan transformasi yang dilakukan pada suatu objek dengan orientasi pada pusat lokal koordinat dari objek. Transformasi global merupakan transformasi yang dilakukan objek dengan orientasi pada titik pusat (0,0) dari scene. Proses transformasi objek yang dapat dilakukan adalah translasi, rotasi, dan dilatasi. Transformasi kamera merupakan transformasi yang dilakukan untuk membentuk suatu kamera virtual sehingga penglihat seperti melihat pada suatu region tertentu saja. Proyeksi merupakan transformasi spesial yang digunakan untuk memproyeksikan suatu benda dari sistem koordinat satu ke sistem koordinat yang lain. Pada metode rasterzation, proyeksi digunakan untuk melakukan proyeksi dari sistem koordinat tiga dimensi ke sistem koordinat dua dimensi. Banyak sekali teori-teori tentang proyeksi, tetapi metode proyeksi yang paling banyak digunakan adalah metode orthogonal dan perspective. Ilustrasi dari kedua tipe proyeksi tersebut dapat dilihat pada gambar 2.2. 8

Gambar 2.2: Tipe proyeksi pada rasterization 1

Clipping Setelah semua objek diproyeksikan ke dalam koordinat dua dimensi, maka ada sebagai dari objek tersebut yang berada diluar bidang lihat dari window atau area dari layar dimana setiap titik akan ditulis. Clipping merupakan proses pemotongan objek yang berada diluar bidang lihat. Metode clipping yang paling banyak digunakan adalah metode sutherland-hodgeman. Proses clipping dengan menggunakan metode sutherland-hodgeman dapat dilihat pada gambar 2.3. dari http://goanna.cs.rmit.edu.au/~gl/teaching/Interactive3D/2009/ lecture3.html 1 Diambil

9

Gambar 2.3: Clipping dengan metode sutherland-hodgeman 2

Scan Conversion Scan Conversion merupakan proses pengisian objek yang telah diproyeksikan dan telah melalui proses clipping sesuai dengan warna yang diinginkan. Permasalahan yang timbul pada proses scan conversion adalah mengetahui apakah suatu titik yang akan dituliskan mempunyai nilai kedalaman yang lebih kecil daripada titik yang telah dituliskan. Metode yang banyak digunakan untuk mengatasi permasalahan tersebut adalah menggunakan algoritma z-buffer dimana setiap titik yang ditulis dilayar akan disimpan kedalamannya pada suatu buffer yang disebut dengan z-buffer dan jika ada titik yang sama yang akan ditulis dilayar maka perlu dibandingkan kedalamannya dengan kedalaman yang telah disimpan pada z-buffer. 2 Diambil

dari http://en.wikipedia.org/wiki/Sutherland-Hodgeman

10

Gambar 2.4: Klasifikasi pada konstruksi photon map [Jen96]

2.1.2 Physically Based Rendering Technique Perbedaan mendasar antara PBRT dan rasterization adalah penurunan dan asumsi yang digunakan. Pada rasterization proses penggambaran dilakukan setelah seluruh objek dipeta dari koordinat tiga dimensi ke koordinat dua dimensi. Hal tersebut sangat berbeda dengan PBRT, dimana pada PBRT dilakukan perancangan algoritma sesuai dengan fenomena yang terjadi pada keadaan nyata. Metode-metode PBRT yang ada sekarang merupakan simulasi sederhana tentang bagaimana suatu partikel cahaya melakukan perjalanan dari sumber cahaya menuju mata penglihat. Beberapa metode PBRT yang banyak digunakan adalah ray tracing, photon mapping, dan radiosity. Ray tracing akan dibahas pada sub bab tersendiri, sedangkan photon mapping dan radiosity akan dibahas secara sederhana pada sub bab ini. Photon Mapping Photon mapping merupakan metode penggambaran PBRT yang cukup baru dan dikembangkan oleh Henrik Wann Jensen dari University of California San Diego. Photon mapping mulai diperkenal pada makalah [Jen96] pada tahun 1996. Perkembangan metode penggambaran dengan photon mapping cukup banyak dikembangkan oleh beberapa peneliti sampai sekarang seperti pada makalah-makalah [JJD08, HOJ08, HJ09]. Metode penggambaran dengan menggunkan photon mapping terbagi menjadi dua tahapan yaitu konstruksi photon map dan rendering. Tahapan konstruksi photon map dilakukan dengan menembakkan photon (paket energi) yang sangat banyak dari sumber cahaya ke dalam scene. Setiap photon ditelusuri ke dalam scene dengan menggunakan metode yang mirip dengan path 11

Gambar 2.5: Ilustrasi BRDF secara geometri3

tracing. Pada saat photon menabrak suatu permukaan objek, maka parameter photon akan disimpan pada photon map dan dilakukan algoritma russian roulette untuk memutuskan apakah photon tersebut diserap atau direfleksikan. Gambar 2.4 merupakan jenis-jenis photon yang digunakan pada photon map. Arah perjalanan photon yang baru akan dihitung dengan menggunakan persamaan BRDF (Bidirectional Reflectance Distribution Function) dari permukaan objek. BRDF adalah suatu persamaan yang merepresentasikan pemantulan cahaya pada suatu permukaan objek. Ilustrasi persamaan BRDF secara geometri dapat dilihat pada gambar 2.5. Photon mapping yang dipaparkan pada makalah [Jen96] menggunakan dua buah jenis photon map yaitu caustic photon map dan global photon map. Caustic photon map digunakan untuk menyimpan photon yang berhubungan dengan caustic dan pembuatannya dilakukan dengan memancarkan photon pada objek-objek specular serta menyimpan sebagaimana suatu photon menabrak suatu permukaan diffuse. Tahapan terakhir yang dilakukan pada metode photon mapping adalah render3 Diambil

dari http://www.vetscite.org/publish/articles/000063/print.html

12

Gambar 2.6: Persamaan penggambaran secara goemetri sederhana 4

ing. Rendering dilakukan dengan menggunakan metode ray tracing monte carlo dimana setiap radiasi cahaya pada suatu titik akan dihitung berdasarkan rata-rata dari beberapa estimasi sampling. Setiap sampling merepresentasikan sebuah ray yang ditembakkan dari mata penglihat ke titik pada bidang gambar lalu masuk ke dalam scene. Setiap titik pada bidang gambar dihitung dengan menggunakan persamaan penggambaran dan dihitung pada saat pertama kali ray menabrak suatu permukaan objek pada scene. Persamaan penggambaran yang dipaparkan pada makalah [Kaj86] dapat dilihat pada persamaan 2.1. Ls (x, ω) = Le (x, ω) +

´

fr (x, ω 0 , ω)Li (x, ω 0 )cos θi dω 0

(2.1)

Ω

Dimana Ls (x, ω) adalah radiasi cahaya yang terlihat oleh mata penglihat pada titik dimana pertama kali ray menabrak permukaan suatu objek dengan x adalah titik tempat pertama kali ray menabrak suatu permukaan objek dan ω adalah arah dari ray yang ditembakkan, Le (x, ω) adalah radiasi cahaya yang di permukaan objek, Li adalah radiasi cahaya yang datang dari arah ω 0 , fr adalah fungsi BRDF, dan Ω adalah permukaan sphere yang menjadi arah dari radiasi cahaya yang lain. Ilustrasi dari persamaan penggambaran pada suatu permukaan objek dapat dilihat pada gambar 2.6. Radiosity Radiosity merupakan algoritma penggambaran global illumination yang digunakan untuk scene yang bersifat diffuse meterial saja. DIffuse material berarti suatu 4 Diambil

dari http://en.wikipedia.org/wiki/Rendering_equation

13

Gambar 2.7: Perbandingan radiosity dengan penggambaran dengan direct illumination 5

permukaan dari suatu objek akan memantulkan energi dari partikel cahaya dan permukaan suatu objek dianggap tidak dapat meneruskan energi cahaya (objek dianggap sebagai objek transparan). Metode radiosity pertama kali dikembangkan pada tahun 1950 sebagai solusi dari permasalahan pengantaran panas pada suatu objek dan mulai dikembangkan untuk memecahkan persamaan penggambaran pada bidang komputer grafik pada tahun 1984 oleh peneliti dari Cornell University. Perbandingan antara penggambaran dengan radiosity dan penggambaran dengan direct illumination dapat dilihat pada gambar 2.7. Persamaan dasar dari radiosity diambil dari model sederhana dari transfer energi, persamaannya adalah sebagai berikut B j = ρ jH j + E j

(2.2)

dimana B j adalah total radiosity pada suatu permukaan objek, ρ j adalah tingkat pemantulan permukaan dari objek, H j adalah energi lain yang berasal dari pantulan cahaya dari permukaan-permukaan objek yang lain, dan E j adalah energi yang dipantulkan oleh permukaan objek yang sedang dihitung. H j adalah suatu persamaan yang dapat didefiniskan sebagai berikut N

H j = ∑ Bi Fi j ,

j = 1..N

(2.3)

i=1 5 Diambil

dari http://en.wikipedia.org/wiki/Radiosity_(3D_computer_graphics)

14

Gambar 2.8: Pendekatan diffuse dan specular [SKSS08]

dimana Bi adalah radiosity dari permukaan i pada suatu objek dan Fi j adalah faktor dimana energi yang meninggalkan permukaan i dapat sampai ke permukaan j yang bernilai antara 0 sampai 1. Makalah-makalah tentang radiosity cukup banyak seperti pada makalah [Kel97, GSCH93, GTGB84], Masing-masing membahas radiosity dan metode untuk mempercepat perhitungan radiosity.

2.2 Shading Shading adalah suatu metode yang dilakukan untuk penggambaran dalam hal melakukan pendekatan implementasi dari persamaan penggambaran yang telah dijelaskan sub bab sebelumnya. Pada pendekatannya, shading membagi permodelan cahaya menjadi tiga jenis yaitu diffuse, ambient, dan specular. Pada sub bab ini ketiga jenis tersebut akan dibahas secara sederhana. Gambar 2.8 merupakan pendekatan cahaya diffuse dan specular. 2.2.1 Diffuse Diffuse merupakan permodelan dari cahaya yang didasarkan pada pemantulan diffuse. Persamaan sederhana dari cahaya diffuse sesuai dengan ilustrasi pada gambar 2.8 adalah sebagai berikut di f f use = kd cos θ = kd (N · L)

(2.4)

diman kd adalah faktor diffuse yang digunakan (pada aplikasinya biasa direpresentasikan dengan warna), θ adalah sudut antara vektor normal dari permukaan objek dengan vektor yang mengarah pada sumber cahaya, N adan L adalah normal vektor 15

Gambar 2.9: Hasil penggambaran pendekatan cahaya diffuse6

dan vektor yang mengarah pada sumber cahaya. Pemodelan cahaya dengan diffuse menghasilkan sebagai dari scene akan berwarna gelap dan sebagai dari scene terlihat terang. Hal tersebut karena jika faktor sudut θ dimana ketika sudut bernilai 90 derajat maka diffuse akan menghasilkan nilai 0 atau permukaan tersebut tidak terkena cahaya sama sekali. Hasil penggambaran dari cahaya diffuse dapat dilihat pada gambar 2.9. 2.2.2 Ambient Pemodelan cahaya dengan ambient adalah diumpamakan bahwa suatu permukaan pada suatu objek akan selalu memancarkan suatu cahaya dengan intensitas tertentu. Cahaya ambient digunakan agar hasil penggambaran tidak hanya gelap dan terang tetapi ada faktor tambahan yang membuat warna dari hasil penggambaran akan menjadi lebih baik. Hasil penggambaran dengan menggunakan cahaya ambient dan diffuse dapat dilihat pada gambar 2.10.

6 Diambil

dx9B3.aspx)

dari

http://www.directxtutorial.com/Tutorial9/B-Direct3DBasics/

16

Gambar 2.10: Penggambaran dengan cahaya diffuse dan ambient7

Gambar 2.11: Penggambaran dengan cahaya diffuse, ambient, dan specular7 7 Diambil

dx9B3.aspx)

dari

http://www.directxtutorial.com/Tutorial9/B-Direct3DBasics/

17

2.2.3 Specular Specular atau bisa disebut dengan specular highlight merupakan pendekatan cahaya pada suatu permukaan yang mengkilat. Persamaan yang digunakan pada cahaya specular adalah sebagai berikut specular = ks (N · H)n

(2.5)

dimana ks adalah faktor specular yang ada pada permukaan pada suatu objek, N adalah normal vektor, n adalah faktor exponesial dari cahaya specular yang diinginkan, dan H adalah halfway vektor dari permukaan. Persamaan dari halfway vektor sendiri adalah sebagai berikut H=

V +L |V + L|

(2.6)

dimana V adalah vektor yang menuju ke mata penglihat, dan L adalah vektor yang menuju ke sumber cahaya. Hasil penggambaran dengan menggunakan ketiga pendekatan cahaya tersebut dapat dilihat pada gambar 2.11.

2.3 Persamaan Parametrik Ray Persamaan parametrik ray merupakan persamaan garis yang dinotasikan dengan titik dan arah bergeraknya titik tersebut. Persamaan parametrik ray 2.7, digunakan untuk merepresentasikan ray yang digunakan untuk melakukan perjalanan partikel cahaya pada metode penggambaran ray tracing. r(t) = o + td

(2.7)

Persamaan 2.7 dibagi menjadi dua buah vektor, vektor o adalah vektor posisi awal dari ray sedangkan vektor d adalah vektor normal arah dari perjalanan ray yang berorientasi terhadap vektor o. Variabel skalar t merupakan skala perpindahan vektor o dengan besaran unit d. Ada beberapa metode mendeteksi perpotongan yang digunakan pada penelitian ini yaitu perpotongan antara ray dengan AABB (Axis Aligned Bounding Box) dan perpotongan antara ray dengan segitiga. Kedua metode tersebut akan dijelaskan secara sederhana pada sub bab 2.3.1 dan 2.3.2. 2.3.1 Perpotongan Ray-AABB AABB (Axis Align Bounding Box) merupakan suatu jenis bangun ruang berbentuk kubus dan sejajar dengan sumbu koordinat. Perhitungan perpotongan antara ray 18

Gambar 2.12: Perpotongan Ray-AABB dengan metode slabs

dengan AABB dapat dilakukan salah satunya dengan menggunakan metode slabs. Metode slabs diperkenalkan pada makalah [KK86] dan digunakan untuk perpotongan dengan bangun bounding volume. Gambar 2.12 merupakan ilustrasi dua dimensi untuk metode slabs. Pada gambar 2.12 dilakukan perhitungan apakah ray R berpotongan dengan AABB dengan koordinat minimum (xi, yi) dan maksimum (xh, yh). Metode slabs menggunakan variabel skalar t, yang terdapat pada rumus 2.7, untuk menentukan tnear dan t f ar. Variabel tnear dan t f ar yang dihasilkan oleh metode slabs adalah perpotongan minimum (saat ray memasuki AABB) dan maksimum (saat ray keluar dari AABB). Algoritma 2.1 adalah penggunaan metode slabs untuk mencari titik perpotongan antara ray dengan AABB pada koordinat dua dimensi. Variabel xo dan yo adalah titik awal ray, sedangkan xd dan yd adalah vektor arah ternormalisasi dari ray relatif terhadap xo dan yo. Titik hasil perpotongan pada metode slabs dihasilkan pada variabel tnear dan t f ar serta dikatakan berpotongan jika tnear < t f ar dan t f ar > 0. 2.3.2 Perpotongan Ray-Segitiga Algoritma perpotongan ray dengan segitiga tidak kalah penting dibandingkan dengan algoritma perpotongan ray dengan AABB. Banyak metode yang dapat digunakan untuk mengimplementasikan algoritma perpotongan ray dengan segitiga, salah satunya dipublikasi pada makalah [MT97] oleh Moller dan Trumbore. Pada makalah tersebut, metode yang digunakan dengan menurunkan persamaan dari koordinat barycentric pada suatu segitiga. Gambar 2.13 merupakan skematik dari 19

Algoritma 2.1 Metode Slabs [KK86] tnear = -infinity; tfar = infinity; T1 = (xi - xo) / xd; T2 = (yi - yo) / yd; if T1 > T2 then swap(T1,T2); if T1 > tnear then tnear = T1; if T2 < tfar then tfar = T2; if tnear > tfar then return false; // ray miss the box if tfar < 0 then return false; // box behind the ray return true;

sistem koordinat barycentric pada sebuah segitiga. Pada bidang komputer grafik, selain untuk perhitungan perpotongan antara ray dengan segitiga, sistem koordinat barycentric juga bisa digunakan untuk texture mapping, interpolasi normal vektor, dan interpolasi warna. Suatu titik pada segitiga dapat direpresentasikan dengan menggunakan sistem koordinat barycentric yaitu dengan menggunakan persamaan sebagai berikut T (u, v) = (1 − u − v)V0 + uV1 + vV2

(2.8)

dimana (u, v) adalah koordinat barycentric, dengan syarat u ≥ 0, v ≥ 0, dan u + v ≤ 1. Untuk V0 , V1 , dan V2 adalah titik-titik koordinat katersian yang membentuk segitiga. Untuk mengetahui apakah suatu ray berpotongan dengan segitiga maka diperlukan persamaan r(t) = T (u, v) sehingga persamaan 2.8 dapat ditulis sebagai berikut o + td = (1 − u − v)V0 + uV1 + vV2

(2.9)

dengan sedikit modifikasi maka persamaan tersebut dapat juga dituliskan sebagai berikut  h

−d, V1 −V0 , V2 −V0

i

 t    u  = o −V0 v

(2.10)

Dengan mencari penyelesain sistem persamaan linier yang ada pada persamaan 2.10, barycentric koordinat (u,v) dan jarak dari pusat ray ke titik perpotongan (t) dapat ditentukan. Persamaan 2.10 dapat diselesaikan dengan menggunakan aturan Cramer sehingga didapatkan persamaan sebagai berikut 20

Gambar 2.13: Koordinat barycentric pada segitiga



   |T, E1 , E2 | t 1      u =  |−d, T, E2 |  |−d, E1 , E2 | |−d, E1 , T | v

(2.11)

dimana E1 = V1 −V0 , E2 = V2 −V0 , dan T = o −V0 . Dari aturan aljabar linier, diketahui bahwa |A, B, C| = −(A ×C) · B = −(C × B) · A sehingga persamaan diatas dapat ditulis ulang sebagai berikut

     (T × E1 ) · E2 Q · E2 t 1  1       (d × E2 ) · T  =  P·T   u = (d × E2 ) · E1 P · E1 (T × E1 ) · D Q·d v 

(2.12)

dimana P = (d × E2 ) dan Q = T × E1 . Pada implementasinya, variabel P dan Q dapat digunakan kembali dalam perhitungan untuk mempercepat proses perhitungannya. Gambar 2.14 merupakan proses perhitungan perpotongan ray dan segitiga dilihat secara geometri dengan M = [−d, V1 −V0 , V2 −V0 ].

2.4 Ray Tracing 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 perhi21

Gambar 2.14: Proses perhitungan perpotongan ray-segitiga secara geometri [MT97]

tungan dan pengertian tersebut hanya digunakan pada bidang keilmuan komputer grafik. Ray tracing diperkenalkan pada makalah [Whi80] dan masih dilakukan dengan bentuk-bentuk geometri yang sederhana seperti bidang datar dan bola. Gambar 2.15 merupakan skema dasar dari ray tracing, dimana dalam perjalanan partikel sinar dari mata penglihat ke sumber cahaya terdapat dua proses yang mensimulasikan sifat-sifat dari cahaya yaitu refraksi dan refleksi. Garis berwarna biru pada gambar 2.15 merupakan partikel sinar yang langsung menuju ke sumber cahaya sedangkan garis berwarna hijau dan biru merupakan partikel cahaya yang melalui proses refleksi dan refraksi untuk dapat mencapai sumber cahaya. Pengertian refleksi adalah pemantulan sinar oleh suatu medium tertentu sedangkan refraksi merupakan penyerapan cahaya pada medium yang berbeda. Jika suatu aplikasi penggambaran tiga dimensi yang mengunakan ray tracing telah mempunyai fungsi untuk menghitung refraksi dan refleksi maka aplikasi tersebut dikatakan telah menerapkan teknik global illumination dalam pengambarannya. Pengertian global illumination berarti perhitungan pencahayaannya tidak hanya berasal hanya dari satu titik saja tetapi merupakan campuran cahaya dari titik tersebut dengan efek cahaya yang ditimbulkan dari lingkungan di sekitarnya.

2.4.1 Jenis Ray Tracing tesSimulasi partikel cahaya pada ray tracing dapat dilakukan dengan dua cara berbeda, yaitu dengan menembakkan ray dari sumber cahaya ke dalam scene dan berakhir pada mata penglihat (seperti yang terjadi di alam) atau dengan menembakkan ray dari bidang gambar dan berakhir pada sumber cahaya. Walaupun ide dari kedua metode tersebut sama, tetapi kedua metode tersebut menghasilkan hasil 22

Gambar 2.15: Skema ray tracing

penggambaran yang berbeda, efisiensi yang berbeda, serta tingkat kesusahan implementasi yang berbeda. Forward Ray Tracing Forward ray tracing merupakan tipe ray tracing dengan metode menembakkan ray dari sumber cahaya ke dalam scene dan berakhir pada mata penglihat. Forward ray tracing mensimulasikan ray sebagai partikel cahaya seperti pada dunia nyata sehingga dibutuhkan banyak sekali ray untuk menghasilkan gambar yang baik. Gambar 2.16 merupakan ilustrasi metode forward ray tracing. Pada gambar tersebut, terlihat bahwa tidak semua ray yang ditembakkan dan ditelusuri dari sumber cahaya sampai ke mata penglihat, pada gambar ray yang sampai ke mata penglihat berwarna biru sedangkan ray yang tidak sampai ke mata penglihat berwarna merah, sehingga pada hasil penggambarannya akan menghasilkan banyak noise yang sangat mengganggu. Satu-satu penyelesaian untuk menghilangkan noise pada gambar hasil adalah dengan menembakkan ray lebih banyak lagi sampai noise tidak terlihat sehingga untuk mendapatkan hasil penggambaran yang baik dibutuhkan daya komputasi yang sangat tinggi. Kelebihan dari forward ray tracing adalah mendekati perumusan dari persamaan global illumination dengan syarat ray yang ditembakkan dari sumber cahaya ke dalam scene sangat banyak. Backward Ray Tracing Backward ray tracing menggunakan analogi yang berkebalikan dengan forward ray tracing, yaitu dengan menembakkan ray dari mata penglihat ke bidang 23

Gambar 2.16: Forward ray tracing

gambar lalu masuk ke scene dan berakhir pada sumber cahaya. Backward ray tracing menghasilkan gambar yang kurang lebih sama dengan forward ray tracing tetapi mengefisienkan ray yang ditelusuri pada scene dan mengurangi daya komputasi untuk prosesnya. Kekurangan dari metode backward ray tracing adalah adanya efek aliasing yang menghasilkan gambar yang sedikit kabur. Efek aliasing terjadi karena sampling setiap titik pada gambar hasil pada dasarnya merupakan suatu bidang besar yang terdiri dari gabungan beberapa sampling tetapi pada backward ray tracing hanya direpesentasikan oleh satu ray sehingga warna yang dihasilkan tidak sesuai dengan kondisi scene. Pada metode backward ray tracing, solusi untuk menghilangkan efek aliasing adalah dengan menggunakan metode super sampling dimana setiap titik pada gambar hasil tidak direpresentasikan sebagai satu ray tetapi sebagai 9 ray yang berjarak seragam dan hasilnya merupakan rata-rata warna yang dihasilkan oleh kesembilan ray tersebut sehingga menghasilkan perpindahan warna yang lebih halus. Gambar 2.17 merupakan ilustrasi penembakan ray pada satu titik pada gambar hasil dengan menggunakan super sampling. 2.4.2 Tahapan Proses Pada Ray Tracing Tahapan proses yang dilakukan pada ray tracing ada 5 buah yaitu persiapan scene, membangun primary ray, menembakkan ray serta melakukan deteksi perpotongan ray dengan objek yang ada di scene, membangun shadow, dan menentukan refleksi atau refraksi ray. Algoritma 2.2 merupakan algoritma dasar untuk proses ray tracing. 24

Gambar 2.17: Super sampling pada backward ray tracing8

Persiapan Scene Persiapan scene merupakan tahapan dimana program menginisialisasi semua struktur data dan memuat model atau scene ke dalam memori komputer untuk diproses lebih lanjut. Selain itu, program juga melakukan konfigurasi terhadap parameter kamera yang digunakan untuk penggambaran. Proses lain yang terjadi pada tahapan ini adalah mengorganisasi data objek atau polygon pada scene dengan struktur data tertentu seperti array dan tree. Sebagian struktur data tersebut tidak hanya menyimpan pointer ke data polygon tetapi bisa menyimpan partisi-partisi dari scene atau membuat objek-objek bayangan untuk meningkatkan efisiensi penggambaran. Struktur data yang dapat meningkatkan efisiensi penggambaran disebut dengan accelerated structure (struktur pemercepat), contoh accelerated structure adalah kd-tree, uniform grid, BVH (Bounding Volume Hierarchy) dan hybrid. Pada sub bab berikutnya akan dipaparkan salah satu accelerated structure yang digunakan dalam tesis ini yaitu uniform grid. Membangun Primary Ray Tahapan pembangunan primary ray dilakukan untuk menentukan ray-ray yang akan ditembakkan ke dalam scene dari mata penglihat untuk setiap titik pada bidang gambar. Primary ray dipengaruhi oleh beberapa faktor yaitu parameter kamera yang digunakan, resolusi bidang gambar yang digunakan, dan metode anti-aliasing yang digunakan bila menggunakan anti-aliasing dalam penggambarannya.

8 Diambil

dari http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/aliasing/

25

Algoritma 2.2 Algoritma ray tracing [Hav00] 1>> Preparing scene 2>> Generating primary ray 3>> Shooting ray to the scene >> Find the nearest intersection point in scene >> If not found fill color with background color >> Calculating the direct lighting of the intersection point >> Check if point under shadow or not >> Creating a reflection and refraction ray for next trace >> Go to step 3 and repeat the step

Menembakkan Ray Penembakan ray dilakukan untuk mencari titik perpotongan terdekat antara ray dengan objek yang ada pada scene. Metode pendeteksian apakah suatu ray berpotongan dengan suatu objek tergantung pada bentuk geometri objeknya. Sebagai contoh jika objek berupa segitiga maka dapat digunakan metode yang dipaparkan pada makalah [MT97] sedangkan jika objek berupa AABB maka dapat digunakan metode “slabs” yang dipaparkan pada makalah [KK86]. Proses penembakan ray dan pendeteksian perpotongan ray dengan objek pada scene merupakan tahapan yang paling banyak membutuhkan daya komputasi dibandingkan pada tahapantahapan yang lain, sebagai gambaran saja jika pada scene terdapat 10 ribu objek dan resolusi bidang gambar yang digunakan adalah 512 x 512 maka pendeteksian yang harus dilakukan adalah 10 ribu x 512 x 512 = 2.621.440.000 pendeteksian dengan asumsi bahwa tidak ada metode anti-aliasing dan accelerated structure yang digunakan pada sistem. Setelah mendapatkan titik perpotongan yang paling minimum dari ray dan objek yang ada pada scene, maka proses selanjutnya adalah menghitung direct lighting sesuai dengan sumber cahaya yang didefinisikan. Direct lighting merupakan gabungan dari ambient lighting, diffuse lighting, dan specular lighting. Membangun Shadow Shadow merupakan salah satu efek yang dapat diimplementasikan dengan mudah pada ray tracing. Setelah melakukan menembakkan ray dan pendeteksian perpotongan antara ray dengan objek-objek pada scene, tahapan selanjutnya yang bisa dilakukan adalah melakukan perhitungan shadow. Ada beberapa jenis shadow tergantung dari berapa sumber cahaya yang ada serta bentuk sumber cahaya yang digunakan (uniform atau non-uniform). Jika digunakan sumber cahaya berbentuk titik, hanya berjumlah satu buah, dan memancarkan cahaya secara uniform ke segala arah maka akan didapatkan efek hard shadow tetapi jika sumber cahaya lebih dari 26

Gambar 2.18: Shadow ray

satu atau bentuk dari sumber cahaya tidak berupa titik (memancarkan cahaya secara tidak uniform) maka akan terbentuk efek soft shadow. Penentuan apakah suatu titik perpotongan antara ray dengan objek yang ada pada scene berada pada daerah shadow atau tidak dengan menembakkan dan menelusuri ray tambahan yang dinamakan shadow ray ke masing-masing sumber cahaya. Jika shadow ray menambrak suatu objek pada scene maka titik perpotongan antara ray dengan objek pada scene yang telah didapatkan diawal berada pada daerah shadow tetapi jika shadow ray berhasil mencapai sumber cahaya tanpa menabrak objek lain pada scene maka titik perpotongan antara ray dengan objek pada scene yang telah didapatkan diawal tidak berada pada daerah shadow. Gambar 2.18 merupakan gambaran penembakan dan penelusuran shadow ray terhadap tiga sumber cahaya. Membangun Refleksi dan Refraksi Ray Tahapan proses yang terakhir pada ray tracing adalah membuat refleksi dan refraksi ray dan setelah itu program akan melakukan penelusuran ulang sesuai dengan refleksi dan refraksi ray yang telah dibuat. Pembangunan refleksi dan refraksi ray adalah membuat hasil penggambaran menjadi lebih realistik tetapi yang perlu diingat adalah refleksi dan refraksi maksimum yang bisa dilakukan oleh ray dari titik 27

Gambar 2.19: Refleksi dan refraksi ray

awal perpotongan antara ray dengan objek pada scene. Semakin banyak refleksi dan refraksi yang dilakukan maka hasil penggambaran akan semakin bagus tetapi akan membutuhkan daya komputasi yang lebih tinggi karena program harus melakukan penelusuran tambahan beberapa kali. Gambar 2.19 merupakan ilustrasi pembentukan refleksi dan refraksi ray dari suatu ray input yang berpotongan dengan permukaan suatu objek pada scene. Perhitungan refleksi ray adalah dengan menggunakan persamaan sebagai berikut Rf = 2N · cos(θ ) − Rin

(2.13)

dimana Rf adalah vektor arah dari refleksi ray yang dihasilkan, N adalah normal vektor pada permukaan objek, θ adalah sudut incident, dan Rin adalah inverse vektor arah pada incident ray. Untuk perhitungan refraksi ray digunakan aturan snell untuk penurunannya dan menghasilkan persamaan sebagai berikut q Rfr = η (N · Rin) − 1 − η 2 (1 − (N · Rin)) N − ηRin

(2.14)

dimana Rfr adalah vektor arah dari refraksi ray yang dihasilkan, sedangkan N dan Rin sama seperti pada persamaan untuk perhitungan refleksi ray, dan η = η1 /η2 dimana η1 adalah refraksi index pada medium pada saat ray berpotongan dengan permukaan objek sedangkan η2 adalah refraksi index pada medium yang menghasilkan refraksi ray. 28

Gambar 2.20: Struktur uniform grid

2.5 Struktur Uniform Grid 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 penggambaran adalah dengan menggunakan accelerated structure yang membagi scene menjadi kumpulan data spasial. Salah satu accelerated structure yang banyak digunakan adalah uniform grid. Gambar 2.20 merupakan gambaran struktur uniform grid yang digunakan. Uniform grid telah dikembangkan dan dipublikasikan pada makalah [Chr05, IDC09, KS09, LD08]. 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. 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.5.1 Resolusi Uniform Grid Resolusi pada struktur uniform grid menjadi faktor yang cukup krusial untuk menentukan kecepatan penggambaran. Hal tersebut dikarenakan jika struktur terlalu rapat atau terlalu renggang maka akan menghasilkan waktu penggam29

Gambar 2.21: Uniform grid traversal

baran yang lebih lama. Pada makalah [WIK+ 06] digunakan persamaan 2.15 untuk menentukan resolusi dari struktur uniform grid. r Nx = dx

3

kP Ny = dy V

r 3

kP Nz = dz V

r 3

kP V

(2.15)

Variabel Nx , Ny , dan Nz adalah resolusi uniform grid pada setiap axis. Variabel k adalah user konstanta yang bisa berubah sesuai dengan keinginan, nilai k menentukan apakah struktur uniform grid yang dihasilkan akan renggang atau rapat. Variabel P adalah jumlah polygon pada scene sedangkan variabel V adalah volume dari scene. Terakhir, variabel dx , dy , dan dz adalah diagonal dari masing-masing axis pada scene. Pada makalah [WIK+ 06], melalui beberapa percobaan maka diambil kesimpulan bahwa nilai k yang paling optimal adalah disekitar nilai 5. 2.5.2 Konstruksi Uniform Grid Setelah menentukan resolusi yang digunakan untuk pembentukan struktur uniform grid, langkah berikutnya adalah memetakan seluruh polygon yang ada pada scene untuk dimasukkan pada cell-cell yang ada pada uniform grid. Tahapan ini disebut dengan konstruksi struktur uniform grid serta menghasilkan struktur uniform grid yang pada cell-cellnya tercatat index dari polygon-polygon yang berpotongan dengan cell. Pada tahap ini digunakan metode pemetaan dari AABB sebuah polygon ke koordinat uniform grid dengan titik (0,0,0) berada di koordinat paling minimum pada AABB scene. 30

2.5.3 Uniform Grid Traversal Proses uniform grid traversal merupakan proses yang dilakukan pada saat penggambaran, yaitu melakukan perjalanan partikel cahaya (ray) dengan posisi koordinat voxel dari uniform grid. Proses traversal dilakukan dengan menggunakan metode 3D-DDA (3D Digital Differential Analyzer), yaitu suatu metode pembentukan garis pada suatu bidang koordinat. Pada makalah [AW87] diperkenal metode increment 3D-DDA, yaitu metode 3D-DDA dengan melakukan penambahan terhadap variabel tertentu untuk setiap tahapannya. Secara skematik dua dimensi, uniform grid traversal dapat digambarkan pada gambar 2.21. Algoritma traversal yang digunakan harus memproses semua cell dari uniform grid yang dilewati, dan ini sedikit berbeda dengan algoritma pembentukan garis biasa yang tidak memperhitungkan ketelitian setiap pixel yang dilewati. Algoritma 3D-DDA yang diperkenalkan oleh [AW87] bisa disebut dengan algoritma 3D-DDA dengan koneksi 6, yaitu algoritma 3D-DDA yang tidak menggunakan koordinat tengah dari cell tetapi menggunakan koordinat yang asli dari garis tersebut sehingga tidak ada cell yang terlewatkan pada saat melakukan traversal. Algoritma 2.3 merupakan psedo code dari algoritma 3D-DDA. Pada psedu code tersebut variabel X, Y, dan Z adalah koordinat cell dari uniform grid sedangkan variabel stepX, stepY, dan stepZ merupakan kenaikan setiap koordinat cell (nilai -1 atau 1 tergantung vektor arah pada ray). Variabel tMaxX, tMaxY, dan tMaxZ digunakan untuk menyimpan nilai t (nilai t digunakan sebagai media pembanding untuk memutuskan koordinat cell mana yang akan ditambah). Tiga variabel terakhir adalah tDeltaX, tDeltaY, dan tDeltaZ digunakan untuk penambahan nilai t pada masing-masing axis koordinat.

2.6 GPGPU GPGPU adalah singkatan dari general purpose GPU yaitu dimana GPU digunakan sebagai media komputasi paralel. Perkembangan GPU sangat signifikan dengan kebutuhan kualitas penggambaran grafik pada game dan desain grafik. Pada awalnya, peneliti GPGPU menggunakan GPU shader untuk melakukan perhitungan tetapi seiring dengan berkembangnya perangkat keras GPU (kartu grafik) maka muncul standar yang mengatur pemakaian GPU sebagai media komputasi paralel. 2.6.1 NVIDIA CUDA NVIDIA CUDA adalah salah satu standar komputasi paralel pada GPU. CUDA (Compute Unified Device Architecture) dikeluarkan oleh NVIDIA pada tahun 31

Algoritma 2.3 Voxel traversal, diambil dari [AW87] list= NIL; do { if(tMaxX < tMaxY) { if(tMaxX < tMaxZ) { X=X+stepX;tMaxX=tMaxX+tDeltaX; } else { Z=Z+stepZ;tMaxZ=tMaxZ+tDeltaZ; } } else { if(tMaxY < tMaxZ) { Y=Y+stepY;tMaxY=tMaxY+tDeltaY; } else { Z=Z+stepZ;tMaxZ=tMaxZ+tDeltaZ; } } list= ObjectList[X][Y][Z]; } while(list == NIL); return(list);

if(X==justOutX)return(NIL); if(Z==justOutZ)return(NIL);

if(Y==justOutY)return(NIL); if(Z == justOutZ)return(NIL);

2007 dan banyak digunakan untuk penelitian-penelitian yang membutuhkan daya komputasi yang besar. Perkembangan kartu grafik / GPU sangat pesat dan mengalahkan perkembangan yang dicapai oleh CPU. Perbandingan perkembangan daya komputasi GPU dengan CPU dapat dilihat pada gambar 2.22. Desain arsitektur perangkat keras GPU adalah multiprosessor SIMT (Single Instruction Multiple Thread) dengan menggunakan sejumlah SM (Stream Multiprocessor). Pada manul [Nvi09a, Nvi09b] dijelaskan bahwa setiap SM akan bertanggung jawab untuk mengeksekusi setiap block dari instruksi yang dijalankan. Setiap SM akan mempunyai on-chip shared memory, 32-bit register, dan instruksi unit untuk menjalankan suatu block thread. 2.6.2 SIMT Programming SIMT programming yang diperkenalkan oleh NVIDIA menggunakan beberapa istilah penting yaitu kernel, block, grid, dan thread. Kernel merupakan kode program yang akan dijalankan secara paralel pada GPU. Block, grid, dan thread adalah manajemen yang digunakan untuk mengeksekusi suatu instruksi. Thread adalah instruksi yang dikerjakan pada satu prosessor sedangkan block adalah kumpulan dari thread yang dieksekusi secara bersama-sama. Resolusi dari block bisa berupa satu dimensi atau dua dimensi. Grid adalah kumpulan dari block dan mempunyai resolusi yang bisa berupa satu dimensi maupun dua dimensi. Satu block akan dieksekusi oleh satu SM (pada standar lama 1 SM = 8 prosessor dan pada standar baru 1 SM = 16 prosessor) dan satu grid akan dieksekusi di beberapa SM secara bersama-sama 32

Gambar 2.22: Operasi floating point antara CPU dan GPU [Nvi09a]

Gambar 2.23: Thread, block, dan grid [Nvi09a]

33

Gambar 2.24: Hirarki memori pada CUDA [Nvi09a]

maupun bergantian. GPU mempunyai thread schedular yang berfungsi untuk mengatur eksekusi yang dilakukan. Istilah thread, block, dan grid dapat divisualisasi secara sederhana pada gambar 2.23. Mekanisme lain yang perlu diperhatikan adalah hirarki memori pada standar CUDA. Terdapat 3 jenis hirarki memori pada CUDA yaitu per thread local memory, per block shared memory, dan global memory. Per thread local memory adalah register yang digunakan setiap thread untuk menampung nilai sementara pada perhitungan dan scope aksesnya hanya pada satu thread. Per block shared memory digunakan untuk menampung sementara nilai yang akan diakses oleh thread lain yang berada pada satu block dan scope aksesnya adalah semua thread yang ada pada satu block. Hirarki terakhir adalah global memory yaitu memori yang berada pada GPU dan dapat diakses oleh seluruh thread yang sedang dieksekusi tanpa kecuali. Skema hirarki memori pada CUDA dapat dilihat pada gambar 2.24.

2.7 Parallel Random Access Machine PRAM (Parallel Random Access Machine) merupakan metode perancangan algoritma paralel yang digunakan untuk lingkungan multiprocessor atau multithreading. Model PRAM menfokuskan pada permasalahan pengaksesan suatu resource secara bersama-sama dengan tidak memperhatikan permasalahan sinkronisasi dan 34

komunikasi antar proses paralel. Dengan kata lain, jika tidak dapat menghasilkan algoritma paralel yang baik pada model PRAM, maka tidak akan didapatkan algoritma paralel yang baik pada dunia nyata. Pemrosesan pada model PRAM dapat menyebabkan akses data yang dilakukan secara simultan oleh beberapa prosessor pada lokasi memori yang sama. Pada model PRAM dilihat dari aturan simultan akses sesuai dengan makalah [CP09] dapat dibedakan sebagai berikut. 1. Exclusive Read Exclusive Write (EREW): Pada model PRAM ini, tidak diperbolehkan untuk menulis atau membaca pada lokasi memori yang sama atau dapat dikatakan bahwa pada model PRAM ini dua atau lebih prosessor yang berbeda tidak akan mengakses, menulis dan membaca, lokasi memori yang sama. 2. Concurrent Read Exclusive Write (CREW): Pada model PRAM ini, dua atau lebih prosessor dapat membaca dari satu lokasi memori yang sama tetapi tidak boleh menulis pada lokasi memori yang sama. 3. Exclusive Read Concurrent Write (ERCW): Pada model PRAM ini, dua atau lebih prosessor tidak boleh membaca pada lokasi memori yang sama tetapi dapat menulis pada lokasi memori yang sama. 4. Concurrent Read Concurrent Write (CRCW): Pada model PRAM ini, dua atau lebih prosessor dapat menulis dan membaca pada lokasi memori yang sama. Terdapat beberapa jenis CRCW diantaranya adalah: (a) Common CRCW: Pada model ini, dua atau lebih prosessor dapat menulis pada lokasi memori yang sama jika data yang ditulis sama. (b) Arbitary CRCW: Pada model ini, data yang dituliskan dipilih secara acak dari data yang dituliskan oleh prosessor pada lokasi memori yang sama. (c) Priority CRCW: Pada model ini, data yang dituliskan adalah data yang dituliskan oleh prosessor dengan prioritas yang paling tinggi. (d) Combining CRCW: Pada model ini, data yang akan dituliskan merupakan kombinasi perhitungan (biasanya menggunakan operator asisiatif dan mutatif, + atau max) dari seluruh data yang dituliskan prosessor pada lokasi memori yang sama. 2.7.1 Dasar Desain Algoritma Pada PRAM Perancangan suatu algoritma dengan model PRAM, biasanya menggunakan paradigma WT (Work-Time) dimana pada WT, setiap tahapan proses dari algoritma dapat mengandung jumlah instruksi yang arbitari serta dilakukan secara simultan sehingga penjadwalan algoritma pada prosessor menjadi lebih mudah. 35

Terdapat dua kompleksitas yang diukur pada WT yaitu kompleksitas dari algoritma dan kompleksitas dari setiap tahapan pada algoritma. Kompleksitas dari algoritma, dilambangkan dengan W (n), adalah total operasi yang dilakukan untuk mengeksekusi algoritma sedangkan kompleksitas setiap tahapan algoritma, dilambangkan dengan S(n), adalah total tahapan yang dilakukan untuk mengeksekusi algoritma. Jika Wi (n) adalah jumlah operasi yang dilakukan pada setiap proses paralel maka, S(n)

W (n) =

∑

Wi (n)

(2.16)

i=1

Beberapa metode perancangan algoritma pada PRAM model adalah dengan menggunakan balanced trees dan pointer jumping. Pada sub bab ini akan dijelaskan kedua teknik perancangan tersebut. Balanced Trees Istilah balanced trees yang digunakan pada PRAM hanya berupa konseptual saja dan tidak berhubungan dengan struktur data tetapi lebih kepada aliran datanya. Metode balanced trees digunakan untuk merancang work-efficient algoritma pada kasus-kasus seperti prefix sum, broadcast, dan perhitungan matrik. Gambar 2.25 merupakan salah satu contoh aliran data pada algoritma prefix sum yang bentuk aliran datanya mirip dengan balanced trees. Pointer Jumping Pointer jumping atau pointer doubling adalah metode pada PRAM yang digunakan untuk melakukan suatu proses komputasi pada struktur data linked list atau tree. Salah satu aplikasi dari pointer jumping adalah mencari jalan dari leaf terbawah ke root dari suatu struktur data tree. 2.7.2 Parallel Prefix Sum Parallel prefix sum adalah suatu algoritma paralel yang digunakan untuk menambahkan isi dari seluruh komponen array satu dimensi. Aplikasi pengembangan dari prefix sum sangatlah banyak dan merupakan metode dasar yang biasa digunakan untuk merancang algoritma paralel yang lain. Prefix sum, biasa juga disebut dengan scan, mempunyai dua jenis variasi yaitu metode inclusive scan dan metode exclusive scan. Inclusive scan merupakan prefix sum dimana setiap elemen pada index j akan ditambahkan dengan elemen pada index dibawahnya termasuk elemen pada 36

Gambar 2.25: Contoh aliran data pada PRAM balanced trees [CP09]

Algoritma 2.4 Algoritma paralel sederhana untuk sum scan [SHG08] for d := 1 to log2 n do forall k in parallel do if k ≥ 2d then x[k] = x[k − 2d−1 ] + x[k];

index j, sedangkan exclusive scan mempunyai pengertian yang sama dengan inclusive scan tetapi elemen pada index j tidak ikut ditambahkan. Persamaan 2.17 merupakan persamaan dari metode inclusive scan. [a0 , a1 , . . . , an−1 ] ⇒ [a0 , (a0 + a1 ), . . . , (a0 + a1 + . . . + an−1 )]

(2.17)

Algoritma 2.4 merupakan algoritma sederhana dan tidak work-efficient untuk melakukan prefix sum pada array x dengan jumlah elemen n dan jumlah prosessor adalah k. Algoritma tersebut menganggap bahwa jumlah prosessor sama dengan jumlah elemen yang ada pada array. Pada mesin yang mengolah data lebih banyak dari jumlah prosessor, maka akan terjadi kondisi race, yaitu kondisi dimana hasil perhitungan suatu thread ditimpa dengan hasil perhitungan thread yang lain, yang terjadi karena eksekusi paralel yang dilakukan tidak secara simultan. Untuk mengurangi jumlah prosessor yang dibutuhkan untuk melakukan perhitungan pada suatu array dengan besar n, buffer tambahan digunakan dalam algoritma. Penggunaan double buffer memang mengurangi jumlah prosessor yang dibutuhkan untuk suatu data array dengan jumlah elemen n, tetapi tidak menyelesaikan permasalahan ji37

Algoritma 2.5 Prefix sum dengan double buffer [SHG08] for d := 1 to log2 n do forall k in parallel do if k ≥ 2d then x[out][k] = x[in][k − 2d−1 ] + x[in][k] else x[out][k] = x[in][k] swap(in, out )

ka data array masukan sangat besar. Algoritma 2.5 merupakan pseudocode dari algoritma scan dengan menggunakan double buffer. Algoritma Scan Yang Work-Efficient Perancangan algoritma scan yang work-efficient diambil dari makalah [Ble90] dan dikembangkan pada makalah [HSO07]. Pada makalah tersebut digunakan balanced trees untuk melakukan penambahan setiap elemen dari array. Balanced trees yang dimaksud dari algoritma ini adalah aliran data untuk setiap proses dan bukan struktur data tree. Binary tree yang digunakan pada algoritma ini adalah binary tree dengan n leaf, mempunyai d = log2 n level, dan setiap level mempunyai 2d node. Terdapat dua tahapan dalam algoritma yang dijabarkan pada makalah [HSO07], yaitu tahapan up-sweep (tahapan ini diambil dari makalah [Ble90]) dan tahapan down-sweep. Tahapan up-sweep merupakan tahapan untuk mencari nilai penambahan dari masing-masing elemen pada array secara parsial. Tahapan up-sweep diilustrasikan pada gambar 2.26 dan implementasinya pada pseudocode 2.6. Hasil dari tahapan ini adalah jumlah masing-masing parsial data (disimpan pada akhir elemen untuk setiap parsial data) dan hasil penambahan total (disimpan pada elemen terakhir pada array) seperti yang terlihat pada gambar 2.26. Tahapan selanjutnya adalah downsweep, yaitu tahapan untuk mengisi seluruh nilai pada elemen lain yang bukan merupakan elemen terakhir dari parsial data dengan menggunakan hasil yang telah didapatkan pada tahapan sebelumnya. Ilustrasi dari tahapan down-sweep terdapat pada gambar 2.27 dan pseudocode dari tahapan tersebut dapat dilihat pada algoritma 2.7. Tahapan down-sweep merupakan tahapan traversal menurun untuk menempatkan nilai-nilai penjumlahan yang tepat untuk setiap elemen pada array.

38

Gambar 2.26: Tahapan up-sweep pada algoritma scan [HSO07]

Algoritma 2.6 Up-sweep pseudocode [HSO07] for d = 0 to log2 n − 1 do forall k = 0 to n − 1 by 2d+1 in parallel do x[k + 2d + 11] = x[k + 2d1] + x[k + 2d + 11]

Gambar 2.27: Tahapan down-sweep pada algoritma scan [HSO07]

Algoritma 2.7 Down-sweep pseudocode [HSO07] x[n − 1] = 0 for d = log2 n − 1 down to 0 do forall k = 0 to n − 1 by 2d + 1 in parallel do t = x[k + 2d − 1] x[k + 2d − 1] = x[k + 2d + 1 − 1] x[k + 2d + 1 − 1] = t + x[k + 2d + 1 − 1]

39


BAB III RANCANGAN SISTEM

Sistem penggambaran tiga dimensi yang dirancang, menggunakan metode ray tracing untuk penggambarannya dan struktur data uniform grid untuk mempercepat proses perhitungannya. Gambar 3.1 merupakan flowchart sederhana dari sistem. Ada empat tahapan yang diimplementasikan pada sistem yaitu load model atau scene, konstruksi struktur uniform grid, inisialisasi kamera, dan uniform grid traversal. Permasalahan utama pada pemrograman SIMT pada pemrograman paralel dengan menggunakan standar CUDA adalah kebutuhan memori yang harus tetap dan tidak bisa berubah pada saat kernel dieksekusi pada media. Metode umum yang digunakan untuk penggambaran dengan menggunakan ray tracing dan uniform grid sebagai accelerated structure adalah dengan menggunakan STL vektor dan linked list. Pada pemrogram SIMT pada CUDA, STL maupun linked list tidak bisa digunakan kerena memiliki memori yang tidak tetap sehingga diperlukan metode tambahan untuk mengimplementasikan sistem. Tahapan pertama dan ketiga dilakukan dengan eksekusi serial pada CPU sedangkan tahapan kedua dan keempat dilakukan dengan eksekusi paralel pada platform CUDA dan pada tahapan inilah pembahasan akan lebih mendetail pada sub bab berikutnya. Sebelum membahas permasalahan sistem, perlu dirancang suatu skema struktur data yang robust dan mudah diakses secara random dan paralel. Rancangan struktur data nantinya akan menentukan kecepatan pembentukan struktur data itu sendiri dan proses uniform grid traversal yang akan banyak mengambil informasi dari struktur data yang dibentuk.

3.1 Rancangan Struktur Data Permasalahan utama yang ada pada struktur uniform grid adalah setiap cell pada uniform grid mungkin akan memotong lebih dari satu polygon sehingga diperlukan struktur tambahan yang menghubungkan antara struktur uniform grid dengan struktur data polygon. Pada penelitian digunakan satu struktur tambahan yang dinamakan triangle offset dan digunakan untuk menghubungkan antara struktur uniform grid dengan struktur triangle data (data polygon).

41

Gambar 3.1: Flowchart sistem secara sederhana

Rancangan struktur data yang digunakan pada penelitian ini terbagi menjadi tiga bagian besar yaitu struktur uniform grid, triangle offset, dan triangle data. Masing-masing data pada struktur uniform grid terdiri dari 2 digit angka yang merupakan index awal dan index akhir dari triangle offset. Kedua, struktur triangle offset adalah struktur yang digunakan untuk mencatat polygon-polygon yang masuk pada suatu cell dan data yang disimpan pada struktur triangle offset adalah index dari triangle data. Struktur terakhir adalah triangle data yang berisi kumpulan polygonpolygon dari scene. Secara skematik, rancangan struktur data uniform grid yang digunakan terdapat pada gambar 3.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 berwarna hijau merupakan kolerasi yang terbentuk antara satu struktur dengan struktur lainnya. Rancangan struktur data tersebut mirip dengan rancangan struktur data yang digunakan pada makalah [KS09, IDC09] yang melakukan penelitian yang bertujuan sama yaitu penggambaran tiga dimensi dengan metode ray tracing dan struktur data uniform grid. 42

Gambar 3.2: Rancangan struktur data

43

Algoritma 3.1 Pemetaan AABB ke koordinat uniform grid UGCoord.x = floor(Coord.x - UGMin.x) / SizePerGrid.x UGCoord.y = floor(Coord.y - UGMin.y) / SizePerGrid.y UGCoord.z = floor(Coord.z - UGMin.z) / SizePerGrid.z

3.2 Konstruksi Struktur Uniform Grid Konstruksi struktur uniform grid merupakan proses pembuatan struktur uniform grid sesuai dengan yang telah dirancang pada sub bab 3.1. Pada tahapan ini terdapat 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 penulis, [FH09]. 3.2.1 Inisialisasi Proses inisialisasi adalah proses menentukan resolusi uniform grid yang digunakan dan memesan memori yang dibutuhkan untuk menyimpan struktur uniform grid (pada gambar 3.2 terdapat pada sebelah kiri atas). Persamaan 2.15 digunakan untuk menentukan resolusi uniform grid dengan nilai variabel k = 5. Nilai k = 5 diambil dari percobaan pada makalah [WIK+ 06] 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. 3.2.2 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 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. Pseudocode sederhana untuk melakukan pemetaan dari koordinat katersian ke koordinat uniform grid dapat dilihat pada algoritma 3.1. 44

Algoritma 3.2 Perhitungan perpotongan cell >> Find AABB Polygon >> Convert AABB Polygon to Uniform Grid Coord. >> In Uniform Grid Coord >> Loop from Min. AABB to Max. AABB >> Save Polygon Index and Cell Index

3.2.3 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 3.1 merupakan persamaan inclusive scan yang digunakan pada proses ini dengan menggunakan pustaka CUDPP (CUDA Data Parallel Processing) [SHG08, SHZO07]. [a0 , a1 , . . . , an−1 ] ⇒ [a0 , (a0 + a1 ), . . . , (a0 + a1 + . . . + an−1 )]

(3.1)

3.2.4 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. Algoritma sederhana yang digunakan pada proses ini dapat dilihat pada algoritma 3.2. Pada algortima tersebut ada 4 buah langkah. Langkah pertama adalah mencari AABB dari polygon yang sedang diproses. Berikutnya melakukan konversi dari koordinat kartesian ke koordinat uniform grid. Lakukan perulangan dari AABB minimum ke AABB maximum yang telah dikonversi ke koordinat uniform grid lalu catat index cell dan index polygon yang sedang diproses. Data index cell akan disimpan pada struktur data sementara sedangkan data index polygon akan disimpan pada struktur triangle offset pada struktur data utama. Struktur data sementara yang berisi index cell akan dihilangkan setelah semua proses konstruksi telah dilewati. 3.2.5 Paralel Sort Langkah berikutnya adalah melakukan sorting berdasarkan index cell sehingga membentuk data yang urut dari index cell terkecil ke yang terbesar. Proses pen45

Algoritma 3.3 Scanning data >> >> >> >> >> >>

IF next index cell is different then endindex = this triangle offset index ENDIF IF previous index cell is different then startindex = this triangle offset index ENDIF

gurutan dilakukan dengan menggunakan algoritma paralel radix sort yang terdapat pada makalah [SHG09], 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. 3.2.6 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. Algoritma 3.3 adalah algoritma yang digunakan untuk melakukan scanning data. Pada algoritma tersebut, 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 triangle offset sekarang merupakan index terakhir pada triangle offset dari cell. 3.2.7 Flowchart Konstruksi Struktur Uniform Grid Gambar 3.3 merupakan flowchart konstruksi struktur data uniform grid beserta data masukan dan data keluaran yang digunakan. Data masukan dan keluaran yang disertakan hanya struktur data yang telah dirancang pada sub bab sebelumnya. Triangle data akan selesai dan tidak akan diubah setelah tahapan load model sedangkan triangle offset tidak akan diubah lagi setelah proses paralel sort. Data uniform grid adalah data yang paling akhir dirubah yaitu pada proses scanning data. 46

Gambar 3.3: Flowchart konstruksi struktur uniform grid

47

Gambar 3.4: Gram-Schmidt Orthonormalization

3.3 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 [AW87] dan juga telah dipaparkan pada bab 2.5.3. 3.3.1 Inisialisasi 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. Gram-Schmidt Orthonormalization Gram-schmidt orthonormalization adalah proses pencarian tiga buah vektor arah kamera yang orthogonal (l,u,v). Tiga buah vektor arah tersebut akan digunakan untuk mencari vektor arah pada setiap titik dari gambar dengan resolusi yang diinginkan. Proses pertama yang dilakukan adalah mencari vektor l dengan menghitung normal vektor dari vektor arah lookat. Setelah itu, mencari vektor v yaitu dengan menggunakan croos product antara vektor l dengan vektor up lalu mengubah vektor hasilnya ke normal vektor. Terakhir, melakukan perhitungan vektor u yaitu dengan melakukan cross product antara vektor v dengan vektor l. 48

Gambar 3.5: Perhitungan vektor arah ray

l=

lookat − campos klookat − camposk

(3.2)

l × up kl × upk

(3.3)

v=

u = v×l

(3.4)

Perhitungan Vektor Arah Ray Vektor arah ray merupakan vektor arah yang berorientasi pada titik-titik yang ada pada gambar yang akan dihasilkan. Pada gambar 3.5 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

(3.5)

Proses selanjutnya seletah melakukan perhitungan vektor ll adalah menghitung vektor arah sesungguhnya untuk setiap titik pada gambar. Algoritma 3.4 adalah algoritma yang digunakan untuk melakukan perhitungan vektor arah untuk setiap 49

Algoritma 3.4 Algoritma perhitungan vektor arah ray l l = campos + d l − av − u ; f o r ( j = 0 ; j < VRES ; j ++) { f o r ( i = 0 ; i < HRES ; i ++) { p = l l + 2 av ( d o u b l e ) i / HRES + 2u ( d o u b l e ) j / VRES ; v e k t o r _ a r a h = p − campos ; . . . } }

titik pada gambar dan persamaan 3.6 digunakan untuk perhitungan vektor arah untuk setiap titik pada gambar. x y p = ll + 2av + 2u resx resy

(3.6)

3.3.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 yang telah dijelaskan pada bab 2.3.1. Hasil keluaran dari proses ini adalah koordinat dalam sistem koordinat uniform grid yang pertama kali berpotongan dengan ray. 3.3.3 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 [AW87] dan telah dijelaskan pada bab 2.5.3. 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 [MT97] dan dijelaskan pada bab 2.3.2. 50

Gambar 3.6: Ray tracing dengan shadow ray1

3.4 Shadow Ray Shadow ray adalah perjalanan ray dari tempat pertama ray tersebut berpotongan dengan suatu polygon ke pusat sumber cahaya dan menentukan apakah cahaya dari sumber cahaya ke titik tersebut terhalang oleh polygon lain atau tidak. Prosesproses yang terjadi pada perhitungan shadow ray sama dengan perhitungan ray tracing traversal, hanya saja pusat ray dan arahnya sudah jelas yaitu titik perpotongan ray dengan segitiga yang mempunyai vektor arah menuju pusat sumber cahaya. Keluaran yang dihasilkan dari proses ini adalah titik terlahang oleh polygon lain (true) atau titik tidak terlahang oleh polygon lain (false). Gambar 3.6 merupakan skema ray tracing dengan menggunakan shadow ray. Pada sistem, shadow ray yang diimplementasikan masih menggunakan metode hard shadow dimana diasumsikan pusat sumber cahaya berupa sebuah bola dan memancarkan cahaya secara uniform. Metode lain yang dapat dikembangkan adalah metode soft shadow yaitu dimana bentuk dari sumber cahaya dapat berupa persegi dan tabung sehingga cahaya yang dipancarkan tidak uniform dan menimbulkan efek shadow yang tidak fokus (blur). Ray tracing dengan menggunakan shadow ray menimbulkan penambahan daya komputasi sekitar 1.5 sampai 2 kali lebih besar. Hal tersebut karena perhitunngan tambahan yang dilakukan pada shadow ray yang kurang lebih sama dengan daya komputasi yang digunakan untuk ray tracing traversal sehingga akan menurunkan performa sistem tetapi menghasilkan gambar dengan kualitas yang lebih bagus. 1 Diambil

dari http://www.codinghorror.com/blog/archives/001073.html

51


BAB IV PENGUJIAN SISTEM

Pengujian pada sistem dilakukan untuk mengukur kinerja sistem yang telah dirancang dan diimplementasikan. Pada penelitian ini, sistem akan diuji coba dengan dua kategori pengujian yaitu evaluasi kinerja pembuatan struktur uniform grid dan evaluasi kinerja ray tracing traversal. Evaluasi kinerja pembuatan struktur uniform grid dilakukan untuk mengetahui kinerja sistem terhadap pembuatan struktur uniform grid yang merupakan tahapan awal pada algoritma ray tracing. Pengujian berikutnya adalah evaluasi kinerja ray tracing traversal yang digunakan untuk mengetahui kinerja sistem pada penggambaran pada model yang static. Pada bab 4.3 dibahas mengenai optimasi sistem yang dapat dilakukan serta efek yang ditimbulkan. Spesifikasi sistem adalah spesifikasi perangkat keras dan perangkat lunak yang dibutuhkan untuk menjalankan sistem. Spesifikasi perangkat keras dan perangkat lunak minimum yang dibutuhkan untuk dapat menjalankan sistem dengan baik adalah komputer dengan kartu grafik yang mendukung standar NVIDIA CUDA (GeForce seri 8 atau lebih baru) dan sistem operasi Linux dengan driver dan pustaka CUDA.

4.1 Evaluasi Kinerja Pembuatan Struktur Uniform Grid Evalusi kinerja pembuatan struktur uniform grid dilakukan dengan menggunakan beberapa model yang banyak digunakan pada penelitian-penelitian yang sejenis seperti model-model pada repositori stanford, model conference room, fairy forest dan sponza atrium. Kinerja yang diperhatikan dalam evaluasi ini adalah waktu pembuatan/konstruksi struktur uniform grid dan memori GPU yang digunakan untuk struktur uniform grid. 4.1.1 Spesifikasi Pengujian Pada pengujian dan evaluasi kinerja pembuatan struktur uniform grid yang akan dilakukan, digunakan spesifikasi perangkat keras dan perangkat lunak dengan rincian sebagai berikut • Kartu grafik NVIDIA GeForce GTX 260 896 MB DDR3 • Sistem operasi Linux Debian squeeze

53

• NVIDIA CUDA Toolkit 2.3 dan NVIDIA CUDA SDK 2.3

Data yang diambil dalam pengujian ini adalah waktu pembuatan atau konstruksi struktur uniform grid (tidak termasuk pengiriman data ke memori GPU) dan memori GPU yang dibutuhkan untuk menyimpan seluruh struktur scene dan struktur uniform grid. Waktu pembuatan atau konstruksi struktur uniform grid merupakan indikasi awal apakah suatu sistem mempunyai algoritma paralel yang bagus atau tidak. Indikasi ini akan dipertanyakan kembali pada saat pengujian ray tracing traversal karena struktur data uniform grid yang dibangun akan mempengaruhi kinerja dari ray tracing traversal. 4.1.2 Hasil Pengujian Gambar 4.1 merupakan visualisasi dari struktur uniform grid model sedangkan tabel data hasil pengujian untuk pembuatan struktur uniform grid dapat dilihat pada tabel 4.1 dan 4.2. Pengambilan waktu konstruksi yang dibutuhkan dilakukan setelah semua data scene (polygon-polygon) selesai di muat ke dalam memori GPU. Data hasil pengujian pada tabel 4.1 memuat informasi tentang waktu pembentukan struktur uniform grid dan kebutuhan total memori GPU untuk struktur uniform grid dan polygon-polygon pada scene. Tabel 4.2 memuat informasi tentang besar struktur triangle offset yang digunakan pada masing-masing model. 4.1.3 Diskusi dan Evaluasi Data hasil pengujian pada tabel 4.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 sekitar dua puluh ribu 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. Data paralel yang harus diproses untuk setiap tahapan dapat dilihat pada tabel 4.3. Dari kedua hal tersebut maka dapat disimpulkan bahwa pada sistem yang dirancang waktu pembuatan struktur uniform grid dipengaruhi oleh jumlah polygon dan besar struktur triangle offset. Struktur triangle offset digunakan untuk mengatasi permasalahan overlapped polygon yang terjadi pada cell pada struktur uniform grid.

54

(a) Model bunny

(b) Model sponza atrium

(c) happy budha Gambar 4.1: Visualisasi hasil konstruksi struktur uniform grid

Tabel 4.1: Hasil Pengujian Pembuatan Struktur Uniform Grid

Model / Scene

Polygon

Resolusi Grid

Wood Doll Bunny Sponza Horse Fairy Forest Conference Hand Dragon Happy Budha Blade xyzrgb_dragon

6018 69451 76148 96966 174117 282755 654666 871414 1087716 1765388 7219045

20x48x34 77x77x60 122x55x58 50x109x91 151x39x151 211x51x134 239x168x82 240x170x108 131x319x131 189x320x147 461x256x307

55

Waktu Konstruksi (ms) 2,45 6,14 10,80 6,81 18,77 24,42 24,26 34,82 44,08 71,30 193,51

Kebutuhan Memori (MB) 0,41 6 7,6 8,2 13,22 18,73 53,2 72,62 90,92 148,94 571,33

Tabel 4.2: Struktur Triangle Offset

Model / Scene

Polygon

Resolusi Grid


6018 69451 76148 96966 174117 282755 654666 871414 1087716 1765388 7219045


Besar Struktur Triangle Offset 24436 239955 517016 273430 1164048 1176884 1467798 2379395 3094383 5372964 12335855

Tabel 4.3: Besar data paralel yang ditangani setiap tahapan

Tahapan Inisialisai Overlapped Polygon Paralel Prefix Sum Perhitungan Perpotongan Cell Paralel Sorting Scanning Data

Jumlah data paralel yang ditangani Serial Code Jumlah Polygon Jumlah Polygon Jumlah Polygon Besar Triangle Offset Besar Triangle Offset

Tabel 4.4: Perbandingan waktu konstruksi dengan sistem lain

Model / Scene Bunny Sponza Conference Fairy Forest Dragon Happy Budha

Sistem yang dirancang 6,14 ms 10,80 ms 24,42 ms 18,77 ms 34,82 ms 44,08 ms

Sistem pada makalah [KS09] n/a 13 ms 27 ms 24 ms n/a n/a

56

Sistem pada makalah [LD08] 10 ms n/a 120 ms n/a 110 ms 140 ms

Gambar 4.2: Perbandingan jumlah polygon dengan besar triangle offset

Fenomena lain yang muncul adalah perbandingan jumlah polygon dengan besar struktur triangle offset. Pada gambar 4.2 dapat dilihat bahwa pada model-model yang digunakan perbandingan sangatlah kecil (sekitar 0.1-0.5) yang artinya semakin kecil perbandingan maka semakin banyak polygon yang overlapped dan semakin besar struktur triangle offset yang harus digunakan. Hal yang sangat mempengaruhi adalah besar resolusi dari uniform grid yang digunakan. Pada makalah [KS09] menjabarkan bahwa resolusi yang paling optimal adalah resolusi yang mendekati bentuk bujur sangkar dan pada makalah tersebut digunakan metode heuristik untuk menentukan resolusi uniform grid yang digunakan. Sistem menggunakan pendekatan yang dijabarkan pada makalah [Ize09] yang menggunakan volume scene, banyaknya polygon, diagonal scene, dan user konstanta. Pendekatan tersebut cukup efisien tetapi bukan pendekatan yang paling baik karena tidak memasukkan unsur besar AABB pada masing-masing polygon sehingga jika terdapat perbedaan besar polygon yang sangat tinggi, struktur menjadi tidak efisien. Tabel 4.4 merupakan perbandingan antara sistem yang dirancang dengan sistem yang dijabarkan pada makalah [KS09] dan sistem yang dijabarkan pada makalah [LD08]. Pada makalah [KS09] digunakan pendekatan yang kurang lebih sama hanya saja pada penentuan resolusi grid-nya digunakan metode heuristik sehingga sangat mendapatkan resolusi grid yang berbeda untuk setiap model. Makalah [LD08] menggunakan struktur hashed grid serta menggunakan CPU sebagai daya komputasinya. Hasil pada tabel 4.4 memperlihatkan bahwa terjadi peningkatan 57

performa untuk pembuatan struktur uniform grid antara CPU sebagai daya komputasinya dengan GPU sebagai daya komputasinya. Peningkatan performa memang terlihat tidak terlalu tinggi (sekitar 2 sampai 3 kali lebih cepat) dibandingkan dengan perbedaan daya komputasi antara CPU dan GPU. Hal tersebut dikarenakan metode ray tracing tidak terlalu cocok diparalelkan pada arsitektur SIMD (Single Instruction Multiple Data) / SIMT (Single Instruction Multiple Thread), dan jika CPU mempunyai jumlah prosessor yang sama maka dapat dipastikan performa pada CPU akan jauh lebih bagus karena mempunyai arsitektur MIMD (Multiple Instruction Multiple Data). Sedangkan perbandingan antara sistem yang dirancang dengan sistem yang kurang lebih sama yang dipaparkan pada makalah [KS09], didapatkan peningkatan yang tidak terlalu signifikan karena kedua sistem tersebut menggunakan analogi dan algoritma pembentukan struktur uniform grid yang kurang lebih sama serta kedua sistem tersebut sama-sama berjalan pada GPU dengan menggunakan standar CUDA.

4.2 Evaluasi Kinerja Ray Tracing Traversal Evaluasi kinerja ray tracing traversal dilakukan untuk mengetahui performansi dari sistem ketika melakukan penggambaran. Pengambilan data dilakukan dengan dua jenis fitur yaitu sistem dengan tidak menggunakan fitur shadow dan sistem yang menggunakan shadow. Model atau scene dan paramter kamera yang digunakan sama seperti pada evaluasi kinerja pembuatan struktur uniform grid. 4.2.1 Spesifikasi Pengujian Spesifikasi pengujian sama dengan pengujian pada pembuatan struktur uniform grid tetapi pada pengujian ray tracing traversal dilakukan pengambilan data sebanyak dua kali yaitu sistem yang tidak menggunakan shadow untuk penggambarannya dan sistem yang menggunakan shadow untuk penggambarannya. Metode shadow yang digunakan adalah hard shadow dimana tidak ada istilah penumbra dan umbra yang biasa digunakan pada teknik shadow dengan sumber cahaya yang pancarannya tidak berbentuk bulat. Pengujian dilakukan dengan resolusi gambar sebesar 1024x1024 dan parameter kamera yang diatur sedemikian rupa sehingga model akan tampak pada gambar. 4.2.2 Hasil Pengujian Data hasil pengujian untuk evaluasi kinerja ray tracing traversal pada dilihat pada tabel 4.5, 4.6, dan 4.7. Beberapa hasil penggambaran dengan atau tanpa efek 58

(a) conference tanpa shadow

(b) conference dengan shadow

(c) sponza tanpa shadow

(d) sponza dengan shadow

Gambar 4.3: Beberapa hasil penggambaran

59

Gambar 4.4: Perbandingan waktu penggambaran

shadow dapat dilihat pada gambar 4.3. Tabel 4.5 merekam waktu yang digunakan untuk penggambaran suatu model dengan efek shadow dan tanpa efek shadow. Tabel 4.6 merupakan perbandingan antara resolusi grid, besar struktur triangle offset dan waktu penggambaran sedangkan tabel terakhir yaitu tabel 4.7 merupakan perbandingan antara sistem yang dirancang dengan sistem pada makalah [KS09] dan sistem yang dirancang pada makalah [LD08]. Seluruh hasil penggambaran pada masing-masing model dapat dilihat pada lampiran. 4.2.3 Diskusi dan Evaluasi Dari hasil pengujian yang dilakukan dan direkap dalam tabel 4.5 menghasilkan waktu penggambaran sangat bervariasi dan tidak hanya bergantung pada banyaknya polygon. Sebagai contoh perbandingan waktu penggambaran antara model conference dengan model blade dimana jumlah polygon dan besar struktur triangle offset pada model blade jauh lebih besar daripada model conference tetapi waktu penggambarannya jauh lebih kecil. Analisa awal bahwa pada model blade cell kosong pada struktur uniform gridnya lebih sedikit daripada pada model conference sehingga proses traversal yang dilakukan pada model blade jauh lebih sedikit daripada pada model conference. Hal tersebut juga terjadi pada model-model dengan ruang kosong yang besar sepeti sponza dan fairy forest. Pada tabel 4.5 terdapat dua data yaitu waktu penggambaran tanpa efek shadow dengan waktu penggambaran dengan efek shadow. Dari kedua data tersebut, dapat divisualisasikan peningkatan waktu penggambaran antara penggambaran tanpa 60

Tabel 4.5: Hasil pengujian ray tracing traversal

Model / Scene Wood Doll Bunny Sponza Horse Fairy Forest Conference Hand Dragon Happy Budha Blade xyzrgb_dragon

Waktu Penggambaran (tanpa shadow) 34,25 ms 61.39 ms 179,84 ms 82,49 ms 499,61 ms 339,91 ms 99,14 ms 133,54 ms 172,40 ms 148,86 ms -

Waktu Penggambaran (dengan shadow) 92,72 ms 209,91 ms 604,91 ms 393,70 ms 1925,18 ms 1645,68 ms 611,34 ms 518,90 ms 861,05 ms 1194,40 ms -

Tabel 4.6: Perbandingan besar triangle offset dengan waktu penggambaran

Model / Scene

Resolusi Grid



Besar Struktur Triangle Offset 24436 239955 517016 273430 1164048 1176884 1467798 2379395 3094383 5372964 12335855

Waktu Penggambaran (tanpa shadow) 34,25 ms 61.39 ms 179,84 ms 82,49 ms 499,61 ms 339,91 ms 99,14 ms 133,54 ms 172,40 ms 148,86 ms -

Tabel 4.7: Perbandingan dengan sistem lainnya (dalam fps)

Model / Scene Bunny Sponza Conference Fairy Forest Dragon Happy Budha

Sistem yang dirancang 16,3 5,56 2,9 2 7,49 5,8

Sistem pada makalah [KS09] n/a n/a 7,7 3,5 n/a n/a

61

Sistem pada makalah [LD08] 1,47 0,54 0.44 n/a 1,25 1,72

shadow dengan pengambaran dengan shadow yaitu pada gambar 4.4. Dari gambar tersebut terlihat peningkatan waktu penggambaran yang beragam antara 4 sampai 10 kali lebih lama daripada tanpa shadow. Hasil lain dari pengujian yang dilakukan adalah gagalnya penggambaran pada model xyzrgb_dragon. Hal tersebut dikarenakan waktu penggambaran yang terlalu lama sehingga mengakibatkan kesalahan time out pada GPU. Hal ini tidak terjadi pada proses pembuatan struktur uniform grid karena waktu pembuatannya masih dibawah 5 detik sehingga tidak terjadi kesalahan time out. Solusi dari masalah ini adalah menggunakan penggambaran progresif sehingga kernel pada GPU tidak dieksekusi terlalu lama. Pada tabel 4.7 terdapat perbandingan antara sistem yang dirancang dengan beberapa sistem yang telah dipaparkan pada makalah [KS09, LD08]. Pada makalah [KS09] digunakan spesifikasi perangkat keras yang lebih bagus (GeForce GTX 280) dan menghasilkan waktu penggambaran yang lebih cepat daripada sistem yang dirancang, sedangkan pada makalah [LD08] digunakan spesifikasi perangkat keras dua prosessor quad-core Intel Xeon 3 GHz dan memori 16 GB dan menghasilkan waktu penggambaran yang lebih lambat daripada sistem yang dirancang. Pada gambar 4.5 merupakan persentase waktu yang digunakan oleh program pada GPU. Gambar 4.5a merupakan persentase waktu eksekusi program pada GPU untuk tahapan pembuatan struktur uniform grid. Pada gambar tersebut terlihat bahwa waktu eksekusi terlama adalah melakukan sorting terhadap struktur triangle offset yaitu sekitar 40% sampai 60% dari total waktu tergantung besar dari struktur triangle offset yang digunakan. Perbandingan antara waktu pembuatan struktur uniform grid dengan ray tracing traversal dapat dilihat pada gambar 4.5b. Dari grafik tersebut terlihat bahwa 80% sampai 95% waktu digunakan untuk melakukan ray tracing traversal dan pada makalah [Hav00] dijelaskan bahwa struktur uniform grid akan melakukan pembuatan struktur dengan cepat tetapi lambat pada saat traversal sedangkan struktur kd-tree, struktur seperti BSP (Binary Space Partitioning) tetapi dengan aturan-aturan tertentu, akan melakukan pembuatan struktur yang lama tetapi cepat dalam melakukan traversal.

4.3 Optimasi Sistem Optimasi sistem dilakukan untuk mempercepat proses-proses yang terjadi pada sistem. Pada grafik yang ditampilkan pada gambar 4.5b, didapatkan bahwa waktu yang digunakan untuk traversal jauh lebih besar daripada waktu yang digunakan untuk proses pembuatan struktur uniform grid sehingga diperlukan sedikit optimisi 62

(a) konstruksi

(b) traversal dan konstruksi Gambar 4.5: Persentase waktu yang digunakan pada GPU

63

agar sistem dapat berjalan secara optimal. Proses optimasi dilakukan dengan percobaan dengan jumlah thread per block dan block per grid yang berbeda-beda. Pada pengujian yang dilakukan pada bab 4.2 digunakan jumlah thread per block sebesar 8 x 8 dan block per grid sama dengan resolusi dibagi dengan jumlah thread per block. Pada bab ini akan dilakukan pengujian dengan jumlah thread per block bervariasi mulai dari 4 x 4 sampai dengan 256 x 256 (maksimum jumlah thread per block) dengan kenaikan 1 untuk setiap pengujian. Model atau scene yang diujikan adalah scene dengan jumlah cell kosong cukup besar yaitu sponza, conference, dan fairy forest. Model fairy forest merupakan model dengan jenis “the teapot in the stadium problem” yaitu dimana terdapat model yang detail dengan volume yang kecil di tengah-tengah model yang tidak terlalu detail dengan volume yang besar. Problem tersebut merupakan problem klasik yang ada pada ray tracing dengan menggunakan struktur uniform grid. 4.3.1 Hasil Pengujian Proses pengujian dilakukan dua tahap yaitu pengujian dengan tidak menggunakan shadow ray dan pengujian dengan menggunakan shadow ray. Pengujian dengan tidak menggunakan shadow ray berjalan baik sampai dengan jumlah thread per block sebesar 16x16 sedangkan jika jumlah thread per block dinaikkan lagi maka sistem akan menghasilkan gambar yang tidak semestinya. Pada pengujian dengan menggunakan shadow ray berjalan baik sampai dengan jumlah thread per block sebesar 13x13 dan jika jumlah thread per block dinaikkan maka sistem akan menghasilkan gambar yang tidak semestinya. Data hasil pengujian dapat dilihat pada tabel 4.8 dan dalam bentuk grafik pada gambar 4.6. 4.3.2 Diskusi dan Evaluasi Dari data hasil percobaan sistem dengan menggunakan jumlah thread per block yang berbeda, didapatkan kesimpulan awal bahwa semakin banyak jumlah thread per block maka waktu penggambaran cenderung menurun. Sesuai dengan tabel 4.8, pada model sponza waktu penggambaran tanpa shadow paling cepat ketika jumlah thread sebesar 11 x 11. Pada model conference waktu penggambaran tanpa shadow paling cepat ketika jumlah thread per block sebesar 16 x 16 sedangkan pada model fairy forest waktu penggambaran paling cepat ketika jumlah thread per block sebesar 15 x 15. Berbeda dengan penggambaran tanpa shadow, pada penggambaran dengan menggunakan shadow semua model menghasilkan waktu penggambaran paling cepat ketika jumlah thread per block sebesar 13 x 13. Pada dua pengujian 64

Gambar 4.6: Grafik penggambaran dengan thread per block yang bervariasi

Tabel 4.8: Hasil pengujian dengan jumlah thread per block bervariasi

Thread Per Block 4x4 5x5 6x6 7x7 8x8 9x9 10 x 10 11 x 11 12 x 12 13 x 13 14 x 14 15 x 15 16 x 16

Tanpa Shadow (ms) Fairy Sponza Conference Forest

Dengan Shadow (ms) Fairy Sponza Conference Forest

312,77

714,41

861,59

1458,39

3371,9

3172,84

233,87

553,67

738,1

1152,82

2819,15

2759,05

173,3

635,78

966,55

523,73

740.98

2425,25 1892.55

2457,33

146,86

444,89 374,37

131,63

339,66

498,74

631.17

1657.57

1766.25

159,27

372,75

488,14

814.51

1939.63

1790.79

145,96

337,94

444,19

730.62

1756.62

1692.03

117,03

292,88

407,49

657.68

1597.7

1589.71

179,43

372,25

434,89

604.62

1423.13

1555.7

165,15

341,38

382,44

552.12

1310.83

1315.61

147,93

316,46

388,79

n/a

n/a

n/a

135,43

297,7

351,04

n/a

n/a

n/a

128,2

278,55

387,86

n/a

n/a

n/a

65

1966.98

yang dilakukan, terdapat kegagalan pada sistem. Kegagalan pertama terjadi pada penggambaran tanpa shadow pada saat jumlah thread per block lebih dari 16 x 16 sedangkan kegagalan kedua terjadi pada penggambaran dengan shadow pada saat jumlah thread per block lebih dari 13 x 13. Kegagalan terjadi bukan karena kegagalan eksekusi, eksekusi berhasil dilakukan tanpa error tetapi menghasilkan gambar yang tidak sesuai (gambar tidak merepresentasikan model). Penjelasan yang mungkin adalah instruksi yang terlalu banyak dimasukkan pada SM, karena eksekusi menggunakan on-chip thread schedular yang terdapat pada perangkat keras CUDA, sehingga menghasilkan suatu kesalahan tertentu yang mengakibatkan proses eksekusi paralel terhenti tanpa menghasilkan pesan kesalahan. Waktu penggambaran yang dihasilkan dipengaruhi oleh beberapa hal, yaitu banyaknya ray yang berpotongan dengan AABB dari scene, banyaknya cell yang dikunjungi oleh ray pada saat traversal, banyaknya polygon yang tergabung dalam cell-cell yang dikunjungi oleh ray, dan jumlah thread per block yang digunakan. Untuk parameter selain jumlah thread per block, semakin banyak maka akan semakin lama waktu penggambaran yang dibutuhkan sedangkan pada parameter jumlah thread per block yang mempengaruhi adalah banyaknya prosessor yang idle (tidak bekerja) pada saat eksekusi paralel dilakukan. Eksekusi paralel yang dilakukan pada standar CUDA secara skematik dapat dilihat pada gambar 4.7. Pada gambar tersebut terlihat bahwa eksekusi dilakukan per block untuk setiap SM, dimana masing-masing SM pada perangkat keras yang digunakan pada pengujian mempunyai 8 prosessor. Jika pada saat eksekusi menggunakan konfigurasi jumlah thread per block lebih kecil dari 8 x 8 maka tidak semua prosessor pada SM akan bekerja (idle) karena jumlah thread lebih kecil daripada jumlah prosessor, jika pada saat eksekusi menggunakan konfigurasi jumlah thread per block 8 x 8 maka prosessor akan bekerja semua tetapi jika salah satu prosessor sudah selesai melakukan eksekusi dan prosessor yang lain masih melakukan eksekusi maka prosessor yang sudah selesai melakukan eksekusi akan menunggu sampai eksekusi pada prosessor yang lain dalam satu block selesai. Kemungkinan konfigurasi yang terakhir adalah dengan jumlah thread per block lebih besar dari 8 x 8, pada konfigurasi ini prosessor pada SM akan secara bergantian melakukan eksekusi pada setiap thread dengan bantuan sebuah chip thread schedular sehingga prosessor yang idle menjadi berkurang tetapi pada konfigurasi thread per block di atas 8 x 8 tidak terjadi penurunan waktu yang signifikan bahkan ada beberapa konfigurasi yang lebih jelek hasilnya daripada konfigurasi sebelumnya. Hal tersebut dikarenakan perbedaan banyaknya prosessor yang idle pada saat eksekusi dan banyaknya prosessor yang idle disebabkan metode yang digunakan banyak meng66

Gambar 4.7: Model eksekusi CUDA [Nvi09a]

gunakan percabangan pada pemrogramannya. Penyelesaian sederhana untuk masalah idle prosessor adalah menggunakan metode penggambaran progresif sehingga setiap tahap dapat ditentukan secara pasti daya komputasi yang dibutuhkan dan dapat menurunkan banyak prosessor yang idle pada saat eksekusi paralel dilakukan. Tahapan yang dimaksud adalah tahapan proses saat ray tracing traversal yaitu pembuatan primary ray, deteksi perpotongan ray dengan AABB dari scene, uniform grid traversal, dan shading. Pada tahapan proses deteksi perpotongan ray dengan AABB dari scene ada kemungkinan ray yang tidak berpotongan sehingga tidak diperlukan proses selanjuutnya, begitupula pada tahapan uniform grid traversal dimana ada kemungkinan ray tidak berpotongan dengan polygon pada scene sehingga tahapan proses shading tidak perlu dilakukan.

67


BAB V PENUTUP

5.1 Kesimpulan 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). • Dari data yang direkap pada tabel 4.7 maka sistem yang dirancang dan di-

jalankan pada GPU, lebih cepat 2 sampai 6 kali daripada sistem yang kurang lebih sama dan dijalankan pada CPU. • Dari grafik pada gambar 4.5, sekitar 80 % sampai 95 % waktu penggambaran

digunakan untuk traversal dan sisanya digunakan untuk pembuatan struktur uniform grid. • Penambahan jumlah thread per block pada saat eksekusi algoritma ray trac-

ing traversal mengalami trend penurunan waktu penggambaran karena penurunan jumlah prosessor yang idle pada saat eksekusi.

5.2 Pengembangan Lebih Lanjut 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 terda-

pat pada hasil penggambaran. • Penambahan efek refleksi dan refraksi cahaya (dengan material tertentu) agar

didapatkan hasil penggambaran yang lebih realistik. 69

• Perancangan sistem lebih lanjut untuk dinamik scene (animated scene) se-

hingga dapat digunakan dengan model / scene yang terdapat animasi didalamnya. • Penggunaan multi GPU untuk implementasi algoritma sehingga waktu penggam-

baran yang dihasilkan lebih cepat.

70

DAFTAR REFERENSI

[AW87]

John Amanatides and Andrew Woo. A fast voxel traversal algorithm for ray tracing. In Proc. Eurographics 1987, August 1987.

[Ble90]

Guy E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, November 1990.

[Chr05]

Martin Christen. Ray tracing on gpu. Master’s thesis, University of Applied Sciences Basel, 2005.

[CP09]

Siddhartha Chatterjee and Jan Prins. Pram algorithms. Parallel Computing Course Notes, University of North Carolina at Chapel Hill, 2009.

[FH09]

Reza Fuad and Mochamad Hariadi. Gpu-based parallel algorithm for construction of uniform grid structure. In National Seminar on Applied Technology, Science, and Arts 2009, 2009.

[GSCH93] Steven J. Gortler, Peter Schröder, Michael F. Cohen, and Pat Hanrahan. Wavelet radiosity. In SIGGRAPH ’93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pages 221–230, New York, NY, USA, 1993. ACM. [GTGB84] Cindy M. Goral, Kenneth E. Torrance, Donald P. Greenberg, and Bennett Battaile. Modeling the interaction of light between diffuse surfaces. SIGGRAPH Comput. Graph., 18(3):213–222, 1984. [Hav00]

Vlastimil Havran. Heuristic ray shooting algorithms. PhD thesis, Czech Technical University, 2000.

[HJ09]

Toshiya Hachisuka and Henrik Wann Jensen. Stochastic progressive photon mapping. ACM Trans. Graph., 28(5):1–8, 2009.

[HOJ08]

Toshiya Hachisuka, Shinji Ogaki, and Henrik Wann Jensen. Progressive photon mapping. ACM Trans. Graph., 27(5):1–8, 2008.

[HSO07]

Mark Harris, Shubhabrata Sengupta, and John D. Owens. Parallel prefix sum (scan) with cuda. GPU Gems 3, pages 851–876, 2007. 71

[IDC09]

Paul Ivson, Leonardo Duarte, and Waldemar Celes. Gpu-accelerated uniform grid construction for ray tracing dynamic scenes. Master’s thesis, PUC-Rio, 2009.

[Ize09]

Thiago Ize. Efficient acceleration structures for ray tracing static and dynamic scenes. PhD thesis, University of Utah, 2009.

[JC07]

Henrik Wann Jensen and Per H. Christensen. High-quality rendering using ray tracing and photon mapping. In Siggraph course notes, 2007.

[Jen96]

Henrik Wann Jensen. Global illumination using photon maps. pages 21–30. Springer-Verlag, 1996.

[JJD08]

Wojciech Jarosz, Henrik Wann Jensen, and Craig Donner. Advanced global illumination using photon mapping. In SIGGRAPH ’08: ACM SIGGRAPH 2008 classes, pages 1–112, New York, NY, USA, 2008. ACM.

[Kaj86]

James T. Kajiya. The rendering equation. SIGGRAPH Comput. Graph., 20(4):143–150, 1986.

[Kel97]

Alexander Keller. Instant radiosity. In SIGGRAPH ’97: Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pages 49–56, New York, NY, USA, 1997. ACM Press/AddisonWesley Publishing Co.

[KK86]

Timothy L. Kay and James T. Kajiya. Ray tracing complex scenes. In SIGGRAPH ’86: Proceedings of the 13th annual conference on Computer graphics and interactive techniques, pages 269–278, New York, NY, USA, 1986. ACM.

[KS09]

Javor Kalojanov and Philipp Slusallek. A parallel algorithm for construction of uniform grids. In HPG ’09: Proceedings of the Conference on High Performance Graphics 2009, pages 23–28, New York, NY, USA, 2009. ACM.

[LD08]

Ares Lagae and Philip Dutré. Compact, fast and robust grids for ray tracing. In SIGGRAPH ’08: ACM SIGGRAPH 2008 talks, pages 1–1, New York, NY, USA, 2008. ACM.

[MT97]

Tomas Möller and Ben Trumbore. Fast, minimum storage ray-triangle intersection. J. Graph. Tools, 2(1):21–28, 1997. 72

[Nvi09a]

NVIDIA Corporation. CUDA 2.3 Programming Guide, 2009.

[Nvi09b]

NVIDIA Corporation. CUDA 2.3 Reference Manual, 2009.

[SHG08]

Shubhabrata Sengupta, Mark Harris, and Michael Garland. Efficient parallel scan algorithms for GPUs. Technical Report NVR-2008-003, NVIDIA Corporation, December 2008.

[SHG09]

N. Satish, M. Harris, and M. Garland. Designing efficient sorting algorithms for manycore gpus. In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pages 1–10, 2009.

[SHZO07] Shubhabrata Sengupta, Mark Harris, Yao Zhang, and John D. Owens. Scan primitives for gpu computing. In GH ’07: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pages 97–106, Aire-la-Ville, Switzerland, Switzerland, 2007. Eurographics Association. [SKSS08] László Szirmay-Kalos, László Szécsi, and Mateu Sbert. GPU-Based Techniques for Global Illumination Effects. Synthesis Lectures on Computer Graphics and Animation. Morgan & Claypool Publishers, 2008. [Whi80]

Turner Whitted. An improved illumination model for shaded display. Commun. ACM, 23(6):343–349, 1980.

[WIK+ 06] Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll, and Steven G. Parker. Ray Tracing Animated Scenes using Coherent Grid Traversal. ACM Transactions on Graphics, 25(3):485–493, Jul 2006. (Proceedings of ACM SIGGRAPH 2006).

73


LAMPIRAN HASIL PENGGAMBARAN

(a) Model wood doll

(b) Model bunny stanford

75

(c) Model sponza atrium

(d) Model Horse georgia university

76

(e) Model fairy forest

(f) Model conference room

77

(g) Model hand (from georgia university)

(h) Model dragon stanford

78

(i) Model happy budha (stanford)

(j) Model blade (dari georgia university)

79


DAFTAR RIWAYAT HIDUP

Reza Fuad Rachmadi, anak pertama dari pasangan suami istri Achmad Fuadi (alm) dan Lina Rachmawati, melakukan studi sekolah dasarnya di SD Pengadilan II Bogor, lalu melanjutkan ke SMPN 1 Bogor dan ke SMUN 1 Bogor. Pada tahun 2003, beliau menempuh jalur SPMB dan diterima di Jurusan Teknik Elektro ITS dan lulus pada tahun 2009. Sekarang beliau sedang menyelesaikan tesis untuk memperoleh gelar S2 pada Jurusan Teknik Elektro ITS bidang studi bidang studi jaringan cerdas multimedia dengan bidang konsentrasi game teknologi.

RANCANG BANGUN RAY TRACING PIPELINE PADA PLATFORM CUDA

Recommend Documents