USING MULTILEVEL HASH TABLES TO SPEED UP RENDERING

D. D. ZHDANOV; Жданов Д. Д.; A. I. LYSYKH; Лысых А. И.; R. R. KHALIMOV; Халимов Р. Р.; I. E. KINEV; Кинев И. Е.; A. D. ZHDANOV; Жданов А. Д.

doi:10.31857/S013234742303007X

USING MULTILEVEL HASH TABLES TO SPEED UP RENDERING

Authors: ZHDANOV D.D.¹, LYSYKH A.I.¹, KHALIMOV R.R.¹, KINEV I.E.¹, ZHDANOV A.D.¹
Affiliations:
1. St. Petersburg National Research University of Information Technologies, Mechanics, and Optics (ITMO University)
Issue: No 3 (2023)
Pages: 37-48
Section: COMPUTER GRAFICS AND VISUALIZATION
URL: https://rjmseer.com/0132-3474/article/view/675747
DOI: https://doi.org/10.31857/S013234742303007X
EDN: https://elibrary.ru/DESNPJ
ID: 675747

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

Abstract
About the authors
References
Supplementary files
Statistics

Abstract

In this paper, we analyze realistic rendering methods in terms of their efficiency in calculating caustic and indirect illumination. As the basic approach to realistic rendering, we choose bidirectional progressive ray tracing with backward photon maps. The main factors that reduce the efficiency of this method are analyzed. It is shown that the main factor that affects its performance is slow access to photon map data. Different techniques for construction of spatial acceleration structures are considered, their advantages and disadvantages are investigated. As the main approaches, we select the regular spatial grid and binary kd tree. The spatial grid provides high-speed access to photon data at low adaptability of photon map partitioning. The kd tree is characterized by high spatial adaptability of photon map partitioning but slow access to photon data. We propose a combined solution that takes advantage of the adaptability of the kd tree and the fast data access of the spatial grid. For this purpose, the regular grid is superimposed on the kd tree constructed based on the principle of space partitioning of a photon region into geometrically identical halves. To reduce memory consumption, we propose, first, to use multilevel spatial grids superimposed on the selected nodes of the kd tree and, second, to store spatial grids in the form of hash tables in order to reduce the size of the acceleration structure. Thus, a spatial acceleration structure of a new type—a tree of hash tables—is proposed and implemented. For the spatial structure developed, we implement methods for finding the nearest photons the integration spheres of which cover the illumination point, as well as methods for finding the intersection between a ray segment and photon integration spheres. The proposed software solutions are implemented in the Lumicept software package; for some scenes, the proposed method is compared with the Lumicept method based on the binary tree. The comparison shows that our method can increase the overall speed of the rendering process by more than 40%.

References

Фролов В.А., Волобой А.Г., Ершов С.В., Галактионов В.А. Современное состояние методов расчета глобальной освещенности в задачах реалистичной компьютерной графики // Труды Института системного программирования РАН. 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.