Bidang
Visibilitas untuk Ray Tracing
Jesper Mortensen 1 Pankaj Khanna 1 Insu Yu 1 Mel Slater 1,2
1
Departemen Ilmu Komputer, Universitas College London, London, Inggris 2
ICREA-Universitat Politecnica` de Catalunya, Departemen de LSI, Barcelona, Spanyol
j.mortensen | p.khanna | i.yu | m.slater @ cs.ucl.ac.uk
Abstrak
Makalah ini menyajikan jenis struktur data
visibilitas untuk pelacakan sinar dipercepat. Bidang visibilitas dibangun
dengan memilih subdivisi titik reguler di atas belahan bumi untuk mendapatkan
satu set arah. Sesuai dengan arah masing-masing ada kemudian kotak persegi
panjang balok paralel, dengan masing-masing balok referensi satu set
pengidentifikasi yang sesuai dengan ob-jects yang memotongnya. Objek yang
tergeletak di sepanjang balok diurutkan menggunakan BSP 1D sepanjang arah
sinar. Sinar yang sesuai dengan sinar apapun dapat dilihat dalam waktu
konstan yang kecil dan set objek yang sesuai dengan sinar dapat dicari untuk
persimpangan dengan sinar menggunakan strategi traversal yang
dioptimalkan.Pendekatan ini berdagang dari rendering speed untuk penggunaan
memori dan waktu pre-processing. Struktur data juga sangat cocok untuk
tugas-tugas integrasi belahan bumi karena sifatnya yang bulat dan hasil untuk
satu tugas tersebut - Ambient Occlusion - juga disajikan. Hasil-hasil
untuk berbagai adegan dengan berbagai metode penyajian disajikan dan
dibandingkan dengan pendekatan yang mapan, pendekatan Ray Coherent Ray Tracing
tunggal dari Wald dan Slusallek et al.
Pengidentifikasi objek. Struktur data
adalah contoh khusus dari 'bidang cahaya virtual' (VLF) [34], yang kami sebut
VLF-RT dalam makalah ini. Sebuah sinar digunakan sebagai array mencari
indeks ke dalam struktur data VLF-RT, dan segera memberikan satu set objek kandidat
untuk pengujian persimpangan objek-ray. Seperangkat objek, sebagian kecil
dari nomor asli dalam adegan, dapat dilalui secara linier atau dengan metode
lain.
Kami membahas latar belakang literatur dan
state-of-the art di Bagian 2. Struktur data VLF-RT untuk penelusuran sinar
disajikan dalam Bagian 3. Dalam Bagian 4 kami memotivasi dan menggambarkan
penggunaan partisi kedalaman seragam untuk fi-nal traversal dari seperangkat
potensial yang terlihat (PVS) kembali dari pencarian sinar ke
VLF-RT. Implementasi de-ekor diberikan dalam Bagian 5. Hasil dalam bentuk
com-parisons antara Coherent Ray Tracing (CRT) [37, 36] dan metode VLF-RT
disajikan dalam Bagian 6. Bagian 7 menyajikan aplikasi untuk Oklusi Ambient dan
kesimpulan dalam Bagian 8, termasuk diskusi tentang bagaimana perubahan adegan
dinamis sangat sederhana dalam metode ini. Dalam makalah ini kami hanya
berkonsentrasi pada pelacakan sinar 'klasik' seperti yang dijelaskan oleh
Whitted [42]. Untuk kompatibilitas dengan CRT, semua contoh kami terbatas
pada poligon, dan dalam hasil utama kami, segitiga. Namun, metode ini
tidak terikat pada benda poligonal.
1. Pendahuluan
Ada kemajuan signifikan terhadap pelacakan sinar
real-time dalam beberapa tahun terakhir, melalui eksploitasi algo-rithms yang
dibuat khusus untuk berkinerja baik pada hardware grafik-ics saat ini [28, 6,
39, 29]. Setiap algoritma pelacakan sinar harus berurusan dengan masalah
ray-object traversal - yaitu, untuk menemukan sinar pada permukaan terdekat
yang bersinggungan, dan masalah ini telah menerima banyak perhatian sejak
diperkenalkannya ray tracing ke dalam grafik komputer [2, 42]. Semua
metode yang sukses bergantung pada struktur data yang ketika dilalui oleh
sinar, menghasilkan sekumpulan objek, pasangan calon, atau perangkat yang dapat
dilihat secara potensial, sehingga sinar dapat berpotongan. Dalam tulisan
ini kami menyajikan modifikasi dari pendekatan standar ini. Kami
mengeksploitasi struktur data 4-dimensi, yang mirip dengan medan cahaya yang
bukannya menyimpan toko pancaran
2. Latar belakang
Ray tracing adalah tipe pertama iluminasi global
yang diperkenalkan ke komputer grafik [42]. Ini sangat sim-ply dan elegan
mendukung bayangan, refleksi dan transmisi spekulatif, dan juga memecahkan
masalah visibilitas. Ini tidak benar menangani jalur cahaya yang
melibatkan pantulan buram atau mengkilap, dan ini tidak akan dipertimbangkan
dalam makalah ini. Manfaat keseluruhan dari pelacakan sinar telah dibahas
berkali-kali, misalnya [13] untuk gambaran umum dan algoritma standar, dan [37]
untuk manfaat potensial dibandingkan dengan pipa grafis standar. Dalam
makalah asli, Whitted menunjukkan bahwa waktu yang sangat banyak untuk
menghasilkan gambar yang ditelusuri sinar diambil oleh kalkulasi objek
sinar-ray. Banyak teknik telah dikembangkan untuk mencoba mengurangi waktu
ini. Ini dapat diklasifikasikan menjadi
Subdivisi objek-ruang dan pembagian ruang meteor-ray. Yang
pertama membangun subdivisi ruang adegan, sehingga setiap sel dalam subdivisi
merujuk ke sekumpulan objek yang relatif kecil, dan ray traversal melalui
subdivisi ini relatif sederhana dan cepat. Untuk setiap sinar yang
diberikan, objek ma-joran yang luas tidak pernah diuji untuk persimpangan -
hanya yang diambil oleh skema ray traversal yang dianggap sebagai kandidat
untuk persimpangan. Contoh dari metode ini termasuk boundary extent
hierarchies [22, 14], metode pembagian ruang langsung - seperti ruang seragam
subdivi-sion [11, 1, 8], oc-trees [12], dan BSP trees [21, 20, 35 ]. Itu
diperdebatkan dalam [35] bahwa dari ini skema pembagian subdivisi BSP di
traversal sinar tercepat, dengan waktu logaritmik dalam jumlah
poligon. Skema klasifikasi Ray di sisi lain memanfaatkan koherensi di
antara sinar. Salah satu contoh dari ini adalah buffer cahaya [16] yang
secara efisien menghitung penyimpangan untuk sinar 'peraba
bayangan'. Namun, pendekatan klasifikasi sinar umum yang diterapkan pada seluruh
proses pelacakan sinar diberikan oleh [3]. Sinar direpresentasikan sebagai
titik di ruang 5D dan 32-pohon ruang sinar dibangun dengan malas karena setiap
sinar berturut-turut ditemukan (sebenarnya enam 32-pohon masing-masing mewakili
salah satu dari enam wajah kotak berlari di sekitar tempat
kejadian). Setiap sel dari 32-pohon mewakili satu set sinar yang sama, dan
sesuai dengan masing-masing sel adalah satu set objek yang dapat
didelegasikan. Setiap objek dalam set kandidat sedemikian rupa sehingga setidaknya
satu dari sinar di sel memotongnya. Dengan kata lain, sel 32 pohon sesuai
dengan sinar dalam ruang 3D yang memotong sekumpulan objek - kandidat yang
ditetapkan untuk sel. Ukuran pohon tergantung pada ukuran maxi-mum yang
diizinkan dari kumpulan objek kandidat. Sekarang diberi sinar baru, itu
disaring ke pohon, calonnya ditetapkan diidentifikasi, dan persimpangan
dilakukan dengan ini. Skema klasifikasi sinar juga dapat ditingkatkan
dengan menggunakan metode subdivisi adaptif [32]. Variasi lain pada
pendekatan ini disajikan dalam [25] yang menghilangkan salah satu dimensi ruang
sinar dengan menggunakan koherensi sinar. Karena banyak sinar dapat
terletak pada garis yang sama, duplikasi sinar dikurangi dengan
mengklasifikasikan garis bukan sinar. Variasi ini menggunakan pohon
pencarian biner untuk menemukan persimpangan dengan daftar objek
candi. Algoritma VLF-RT yang disajikan dalam makalah ini dapat dianggap
sebagai representasi yang jauh lebih efisien dari ide yang sama - karena dalam
hal ini sinar yang sama juga dikelompokkan bersama-sama dan masing-masing
kelompok sinar tersebut memiliki satu set objek candi. Namun, struktur
datanya jauh lebih sederhana daripada 32 pohon, dan pengambilan hasil
kumpulan-sinar lebih dicari daripada penelusuran pohon. Dalam masing-masing
dua kategori besar ini ada banyak proposal untuk peningkatan lebih lanjut dan
substansial dalam kecepatan traversal ray-object. Sebagai contoh,
membangun gagasan representasi BSP Havran [19, 18] memperkenalkan pohon tali
untuk mempercepat pohon ray-BSP traversal, dan dalam [30] biaya traversal BSP
dikurangi dengan menghitung titik masuk pohon BSP untuk pengumpulan tions of
rays. Selain itu, skema caching telah diperkenalkan. Dipotong untuk
menggunakan kembali elemen solusi di beberapa pandangan, mengeksploitasi
semacam koherensi ray-view [41, 40].
Dengan pengenalan perangkat keras grafis yang
dapat diprogram menggantikan fungsi pipa tetap dan pertumbuhan pesat kinerja
perangkat keras grafis sejumlah upaya telah dilakukan untuk memetakan ray
tracing ke unit pemrosesan grafik (GPU) [29, 6]. Segmen segitiga-ray
mentah pada GPU telah terbukti mengungguli implementasi CPU. Namun
demikian, struktur data pembagian ruang kd-tree memetakan secara buruk ke
arsitektur streaming dan mengharuskan penggunaan grid seragam; struktur
akselerasi suboptimal. Upaya telah dilakukan untuk memetakan struktur data
kd-tree ke GPU [10], tetapi sejauh ini algoritma pelacakan sinar CPU bekerja
lebih baik daripada rekan-rekan GPU.
Kemajuan dalam kekuatan prosesor dan bandwidth
jaringan telah mendukung kecepatan besar dalam pelacakan sinar sehingga hari
ini adalah mungkin untuk mencapai kecepatan interaktif untuk jutaan poligon
pada kelompok PC konsumen [39].Pencarian ulang ini mengandalkan skema pembagian
ruang untuk solusi persimpangan cepat, khususnya pohon BSP, bersama-sama dengan
organisasi yang tepat dari keseluruhan algoritma agar sesuai dengan kebutuhan
perangkat keras, dan implementasi paralel atas PC clus-ters [38, 4]
]. Bukti sampai saat ini menunjukkan bahwa satu skema pada
khususnya; koheren ray tracing (CRT) [37] adalah implementasi tercepat
dari ray tracing. Ini menggunakan sub divisi ruang pohon
BSP.Pelaksanaannya diatur sedemikian rupa sehingga sebagian besar akses memori
masuk ke dalam dua cache prosesor pertama, yang dengan sendirinya menghasilkan
percepatan hingga setengah urutan mag-nitude seperti yang dilaporkan dalam
makalah asli. Selain itu, paket dari 4 sinar SIMD dilacak secara
paralel. Kami juga telah menerapkan skema CRT sinar tunggal, dan dengan
hasil inilah kami membandingkan pendekatan baru kami dalam Bagian 6 dan 7.
3. Bidang Visibilitas untuk Ray Tracing
Pada bagian berikut ini kami membahas struktur data, konstruksinya
dan bagaimana melakukan kueri terhadapnya.
3.1. Struktur data
Struktur data lapangan cahaya virtual awalnya
di-spired oleh bidang cahaya [27, 15] dan jenis representasi yang digunakan
mirip dengan yang di [5] dan juga untuk struktur data yang digunakan untuk
visibilitas culling di [7] . Sedangkan medan cahaya hanya-ketik hanya
menyimpan cahaya di persimpangan pertama dari sinar dengan objek, Layered Depth
Images [31] menjaga informasi radi-ance tentang masing-masing permukaan yang
sinar antar-sekte bukan hanya permukaan pertama, dan di itu merasakan struktur
data juga mirip dengan LDI. Struktur data VLF umum untuk pandangan solusi
penerangan global independen telah digunakan sebelumnya di mana informasi
pancaran
Disimpan [34]. Namun, di VLF-RT kami tidak
pernah menyimpan rasie, hanya pengidentifikasi objek (sebenarnya poligon). The
VLF-RT dengan demikian menggunakan modifikasi struktur data VLF sebagai awalnya
diperkenalkan tetapi berorientasi pada ray tracing, dan karena itu solusinya
adalah pandangan-tergantung. Ini juga membutuhkan urutan memori kurang
besar.
Kami sekarang menjelaskan VLF-RT. Adegan dapat
dikurung , misalnya, oleh kubus biasa. Anggaplah ini adalah sebuah
kubus terikat oleh (−1, −1, −1) ke (1, 1, 1). Pertimbangkan wajah bawah (z
= −1) dibatasi oleh (−1, −1, −1) dan (1, 1, −1). Ini dibagi lagi menjadi n
x n ubin persegi. Setiap ubin adalah dasar dari paralel balok t sumbu
z yang memanjang tanpa batas (meskipun hanya bagian terbatas yang memotong
adegan itu menarik). Set balok n n n paralel ini sepanjang sumbu-z disebut
sebagai sub-paralel paralel kanonik (PSF). Jika saya menunjuk dengan
koordinat spher-ical ω i = (θ i ,
φ i ) dipilih pada unit hemi-sphere, maka PSFs
didefinisikan sebagai rotasi dari PSF kanonik dengan memutar arah (0, 0, 1) ke
dalam titik bulat yang sesuai. Rotasi dapat dicapai dengan cara apa pun
yang konsisten di seluruh. Lihat semua berkas dalam PSF
kanonis. Ini akan memotong sejumlah permukaan di TKP. Ubin yang
sesuai dengan balok itu menyimpan kumpulan pengidentifikasi permukaan
ini. Proses menemukan semua permukaan permukaan dengan ubin PSF kanonik
sangatlah mudah. Jika kita mempertimbangkan kasus khusus bahwa semua
permukaan adalah poligon, maka ini mirip dengan raster-isian polygon dan dapat
diimplementasikan dengan sangat efisien karena efektif hanya untuk resolusi n ×
n. Diberikan PSF lainnya, sesuai dengan arah ω i seluruh
adegan dapat dirotasi sedemikian rupa sehingga ω i ditransformasi
menjadi berbaring (0, 0, 1) - sumbu z. Rasterisasi kemudian dilakukan di
ruang kanonik. Ini sangat penting untuk memilih parameterisasi di atas belahan
bumi sehingga tidak ada pencarian yang diperlukan untuk menemukan rujukan
PSF terdekat ke arah sembarang - karena pencarian sinar tersebut merupakan
operasi penting selama pelacakan sinar. Metode untuk menempatkan
titik-titik di belahan bumi menggunakan pembagian rekursif tetrahedron reguler,
yang memisahkan belahan menjadi segitiga. Pencarian waktu konstan yang
cepat dicapai untuk setiap titik sembarang di belahan bumi untuk menemukan
titik penyimpanan tertutup ke suatu titik tertentu di belahan bumi dengan
metode yang dijelaskan dalam [33]. Set (terbatas) dari arah PSF ggi
dilambangkan Ω l dan ω i ∈ Ω l mengacu pada arah
tertentu. Sistem koordinat ubin direferensikan oleh (s, t), di mana s, t =
0, 1,. . . , n - 1. Oleh karena itu, sebuah ubin direferensikan
sebagai (ω i , s, t). Kumpulan pengidentifikasi yang
terkait dengan til e dilambangkan dengan S (ω i , s,
t).
3.2. Membangun Struktur Data
Penerapan struktur data ini untuk pelacakan sinar sangat
mudah. Pertama struktur data seperti yang dibahas di atas
dibangun. Untuk setiap P SF ω i scene
ditransformasikan ke ruang kanonikal, dan setiap poligon adalah ortho-
Grafis diproyeksikan ke dasar PSF, dan ubin yang mencakup
dihitung. Ini dapat dicapai dengan melintasi setiap tepi poligon melalui
ubin untuk menghitung ubin dari semua tepi poligon, dan kemudian mengisi ubin
non-tepi yang terletak di dalam poligon. Penting bahwa algoritma trailing
tepi-tepi memungkinkan jalur 8-terhubung, daripada mengikuti algoritma gaya DDA
tradisional. Perbedaannya ditunjukkan pada Gambar 1.
Metode hms semacam ini dibahas dengan mengacu pada konteks 3D di
[9] tetapi mudah disesuaikan dengan 2D. Ketika ubin (s, t) ditemukan
ditutupi oleh
Sebuah poligon, identifier poligonnya ditulis ke
dalam S (ω i , s, t). Pada akhir proses ini untuk
semua PSF struktur data sudah selesai.
Gambar 1. Menemukan ubin
yang sesuai dengan tepi poligon - yang benar adalah ubin yang diarsir,
algoritma DDA hanya akan menghasilkan ubin yang ditandai.
3.3. Interseksi
Objek-Ray
Sekarang anggaplah bahwa
semua pengidentifikasi poligon untuk semua ubin di semua PSF telah dihitung,
dan bahwa kita memerlukan kumpulan objek yang dapat didelegasikan untuk sebuah
sinar dengan arah ω dan asal (x, y, z).Temukan arah di Ω l yang
paling dekat dengan ω dan anggaplah ini adalah ω j . Akan
ada matriks rotasi M j pra-dihitung dan disimpan dengan P
SF ω j yang memutar arah ω j ke
(0, 0, 1). Kemudian (x, y, z) × M j = (x q ,
y q , z q ) akanmenjadi titik di
ruang kanonik P SF ω j yang berkorelasi
dengan (x, y, z) di dunia ruang. Khususnya projeksi (x q ,
y q , −1) akan menjadi milik ubin tertentu. Himpunan
pengidentifikasi di ubin itu membentuk satu set yang berpotensi terlihat untuk
sinar itu.
Situasi ini
sebenarnya sedikit lebih rumit. Gambar-ure 2 menunjukkan analog 2D dari
suatu kondisi di mana sinar akan memproyeksikan ke lebih dari satu ubin. Dalam kasus Ray A jika kita
hanya memproyeksikan asal-usul sinar ke dasar PSF itu akan mengambil ubin 4.
Namun, jelas pasangan calon yang tepat akan menjadi gabungan dari ubin 2, 3 dan
4. Oleh karena itu dua titik pada setiap sinar harus memproyeksikan d -
asal, dan titik akhir. Dalam kasus bayangan peraba sinar
titik-akhir diberikan oleh posisi sumber cahaya. Dalam kasus sinar primer
atau sekunder titik pada sinar yang memotong dengan batas adegan (diwakili oleh
lingkaran pada Gambar-ure 2) dapat digunakan. Jika proyeksi dari dua
titik ini
Gambar 2. Sinar tumpang
tindih lebih dari satu ubin.
Tidak dalam ubin yang sama maka set objek kandidat yang tepat
adalah penyatuan semua ubin yang melintasi sinar. Untuk jumlah PSF yang
cukup besar (l), arah sinar akan lebih terwakili dan kedua ujung-ujung sinar
akan memproyeksikan ke ubin yang sama.
4. Ray-Tile Traversal
Setelah PSF dan genteng telah diidentifikasi
untuk sebuah sinar, rangkaian poligon yang dirujuk harus dicari untuk menemukan
persimpangan sinar-poligon terdekat (jika ada). Ini adalah operasi kritis. Untuk
jumlah poligon yang cukup besar, pendekatan yang disajikan sejauh ini sangat
menderita dan lebih cepat untuk tidak menggunakan menggunakan pohon BSP tipe
CRT untuk melintasi seluruh rangkaian poligon untuk setiap sinar dibandingkan
dengan pencarian linear dari poligon dalam ubin . Alasannya adalah karena
kinerja logarith-mic pohon BSP dan kinerja linear dalam jumlah rata-rata
poligon per petak pendekatan VLF-RT. Di sisi lain pendekatan VLF-RT memang
memiliki keuntungan bahwa tanpa adanya lintasan sinar, dan secara simultan
dengan pencarian, adalah mungkin untuk mengurangi ruang pencarian menjadi
bagian yang sangat kecil dari ukuran totalnya. Untuk mengurangi
ketergantungan linear dari waktu pada rata-rata jumlah poligon per ubin,
kompleksitas kedalaman sepanjang ubin (sepanjang arah PSF) dikurangi dengan
mengosongkan poligon ubin ke dalam partisi 1D BSP. Memisahkan pesawat
adalah or-thogonal dengan arah sinar dan dipilih menggunakan split median
sederhana. Partisi BSP ini sepanjang ubin dapat diwakili secara efisien
oleh array 1D standar. Poligon yang mengangkang beberapa daun BSP
ditugaskan untuk masing-masing daun. Selama pengujian persimpangan,
ubin-BSP traversal in-volses rekursif dari segmen ray yang berhubungan dengan
ubin di seluruh bidang partisi BSP dan mengunjungi node / daun dari dekat ke
jauh sepanjang sinar. Ini traversal hampir-jauh-jauh memungkinkan
terminasi dini ketika persimpangan ditemukan. Kinerja proses ini lebih
ditingkatkan dengan menggunakan stack daripada kode rekursi eksplisit. Per-
Gambar 3. Sambungan Ray
/ Tile dengan lintasan linear dari pohon-pohon BSP 1D. Daun BSP yang ditandai dilalui dari
dekat ke jauh sepanjang sinar.
Dapat lebih dikurangi dan rekursi dihindari sepenuhnya dengan
melintasi BSP daun secara linear. BSP daun terdekat dan terjauh dapat
ditentukan langsung dari nilai t-silang parametrik sinar dengan batas-batas
ubin. Mengingat representasi 1D array dari BSP, sekali mulai dan akhir daun
ditentukan, daun intervensi dapat dikunjungi dekat ke jauh dalam traversal
linear sederhana. Hal ini dimungkinkan karena daun sudah benar selaras
dalam urutan yang diperlukan sepanjang arah sinar. Penghentian awal dari
proses ini lagi mungkin karena dekat dengan traversal yang jauh. Gambar 3
menunjukkan persimpangan linier dari daun ubin-BSP selama ray-traversal dari
beberapa ubin - hanya poligon yang terletak di daun abu-abu yang diuji untuk
persimpangan.
5. Masalah Implementasi
Linear traversal dari ubin-BSP sangat efisien
karena traversal dapat direalisasikan dengan implementasi yang sangat sederhana
yang tidak memerlukan pencarian kerja untuk menghitung urutan yang benar untuk
mengunjungi BSP daun. Masuk dan keluar dari t-nilai parametrik pada batas-batas
ubin dihitung secara in-crementally ketika traversal melintasi ke ubin baru. Saat
membangun ubin-BSP, poligon dipotong ke batas ubin sebelum membandingkan
rentang kedalaman poligon dengan bidang pembelahan - ini mencegah ekses yang
tidak perlu dalam daftar poligon yang ditetapkan. Ketika memotong sinar
tertentu, PSF terdekat digunakan dan sinar diproyeksikan ke PSF ini menggunakan
algoritma rasterisasi garis yang mirip dengan yang digunakan dalam rasterisasi
ubin selama inisialisasi (lihat Gambar 1). Juga, sinar terpotong ke
persimpangannya dengan adegan itu
Batas. Daftar ubin berpotongan (misalnya
ubin 2 hingga 4 pada Gambar-ure 2) dilalui di depan ke urutan belakang dan
segmen sinar untuk setiap ubin dibatasi oleh perpotongan sinar dengan batas
ubin itu. Dalam sebuah ubin, segmen ray diinteraksikan menggunakan linear
traversal dari BSP ubin. Perhatikan bahwa perbedaan arah antara sinar dan
arah PSF telah dibesar-besarkan pada Gambar 2 dan 3 untuk mengilustrasikan
masalah dengan lebih jelas; dalam prakteknya hanya sejumlah kecil ubin
yang berpotongan tergantung pada resolusi ubin (n) dan jumlah PSF (l). Situasi
yang ideal adalah ketika arah sinar cocok dengan arah PSF sangat erat - hanya
satu ubin yang perlu dipertimbangkan dalam kasus itu (Ray C ). Jelas
tidak ada penyilangan ubin dalam kasus ini dan traversal linear sederhana dari
ubin-BSP untuk seluruh segmen-ray adalah semua yang diperlukan.
Gambar 4. Gambar dari
adegan acak. Adegan 9K
(kiri) dan 16K (kanan) dilihat dari dua sudut pandang yang digunakan untuk
menentukan kinerja.
5.1. Implementasi Coherent Ray Tracing
Pendekatan CRT sinar tunggal diimplementasikan berikut [37]. Ini
menggunakan median spasial untuk BSP membelah pesawat, dan tata letak segitiga
dioptimalkan dijelaskan dalam [36]. Rekover BSP traver-sal digulirkan
menggunakan stack eksplisit, dan kernel intersection secara langsung inline
menggunakan makro. Semua kode kerangka lain seperti pembuatan sinar,
bayangan, dll. Dibagi antara dua implementasi.
6. Hasil
Kami membandingkan kinerja VLF-RT dengan
implementasi CRT yang dijelaskan di atas. Untuk setiap metode kami
menggunakan parameter yang paling cepat untuk metode itu. Dalam kasus
pohon BSP untuk CRT, parameterisasi harus dipilih khususnya kedalaman maksimum
pohon, dan jumlah maksimum maksimum poligon diizinkan per simpul daun (sub-ject
ke kedalaman maksimum). Untuk menentukan parameter ini kami menjalankan
serangkaian percobaan pra-uji dengan adegan yang dijelaskan dalam bagian berikut,
untuk menentukan kombinasi terbaik kedalaman dan ukuran daun - ini kemudian
digunakan dalam tes kinerja komparatif. Sederhananya, kedalaman ideal dari
ubin-BSP ditentukan untuk VLF-RT menggunakan strategi yang sama. Kami juga
dapat memvariasikan jumlah PSF dan resolusi ubin - sudah mengetahui bahwa
resolusi yang lebih tinggi akan menghasilkan kinerja yang lebih baik. Semua
timing diperoleh pada 2.8Ghz Pentium 4 dengan memori sistem 2GB.
6.1. Perbandingan Performa
Kami tertarik pada kecepatan ray-traversal karena jumlah poligon
meningkat. Untuk tujuan ini kami menggunakan adegan artifi-cial dengan
segitiga acak terdistribusi seragam (Gambar-ure 4). Gambar 5 menunjukkan
waktu frame, dirata-ratakan selama beberapa frame untuk meningkatkan jumlah
segitiga yang dilihat dari jalur kamera pendek melalui adegan. Sekali
lagi, hasil untuk parameter seval diperoleh dan hasil dari parameterisasi
terbaik disajikan.
Gambar 5. Waktu
rata-rata untuk membuat gambar 512 × 512 dari adegan dengan meningkatnya jumlah
segitiga acak yang terdistribusi secara seragam.
6.2. Walkthrough
Pada bagian sebelumnya kami membahas kinerja untuk skalabilitas
VLF-RT untuk adegan yang tersusun dari poligon acak. Kami sekarang
mempertimbangkan sebuah walkthrough dari adegan 'Classroom' yang lebih
re-alistic (Gambar 7). Adegan terdiri dari 51.208 poligon dan 4 titik
sumber cahaya. Dua metode shad-ing digunakan: metode OpenGL sederhana
seperti yang hanya mentransmisikan sinar primer dan titik warna berdasarkan
tekstur menyebar lokal dan jarak / arah ke sumber cahaya; dan Shading
tipe-Whitting yang menggunakan pantulan sekunder dan sinar bayangan. Frame
perbandingan membuat waktu untuk berjalan-jalan dari adegan kelas sepanjang
jalur kamera tetap yang terdiri dari 420 frame untuk CRT dan VLF-RT meth-ods
ditunjukkan pada Gambar 6. Hasil ini untuk parameter opti-mum untuk CRT (BSP
kedalaman 23) dan VLF-RT (128 × 128 ubin, ubin-BSP kedalaman 5) - jumlah PSF
Gambar 6. Render frame
kali untuk adegan ruang kelas.
Namun tetap diperbaiki
di 513. Ukuran gambar yang diberikan per frame adalah 256 × 256.
Gambar 7. Adegan kelas
dengan shading Whitted dan OpenGL.
7. Aplikasi untuk Oklusi Ambient
Ketika menyinari adegan / gambar, perhitungan
dif-fuse antar-refleksi seringkali sangat mahal. Biasanya hanya beberapa
iterasi transfer difus yang dihitung - mungkin meninggalkan beberapa fragmen
dari pemandangan yang benar-benar gelap.Untuk mengatasi ini istilah ambient
(biasanya konstan) ditambahkan ke perhitungan shading untuk memperhitungkan
iterasi selanjutnya dari transfer difus - istilah ambient konstan ini dapat
bagaimana membuat hasil tampak artifisial. Oklusi ambien adalah metode
yang digunakan untuk membuat gambar terlihat lebih masuk akal secara fisik. Alih-alih
menggunakan istilah ambien konstan, visibilitas pada suatu titik diambil
sampelnya dan titik tersebut diarsir berdasarkan jumlah sampel yang tidak
segera tersumbat. Illu-mination biasanya dari skylight atau langit-kubah
di atas objek dan hasil bayangan yang mensimulasikan bayangan lembut. Oklusi
Ambient pada suatu titik dapat dihitung dengan memasukkan bayangan sinar ke
dalam adegan untuk mengintegrasikan visibilitas atas belahan di sekitar normal
pada titik tersebut. Arah yang dipilih untuk integrasi ini secara merata
diambil sampelnya di atas belahan bumi untuk menghindari bias dan sejumlah
besar sinar dilemparkan untuk mengurangi kebisingan. Struktur data VLF-RT
memiliki beberapa
Gambar 8. Gambar-gambar
Ray yang ditelusuri dengan ambient Oc-clusion shading.
Keuntungan dalam perhitungan Ambient Occlusion pada suatu titik. Seperti
disebutkan, arah yang dipilih untuk sinar yang dilemparkan dari titik harus
secara merata diambil sampelnya di atas belahan atas titik tersebut. Arah-arah
ini juga bisa dipilih dari set arah PSF karena ini mewakili distribusi arah
yang seragam. Ketika bayangan sinar dilemparkan ke adegan dari titik dan
terletak di sepanjang arah PSF, kedua titik akhir dari sinar itu jatuh pada
ubin yang sama (lihat Gambar 2, Ray C ). Dalam hal
ini, sinar tidak akan melewati batas-batas ubin dan hanya perlu untuk melintasi
ubin BSP terkait dari dekat-ke-jauh. Ini adalah proses yang sangat
sederhana karena struktur data yang optimal untuk traversal alam ini. Image
render times untuk berbagai adegan (Gambar-ure 8) diperoleh menggunakan
parameter optimal untuk BSP
|
CRT
|
VLF-RT
|
Kecepatan Relatif
|
|
|
Sapi
|
38,01 detik
|
15,15 detik
|
2,51x
|
|
(5.8K polys)
|
(Kedalaman BSP 16)
|
(Kedalaman tBSP 3)
|
|
|
Kalajengking
|
32,19 detik
|
17,88 detik
|
1.80x
|
|
(10K polys)
|
(Kedalaman BSP 19)
|
(Kedalaman tBSP 3)
|
|
|
Bugatti
|
43,54 detik
|
21,63 detik
|
2,01x
|
|
(11K polys)
|
(Kedalaman BSP 17)
|
(kedalaman TBSP 4)
|
|
|
Gereja
|
25.50 detik
|
14.07 detik
|
1,81x
|
|
(16K polys)
|
(Kedalaman BSP 19)
|
(kedalaman TBSP 4)
|
|
|
Kapal penarik
|
44,36 detik
|
30,65 detik
|
1.45x
|
|
(34K polys)
|
(Kedalaman BSP 23)
|
(kedalaman TBSP 4)
|
|
Tabel 1. Kinerja
komparatif untuk bayangan Oklusi Ambient.
Kedalaman pohon di kedalaman CRT dan ubin-BSP di VLF-RT. Jumlah
arah PSF dan resolusi ubin per PSF tetap dipertahankan pada 513 dan 128 × 128
masing-masing. Tabel 1 menunjukkan waktu yang dibutuhkan untuk membuat
gambar Ambient Occlusion berbayang dari beberapa adegan untuk kedua metode.
Sebanyak 513 sinar dilemparkan ke TKP dari setiap titik permukaan
untuk mengintegrasikan visibilitas atas belahan bumi. Ukuran gambar 256 ×
256 diberikan untuk setiap adegan. Hasil ini menunjukkan keuntungan yang
signifikan untuk metode VLF-RT untuk naungan jenis Ambient Occlusion yang
membutuhkan integrasi visibilitas atas belahan bumi. Untuk adegan Gereja,
CRT melacak ∼ 1,3 Mrays / sec
sedangkan jejak VLF-RT ∼ 2.4
Hr / dtk.
Menjelajah penelusuran sinar dapat digunakan untuk membuat bingkai
berikutnya seperti biasa. Untuk menghapus objek dari struktur data VLF-RT,
semua PSF dikunjungi, dan objek rasterised ke dalam sistem koordinat ubin
seperti biasa, kecuali bahwa dalam hal ini pengidentifikasi objek dihapus
daripada ditambahkan. Kemudian geometri poligon diubah, dan dimasukkan
kembali ke dalam struktur ubin dan BSP.
Ucapan Terima Kasih
Penelitian ini didanai oleh EPSRC GR / R13685 /
01. Terima kasih kepada Ingo Wald dan Carsten Benthin untuk memberikan
sug-gestions pada pelacakan sinar real time.
|
8.
Kesimpulan
|
|
|
Dalam makalah ini kami telah memperkenalkan
metode ray-traversal baru, dan mengilustrasikan aplikasinya dalam penelusuran
sinar klasik dan aplikasi ray tracing untuk shading oc-clusion yang efisien. Metode
ini bergantung pada pencarian yang sangat cepat untuk mendapatkan pasangan
calon poligon untuk setiap sinar, dan kemudian poligon ini dapat dilalui oleh
pohon BSP dengan pembagian sepanjang hanya satu sumbu. Hasilnya
menunjukkan bahwa metode ini berkinerja lebih baik daripada metode CRT sinar
tunggal dengan pohon BSP median spasial untuk berbagai adegan.
Tentunya implementasi CRT yang digunakan jauh
dari op-timal. Kinerja dapat meningkat secara signifikan dengan
menggunakan heuristik pembelahan pesawat yang berbeda [17] dan bundling sinar
[37], dan akan menarik untuk melihat bagaimana pendekatan yang disajikan di
sini tarif jika optimisasi ini diperkenalkan ke kedua algoritma; ini
adalah area penelitian yang sedang berlangsung.
Dalam makalah ini kami hanya membahas aplikasi walkthrough. Namun,
penelusuran sinar real-time juga menuntut kemungkinan perubahan dinamis pada
objek. Ini mudah dicapai dengan metode VLF-RT [24, 23]. Ketika suatu
objek diubah, pertama-tama harus dihapus dari struktur data, kemudian
geometrinya diubah dan dimasukkan kembali ke dalam struktur data. Setelah
operasi-operasi ini dilakukan,
Referensi
[1] J.
Amanatides. Ray menelusuri dengan kerucut. Dalam SIGGRAPH '84:
Prosiding konferensi tahunan ke-11 pada grafik Com-puter dan teknik interaktif,
halaman 129–135, 1984.
[2] A.
Appel. Beberapa teknik untuk rendering mesin shading dari zat padat. AFIPS
1968 Spring Joint Computer Conference, 32: 37–45, 1968.
[3] J.
Arvo dan D. Kirk. Pelacakan sinar cepat berdasarkan klasifikasi sinar. Dalam
SIGGRAPH '87: Prosiding konferensi tahunan ke-14 pada grafik Komputer dan
teknik interaktif, volume 21, halaman 55–64, Juli 1987.
[4] C.
Benthin, I. Wald, dan P. Slusallek. Pendekatan terukur untuk penerangan
global interaktif. Forum Grafis Komputer (Proc.of Eurographics), 22 (3):
621–630, 2003.
[5] E.
Camahort, A. Lerios, dan D. Fussell. Bidang cahaya seragam sam-pled. Dalam
Rendering Techniques '98 (Proceedings of Eurographics Rendering Workshop '98),
halaman 117–130, 1998.
[6] NA
Carr, JD Hall, dan JC Hart. Sinar en-gine. Dalam HWWS '02: Prosiding
konferensi ACM SIG-GRAPH / EUROGRAPHICS pada perangkat keras Grafik, halaman
37–46, 2002.
[7] Y.
Chrysanthou, D. Cohen-Or, dan D. Lischinki. Cepat visibilitas kuantitatif
pro-perkiraan untuk adegan yang kompleks. In Pro-
ceedings of Computer Graphics International '98
(CGI '98), halaman 220–227, 1998.
[8] JG
Cleary dan G. Wyvill. Analisis suatu algoritma untuk penelusuran sinar
cepat menggunakan subdivisi ruang seragam. The Visual Computer, 4 (2):
65–83, 1988.
[9] D.
Cohen dan A. Kaufman. Pindai algoritme konversi untuk objek linear dan
kuadrat. Dalam A. Kaufman, editor, Vol-ume Visualization, halaman 280–300. IEEE
Computer Society Press, Los Alamitos, CA, AS, 1990.
[10] T.
Foley dan J. Sugerman. Struktur akselerasi pohon KD untuk raytracer GPU. Dalam
HWWS '05: Prosiding konferensi ACM SIGGRAPH / EUROGRAPHICS pada perangkat keras
Grafik-ics, halaman 15-22, 2005.
[11] A.
Fujimoto, T. Tanaka, dan K. Iwata. SENI: Sistem ray-tracing dipercepat. IEEE
Computer Graphics & Applica-tions, 6 (4): 16–26, April 1986.
[12] SEBAGAI
Glassner. Subdivisi ruang untuk penelusuran sinar cepat. IEEE
Computer Graphics & Applications, 4 (10): 15-22, 1984.
[13] SEBAGAI
Glassner. Sebuah Pengantar Ray tracing. Academic Press, San Diego,
CA, USA, Januari 1989.
[14] J.
Goldsmith dan JK Salmon. Pembuatan otomatis hierarki obyektif untuk
pelacakan sinar. IEEE Computer Graphics & Applications, 7 (5): 14–20
Mei 1987.
[15] SJ
Gortler, R. Grzeszczuk, R. Szeliski, dan MF Cohen. Lumigraph. Dalam
SIGGRAPH '96: Prosiding konferensi tahunan ke-23 pada grafik Komputer dan
teknik interaktif, halaman 43-54, 1996.
[16] EA
Haines dan DP Greenberg. Penyangga cahaya: Akselerator bayangan-pengujian. IEEE
Computer Graphics & Ap-plications, 6 (9): 6–16, 1986.
[17] V.
Havran. Heuristic Ray Shooting Algorithms. Tesis PhD, Universitas
Teknik Ceko di Praha, Praha, April 2001.
ˇ
[18] V.
Havran, J. Bittner, dan J. Zara´. Ray menelusuri dengan pohon tali. Dalam
Prosiding Konferensi Musim Semi ke-13 pada Grafik Com-puter, halaman 130–139,
1998.
ˇ
[19] V.
Havran, T. Kopal, J. Bittner, dan J. Zara´. Cepat algoritma bsp traversal
yang kuat untuk ray tracing. Jurnal Alat Grafis, 2 (4): 15–23, 1997.
[20] FW
Jansen. Struktur data untuk penelusuran sinar. Dalam proses lokakarya
(Seminar Eurografi di Struktur data untuk grafik raster), halaman 57–73. Springer-Verlag,
Inc., NY, USA, 1986.
[21] MR
Kaplan. Pelacakan ruang: Pelacak sinar waktu konstan. Dalam SIGGRAPH
'85 State of the Art dalam catatan seminar Sintesis Gambar, volume 19, halaman
149–158, Juli 1985.
[22] TL
Kay dan JT Kajiya. Ray menelusuri adegan-adegan rumit. Dalam SIGGRAPH
'86: Prosiding konferensi tahunan ke-13 pada grafik Komputer dan teknik
interaktif, volume 20, halaman 269–278, NY, USA, 1986.
[23] P.
Khanna, J. Mortensen, I. Yu, dan M. Slater. Pelacakan cepat adegan-adegan
dengan gerakan tidak terstruktur. Laporan teknis, University College
London, 2004.
[24] P.
Khanna, J. Mortensen, I. Yu, dan M. Slater. Bidang visibilitas untuk
pelacakan sinar dinamis. Laporan teknis, University College London, 2004.
[25] B.
Kwon, DS Kim, K.-Y. Chwa, dan SY Shin. Klasifikasi sinar
efisien-memori untuk operasi visibilitas. Transaksi IEEE pada Visualisasi
dan Grafik Komputer, 4 (3): 193–201, Juli 1998.
[26] H.
Landis. Pencahayaan global siap produksi. Dalam Catatan Kursus
SIG-GRAPH 2002, 2002.
[27] M.
Levoy dan P. Hanrahan. Rendering medan cahaya. Dalam SIG-GRAPH '96:
Prosiding konferensi tahunan ke-23 pada grafik Komputer dan teknik interaktif,
halaman 31–42, 1996.
[28] M.
Pharr, C. Kolb, R. Gershbein, dan P. Hanrahan. Ren-buzz adegan kompleks
dengan tracing sinar koheren-memori. Dalam SIGGRAPH '97: Prosiding
konferensi tahunan ke-24 pada grafik Komputer dan teknik interaktif, halaman
101–108, Agustus 1997.
[29] TJ
Purcell, I. Buck, WR Mark, dan P. Hanrahan. Ray menelusuri pada perangkat
keras grafis yang dapat diprogram. ACM Trans-tindakan di Graphics, 21 (3):
703-712, Juli 2002.
[30] A.
Reshetov, A. Soupikov, dan J. Hurley. Algoritma pelacakan sinar
multi-level. Transaksi ACM pada Grafik, 24 (3): 1176–1185, 2005.
[31] J.
Shade, S. Gortler, L. wei He, dan R. Szeliski. Gambar kedalaman berlapis. Dalam
SIGGRAPH '98: Prosiding konferensi tahunan ke-25 pada grafik Komputer dan
teknik interaktif, halaman 231–242, 1998.
[32] G.
Simiakakis dan AM Day. Subdivisi lima dimensi adaptasi untuk pelacakan
sinar. Forum Grafis Komputer (Proc.of Eurographics), 13 (2): 133–140,
1994.
[33] M.
Slater. Permintaan waktu yang konstan pada titik-titik terdistribusi
secara merata di suatu belahan bumi. Jurnal Alat Grafis, 7 (1): 33–44,
2002.
[34] M.
Slater, J. Mortensen, P. Khanna, dan I. Yu. Pendekatan medan cahaya
virtual untuk iluminasi global. Dalam Proceedings of Computer Graphics
International (CGI 2004), halaman 102-109. IEEE Computer Society Press, 16-19 Juni
2004.
[35] K.
Sung dan P. Shirley. Ray menelusuri dengan pohon bsp. Di D. Kirk,
editor, Graphics Gems III, volume versi IBM, halaman 271–274. Morgan
Kaufmann Publishers, 1992.
[36] I.
Wald. Realtime Ray Tracing dan Interaktif Global Illu-mination. PhD
thesis, Saarland University, 2004.
[37] I.
Wald, C. Benthin, M. Wagner, dan P. Slusallek. Render inter-aktif dengan
pelacakan sinar koheren. Dalam Forum Grafis Komputer (Prosiding
EUROGRAPHICS 2001), volume 20, halaman 153–164, 2001.
[38] I.
Wald, T. Kollig, C. Benthin, A. Keller, dan P. Slusallek. Pencahayaan
global interaktif menggunakan pelacakan sinar cepat. Di
Rendering Techniques 2002 (Prosiding lokakarya
grafis Euro ke-13 tentang Rendering), 2002.
[39] I.
Wald, TJ Purcell, J. Schmittler, C. Benthin, dan P. Slusallek. Pelacakan
sinar realtime dan penggunaannya untuk iluminasi global interaktif. Eurographics
2003 STAR Report, 22 (3), 2003.
[40] B.
Walter, G. Drettakis, dan S. Parker. Perenderan interaktif menggunakan
render cache. Dalam teknik Rendering '99 (Pro-ceedings dari 10th
Eurographics Workshop on Rendering), volume 10, halaman 235–246, Juni 1999.
[41] G.
Ward dan M. Simmons. Cache holodeck ray: sistem render inter-aktif untuk
iluminasi global di lingkungan nondiffuse. ACM Transactions on Graphics,
18 (4): 361–368, 1999.
[42] T.
Whitted. Model iluminasi yang ditingkatkan untuk dis-play berbayang. Komunikasi
ACM, 23 (6): 343–349, 1980.
Posts
