A key part of the most common ray tracing methods is the traversal/search for intersections with a hierarchical structure – BVH, which describes the scene geometry. This paper presents a comparative analysis of the performance of several BVH tree traversal methods on stationary and mobile graphics processors. We investigated BVH trees with varying depths and numbers of child nodes, implemented several stack-based traversal algorithms, and two different stackless traversal algorithms; we proposed our own stackless traversal variant, which is more performant than existing ones in some cases. We proposed our own compression method for BVH trees with 2 nodes, losing no more than 15% performance. We identified a common problem that occurs in almost all algorithms when implemented on graphics processors. We believe that our analysis will help developers of ray tracing hardware accelerators create more economical hardware solutions, not limited solely to ray tracing. More specifically, our experimental results suggest that up to a 5x speedup can be achieved by changing the L2 cache mechanism, and this has likely already been implemented in stationary GPUs with hardware-accelerated ray tracing, not only within the ray tracing mechanism itself but also in a more general context.
Ключевой частью наиболее распространенных методов трассировки лучей является обход/поиск пересечения с иерархической структурой – BVH, описывающей геометрию сцены. В данной работе представлен сравнительный анализ производительности нескольких методов обхода BVH-деревьев на стационарных и мобильных графических процессорах. Мы исследовали BVH-деревья с различной глубиной и количеством дочерних узлов, реализовали несколько алгоритмов обхода со стэком и два различных алгоритма безстэкового обхода; предложили свой вариант безстэкового обхода, более производительный чем существующие в ряде случаев. Предложили свой вариант сжатия BVH-дерева с двумя узлами, теряющий не более 15% производительности. Мы выявили некоторую общую проблему, встречающуюся почти во всех алгоритмах при их реализации на графических процессорах. Мы полагаем, что наш анализ поможет разработчикам аппаратных ускорителей трассировки лучей создавать более экономное аппаратное решение, не ограничиваемое при этом только лишь трассировкой лучей. Если говорить более конкретно, результаты наших экспериментов говорят о том, что можно получить ускорение до 5 раз с помощью изменения механизма работы L2-кэша, причем на стационарных GPU с аппаратным ускорением трассировки лучей это, по-видимому, уже сделано не только в рамках непосредственно механизма аппаратного ускорения трассировки лучей, но и в более общем случае.