We present a novel, 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 the 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. 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 in 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 caches.
우리는 광선 추적법(ray tracing) 알고리즘을 위한 새롭고, 캐시 어블리비어스(cache-oblivious)의 특성을 가진 광선 재배열 방법을 제안한다. 패스 추적법(path tracing)이나 포톤 매핑(photon mapping)과 같은 전역조명법(global illumination) 방법들은 광선 추적법을 주 엔진으로 사용하고 있으며, 다양한 시각적 효과를 만들어 내기 위해 많은 광선들을 만들어 낸다. 그러나, 이러한 광선들은 매우 인코히어런트(incoherent) 하고, 낮은 캐시 이용률을 보인다. 이 문제를 해결하여 캐시 이용률을 높이기 위해 우리는 교점 휴리스틱(hit point heuristic)을 제안한다. 교점 휴리스틱은 광선 재배열을 위해서 광선과 모델의 교점을 사용한다. 우리는 이 교점을 가지고, 공간 채움 곡선(space filling curve)을 사용하여 광선들을 정렬한다. 광선과 모델의 교점은 오직 광선과 모델들의 교점 검사 후에 알 수 있기 때문에 우리는 광선과 간략화된 모델사이의 교점 검사를 통해 얻어진 대략적인 교점을 사용한다. 우리의 광선 재배열 방법은 보편적인 광선 추적 시스템의 다른 컴포넌트들과 독립적이기 때문에 높은 이식성을 가진다. 우리는 이 방법을 포톤 매핑과 패스 추적법에 적용하여 주 메모리의 사이즈보다 큰 대용량 모델에 대해서 10 배 이상의 속도향상을 얻었다. 또한, 우리의 방법을 사용하면 주 메모리의 사이즈보다 작은 일반 모델에 대해서도 속도향상을 얻을 수 있다. 일반 모델과 대용량 모델에서 얻을 수 있는 속도 향상의 이유는 L1/L2 캐시와 주 메모리, 그리고 디스크사이에서 일어나는 캐시 미스 횟수의 감소다. 이 결과는 다양한 캐시 종류에서도 잘 동작하는 캐시 어블리비어스 특성을 보여준다. 캐시 어블리비어스 특성과 높은 이식성때문에 우리 방법은 기존의 광선 추적법 기반 시스템에 널리 적용할 수 있고, 다양한 캐시 종류와 모델에서도 이 방법을 사용할 수 있다.
