NDLI: Cache-oblivious ray reordering

Content Provider	ACM Digital Library
Author	Byun, Yongyoung Ban, Yun-Ji Yoon, Sung-Eui Kim, Hye-Sun Claudio, Pio Moon, Bochang Nam, Seung Woo Kim, Tae-Joon
Copyright Year	2010
Abstract	We present a cache-oblivious ray reordering method for ray tracing. Many global illumination methods such as path tracing and photon mapping use ray tracing and generate lots of rays to simulate various realistic visual effects. However, these rays tend to be very incoherent and show lower cache utilizations during ray tracing of models. In order to address this problem and improve the ray coherence, we propose a novel Hit Point Heuristic (HPH) to compute a coherent ordering of rays. The HPH uses the hit points between rays and the scene as a ray reordering measure. We reorder rays by using a space-filling curve based on their hit points. Since a hit point of a ray is available only after performing the ray intersection test with the scene, we compute an approximate hit point for the ray by performing an intersection test between the ray and simplified representations of the original models. Our method is a highly modular approach, since our reordering method is decoupled from other components of common ray tracing systems. We apply our method to photon mapping and path tracing and achieve more than an order of magnitude performance improvement for massive models that cannot fit into main memory, compared to rendering without reordering rays. Also, our method shows a performance improvement even for ray tracing small models that can fit into main memory. This performance improvement for small and massive models is caused by reducing cache misses occurring between different memory levels including the L1/L2 caches, main memory, and disk. This result demonstrates the cache-oblivious nature of our method, which works for various kinds of cache parameters. Because of the cache-obliviousness and the high modularity, our method can be widely applied to many existing ray tracing systems and show performance improvements with various models and machines that have different cache parameters.
Starting Page	1
Ending Page	10
Page Count	10
File Format	PDF
ISSN	07300301
e-ISSN	15577368
DOI	10.1145/1805964.1805972
Volume Number	29
Issue Number	3
Journal	ACM Transactions on Graphics (TOG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-07-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Ray coherence Cache utilization Ray tracing Reordering
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exploiting coherence for multiprocessor ray tracing

Cache-oblivious mesh layouts

Beam tracing polygonal objects

Ray tracing parametric surface patches utilizing numerical techniques and ray coherence

Ray tracing on programmable graphics hardware

Ray tracing with polarization parameters

Locality-oblivious cache organization leveraging single-cycle multi-hop NoCs (SIGP, Vol. 49, Issue. 4)

R-LODs: fast LOD-based ray tracing of massive models

Ray tracing parametric patches

Cache-oblivious ray reordering

Similar Documents

Exploiting coherence for multiprocessor ray tracing

Cache-oblivious mesh layouts

Beam tracing polygonal objects

Ray tracing parametric surface patches utilizing numerical techniques and ray coherence

Ray tracing on programmable graphics hardware

Ray tracing with polarization parameters

Locality-oblivious cache organization leveraging single-cycle multi-hop NoCs (SIGP, Vol. 49, Issue. 4)

R-LODs: fast LOD-based ray tracing of massive models

Ray tracing parametric patches

Cache-oblivious ray reordering