Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Hierarchical data structures in rendering scenes containing a massive number of light sources

, ,

DOI: http://dx.doi.org/10.15439/2022F92

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 535544 ()

Full text

Abstract. In order to speed up the process of rendering scenes containing many light sources, spatial data structures are used, which allow the number of lights processed for each pixel to be reduced during lighting computation. Examples of algorithms using such data structures are clustered shading and hybrid lighting. Alongside the rendering time, it is important to consider memory consumption resulting from processing a large number of lights. This paper presents a novel modification of the hybrid lighting algorithm using an octree that allows for a significant reduction in the amount of memory required to store the data structure. The proposed modification uses an octree to store the information about the rendered space. Detailed analysis of the proposed algorithm, and numerical results obtained for various 3D scenes, as well as different input data, all prove that the proposed method significantly reduces the memory required to store lists of lights used by the algorithm.


  1. M. McGuire, “Computer graphics archive,” July 2017. [Online]. Available: https://casual-effects.com/data
  2. A. Lauritzen, “Deferred rendering for current and future rendering pipelines,” SIGGRAPH Course: Beyond Programmable Shading, pp. 1–34, 2010.
  3. O. Olsson, E. Persson, and M. Billeter, “Real-time many-light management and shadows with clustered shading,” in ACM SIGGRAPH 2015 Courses, 2015, pp. 1–398.
  4. O. Olsson and U. Assarsson, “Tiled shading,” Journal of Graphics, vol. GPU, pp. 235–251, 11 2011.
  5. T. Harada, “A 2.5 d culling for forward+,” in SIGGRAPH Asia 2012 Technical Briefs, 2012, pp. 1–4.
  6. O. Olsson, M. Billeter, and U. Assarsson, “Clustered deferred and forward shading,” in Proceedings of the Fourth ACM SIGGRAPH/Euro-graphics conference on High-Performance Graphics. Citeseer, 2012, pp. 87–96.
  7. J. Archer, G. Leach, P. Knowles, and R. van Schyndel, “Hybrid lighting for faster rendering of scenes with many lights,” The Visual Computer, vol. 34, no. 6, pp. 853–862, 2018.
  8. J. Dupuy, J.-C. Iehl, and P. Poulin, Quadtrees on the GPU, 10 2018, pp. 211–222.
  9. D. Wehr and R. Radkowski, “Parallel kd-tree construction on the gpu with an adaptive split and sort strategy,” International Journal of Parallel Programming, vol. 46, no. 6, pp. 1139–1156, 2018.
  10. J. R. Jørgensen, K. Scheel, and I. Assent, “Gpu-inscy: A gpu-parallel algorithm and tree structure for efficient density-based subspace clustering.” in EDBT, 2021, pp. 25–36.
  11. C. Crassin, F. Neyret, M. Sainz, S. Green, and E. Eisemann, “Interactive indirect illumination using voxel cone tracing,” in Computer Graphics Forum, vol. 30, no. 7. Wiley Online Library, 2011, pp. 1921–1930.
  12. Y. O’Donnell and M. G. Chajdas, “Tiled light trees,” in Proceedings of the 21st ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 2017, pp. 1–7.
  13. Microsoft, “Direct3d 11 website,” 2022. [Online]. Available: https://docs.microsoft.com/en-us/windows/win32/direct3d11/atoc-dx-graphics-direct3d-11
  14. NVIDIA Corporation, “Cuda toolkit website,” 2022. [Online]. Available: https://developer.nvidia.com/cuda-toolkit
  15. J. Burkardt, “The truncated normal distribution,” Department of Scientific Computing Website, Florida State University, pp. 1–35, 2014.
  16. O. Olsson, E. Sintorn, V. Kämpe, M. Billeter, and U. Assarsson, “Efficient virtual shadow maps for many lights,” in Proceedings of the 18th Meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ser. I3D ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 87–96. [Online]. Available: https://doi.org/10.1145/2556700.2556701
  17. K. Kluczek, “Quality metric for shadow rendering,” in 2016 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 2016, pp. 791–796.