THE ALGORITHMS OF PARALLEL RADIX SORTING ON GPGPU
UDC 004.424.5.032.24
DOI:
This paper analyzes the possibilities of developing the BVH tree construction algorithm. This algorithm should allow to quickly rebuild the tree when you change the parameters of the problem. It is proposed to analyze the linear BVH tree, first select the order in which the leaf nodes are indicated in the tree, then the internal nodes are generated in this order. The z-order curve is selected and the Morton codes for each leaf node are calculated. The next step is to sort the resulting Morton codes. The binary sequence sorting algorithm uses a parallel Radix Sort algorithm. To analyze the sequence of leaf nodes, it is necessary to divide it into subintervals, the sizes of which are determined by binary search. In order to increase the occupancy of the graphics card, you are prompted to specify the internal nodes in a certain way, and then you have the opportunity to find out what range of leaf nodes any selected internal node belongs to. DirectCompute technology and Shader programming language-HLSL were used to test the algorithm of fast BVH tree construction on GPGPU. Given the dependence of running time of each of the number of primitives in the computation of the bounding volumes of the leaf nodes and their codes of Morton, forming a tree hierarchy, the computation of the bounding volumes of internal nodes.
1. Boundin Volume Hierarchy [электронный ресурс]: https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
2. Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees, Tero Karras, NVIDIA Research, 2012 [электронный ресурс]: https://devblogs.nvidia.com/wpcontent/uploads/2012/11/karras2012hpg_paper.pdf
3. Simpler and Faster HLBVH with Work Queues, Kirill Garanzha, Jacopo Pantaleoni, David McAllister, NVIDIA [электронный ресурс]: http://www.highperformancegraphics.org/previous/www_2011/media/Papers /HPG2011_Papers_Garanzha.pdf
4. Fast BVH Construction on GPUs, C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, D. Manocha [электронный ресурс]: http://luebke.us/publications/eg09.pdf
5. Space filling curve [электронный ресурс]: https://en.wikipedia.org/wiki/Space-filling_curve
6. Z-order curve [электронный ресурс]: https://en.wikipedia.org/wiki/Zorder_curve
Keywords: bhv-tree, binary search, video card, leaf node, morton codes
For citation: Vorontsov G.V. Preobrazhensky A.P. Choporov O.N. THE ALGORITHMS OF PARALLEL RADIX SORTING ON GPGPU. Modeling, Optimization and Information Technology. 2018;6(2). Available from: https://moit.vivt.ru/wp-content/uploads/2018/04/VoronzovSoavtori_2_18_1.pdf DOI: (In Russ).