Spatio-Temporal Hierarchical Data Structure Based on Sparse Voxel Octrees for Representation of the Geometry of Time-Variable Three-Dimensional Scenes

Abstract

The paper deals with the problematics of representation of the geometry of three-dimensional scenes in computer graphics using domain-specific hierarchical data structures based on octant trees or directed acyclic graphs as the means of space saving binary representation of this information. Several hierarchical data structures were introduced in this field in past decades. In this paper we are moving this problematic to the field of the representation of three-dimensional scenes which are rather dynamic in time, so their geometry is changing on the regular basis. We are investigating the influence of this time-variability on the size of the related hierarchical data structure on binary level. We are comparing the approach in which each time step is considered as the stand-alone static three-dimensional scene and therefore is represented by its own hierarchical data structure with the approach when this time-variable scene is considered as the four dimensional space and spatio-temporal sparse voxel octree hierarchical data structure is used for the representation of the geometry of this scene. We tested both approaches on three different scenes which were obtained by voxelization into two different resolutions of polygonal surface models represented originally as the mesh of triangles in Wavefront Object file format. Results of the tests show that spatio-temporal sparse voxel octree is better solution, when we obtained from 1.73 to 2.08 more compact binary representation, in comparison to the solution when time frames were encoded separately as the set of sparse voxel octrees.

Keywords

• lossless data compression
• voxelized spatio-temporal three-dimensional scenes
• geometry of the scene
• hierarchical data structures
• sparse voxel octrees