Incremental Division of Very Large Point Clouds for Scalable 3D Surface Reconstruction

The recent progress in Structure from Motion and Multi-View Stereo as well as the always rising number of high resolution images lead to ever larger 3D point clouds. Unfortunately, due to the large amount of memory and processing power needed, there are no suitable means for manipulating these massive amounts of data as a whole, such as fusion by 3D surface reconstruction methods. In this paper we, therefore, present an algorithm for division of very large 3D point clouds into smaller subsets allowing for a parallel 3D reconstruction of many suitably small parts. Within our space division algorithm, octrees are built representing the divided space. To limit the maximum size of the underlying data structure, we present an incremental extension of the algorithm which renders a division of billions of 3D points possible and speeds up the processing on multi-core systems. As the proposed space division does not guarantee a density-based decomposition, we show the limitations of kd-trees as an alternative data structure. Space division is especially important for volumetric 3D reconstruction, as the latter has a high memory requirement. To this end, we finally discuss the adaptability of the space division to existing surface reconstruction methods to achieve scalable 3D reconstruction and show examples on existing and novel datasets which demonstrate the potential of the incremental space division algorithm.