Terrain topology plays an important role in simulations and segmentation. A widely used terrain representation is the Triangulated Irregular Network (TIN). However, topological analysis on TINs is challenging due to high time and memory requirements, which limit the size of the terrain that can be analyzed. We address this problem by proposing a novel framework for efficient and scalable analysis of large TINs based on Morse theory using Apache Spark. The proposed framework, named Morse–Spark, is based on a data structure for encoding the minimal information of a triangle mesh. Morse–Spark provides optimized methods for the local extraction of many connectivity relations, beginning with the global retrieval of the Vertex–Triangle relation. These relations serve as the foundation for computing terrain morphology through integrated, scalable algorithms. To evaluate the effectiveness and scalability of such a framework, we compare Morse–Spark against a vanilla Spark implementation, a MPI-supported Topology Toolkit (MPI-TTK) implementation, and three well-established software libraries for the topological analysis of TINs. Our experimental evaluation with real-world TINs shows that Morse–Spark can effectively handle datasets around 13 times larger than those processed by state-of-the-art tools for distributed computing (e.g. MPI-TTK).

Understanding the complex topography of polar sea ice is essential for assessing its impacts on sea ice processes. Recently, large volumes of high-resolution Light Detection and Ranging (LiDAR) altimeter data covering extensive polar regions became available. Current methods for extracting topographic features either rely on along-track elevation profiles limited to one dimension, as it is the case with ICESat-2 data, or convert point clouds into a raster grid. In our work, we model the ice surface as a Triangulated Irregular Network (TIN) connecting the original data points, and we focus on extracting pressure ridges from TINs. Pressure ridges are important factors, for instance, in sea ice navigability analysis and atmosphere-ice-momentum transfer models. We present a technique for extracting the structure of pressure ridges based on combinatorial topology, specifically discrete Morse theory. We show our results by using LiDAR point clouds collected from the OIB Airborne Topographic Mapper (ATM). The extracted ridges are compared with those obtained from one-dimensional profiles extracted from ICESat-2 data in the same region, showing that the proposed strategy provides information that cannot be derived from one-dimensional profiles alone.

The scale-space method is a well-established framework that constructs a hierarchical representation of an input signal and facilitates coarse-to-fine visual reasoning. Considering the terrain elevation function as the input signal, the scale-space method can identify and track significant topographic features across different scales. The number of scales a feature persists, called its life span, indicates the importance of that feature. In this way, important topographic features of a landscape can be selected, which are useful for many applications, including cartography, nautical charting, and land-use planning. The scale-space methods developed for terrain data use gridded Digital Elevation Models (DEMs) to represent the terrain. However, gridded DEMs lack the flexibility to adapt to the irregular distribution of input data and the varied topological complexity of different regions. Instead, Triangulated Irregular Networks (TINs) can be directly generated from irregularly distributed point clouds and accurately preserve important features. In this work, we introduce a novel scale-space analysis pipeline for TINs, addressing the multiple challenges in extending grid-based scale-space methods to TINs. Our pipeline can efficiently identify and track topologically important features on TINs. Moreover, it is capable of analyzing terrains with irregular boundaries, which poses challenges for grid-based methods. Comprehensive experiments show that, compared to grid-based methods, our TIN-based pipeline is more efficient, accurate, and has better resolution robustness.

