Recent advances in range measurement devices have opened up new opportunities and challenges for fast 3D modeling of large scale outdoor environments. Applications of such technologies include virtual walk and fly through, urban planning, disaster management, object recognition, training, and simulations. We note that the scan line ordering of terrestrial LIDAR range data is conducive to stream processing, and we show how a fast surface reconstruction algorithm for this data generates the locality necessary to be efficiently represented with a streaming mesh format. We show algorithms for converting such meshes to a streaming mesh format, and for efficiently computing statistics about connected components of these meshes with a memory use that grows linearly as only 0.1% of the number of triangles in the mesh, plus a small constant overhead. Finally, we show how to exploit the locality of streaming meshes to efficiently merge terrestrial meshes with data from airborne sensors. Our merge algorithm requires only a tiny, linearly-increasing amount of additional memory as the amount of terrestrial data increases. We demonstrate the effectiveness and generality of our results on data sets obtained by three different acquisition systems, including a merge of a mesh generated from 129 million airborne points with a terrestrial mesh with over 200 million triangles generated from 570 million terrestrial range points. The algorithm scales linearly in time with the amount of data and is able to merge this large data set in 2.5 hours.





Download Full History