Accelerated Ray Tracing using R-Trees

Dirk Feldmann

2015

Abstract

Efficient ray tracing for rendering needs to minimize the number of redundant intersection tests between rays and geometric primitives. Hence, ray tracers usually employ spatial indexes to organize the scene to be rendered. The most popular ones for this purpose are currently kd-trees and bounding volume hierarchies, for they have been found to yield best performances and can be adapted to contemporary GPU architectures. These adaptations usually come along with costs for additional memory or preprocessing and comprise the employment of stackless traversal algorithms. R-trees are height-balanced spatial indexes with a fixed maximum number of children per node and were designed to reduce access to secondary memory. Although these properties make them compelling for GPU ray tracing, they have not been used in this context so far. In this article, we demonstrate how R-trees can accelerate ray tracing and their competitiveness for this task. Our method is based on two traversal schemes that exploit the regularity of R-trees and forgo preprocessing or alterations of the data structure, with the first algorithm being moreover stackless. We evaluate our approach in implementations for CPUs and GPUs and compare its performance to results we obtained by means of kd-trees.

Paper Citation

in Harvard Style

Feldmann D. (2015). Accelerated Ray Tracing using R-Trees . In Proceedings of the 10th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2015) ISBN 978-989-758-087-1, pages 247-257. DOI: 10.5220/0005304802470257

in Bibtex Style

@conference{grapp15,
author={Dirk Feldmann},
title={Accelerated Ray Tracing using R-Trees},
booktitle={Proceedings of the 10th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2015)},
year={2015},
pages={247-257},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005304802470257},
isbn={978-989-758-087-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 10th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2015)
TI - Accelerated Ray Tracing using R-Trees
SN - 978-989-758-087-1
AU - Feldmann D.
PY - 2015
SP - 247
EP - 257
DO - 10.5220/0005304802470257