Efficient Visibility Heuristics for kd-trees Using the RTSAH

Moulin, Matthias; Billen, Niels; Dutré, Philip

Efficient Visibility Heuristics for kd-trees Using the RTSAH

Files

031-039.pdf (10.53 MB)

Date

2015

Authors

Moulin, Matthias
Billen, Niels
Dutré, Philip

Publisher

The Eurographics Association

Abstract

Acceleration data structures such as kd-trees aim at reducing the per-ray cost which is crucial for rendering performance. The de-facto standard for constructing kd-trees, the Surface Area Heuristic (SAH), does not take ray termination into account and instead assumes rays never hit a geometric primitive. The Ray Termination Surface Area Heuristic (RTSAH) is a cost metric originally used for determining the traversal order of the voxels for occlusion rays that takes ray termination into account. We adapt this RTSAH to building kd-trees that aim at reducing the per-ray cost of rays. Our build procedure has the same overall computational complexity and considers the same finite set of splitting planes as the SAH. By taking ray termination into account, we favor cutting off child voxels which are not or hardly visible to each other. This results in fundamentally different and more qualitative kd-trees compared to the SAH.

        @inproceedings{10.2312:sre.20151164
,
booktitle = {Eurographics Symposium on Rendering - Experimental Ideas & Implementations
},
editor = {Jaakko Lehtinen and Derek Nowrouzezahrai
},
title = {{Efficient Visibility Heuristics for kd-trees Using the RTSAH
}},
author = {Moulin, Matthias and 
Billen, Niels and 
Dutré, Philip
},
year = {2015
},
publisher = {The Eurographics Association
},
ISBN = {},
DOI = {10.2312/sre.20151164
}
}