A common first step in the terrain processing pipeline of large Triangulated Irregular Networks (TINs) is simplifying the TIN to make it manageable for further processing. The major problem with TIN simplification algorithms is that they create or remove critical points in an uncontrolled way. Topology-aware operators have been defined to solve this issue by coarsening a TIN without affecting the topology of its underlying terrain, i.e., without modifying critical simplices describing pits, saddles, peaks, and their connectivity. While effective, existing algorithms are sequential in nature and are not scalable enough to perform well with large terrains on multicore systems. Here, we consider the problem of topology-aware simplification of very large meshes. We define a topology-aware simplification algorithm on a compact and distributed data structure for triangle meshes, namely the Terrain trees. Terrain trees reduce both the memory and time requirements of the simplification procedure by adopting a batched processing strategy of the mesh elements. Furthermore, we define a new parallel topology-aware simplification algorithm that takes advantage of the spatial domain decomposition at the basis of Terrain trees. Scalability and efficiency are experimentally demonstrated on real-world TINs originated from topographic and bathymetric LiDAR data. Our experiments show that topology-aware simplification on Terrain trees uses 40% less memory and half the time than the same approach implemented on the most compact and efficient connectivity-based data structure for TINs. Beyond that, our parallel algorithm on the Terrain trees reaches a 12x speedup when using 20 threads.

Light Detection and Ranging (LiDAR) sensors generate dense point clouds that can be used to map forest structures at a high spatial resolution level. In this work, we consider the problem of identifying individual trees in a LiDAR point cloud. Existing techniques generally require intense parameter tuning and user interactions. Our goal is defining an automatic approach capable of providing robust results with minimal user interactions.

Computing with trajectories has become an important and practical research topic. In many scenarios, the goal is to find similar trajectories. The Fréchet distance is a very promising metric for measuring trajectory similarity and yet limited in practical applications due to its expensive computing complexity. In this paper, we demonstrate an efcicient approach to retrieve similar trajectories using the Fréchet distance. Essentially, the proposed method builds up a set of R-trees for indexing trajectories and thereby enables multi-level of positive and negative filtering to speed up the similarity queries. For answering 5,000 queries on a dataset of 20,000 trajectories, the experimental results show that the proposed method achieves significant speedups at certain filtering levels while maintaining very high precision and recall in retrieving similar trajectories.

Terrain trees are a new in-core family of spatial indexes for the representation and analysis of Triangulated Irregular Networks (TINs). Terrain trees combine a minimal encoding of the connectivity of the underlying triangle mesh with a hierarchical spatial index, implicitly representing the topological relations among vertices, edges and triangles. Topological relations are extracted locally within each leaf block of the hierarchal index at runtime, based on specific application needs. We have developed a tool based on Terrain trees for terrain analysis, which includes state-of-the-art estimators for slope and curvature, and for the extraction of critical points, as well as algorithms for topology-based terrain segmentation and multifield terrain analysis. By working on TINs generated from very large LiDAR (Light, Detection and Ranging) data sets, we demonstrate the effectiveness and scalability of the Terrain trees against a state-of-the-art compact data structures.

We consider the problem of efficient computing and simplifying Morse complexes on a Triangulated Irregular Network (TIN) based on discrete Morse theory. We develop a compact encoding for the discrete Morse gradient field, defined by the terrain elevation, by attaching it to the triangles of the TIN. This encoding is suitable to be combined with any TIN data structure storing just its vertices and triangles. We show how to compute such gradient field from the elevation values given at the TIN vertices, and how to simplify it effectively in order to reduce the number of critical elements. We demonstrate the effectiveness and scalability of our approach over large terrains by developing algorithms for extracting the cells of the Morse complexes as well as the graph joining the critical elements from the discrete gradient field. We compare implementations of our approach on a widely-used and compact adjacency-based topological data structure for a TIN and on a compact spatio-topological data structure that we have recently developed, the PR-star quadtree.

We consider the problem of modeling a terrain from both a geometric and a morphological point of view for efficient and effective terrain analysis on large data sets. We devise and implement a simplification hierarchy for a triangulated terrain, where the terrain is represented as a triangle mesh and its morphology is described by a discrete Morse gradient field defined on the basis on the elevation values given at the vertices of the mesh. The discrete Morse gradient is attached to the triangles, edges and vertices of the mesh. We define a new edge-contraction operator for the edges of the triangle mesh, which does not change the behavior of the gradient flow and does not create new critical points, and we apply it to the original full-resolution mesh in combination with a topological simplification operator which eliminates critical simplices in pair. We build the simplification hierarchy based on suitably combining such operators and we evaluate it experimentally.

