ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Cache-Oblivious Ray Reordering
Cited 38 time in scopus Share share facebook twitter linkedin kakaostory
Authors
Bochang Moon, Yongyoung Byun, Tae-Joon Kim, Pio Claudio, Hye-Sun Kim, Yun-Ji Ban, Seung Woo Nam, Sung-Eui Yoon
Issue Date
2010-06
Citation
ACM Transactions on Graphics, v.29, no.3, pp.1-10
ISSN
0730-0301
Publisher
ACM
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1145/1805964.1805972
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. © 2010 ACM 0730-0301/2010/06-ART28 $10.00.
KSP Keywords
Cache misses, Cache-oblivious, Intersection test, Massive models, Path tracing, Ray tracing, Space-filling curve, Visual Effects, global illumination, main memory, modular approach