Исследование методов обхода двухуровневых BVH-деревьев на графических процессорах

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Ключевой частью наиболее распространенных методов трассировки лучей является обход/поиск пересечения с иерархической структурой – BVH, описывающей геометрию сцены. В данной работе представлен сравнительный анализ производительности нескольких методов обхода BVH-деревьев на стационарных и мобильных графических процессорах. Мы исследовали BVH-деревья с различной глубиной и количеством дочерних узлов, реализовали несколько алгоритмов обхода со стэком и два различных алгоритма безстэкового обхода; предложили свой вариант безстэкового обхода, более производительный чем существующие в ряде случаев. Предложили свой вариант сжатия BVH-дерева с двумя узлами, теряющий не более 15% производительности. Мы выявили некоторую общую проблему, встречающуюся почти во всех алгоритмах при их реализации на графических процессорах. Мы полагаем, что наш анализ поможет разработчикам аппаратных ускорителей трассировки лучей создавать более экономное аппаратное решение, не ограничиваемое при этом только лишь трассировкой лучей. Если говорить более конкретно, результаты наших экспериментов говорят о том, что можно получить ускорение до 5 раз с помощью изменения механизма работы L2-кэша, причем на стационарных GPU с аппаратным ускорением трассировки лучей это, по-видимому, уже сделано не только в рамках непосредственно механизма аппаратного ускорения трассировки лучей, но и в более общем случае.

Полный текст

Доступ закрыт

Об авторах

Л. М. Смирнов

Московский государственный университет им. М. В. Ломоносова, факультет высшей математики и кибернетики

Автор, ответственный за переписку.
Email: lyovasmirnov@gmail.com
ORCID iD: 0000-0001-5385-4841
Россия, 119991 Москва, ГСП-1, Ленинские горы, 119

В. А. Фролов

Институт искусственного интеллекта Московского государственного университета им. М. В. Ломоносова; Московский государственный университет им. М. В. Ломоносова, факультет высшей математики и кибернетики; Институт прикладной математики им. М. В. Келдыша РАН

Email: vladimir.frolov@graphics.cs.msu.ru
ORCID iD: 0000-0001-8829-9884
Россия, 119899 Москва, Ленинские горы; 119991 Москва, ГСП-1, Ленинские горы, 119; 125047 Москва, Миусская пл. 4

Ю. А. Крячко

Московский государственный университет им. М. В. Ломоносова, факультет высшей математики и кибернетики

Email: yuri.kryachko@gmail.com
ORCID iD: 0009-0009-5676-0475
Россия, 119991 Москва, ГСП-1, Ленинские горы, 119

А. Г. Волобой

Институт прикладной математики им. М. В. Келдыша РАН

Email: voloboy@gin.keldysh.ru
ORCID iD: 0000-0003-1252-8294
Россия, 125047 Москва, Миусская пл. 4