We propose a new technique for eliminating flat edges from a Triangulated Irregular Network (TIN) in a morphologically consistent way. The algorithm is meant to be a preprocessing step for performing morphological computations on a terrain. Terrain morphology is rooted in Morse theory for smooth functions. Segmentation algorithms have been defined for TINs, mostly based on discrete versions of Morse theory, and under the assumption that the terrain model does not include flat edges. On the other hand, flat edges often occur in real data, and thus either they are eliminated through data perturbation, or the segmentation algorithms must be able to deal with them. In both cases, the resulting Morse segmentations are highly affected by the presence of flat edges. The new technique we propose provides a better solution, as it preserves the set of maxima and minima of the original terrain, and improves consistency among the terrain decompositions produced by different segmentation algorithms.

We describe a dual graph-based representation for the ascending and descending Morse complexes of a scalar field, and a compact and dimension-independent data structure based on it, which assumes a discrete representation of the field as a simplicial mesh. We present atomic dimension-independent simplification operators on the graph-based representation. Based on such operators, we have developed a simplification algorithm, which allows generalization of the ascending and descending Morse complexes at different levels of resolution. We show here the results of our implementation, discussing the computation times and the size of the resulting simplified graphs, also in comparison with the size of the original full-resolution graph.

We propose the PR-star octree as a combined spatial data structure for performing efficient topological queries on tetrahedral meshes. The PR-star octree augments the Point Region octree (PR Octree) with a list of tetrahedra incident to its indexed vertices, i.e. those in the star of its vertices. Thus, each leaf node encodes the minimal amount of information necessary to locally reconstruct the topological connectivity of its indexed elements. This provides the flexibility to efficiently construct the optimal data structure to solve the task at hand using a fraction of the memory required for a corresponding data structure on the global tetrahedral mesh. Due to the spatial locality of successive queries in typical GIS applications, the construction costs of these runtime data structures are amortized over multiple accesses while processing each node. We demonstrate the advantages of the PR-star octree representation in several typical GIS applications, including detection of the domain boundaries, computation of local curvature estimates and mesh simplification.

We address the problem of performing spatial queries on \ntetrahedral meshes. These latter arise in several application \ndomains including 3D GIS, scientific visualization, finite el- \nement analysis. We have defined and implemented a family \nof spatial indexes, that we call tetrahedral trees. Tetrahedral \ntrees subdivide a cubic domain containing the mesh in an \noctree or 3D kd-tree fashion, with three different subdivision \ncriteria. Here, we present and compare such indexes, their \nmemory usage, and spatial queries on them.

We investigate a morphological approach to the analysis and understanding of 3D scalar fields defined by volume data sets. We consider a discrete model of the 3D field obtained by discretizing its domain into a tetrahedral mesh. We use Morse theory as the basic mathematical tool which provides a segmentation of the graph of the scalar field based on relevant morphological features (such as critical points). Since the graph of a discrete 3D field is a tetrahedral hypersurface in 4D space, we measure the distortion of the transformation which maps the tetrahedral decomposition of the domain of the scalar field into the tetrahedral mesh representing its graph in R4, and we call it discrete distortion. We develop a segmentation algorithm to produce a Morse decompositions associated with the scalar field and its discrete distortion. We use a merging procedure to control the number of 3D regions in the segmentation output. Experimental results show the validity of our approach.

In order to characterize the morphology of a triangulated terrain, we define several discrete estimators that mimic mean and Gaussian curvatures in the discrete case. We start from concentrated curvature, a discrete notion of Gaussian curvature for polyhedral surfaces, defined by Troyanov [7]. Since concentrated curvature does not depend on the local geometric shape of the terrain, we introduce Ccurvature that allows us to obtain discrete counterparts of both Gaussian and mean curvature. Finally, we define distortion, which behaves as an approximation of mean curvature. We apply all such measures to the analysis of the morphology of triangulated terrains.

