Shell: A Spatial Decomposition Data Structure for 3D Curve Traversal on Many-Core Architectures

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.