Terrain Trees Library: a tool for efficient and scalable terrain mesh processing

Keywords: terrain modeling, Triangulated Irregular Networks (TINs), spatial indexes, terrain analysis, topological methods
Session Type: Virtual Poster Abstract
Day: Friday
Session Start / End Time: 2/25/2022 08:00 AM (Eastern Time (US & Canada)) - 2/25/2022 09:20 AM (Eastern Time (US & Canada))
Room: Virtual 38

Abstract

In light of the increased availability of massive point cloud data, acquired by remote sensing techniques, we need software tools for their efficient representation and processing. Triangulated Irregular Networks (TINs) can be generated from point clouds without being interpolated into raster-based terrain models, but current tools cannot handle massive TINs due to the large storage costs.

To provide a solution, we present the Terrain Trees Library (TTL), a library for terrain analysis based on a new scalable data structure named Terrain trees. A Terrain tree relies on a hierarchical spatial index where each leaf block encodes the minimum amount of connectivity information for the TIN. Connectivity relations among the elements of the TIN are extracted locally within each leaf block at run-time and discarded when no longer needed. Moreover, the domain decomposition makes the library well-suited for parallel processing.

TTL contains a kernel for connectivity and spatial queries, and modules for extracting morphological features, including slope, roughness, and curvature. It also contains modules for extracting topological structures, like critical point, critical net, watershed segmentation, based on the discrete Morse gradient, and the computation of a multifield correlation measure, which integrates multiple scalar fields defined on the same terrain.

We compared TTL against the most compact state-of-the-art data structure for TINs, the IA data structure. When encoded by Terrain trees, the same TIN takes 36% less storage than when encoded by the IA data structure. Moreover, TTL shows better performance than the IA data structure in most terrain analysis operations.