В данной статье проводится анализ возможностей разработки алгоритма построения BVH-дерева. Этот алгоритм должен позволять быструю перестройку дерева при изменении параметров задачи. Предлагается анализировать линейное BVH-дерево, вначале выбирается порядок, в котором листовые узлы обозначаются в дереве, затем генерируются внутренние узлы по этому порядку. Рассматривается кривая Z-порядка, вычисляются Мортон-коды для каждого листового узла. На следующем шаге осуществляется сортировка получившихся Мортон-кодов. В алгоритме сортировки двоичной последовательности используется параллельный алгоритм Radix Sort. Для анализа последовательности листовых узлов, необходимо разбить ее на подинтервалы, размеры которых определяются в рамках бинарного поиска. Чтобы повысить значение занятости видеокарты, предлагается указать внутренние узлы определенным образом, и тогда, появляется возможность узнать, к какому диапазону листовых узлов относится любой выбранный внутренний узел. Для тестирования алгоритма быстрого построения BVH-дерева на GPGPU была использована технология DirectCompute и язык программирования шейдеров — HLSL. Приведена зависимость времени выполнения каждой от количества примитивов при вычислении ограничивающих объемов листовых узлов и их кодов Мортона, формировании иерархии дерева, а также вычислении ограничивающих объемов внутренних узлов.
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.
The authors declare that there are no conflicts of interest present.