Bintrees based on longest edge bisection and hierarchies of diamonds are popular multiresolution techniques on regularly sampled terrain datasets. In this work, we consider Sparse Terrain Pyramids as a compact multiresolution representation for terrain datasets whose samples are a subset of those lying on a regular grid. While previous diamond-based approaches can efficiently represent meshes built on a complete grid of resolution (2k +1)2, this is not suitable when the field values are uniform in large areas or simply non-existent. We explore properties of diamonds to simplify an encoding of the implicit dependency relationship between diamonds. Additionally, we introduce a diamond clustering technique to further reduce the geometric and topological overhead of such representations. We demonstrate the coherence of our clustering technique as well as the compactness of our representation.

We propose a new multi-scale terrain model, based on a hierarchical representation for the morphology of a terrain. The basis of our morphological model is a dual Morse decomposition of the terrain, composed by the stable and unstable manifolds defined by its critical points and its integral lines. We propose a two-level representation of the dual Morse decomposition and we define new simplification operators for the Morse decomposition which act on such representation. Based on these operators, we define a hierarchical morphology-based representation, that we call a Multi-scale Morse Complex (MMC). Results from our implementation of the MMC are presented.

We propose a technique for simplification and multiresolution modeling of a terrain represented as a TIN. Our goal is to maintain the morphological structure of the terrain in the resulting multiresolution model. To this aim, we extend Morse theory, developed for continuous and differentiable functions, to the case of piecewise linear functions. We decompose a TIN into areas with uniform morphological properties (such as valleys, basins, etc.) separated by a network of critical lines and points. We describe an algorithm to compute the above decomposition and the critical net, and a TIN simplification algorithm that preserves them. On this basis, we build a multiresolution terrain model, which provides a representation of critical features at any level of detail.

We present a model for describing the visibility of a polyhedral terrain from a fixed viewpoint, based on a collection of nested horizons. We briefly introduce the concepts of mathematical and digital terrain models, and some background notions for visibility problems on terrains. Then, we define horizons on a polyhedral terrain, and introduce a visibility model, that we call the horizon map. We present a construction algorithm and a data structure for encoding the horizon map, and show how it can be used for solving point visibility queries with respect to a fixed viewpoint.

In this paper, we address the problem of computing visibility information on triangulated digital terrain models. We present first a general introduction to digital terrain models. Visibility problems on terrains are classified, according to the kind of visibility information they compute, into point visibility, line visibility and region visibility. A survey of the state-of-the-art of the algorithms for computing the different kinds of visibility information is presented, according to the previous classification. A new algorithm for computing the horizon on a digital terrain model is also described.

Line-of-sight communication on topographic surfaces has relevance for several applications of Geographical Information Systems. In this paper, we study the problem of linking a set of transceiver stations in a visibility-connected communication network, by placing a minimum number of relays on the terrain surface. The problem is studied in the framework of a discrete visibility model, where the mutual visibility of a finite set of sites on the terrain is represented through a graph, called the visibility graph. While in the special case of only two transceivers an optimal solution can be found in polynomial time, by computing a minimum path on the visibility graph, the general problem is equivalent to a Steiner problem on the visibility graph, and, thus, it is untractable in practice. In the latter case, we propose a practical approximate solution based on a Steiner heuristic. For both the special and the general case, we propose both a static and a dynamic algorithm that allow computation of a solution, and we show experimental results.

In this paper we address the problem of computing visibility information on digital terrain models in parallel. We propose a parallel algorithm for computing the visible region of an observation point located on the terrain. The algorithm is based on a sequential triangle-sorting visibility approach proposed by De Floriani et al. (1989). Static and dynamic parallelization strategies, both in terms of partitioning criteria and scheduling policies, are discussed. The different parallelization strategies are implemented on an MIMD multicomputer and evaluated through experimental results.