Efficient terrain analysis of point cloud datasets on a decomposition-based data representation

Abstract

With a modern focus on LiDAR (Light Detection and Ranging) technologies, which generate precise three-dimensional measurements from the Earth’s surface, the amount of spatial data in the form of massive point clouds has dramatically increased. This dissertation addresses the problem of direct terrain analysis using large LiDAR point clouds without interpolating them into gridded Digital Elevation Models (DEMs). Unlike gridded DEMs, Triangulated Irregular Networks (TINs) maintain full information of point clouds and can represent terrains with variable resolution. When using TINs to represent large terrains, the major challenges are the high storage and time costs. To address these, this dissertation introduces a family of decomposition-based data structures, named Terrain trees family, for encoding TINs. A Terrain tree employs a nested subdivision strategy, partitioning the domain of the triangle mesh into several leaf blocks. Each leaf block contains the minimum amount of information required for extracting all connectivity relations that are needed for TIN navigation and terrain analysis. A new library for terrain analysis, the Terrain trees library (TTL), is developed based on the Terrain trees. Performance evaluation of TTL shows that a Terrain tree can encode the same terrain with ~36% less storagethan the state-of-art, compact data structure while maintaining good computing performance in extracting connectivity relations. Despite the highly efficient data structure, managing large TINs on local machines remains challenging, particularly for complex analyses or simulations. Mesh simplification methods are commonly applied to reduce TIN sizes to enable downstream processing. However, these simplification methods can modify the topology of the underlying terrain in an uncontrolled manner, which affects the results of terrain analysis applications. To address this issue, a topology-aware mesh simplification method based on Terrain trees is proposed. A parallel version of this simplification method is also developed, which simplifies different leaf blocks at the same time using a shared-memory implementation. A leaf-locking strategy is employed to avoid conflicts among leaf blocks during parallel computing. TTL and the topology-aware mesh simplification methods on Terrain trees effectively lower the memory and time requirements for terrain analysis on TINs. This dissertation demonstrates the effectiveness of TIN-based models in real-world applications using sea ice topography as an example. Studying sea ice topography is crucial as it enhances our ability to monitor sea ice volume changes and comprehend sea ice processes. Besides, timely and precise assessments of sea ice dynamics are critical in the context of climate change and its impacts on polar regions. TIN-based surface models are employed to represent the sea ice surface, and methods are developed for extracting important sea ice topographic features, such as density, regions without measurements, roughness, and pressure ridge structures, from TINs.