This paper presents a parallel kd-tree traversal algorithm based on the parallel binary radix tree construction scheme proposed by Tero Karras in 2012. In his paper, Tero Karras proposed parallel tree construction algorithm which can maximize the utilization of GPU threads, but implementation and analysis of kd-tree are not fully discussed. This paper aims to fill the gap for the specific kd-tree cases. As an application for the kd-tree traversal method proposed in this paper, the proposed method has been implemented with NVIDIA’s CUDA framework and tested on NVIDIA’s realtime raytracing library, OptiX. As a result, the proposed method can construct tree structures within the requirement for realtime process, but still needs specialized spatial caching data structure like the “primitive tree” for highly detailed meshes to handle spatial queries as fast as to visualize implicit surfaces under OptiX framework. However, the proposed method can be applied to dynamic collision detection and manage scene and object information for game applications thanks to its fast tree construction process. Also, realtime raytracing can be applied to game applications based on this study.

We have constructed a 3-dim hydrodynamics code called BTSPH. The fluid dynamics part of the code is based on the smoothed particle hydrodynamics (SPH), and for its Poisson solver the binary tree (BT) scheme is employed. We let the smoothing length in the SPH algorithm vary with space and time, so that resolution of the calculation is considerably enhanced over the version of SPH with fixed smoothing length. The binary tree scheme calculates the gravitational force at a point by collecting the monopole forces from neighboring particles and the multipole forces from aggregates of distant particles. The BTSPH is free from geometric constraints, does not rely on grids, and needs arrays of moderate size. With the code we have run the following set of test calculations: one-dim shock tube, adiabatic collapse of an isothermal cloud, small oscillation of an equilibrium polytrope of index 3/2, and tidal encounter of the polytrope and a point mass perturber. Results of the tests confirmed the code performance.