Unstructured data are collections of points with irregular topology, often represented through simplicial meshes, such as triangle and tetrahedral meshes. Whenever possible such representations are avoided in visualization since they are computationally demanding if compared with regular grids. In this work, we aim at simplifying the encoding and processing of simplicial meshes. The article proposes TopoCluster, a new localized data structure for tetrahedral meshes. TopoCluster provides efficient computation of the connectivity of the mesh elements with a low memory footprint. The key idea of TopoCluster is to subdivide the simplicial mesh into clusters. Then, the connectivity information is computed locally for each cluster and discarded when it is no longer needed. We define two instances of TopoCluster. The first instance prioritizes time efficiency and provides only a modest savings in memory, while the second instance drastically reduces memory consumption up to an order of magnitude with respect to comparable data structures. Thanks to the simple interface provided by TopoCluster, we have been able to integrate both data structures into the existing Topological Toolkit (TTK) framework. As a result, users can run any plugin of TTK using TopoCluster without changing a single line of code.

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.

Abstract Simplicial complexes are widely used to discretize shapes. In low dimensions, a 3D shape is represented by discretizing its boundary surface, encoded as a triangle mesh, or by discretizing the enclosed volume, encoded as a tetrahedral mesh. High‐dimensional simplicial complexes have recently found their application in topological data analysis. Topological data analysis aims at studying a point cloud P, possibly embedded in a high‐dimensional metric space, by investigating the topological characteristics of the simplicial complexes built on P. Analysing such complexes is not feasible due to their size and dimensions. To this aim, the idea of simplifying a complex while preserving its topological features has been proposed in the literature. Here, we consider the problem of efficiently simplifying simplicial complexes in arbitrary dimensions. We provide a new definition for the edge contraction operator, based on a top‐based data structure, with the objective of preserving structural aspects of a simplicial shape (i.e., its homology), and a new algorithm for verifying the link condition on a top‐based representation. We implement the simplification algorithm obtained by coupling the new edge contraction and the link condition on a specific top‐based data structure, that we use to demonstrate the scalability of our approach.

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.

Abstract We consider the problem of computing discrete Morse and Morse‐Smale complexes on an unstructured tetrahedral mesh discretizing the domain of a 3D scalar field. We use a duality argument to define the cells of the descending Morse complex in terms of the supplied (primal) tetrahedral mesh and those of the ascending complex in terms of its dual mesh. The Morse‐Smale complex is then described combinatorially as collections of cells from the intersection of the primal and dual meshes. We introduce a simple compact encoding for discrete vector fields attached to the mesh tetrahedra that is suitable for combination with any topological data structure encoding just the vertices and tetrahedra of the mesh. We demonstrate the effectiveness and scalability of our approach over large unstructured tetrahedral meshes by developing algorithms for computing the discrete gradient field and for extracting the cells of the Morse and Morse‐Smale complexes. We compare implementations of our approach on an adjacency‐based topological data structure and on the PR‐star octree, a compact spatio‐topological data structure.

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.