Список литературы

  1. Beets K. The six levels of ray tracing acceleration. Imagination white paper. https://forums.macrumors.com/attachments/imagination-raytracing-primer-sept2020-pdf.1973926/
  2. Meister D., Bittne J. Performance Comparison of Bounding Volume Hierarchies for GPU Ray Tracing, Journal of Computer Graphics Techniques (JCGT). 2022. V. 11. № 4. Р. 1–19. http://jcgt.org/published/0011/04/01/
  3. Meister D., Ogaki S., Benthin C., Michael J., Doyle M.J., Guthe М., Bittner J. A Survey on Bounding Volume Hierarchies for Ray Tracing. Computer Graphics Forum. 2021. V. 40. P. 683–712.
  4. Aila T., Laine S. Understanding the Efficiency of Ray Traversal on GPUs. In Proceedings of HPG. 2009. Р. 145–149. 16, 17, 23.
  5. Aila T., Karras T. Architecture Considerations for Tracing Incoherent Rays. In Proceedings of PG. 2010. Р. 113–122. 18, 19.
  6. Aila T., Karras T., Laine S. On Quality Metrics of Bounding Volume Hierarchies. HPG. 2013. Р. 101–108. 4, 5, 10.
  7. Lier A., Stamminger M., Selgrad K. CPU-style SIMD ray traversal on GPUs. In Proceedings of the Conference on High-Performance Graphics, Association for Computing Machinery, 7:1–7:4. 2018. https://doi.org/10.1145/3231578. 3231583. 7, 8, 11, 15
  8. Ernst M., Greiner G. Early Split Clipping for Bounding Volume Hierarchies. In Proceedings of Symposium on Interactive Ray Tracing. 2007. Р. 73–78. 9, 10.
  9. Stich M., Friedrich H., Dietrich A. Spatial Splits in Bounding Volume Hierarchies. In Proceedings of the High-Performance Graphics. 2009. Р. 7–13. 10, 22, 23.
  10. Segivia B., Ernst M. Memory Efficient Ray Tracing with Hierarchical Mesh Quantization. In Proceedings of Graphics Interface. 2010. Р. 153–160. 12, 13.
  11. Mahovsky J., Wyvill B. Memory-Conserving Bounding Volume Hierarchies with Coherent Raytracing. Computer Graphics Forum 25. 2006. № 2. Р. 173–182. 12.
  12. Liktor G., Vaidyanathan K. Bandwidth-efficient BVH Layout for Incremental Hardware Traversal. In Proceedings of High-Performance Graphics. 2016. Р. 51–61. 8, 18, 19.
  13. Kalojanov J., Billeter M., Slusallek P. Two‐level grids for ray tracing on GPUs // Computer Graphics Forum. Oxford, UK: Blackwell Publishing Ltd. 2011. V. 30. № 2. P. 307–314.
  14. Bartels P., Harada T. Combining GPU Tracing Methods within a Single Ray Query. In SIGGRAPH Asia 2022 Technical Communications (SA '22). Association for Computing Machinery, New York, NY, USA, 2022. Article 17, 1–4. https://doi.org/10.1145/3550340.3564231
  15. Zellmann S., Wu Q., Ma K.L., Wald I. Memory-Efficient GPU Volume Path Tracing of AMR Data Using the Dual Mesh. 2023.
  16. Garanzha K., Bel A., Premoze S., Galaktionov V. (2011). Out-of-core GPU ray tracing of complex scenes. In ACM SIGGRAPH 2011 Talks (pp. 1-1).
  17. Roberto T. et al. Ray casting using a roped BVH with CUDA. Spring conference on Computer graphics. 2009.
  18. Binder N., Keller A. Efficient Stackless Hierarchy Traversal on GPUs with Backtracking in Constant Time. In Proceedings of High-Performance Graphics. 2016. Р. 41–50. 17.
  19. Laine S., Karra T., Aila T. Megakernels Considered Harmful: Wavefront Path Tracing on GPUs. High-Performance Graphics 2013.
  20. Wald I., Woop S., Benthin C., Johnson G.S. & Ernst M. (2014). Embree: a kernel framework for efficient CPU ray tracing. ACM Transactions on Graphics (TOG). 2014. № 33(4). Р. 1–8.
  21. Wald I., Benthin C., Boulos S. Getting Rid of Packets – Efficient SIMD Single-Ray Traversal using Multi-Branching BVHs. In Symposium on Interactive Ray Tracing. 2008. Р. 49–57. 10, 14, 22, 23.
  22. Popov S., Georgiev I., Dimov R., Slusallek P. Object Partitioning Considered Harmful: Space Subdivision for BVHs. In Proceedings of High-Performance Graphics. 2009. Р. 15–22. 4, 5, 10, 22.
  23. Ylitie H., Karras T., Laine S. Efficient Incoherent Ray Traversal on GPUs Through Compressed Wide BVHs. In Proceedings of High-Performance Graphics. 2017. Р. 4: 1–4: 13, 10, 12, 16, 17, 22, 23
  24. Yoon S.E., Manocha D. Cache-Efficient Layouts of Bounding Volume Hierarchies. Computer Graphics Forum. 2006. 8.
  25. Wachter C., Keller A. Instant Ray Tracing: The Bounding Interval Hierarchy. In Proceedings Eurographics Symposium on Rendering. 2006. Р. 139–149. 13.
  26. Eisemann M., Woizischke C., Magnor M. Ray Tracing with the Single Slab Hierarchy. In Proceedings of Vision, Modeling, and Visualization. 2008. Р. 373–381. 13.
  27. Lin D., Vasiou E., Yuksel C., Kopta D., Brunvand E. Hardware-Accelerated Dual-Split Trees. Proceedings of the ACM on Computer Graphics and Interactive Techniques 3, 2 (2020). 13.
  28. Weier P., Rath A., Michel É., Georgiev I., Slusallek P., Boubekeur T. N-BVH: Neural ray queries with bounding volume hierarchies. In ACM SIGGRAPH 2024 Conference Papers (SIGGRAPH '24). Association for Computing Machinery, New York, NY, USA, Article 99, 1–11. doi: 10.1145/3641519.3657464.
  29. Frolov V., Sanzharov V., Garifullin A., Raenchuk M., Voloboy A. CrossRT: A cross platform programming technology for hardware-accelerated ray tracing in CG and CV applications // arXiv:2409.12617

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рис. 1. Сравнение количества арифметических операций на луч для сцены Cry Sponza. Желтый (первый столбец) – LBVH-билдер, реализованный в библиотеке Embree, зеленый и фиолетовый (второй и третий) – варианты SBVH. Зеленый – наш собственный построитель, фиолетовый – реализация из библиотеки Intel Embree. Левое изображение – данные для сцены Cry Sponza. Правое – для сцены Bistro.

Скачать (1MB)
Метаданные
3. Рис. 2. Сравнение среднего числа арифметических операций на луч для сцен геометрически сложных Cry Sponza и Bistro. Для сцен с более простой геометрией такой разницы не наблюдается.

Скачать (778KB)
Метаданные
4. Рис. 3. CALBVH (вверху) / COLBVH (внизу). Средняя скорость трассировки лучей для различных вариантов трилетов, %, от самого быстрого в зависимости от различного типа и схемы расположения трилов в памяти. Поскольку измерения сделаны на мобильном GPU, наиболее эффективным оказался подход, в котором трилет целиком помещается в 64 байта (SuperTreeletAlignedMerged2).

Скачать (860KB)
Метаданные
5. Рис. 4. Предлагаемая 6-битная схема кодирования координат плоскостей. Регулярная сетка внутри опорной рамки показывает возможные положения плоскостей внутренних рамок. Синие точки отмечают минимум и максимум, сохраняемые с половинной точностью.

Скачать (2MB)
Метаданные
6. Рис. 5. Схематичное представление алгоритма сохранения вершин. Сверху – базовый алгоритм, снизу – модифицированный.

Скачать (568KB)
Метаданные
7. Рис. 6.1 Изображения тестовых сцен. Первое число (до ʽ/ʼ) для каждой сцены отображает количество уникальных треугольников, хранящихся в памяти, второе (после ʽ/ʼ) – количество видимых (инстанцированных) треугольников. Число после запятой – число инстансов. Далее характеристики сцен: (1) instanced_objects: 170K/62M т., 601 инст; (2) dragon: 871K/871K т., 1 инст. (3) bonsai: 650K/650K т./ 1инст; (4) sponza_c: 66K/66K т., 1 инст.

Скачать (5MB)
Метаданные
8. Рис. 6.2 Изображения тестовых сцен. Первое число (до ʽ/ʼ) для каждой сцены отображает количество уникальных треугольников, хранящихся в памяти, второе (после ʽ/ʼ) – количество видимых (инстанцированных) треугольников. Число после запятой – число инстансов. Далее характеристики сцен: (5) cry_spon- za_c: 244K/262K т., 17 инст; (6) cry_sponza: 244K/262K т., 281 инст. (7) hero: 28K/28K т., 4 инст; (8) human_sophi: 16.5K/16.5K т., 4 инст.

Скачать (8MB)
Метаданные
9. Рис. 7. Количество миллионов лучей в секунду на Adreno 660 (слева) и Mali-G57 (справа) при различных разрешениях на разных сценах.

Скачать (498KB)
Метаданные
10. Рис. 8. Количество миллионов лучей в секунду на Nvidia 2070 при различных разрешениях на разных сценах.

Скачать (275KB)
Метаданные
11. Рис. 9. Количество MRays/s на Adreno 660 при различных алгоритмах обхода на двух сценах.

Скачать (562KB)
Метаданные
12. Рис. 10. Количество MRays/s на Mali-G57 при различных алгоритмах обхода на двух сценах.

Скачать (672KB)
Метаданные
13. Рис. 11. Среднее число MRays/s на Adreno 660 при различных алгоритмах обхода на остальных сценах.

Скачать (1MB)
Метаданные
14. Рис. 12. Среднее число MRays/s на NV2070 при различных алгоритмах обхода на остальных сценах.

Скачать (782KB)
Метаданные
15. Рис. 13. Количество MRays/s на Mali-G57 при использовании одного большого ядра (WhittedRT) или раздельных ядер (WhittedRTSeparate) в двух различных реализациях обхода BVH4-дерева.

Скачать (681KB)
Метаданные
16. Рис. 14. Количество MRays/s на Nvidia 2070 при использовании одного большого ядра (WhittedRT) или раздельных ядер (WhittedRTSeparate) в двух различных реализациях обхода BVH4-дерева.

Скачать (706KB)
Метаданные
17. Рис. 15. Количество MRays/s на Adreno 660 при использовании одного большого ядра (WhittedRT) или раздельных ядер(WhittedRTSeparate) в двух различных реализациях обхода BVH4-дерева.

Скачать (307KB)
Метаданные
18. Рис. 16. Сравнение разработанного решения (BVH2Fat32, красный столбец) и [2] (Hippie, синий столбец) на видеокарте Nvidia 3070M в MRays/s.

Скачать (1MB)
Метаданные
19. Рис. 17. Сравнение времени рендеринга (первичная трассировка лучей) в ms для разработанного решения (BVH2Fat32, левая часть картинки) и (правая часть) на NV3070 RTX, 1400 × 1400. В табл. 3 данные в MRays/s.

Скачать (1MB)
Метаданные

© Российская академия наук, 2025