EFFICIENT REPRESENTATION AND ANALYSIS OF LARGE MESHES USING APACHE SPARK

Abstract

Large triangle and tetrahedral meshes derived from remote sensing data, such as LiDAR (Light Detection and Ranging) point clouds, provide faithful representations of surfaces and volumetric domains, but their practical use at scale is limited by the high memory and computational costs of processing and storing mesh connectivity. These limitations are especially severe for modern datasets containing billions of points, where conventional shared-memory data structures and single-machine algorithms are no longer sufficient. Although distributed computing offers a natural way to address these challenges, existing solutions often require substantial redesign of data structures and algorithms to manage partitioning, communication, and synchronization efficiently. This dissertation investigates how Apache Spark can serve as a high-level distributed environment for the scalable representation and topological analysis of very large meshes. It introduces compact distributed data representations for large meshes, develops scalable algorithms for topological analysis, and demonstrates the practical value of the framework through a real-world application to sea-ice pressure ridge extraction. To support efficient distributed processing, this dissertation proposes two compact representations, Morse-Spark for triangle meshes and Tetra-Spark for tetrahedral meshes. Both frameworks adopt a minimal encoding strategy that stores only vertices and top-dimensional simplices in Spark DataFrames, while deriving connectivity relations on demand. A key aspect of this design is the precomputation of the relation between vertices and top simplices, which enables various connectivity relations to be computed locally. Experimental results show substantial performance gains over naive Spark-based approaches, with strong scalability on large triangle and tetrahedral meshes. Building on this representation, the dissertation develops distributed algorithms for topological analysis based on discrete Morse theory. For triangle meshes, the proposed methods compute the Forman gradient and extract Morse manifolds through auxiliary graph structures derived from the gradient. The same design principles are then extended to tetrahedral meshes for the analysis of 3D scalar fields. By minimizing inter-node communication via local operations, the framework supports large-scale topological analysis that would be impractical with existing single-machine approaches. The practical value of the framework is demonstrated through a case study on extracting sea-ice pressure ridges from large airborne LiDAR point clouds. The dissertation develops a workflow that includes point-cloud preprocessing, Triangulated Irregular Network (TIN) construction, surface-network computation, topological simplification, and ridge extraction. By identifying ridges as topological structures on the triangulated ice surface, the method preserves their spatial connectivity and provides a more structural representation than profile-based or raster-based approaches. The extracted ridges show good agreement with both ICESat-2 ridge detections and a single-machine reference method.