PSVDAG: Compact Voxelized Representation of 3D Scenes Using Pointerless Sparse Voxel Directed Acyclic Graphs

Abstract

This paper deals with the issue of geometry representation of voxelized three-dimensional scenes using hierarchical data structures. These include pointerless Sparse Voxel Octrees that have no pointers on child nodes and allow a compact binary representation. However, if necessary, there is a possibility to reconstruct these pointers for rapid traversing. Sparse Voxel Directed Acyclic Graphs added 32-bit pointers to child nodes and merging of common subtrees, which can be considered lossless compression. By merging common subtrees, no decompression overhead occurs at the time of traversing. The hierarchical data structure proposed herein - the Pointerless Sparse Voxel Directed Acyclic Graph - incorporates the benefits of both - pointerless Sparse Voxel Octrees (by avoiding storing pointers on child nodes) and Sparse Voxel Directed Acyclic Graphs (by allowing the merging of common subtrees due the introduction of labels and callers). The proposed data structure supports the quick and easy reconstruction of pointers by introducing the Active Child Node Count. It also potentially allows Child Node Mask compression of its nodes. This paper presents the proposed data structure and its binary-level encoding in detail. It compares the effectiveness of the representation of voxelized three-dimensional scenes (originally represented in OBJ format) in the proposed data structure with the data structures mentioned above. It also summarizes statistical data providing a more detailed description of the various parameters of the data structure for different scenes stored in multiple resolutions.