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

Обложка

Цитировать

Полный текст

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

Аннотация

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

Об авторах

Л. М. Смирнов

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

Email: lyovasmirnov@gmail.com
119991 Москва, ГСП-1, Ленинские горы, 119, Россия

В. А. Фролов

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

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

Ю. А. Крячко

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

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

А. Г. Волобой

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

Email: voloboy@gin.keldysh.ru
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
Скачать

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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».