Cache-Oblivious Ray Reordering
Video (mov, 27MB)
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.
Contents
Paper:
Cache-Oblivious Ray Reordering
@article{1805972,
author = {Moon, Bochang and Byun, Yongyoung and Kim, Tae-Joon and Claudio, Pio and Kim, Hye-Sun and Ban, Yun-Ji and Nam, Seung Woo and Yoon, Sung-Eui},
title = {Cache-oblivious ray reordering},
journal = {ACM Trans. Graph.},
volume = {29},
number = {3},
year = {2010},
issn = {0730-0301},
pages = {1--10},
doi = {http://doi.acm.org/10.1145/1805964.1805972},
publisher = {ACM},
address = {New York, NY, USA},
}
Earlier version (technical report):
Cache-Oblivious Ray Reordering
Bochang Moon, Youngyong Byun, Tae-Joon Kim, Pio Claudio, and Sung-Eui Yoon
KAIST Tech. Report, CS/TR-2009-314
May, 2009
Related Links
Cache-Oblivious Mesh Layouts
Dept. of Computer Science
KAIST
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com