loading page

Terrain Trees Library: a tool for efficient and scalable terrain mesh processing
  • +1
  • Yunting Song,
  • Fellegara Riccardo,
  • Federico Iuricich,
  • Leila De Floriani
Yunting Song
University of Maryland College Park

Corresponding Author:[email protected]

Author Profile
Fellegara Riccardo
German Aerospace Center DLR Braunschweig
Author Profile
Federico Iuricich
Clemson University
Author Profile
Leila De Floriani
University of Maryland College Park
Author Profile


In light of the increased availability of massive point cloud data, acquired by advanced remote sensing techniques, software tools for their efficient representation and processing are needed. Triangulated Irregular Networks (TINs) are an effective way to represent point clouds without the need to interpolate them into raster-based terrain models. However, GISs tools have limited support for TINs due to large storage costs. For this reason, 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 hierarchical 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 edge and triangle slopes, roughness, curvature. It also contains modules for extracting topological structures, like critical point, critical net, watershed segmentation, based on the discrete Morse gradient, and a technique for multivariate data visualization, which enables the analysis of multiple scalar fields defined on the same terrain. To evaluate the effectiveness and scalability of TTL, we compared it against the most compact state-of-the-art data structure for TINs, the IA data structure. When encoded by Terrain trees, a TIN requires 36% less storage than when encoded by the IA data structure. Beyond this storage reduction, Terrain trees also show better performance than the IA data structure in most terrain analysis operations. This speedup is obtained since Terrain trees enable 57% to 72% faster extraction of the triangles incident in a vertex. Extracting the triangles incident in vertices as well as the adjacent vertices on the mesh is a key task in most terrain feature extraction operations on a TIN. Using Terrain trees, we achieved 36% to 55% less time consumption computing morphological features and 20% less time consumption computing the discrete Morse gradient than using the IA data structure.