БЫСТРОЕ ПОСТРОЕНИЕ BVH ДЕРЕВА НА GPGPU

В данной статье проводится анализ возможностей разработки алгоритма построения BVH-дерева. Этот алгоритм должен позволять быструю перестройку дерева при изменении параметров задачи. Предлагается анализировать линейное BVH-дерево, вначале выбирается порядок, в котором листовые узлы обозначаются в дереве, затем генерируются внутренние узлы по этому порядку. Рассматривается кривая Z-порядка, вычисляются Мортон-коды для каждого листового узла. На следующем шаге осуществляется сортировка получившихся Мортон-кодов. В алгоритме сортировки двоичной последовательности используется параллельный алгоритм Radix Sort. Для анализа последовательности листовых узлов, необходимо разбить ее на подинтервалы, размеры которых определяются в рамках бинарного поиска. Чтобы повысить значение занятости видеокарты, предлагается указать внутренние узлы определенным образом, и тогда, появляется возможность узнать, к какому диапазону листовых узлов относится любой выбранный внутренний узел. Для тестирования алгоритма быстрого построения BVH-дерева на GPGPU была использована технология DirectCompute и язык программирования шейдеров — HLSL. Приведена зависимость времени выполнения каждой от количества примитивов при вычислении ограничивающих объемов листовых узлов и их кодов Мортона, формировании иерархии дерева, а также вычислении ограничивающих объемов внутренних узлов.

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