Efficient Randomized Hierarchy Construction for Interactive Visualization of Large Scale Point Clouds

Point cloud is widely used in various applications like 3D geographical information system (GIS), cultural heritage preservation, urban planning, etc. Most of these applications require interactive visualization of massive point cloud, which is challenging since their sizes are usually very large. This paper presents a method to construct a hierarchical data structure for point cloud data organization and real-time rendering, with an emphasis on speeding up the construction processing. The overall pipeline consists of the following three steps: first, the spatial extent of the whole dataset is divided into nested blocks; second, data in each block is reorganized using a octree based on random subsampling in a parallel fashion; finally, octree of all blocks are merged into a consistent hierarchy. The effectiveness and efficiency of the above approach was demonstrated by applying it to a set of point clouds of varying sizes reconstructed using photogrammetry pipeline.