Conference material: "Proceedings of the International Conference on Computer Graphics and Vision “Graphicon” (19-21 September 2023, Moscow)"
Authors:Lysykh A.I., Kinev I.E., Zhdanov D.D.
Optimization of Multilevel Spatial Partitioning Accelerating Structure of Hash Tables and Kd-tree
Abstract:
This research conducts an in-depth analysis of existing types of spatial partitioning acceleration structures. It investigates the properties and characteristics of the original combined spatial partitioning structure, based on hash tables and kd-trees. Three types of use cases for this structure are identified: dynamic, balanced, and static. Methods for optimizing the structure construction and cell search algorithms are proposed. For each of the three usage scenarios, algorithms for determining the size and placement levels of hash tables are introduced. An analysis of the optimal parameter values for these algorithms in each usage case is performed. Furthermore, a comparative efficiency analysis of the modified structure against the original combined structure and kd-tree is carried out. The comparison reveals that the resulting structure significantly enhances cell search efficiency for the considered types of structure usage.
Keywords:
Spatial partitioning structures, optimization, rendering, photon maps, ray tracing
