Modeling and analysis of very large terrains reconstructed from LiDAR point clouds

Available software tools for terrain reconstruction and analysis from LiDAR (Light Detection and Ranging) data contain a variety of algorithms for processing such data, which almost always require converting the original point cloud into a raster model. This conversion can seriously affect data analysis, resulting in loss of information, or in raster images being too big to be processed on a local machine. Our solution is dealing directly with the scattered point clouds, and, thus, an unstructured triangle mesh connecting the points needs to be built, encoded and processed for data analysis. Existing tools which work on triangle meshes generated from LiDAR data can only handle triangle meshes of limited size. The lack of scalable data structures for triangle meshes greatly limited their applicability to very large point clouds currently available, which can vary from 0.2 to 60 billion points. In our research, we have developed a family of new data structures, the Terrain trees, for big triangle meshes, based on the Stellar decomposition model, and we have demonstrated their efficiency and effectiveness for spatial and connectivity queries, and for morphological analysis of very large triangulated terrains on commodity hardware. Our representations use spatial indexes to efficiently generate local application-dependent combinatorial data structures at runtime, and, thus, they are extremely compact and well-suited for distributed computation.