ИСПОЛЬЗОВАНИЕ МНОГОУРОВНЕВЫХ ХЭШ-ТАБЛИЦ ДЛЯ УСКОРЕНИЯ ПРОЦЕССА РЕНДЕРИНГА
- Авторы: Жданов Д.Д.1, Лысых А.И.1, Халимов Р.Р.1, Кинев И.Е.1, Жданов А.Д.1
-
Учреждения:
- Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
- Выпуск: № 3 (2023)
- Страницы: 37-48
- Раздел: КОМПЬЮТЕРНАЯ ГРАФИКА И ВИЗУАЛИЗАЦИЯ
- URL: https://journals.rcsi.science/0132-3474/article/view/137625
- DOI: https://doi.org/10.31857/S013234742303007X
- EDN: https://elibrary.ru/DESNPJ
- ID: 137625
Цитировать
Аннотация
Проведен анализ методов реалистичного рендеринга с точки зрения эффективности расчета яркостей каустического и вторичного освещений. В качестве основного подхода для реализации реалистичного рендеринга был выбран метод двунаправленной прогрессивной трассировки лучей с обратными фотонными картами. Проведен анализ основных причин, снижающих производительность данного метода. Показано, что главным фактором, снижающим его производительность, является медленный доступ к данным фотонных карт. Рассмотрены различные варианты построения ускоряющих пространственных структур, исследованы их преимущества и недостатки. В качестве основных подходов были выбраны регулярная пространственная решетка и бинарное kd-дерево. Пространственная решетка обеспечивает высокую скорость доступа к данным при низкой адаптивности разбиения фотонной карты. Kd-дерево обеспечивает высокую пространственную адаптивность разбиения карты при низкой скорости доступа к данным. Предложено комбинированное решение, объединяющее адаптивность kd-дерева с высокой скоростью доступа к данным пространственной решетки. Для этого регулярная решетка накладывается на kd-дерево, построенное по принципу пространственного деления области фотонов на геометрически равные половины. Для уменьшения объемов памяти было предложено, во-первых, использовать многоуровневые пространственные решетки, накладываемые на выбранные узлы kd-дерева, и, во-вторых, для уменьшения объема памяти ускоряющей структуры хранить пространственные решетки в виде хэш-таблиц. В результате был предложен и реализован новый тип пространственных ускоряющих структур, представляющих собой дерево хэш-таблиц. Для разработанной пространственной структуры были реализованы методы поиска ближайших фотонов, сферы интегрирования которых покрывают точку освещения, и методы поиска пересечения сегмента луча со сферами интегрирования фотонов. Разработанные программные решения были реализованы в программном комплексе Lumicept, и для ряда базовых сцен было произведено сравнение скорости работы предложенного метода с методом, основанным на бинарном дереве, имеющемся в Lumicept. Сравнение показало, что новый метод может повысить общую производительность процедуры рендеринга более чем на 40%.
Об авторах
Д. Д. Жданов
Санкт-Петербургский национальный исследовательский университет информационных технологий,механики и оптики
Email: ddzhdanov@mail.ru
Россия, 197101, Санкт-Петербург, Кронверкский пр., 49
А. И. Лысых
Санкт-Петербургский национальный исследовательский университет информационных технологий,механики и оптики
Email: lysykhai@ya.ru
Россия, 197101, Санкт-Петербург, Кронверкский пр., 49
Р. Р. Халимов
Санкт-Петербургский национальный исследовательский университет информационных технологий,механики и оптики
Email: khalimov.ruslan@mail.ru
Россия, 197101, Санкт-Петербург, Кронверкский пр., 49
И. Е. Кинев
Санкт-Петербургский национальный исследовательский университет информационных технологий,механики и оптики
Email: igorkinevitmo@gmail.com
Россия, 197101, Санкт-Петербург, Кронверкский пр., 49
А. Д. Жданов
Санкт-Петербургский национальный исследовательский университет информационных технологий,механики и оптики
Автор, ответственный за переписку.
Email: andrew.gtx@gmail.com
Россия, 197101, Санкт-Петербург, Кронверкский пр., 49
Список литературы
- Фролов В.А., Волобой А.Г., Ершов С.В., Галактионов В.А. Современное состояние методов расчета глобальной освещенности в задачах реалистичной компьютерной графики // Труды Института системного программирования РАН. 2021. Т. 33. № 2. С. 7–48.
- 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.
- 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
- Wenzel J. Light Transport on Path-Space Manifolds, Ph.D. thesis. 2013.
- 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
- Bitterli B., Jakob W., Novák J., Jarosz W. Reversible jump metropolis light transport using inverse mappings, 2017. arXiv:1704.06835
- Gruson A., West R., Hachisuka T. Stratified Markov Chain Monte Carlo Light Transport // Computer Graphics Forum. 2020. https://doi.org/10.1111/cgf.13935
- Jensen H.W. Global illumination using photon maps / H.W. Jensen // Eurographics Workshop on Rendering techniques. Vienna: Springer, 1996. P. 21–30.
- 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.
- 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.
- Zhdanov A.D., Zhdanov D.D. Progressive backward photon mapping // Programming and Computer Software. 2021. V. 47. № 3. P. 185–193.
- Bentley J.L., Friedman J.H. Data structures for range searching // ACM Computing Surveys (CSUR). 1979. V. 11. № 4. P. 397–409.
- 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
- 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.
- Knoll Aaron. A survey of octree volume rendering methods.
- Fabianowski Bartosz, Dingliana J. Compact BVH Storage for Ray Tracing and Photon Mapping.
- 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
- 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
- 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
- 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
- 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.
- Халимов Р.Р., Жданов Д.Д., Жданов А.Д. Формирование эффективной пространственной структуры фотонных карт для ускорения процесса рендеринга // Труды Международной конференции по компьютерной графике и зрению “Графикон”. 2022. Т. 32. С. 110–123.
- Havran Vlastimil. Heuristic ray shooting algorithms. 2000.
- 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
- 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
- Lumicept Integra [Электронный ресурс]. URL: https://integra.jp/en/products/lumicept.
- 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.