Abstract
Shared memory many-core processors such as GPUs have been extensively used in accelerating computation-intensive algorithms and applications. 3D curve traversal is a fundamental process in many applications, and is commonly accelerated by spatial decomposition schemes captured in hierarchical data structures (e.g., kd-trees). However, using hierarchical structures requires repeated hierarchical searches, which are time-consuming on shared memory many-core architectures. In this paper, we propose a novel spatial decomposition based data structure, called Shell, which completely avoids hierarchical search for 3D curve traversal. In Shell, a structure is built on the boundary of each region in the decomposed space, which allows any curve traversing in a region to find the next neighboring region to traverse using table lookup schemes. While our approach works for other spatial decomposition paradigms and many-core processors, we illustrate it using kd-tree on GPU and compare with the fastest known kd-tree ray traversal algorithms. Experimental results show that our approach accelerates ray traversal considerably over the kd-tree approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aila, T., Laine, S.: Understanding the efficiency of ray traversal on GPUs. In: Proceedings of the 1st ACM Conference on High Performance Graphics, pp. 145–149 (2009)
Bethel, E., Howison, M.: Multi-core and many-core shared-memory parallel raycasting volume rendering optimization and tuning. International Journal of High Performance Computing Applications 26(4), 399–412 (2012)
Foley, T., Sugerman, J.: Kd-tree acceleration structures for a GPU raytracer. In: Proceedings of Graphics Hardware, pp. 15–22 (2005)
Hapala, M., Havran, V.: Review: Kd-tree traversal algorithms for ray tracing. Computer Graphics Forum 30(1), 199–213 (2011)
Havran, V., Bittner, J., Zara, J.: Ray tracing with rope trees. In: Proceedings of Spring Conference on Computer Graphics, pp. 130–139 (1998)
Horn, D.R., Sugerman, J., Houston, M., Hanrahan, P.: Interactive k-d tree GPU ray tracing. In: Proceedings of Symposium on Interactive 3D Games and Graphics, pp. 167–174 (2007)
Huges, D.M., Lim, I.S.: Kd-jump: A path-preserving stackless traversal for faster isosurface raytraing on GPUs. IEEE Transactions on Visualization and Computer Graphics 15(6), 1555–1562 (2009)
Kalojanov, J., Billeter, M., Slusallek, P.: Two-level grids for ray tracing on GPUs. Computer Graphics Forum 30(2), 307–314 (2011)
NVIDIA Corporation. NVIDIA CUDA C programming guide version 5.0 (2013), http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html
Popov, S., Gunther, J., Seidel, H.P., Slusallek, P.: Stackless kd-tree traversal for high performance GPU ray tracing. Computer Graphics Forum 26(3), 415–424 (2007)
Santos, A., Teixeira, J.M., Farias, T., Teichrieb, V., Kelner, J.: Understanding the efficiency of kd-tree ray traversal techniques over a GPGPU architecture. International Journal of Parallel Programming 40(3), 331–352 (2012)
Xiao, K., Zhou, B., Chen, D.Z., Hu, X.S.: Efficient implementation of the 3D-DDA ray traversal algorithm on GPU and its application in radiation dose calculation. Medical Physics 39, 7619–7626 (2012)
Zlatuska, M., Havran, V.: Ray tracing on a GPU with CUDA – Comparative study of three algorithms. In: Proceedings of Computer Graphics, Visualization and Computer Vision, pp. 69–75 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xiao, K., Chen, D.Z., Hu, X.S., Zhou, B. (2013). Shell: A Spatial Decomposition Data Structure for 3D Curve Traversal on Many-Core Architectures. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_69
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_69
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)