James Andrews

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-70

May 19, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-70.pdf

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.

Advisors: Avideh Zakhor

---

BibTeX citation:

@mastersthesis{Andrews:EECS-2009-70,
    Author= {Andrews, James},
    Title= {Merging Surface Reconstructions of Terrestrial and Airborne LIDAR Range Data},
    School= {EECS Department, University of California, Berkeley},
    Year= {2009},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-70.html},
    Number= {UCB/EECS-2009-70},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Andrews, James 
%T Merging Surface Reconstructions of Terrestrial and Airborne LIDAR Range Data
%I EECS Department, University of California, Berkeley
%D 2009
%8 May 19
%@ UCB/EECS-2009-70
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-70.html
%F Andrews:EECS-2009-70