Tero Karras
ABSTRACT
A number of methods for constructing bounding volume hierarchies and point-based octrees on the GPU are based on the idea of ordering primitives along a space-filling curve. A major shortcoming with these methods is that they construct levels of the tree sequentially, which limits the amount of parallelism that they can achieve. We present a novel approach that improves scalability by constructing the entire tree in parallel. Our main contribution is an in-place algorithm for constructing binary radix trees, which we use as a building block for other types of trees.
- AILA T., LAINE S.: Understanding the efficiency of ray traversal on GPUs. In Proc. High Performance Graphics (2009), pp. 145-149. Google Scholar
Digital Library
- CRASSIN C., NEYRET F., SAINZ M., GREEN S., EISEMANN E.: Interactive indirect illumination using voxel cone tracing. Computer Graphics Forum 30, 7 (2011), 1921-1930.Google ScholarCross Ref
- DANILEWSKI P., POPOV S., SLUSALLEK P.: Binned SAH Kd-Tree Construction on a GPU. Tech. rep., Saarland University, 6 2010.Google Scholar
- ERICSON C.: Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3D Technology). 2004. Google ScholarDigital Library
- GARANZHA K., PANTALEONI J., MCALLISTER D. K.: Simpler and faster HLBVH with work queues. In Proc. High Performance Graphics (2011), pp. 59-64. Google ScholarDigital Library
- LAUTERBACH C., GARLAND M., SENGUPTA S., LUEBKE D., MANOCHA D.: Fast BVH construction on GPUs. Computer Graphics Forum 28, 2 (2009), 375-384.Google ScholarCross Ref
- MERRILL D. G., GRIMSHAW A. S.: Revisiting sorting for GPGPU stream architectures. In Proc. Parallel Architectures and Compilation Techniques (2010), pp. 545-546. Google ScholarDigital Library
- PANTALEONI J., LUEBKE D.: HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In Proc. High Performance Graphics (2010), 87-95. Google ScholarDigital Library
- YOKOTA R., BARBA L. A.: Fast n-body simulations on GPUs. ArXiv e-prints (aug 2011).Google Scholar
- ZHOU K., GONG M., HUANG X., GUO B.: Dataparallel octrees for surface reconstruction. IEEE Trans. Vis. Comput. Graph. 17, 5 (2011), 669-681. Google ScholarDigital Library
Index Terms
- Maximizing parallelism in the construction of BVHs, octrees, and k-d trees
Recommendations
Linear-Time Construction of Two-Dimensional Suffix Trees
ICAL '99: Proceedings of the 26th International Colloquium on Automata, Languages and ProgrammingThe suffix tree of a string S is a compacted trie that represents all suffixes of S. Linear-time algorithms for constructing the suffix tree have been known for quite a while. In two dimensions, however, linear-time construction of two-dimensional ...
Comments