1. На главную
  2. Электронные версии
  3. Программирование
  4. № 3, 2023

Программирование, 2023, № 3, стр. 37-48

ИСПОЛЬЗОВАНИЕ МНОГОУРОВНЕВЫХ ХЭШ-ТАБЛИЦ ДЛЯ УСКОРЕНИЯ ПРОЦЕССА РЕНДЕРИНГА

Д. Д. Жданов a, *, А. И. Лысых a, **, Р. Р. Халимов a, ***, И. Е. Кинев a, ****, А. Д. Жданов a, *****

a Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
197101 Санкт-Петербург, Кронверкский пр., 49, Россия

* E-mail: ddzhdanov@mail.ru
** E-mail: lysykhai@ya.ru
*** E-mail: khalimov.ruslan@mail.ru
**** E-mail: igorkinevitmo@gmail.com
***** E-mail: andrew.gtx@gmail.com

Поступила в редакцию 10.01.2023
После доработки 18.01.2023
Принята к публикации 22.01.2023

Аннотация

Проведен анализ методов реалистичного рендеринга с точки зрения эффективности расчета яркостей каустического и вторичного освещений. В качестве основного подхода для реализации реалистичного рендеринга был выбран метод двунаправленной прогрессивной трассировки лучей с обратными фотонными картами. Проведен анализ основных причин, снижающих производительность данного метода. Показано, что главным фактором, снижающим его производительность, является медленный доступ к данным фотонных карт. Рассмотрены различные варианты построения ускоряющих пространственных структур, исследованы их преимущества и недостатки. В качестве основных подходов были выбраны регулярная пространственная решетка и бинарное kd-дерево. Пространственная решетка обеспечивает высокую скорость доступа к данным при низкой адаптивности разбиения фотонной карты. Kd-дерево обеспечивает высокую пространственную адаптивность разбиения карты при низкой скорости доступа к данным. Предложено комбинированное решение, объединяющее адаптивность kd-дерева с высокой скоростью доступа к данным пространственной решетки. Для этого регулярная решетка накладывается на kd-дерево, построенное по принципу пространственного деления области фотонов на геометрически равные половины. Для уменьшения объемов памяти было предложено, во-первых, использовать многоуровневые пространственные решетки, накладываемые на выбранные узлы kd-дерева, и, во-вторых, для уменьшения объема памяти ускоряющей структуры хранить пространственные решетки в виде хэш-таблиц. В результате был предложен и реализован новый тип пространственных ускоряющих структур, представляющих собой дерево хэш-таблиц. Для разработанной пространственной структуры были реализованы методы поиска ближайших фотонов, сферы интегрирования которых покрывают точку освещения, и методы поиска пересечения сегмента луча со сферами интегрирования фотонов. Разработанные программные решения были реализованы в программном комплексе Lumicept, и для ряда базовых сцен было произведено сравнение скорости работы предложенного метода с методом, основанным на бинарном дереве, имеющемся в Lumicept. Сравнение показало, что новый метод может повысить общую производительность процедуры рендеринга более чем на 40%.

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

  1. Фролов В.А., Волобой А.Г., Ершов С.В., Галактионов В.А. Современное состояние методов расчета глобальной освещенности в задачах реалистичной компьютерной графики // Труды Института системного программирования РАН. 2021. Т. 33. № 2. С. 7–48.

  2. Georgiev I., Krivanek J., Davidovic T., Slusallek P. Light Transport Simulation with Vertex Connection and Merging // ACM Transactions on Graphics. 2012. V. 31. № 6. P. 1–10.

  3. Veach E., Guibas L.J. Metropolis light transport, in: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques / SIGGRAPH ’97, ACM Press/Addison-Wesley Publishing Co., USA. 1997. P. 65–76. URL: https://doi. org/https://doi.org/10.1145/258734.258775. doi:. 258775.10.1145/258734.258775

  4. Wenzel J. Light Transport on Path-Space Manifolds, Ph.D. thesis. 2013.

  5. Kaplanyan A.S., Hanika J., Dachsbacher C. The natural-constraint representation of the path space for efficient light transport simulation // ACM Trans. Graph. 2014. V. 33. URL: https://doi.org/10.1145/ 2601097.2601108

  6. Bitterli B., Jakob W., Novák J., Jarosz W. Reversible jump metropolis light transport using inverse mappings, 2017. arXiv:1704.06835

  7. Gruson A., West R., Hachisuka T. Stratified Markov Chain Monte Carlo Light Transport // Computer Graphics Forum. 2020. https://doi.org/10.1111/cgf.13935

  8. Jensen H.W. Global illumination using photon maps / H.W. Jensen // Eurographics Workshop on Rendering techniques. Vienna: Springer, 1996. P. 21–30.

  9. Havran V., Herzog R., Seidel H.P. Final gathering via reverse photon mapping // Computer Graphics Forum. Oxford, UK and Boston, USA: Blackwell Publishing, 2005. V. 24. № 3. P. 323–332.

  10. Zhdanov A., Zhdanov D. The Backward Photon Mapping for the Realistic Image Rendering // Proc. 30th Conf. on Computer Graphics and Machine Vision (GraphiCon 2020), CEUR Workshop Proceedings. 2020. V. 2744. P. 1–12.

  11. Zhdanov A.D., Zhdanov D.D. Progressive backward photon mapping // Programming and Computer Software. 2021. V. 47. № 3. P. 185–193.

  12. Bentley J.L., Friedman J.H. Data structures for range searching // ACM Computing Surveys (CSUR). 1979. V. 11. № 4. P. 397–409.

  13. Toshiya Hachisuka, Henrik Wann Jensen. Parallel progressive photon mapping on GPUs / In ACM SIGGRAPH ASIA 2010 Sketches (SA '10). New York, NY, USA: Association for Computing Machinery, Article 54, 1. https://doi.org/10.1145/1899950.1900004

  14. Hunt W., Mark W.R., Stoll G. Fast kd-tree construction with an adaptive error-bounded heuristic // 2006 IEEE Symposium on Interactive Ray Tracing. IEEE, 2006. P. 81–88.

  15. Knoll Aaron. A survey of octree volume rendering methods.

  16. Fabianowski Bartosz, Dingliana J. Compact BVH Storage for Ray Tracing and Photon Mapping.

  17. Bradshaw Gareth, O’Sullivan Carol. Sphere-tree construction using dynamic medial axis approximation / In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation (SCA '02). New York, NY, USA, Association for Computing Machinery. 2002. P. 33–40. https://doi.org/10.1145/545261.545267

  18. Gino van den Bergen. Efficient collision detection of complex deformable models using AABB trees // J. Graph. Tools. 1997. V. 2. № 4. P. 1–13. https://doi.org/10.1080/10867651.1997.10487480

  19. Gottschalk S., Lin M.C., Manocha D. OBBTree: a hierarchical structure for rapid interference detection / In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '96). New York, NY, USA: Association for Computing Machinery, 1996. P. 171–180. https://doi.org/10.1145/237170.237244

  20. Martin Stich, Heiko Friedrich, Andreas Dietrich. Spatial splits in bounding volume hierarchies / In Proceedings of the Conference on High Performance Graphics 2009 (HPG '09). New York, NY, USA, Association for Computing Machinery. P. 7–13. https://doi.org/10.1145/1572769.1572771

  21. Wald Ingo, Günther Johannes, Slusallek Philipp, Cani Marie-Paule, Slater Mel. Balancing Considered Harmful - Faster Photon Mapping using the Voxel Volume Heuristic / The European Association for Computer Graphics 25th Annual Conference EUROGRAPHICS 2004. Blackwell, 2004. V. 23. P. 595–603.

  22. Халимов Р.Р., Жданов Д.Д., Жданов А.Д. Формирование эффективной пространственной структуры фотонных карт для ускорения процесса рендеринга // Труды Международной конференции по компьютерной графике и зрению “Графикон”. 2022. Т. 32. С. 110–123.

  23. Havran Vlastimil. Heuristic ray shooting algorithms. 2000.

  24. Hapala M., Havran V. Review: Kd-tree Traversal Algorithms for Ray Tracing // Computer Graphics Forum. V. 30. P. 199–213. https://doi.org/10.1111/j.1467-8659.2010.01844.x

  25. Foley T., Sugerman J. KD-tree acceleration structures for a GPU raytracer // In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware (HWWS '05). New York, NY, USA, Association for Computing Machinery. P. 15–22. https://doi.org/10.1145/1071866.1071869

  26. Lumicept Integra [Электронный ресурс]. URL: https://integra.jp/en/products/lumicept.

  27. Zhdanov A.D., Zhdanov D.D. The two-level semi-synchronous parallelization method for the caustic and indirect luminance calculation in realistic rendering // CEUR Workshop Proceedings. 2020. V. 2744. P. 1–12.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Программирование

Архивы выпусков Информация о журнале Отправить рукопись в журнал