Large Scale 3D Modelling via Sparse Volumes

Kurzfassung

Spatial 3D reconstruction received enormous interest in the last years. However, the goal to store, to process and to visualize the acquired data is still very challenging. Discrete voxel based representation techniques became state of the art in todays research approaches. These allow summary of redundant measurements and fast coordinate based access to the data leading to efficient volume computations. Unfortunately, representing the 3D space with a dense voxel grid requires huge amount of storage. Representing a volume of 100 x 100 x 100m3 with resolution of 1cm with a dense grid of 32-bit floating point values, results in a 3:8 TB storage requirement. This motivated many state of the art approaches to apply octrees to build sparse 3D volumes, where only the occupied voxels are stored. This however, increases the data access complexity from O(1) to O(d) with d as the depth of the octree, growing logarithmically when the volume or the resolution of the model is increasing. In this work we propose to combine octrees with hash tables leading to sparse voxel representation well suited for efficient storage and fast data access common in 3D modelling computations. The hash table is used to access grid cells, which further contain an octree in itself. Since the internal octrees are constructed of much smaller depth e.g. di = 1, this dramatically decreases the access time complexity to O(di). For a standard octree with depth d = 16 , this leads to a speed-up of factor 16. An additional advantage of the hash table approach is that the volume size is not limited and is suited for modelling huge environments.