Improving ray traversal by using several specialized kd-trees

Roberto Torres, Pedro J. Martín, Antonio Gavilanes, Luis F. Ayuso

GRAPP 2012: 7th International Conference on Computer Graphics Theory and Applications 2012 (Rome, Italy).


 In this paper, we present several variants of the Surface Area Heuristics (SAH) to build kd-trees for specific
sets of rays’ directions. In order to cover the whole space of directions, several pairwise disjoint sets of
directions are considered and each of them leads to a different specialized kd-tree. We call Multi-kd-tree the
set of these kd-trees. During rendering, each ray will traverse the kd-tree associated with the set containing
the ray’s direction. In order to evaluate the efficiency of our proposal, we have implemented a Path Tracing
and an Ambient Occlusion renderer on GPU with CUDA. A single kd-tree built with SAH has been compared
to a Multi-kd-tree and we show that all the new heuristics exhibit a better performance than SAH over usual

Donwload: download PDF pdf bibtex