Premium
Stackless Multi‐BVH Traversal for CPU, MIC and GPU Ray Tracing
Author(s) -
Áfra Attila T.,
SzirmayKalos László
Publication year - 2014
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12259
Subject(s) - computer science , tree traversal , parallel computing , simd , rendering (computer graphics) , ray tracing (physics) , xeon phi , massively parallel , traverse , graph traversal , computational science , computer graphics (images) , algorithm , physics , geodesy , quantum mechanics , geography
Abstract Stackless traversal algorithms for ray tracing acceleration structures require significantly less storage per ray than ordinary stack‐based ones. This advantage is important for massively parallel rendering methods, where there are many rays in flight. On SIMD architectures, a commonly used acceleration structure is the MBVH, which has multiple bounding boxes per node for improved parallelism. It scales to branching factors higher than two, for which, however, only stack‐based traversal methods have been proposed so far. In this paper, we introduce a novel stackless traversal algorithm for MBVHs with up to four‐way branching. Our approach replaces the stack with a small bitmask, supports dynamic ordered traversal, and has a low computation overhead. We also present efficient implementation techniques for recent CPU, MIC (Intel Xeon Phi) and GPU (NVIDIA Kepler) architectures.