БЫСТРОЕ ПОСТРОЕНИЕ BVH ДЕРЕВА НА GPGPU
УДК 004.424.5.032.24
DOI:
В данной статье проводится анализ возможностей разработки алгоритма построения 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
Ключевые слова: bhv-дерево, бинарный поиск, видеокарта, листовой узел, коды мортона
Для цитирования: Воронцов Г.В., Преображенский А.П., Чопоров О.Н. БЫСТРОЕ ПОСТРОЕНИЕ BVH ДЕРЕВА НА GPGPU. Моделирование, оптимизация и информационные технологии. 2018;6(2). URL: https://moit.vivt.ru/wp-content/uploads/2018/04/VoronzovSoavtori_2_18_1.pdf DOI:
Опубликована 30.06.2018