Parallel Topology-aware Mesh Simplification on Terrain Trees
Y. Song, R. Fellegara, F. Iuricich, L. De Floriani
ACM Trans. Spatial Algorithms Syst., 10(2), 2024.
[bibtex][doi]abstract
We address the problem of performing a topology-aware simplification algorithm on a compact and distributed data structure for triangle meshes, the Terrain trees. Topology-aware operators have been defined to coarsen a Triangulated Irregular Network (TIN) without affecting the topology of its underlying terrain, i.e., without modifying critical features of the terrain, such as pits, saddles, peaks, and their connectivity. However, their scalability is limited for large-scale meshes. Our proposed algorithm uses a batched processing strategy to reduce both the memory and time requirements of the simplification process, and thanks to the spatial decomposition on the basis of Terrain trees, it can be easily parallelized. Also, since a Terrain tree after the simplification process becomes less compact and efficient, we propose an efficient post-processing step for updating hierarchical spatial decomposition. Our experiments on real-world TINs, derived from topographic and bathymetric LiDAR data, demonstrate the scalability and efficiency of our approach. Specifically, topology-aware simplification on Terrain trees uses 40\% less memory and half the time compared to the most compact and efficient connectivity-based data structure for TINs. Furthermore, the parallel simplification algorithm on the Terrain trees exhibits a 12\texttimes{} speedup with an OpenMP implementation. The quality of the output mesh is not significantly affected by the distributed and parallel simplification strategy of Terrain trees, and we obtain similar quality levels compared to the global baseline method.
Immersive and Interactive 3D Visualization of Large-Scale Geoscientific Data
M. Flatken, S. Schneegans, R. Fellegara, A. Gerndt
PRESENCE: Virtual and Augmented Reality, 33, 57-76, 2024.
[bibtex][doi]abstract
{Virtual reality (VR) technology has great potential in supporting planetary scientists and the field of geosciences by offering immersive and interactive experiences for data exploration and analysis. This paper shows the opportunities presented by the use of VR technology in the geosciences domain while also identifying the open challenges associated with this integration. Our focus is on highlighting the several benefits that VR brings, including stereo vision, head tracking, and collaborative capabilities. These features can foster knowledge exchange and interdisciplinary research. Nevertheless, the adoption of VR presents certain challenges that need to be addressed. These include maintaining high refresh rates, handling large heterogeneous datasets, and striking a balance between visualization fidelity and performance. Fortunately, significant advancements have been made in high-performance data analysis, progressive data streaming, and real-time visualization, enabling interactive exploration of large-scale datasets within VR environments. To support a broader adoption among domain experts, we propose a visualization approach that scales both with display and with data size. As such, the system can be used to interactively explore large-scale datasets in immersive environments like CAVEs or powerwalls, on HMDs, or on traditional desktop setups. This approach allows for seamless transitions between desktop and VR experiences, leveraging immersive environments for collaboration and outreach activities. In this paper, we present an architectural framework, hardware environments, use cases, lessons learned, and the future potential of VR in this field. Through this scalable system, we anticipate transformative advancements in scientific exploration, collaboration, and knowledge dissemination.}
Immersive and Interactive 3D Visualization of Large-Scale Geo-Scientific Data
M. Flatken, S. Schneegans, R. Fellegara, A. Gerndt
2023 IEEE Conference on Virtual Reality and 3D User Interfaces Abstracts and Workshops (VRW), 211--215, 2023.
[bibtex][doi]abstract
In this paper, we present a software architecture and framework developed over the past decade to enable scalable and highly interactive visualizations for large datasets and display sizes. The framework integrates distributed data processing, data streaming, and dynamic scheduling to allow for view-dependent feature extraction and progressive data streaming. Additionally, the framework has been designed to support visualizations from local desktop workstations to large multi-display virtual environments.
TopoCluster: A Localized Data Structure for Topology-Based Visualization
G. Liu, F. Iuricich, R. Fellegara, L. De Floriani
IEEE Transactions on Visualization and Computer Graphics, 29(2), 1506-1517, 2023.
[bibtex][doi]abstract
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.
Explorative, Immersive Visualization of Space Weather Phenomena
R. Fellegara, K. Krösl, S. Markidis, F. Roshani, M. Flatken, J. Fritsch, A. Gerndt, A. Fuhrmann, M. Hürbe, D. Stoll, J. Klug, E. Ntagiou
17th International Conference on Space Operations, SpaceOps 2023, 2023.
[bibtex][url]abstract
Interactive data exploration represents a key challenge for both the analysis and visualization pipelines in various domains, due to the exponential growth of the data generated by modern sensors. Thanks to recent advances in high-performance computing, processing large-scale data becomes feasible, but the visualization and interactive exploration of such data remain an open challenge. While exploring multi-dimensional data on two-dimensional displays has been a research topic for decades, technologies such as virtual reality (VR) or augmented reality (AR) now allow us to leverage the third dimension and explore three-dimensional data in its spatial context, using immersive analytics, which is seen as an emerging research field and key to support analytical reasoning and decision making. Some modern visualization tools are already exploiting VR and AR to enhance data visualization and exploration, but many existing solutions are limited in functionality, immersivity, or usability. There are several challenges to overcome when developing immersive experiences. In this paper, we present an approach for explorative, immersive visualization of space weather phenomena. The main goal of this work is to define a pipeline that starts from the output of a space weather simulation (e.g., coming from ENLIL or EUHFORIA models), and executes a data preparation step in which the data is reduced to the specific needs of a given visualization tool. This post-processed data is visualized by two distinct visualization tools: one targeting domain experts, and the latter targeting the general public. The final objective of this activity is to provide tools for helping experts interpret complex space weather phenomena, and raising awareness for space weather conditions and their effects on our life on Earth, in the general public.
Terrain trees: a framework for representing, analyzing and visualizing triangulated terrains
R. Fellegara, F. Iuricich, Y. Song, L. Floriani
GeoInformatica, 27(3), 525--564, 2023.
[bibtex][doi]abstract
We propose a family of spatial data structures for the representation and processing of Triangulated Irregular Networks (TINs). We call such data structures Terrain trees. A Terrain tree combines a minimal encoding of the connectivity of the TIN with a hierarchical spatial index. Connectivity relations are extracted locally at run-time, within each leaf block of the hierarchy, based on specific application needs. Spatial queries are performed by exploring the hierarchical data structure. We present a new framework for terrain analysis based on Terrain trees. The framework, implemented in the Terrain trees library (TTL), contains algorithms for morphological features extraction, such as roughness and curvature, and for topology-based analysis of terrains. Moreover, it includes a technique for multivariate visualization, which enables the analysis of multiple scalar fields defined on the same terrain. To prove the effectiveness and scalability of such framework, we have compared the different Terrain trees against each other and also against the most compact state-of-the-art data structure for TINs. Comparisons are performed on storage and generation costs and on the efficiency in performing terrain analysis operations.
VESTEC: Visual Exploration and Sampling Toolkit for Extreme Computing
M. Flatken, A. Podobas, R. Fellegara, A. Basermann, J. Holke, D. Knapp, M. Kontak, C. Krullikowski, M. Nolde, N. Brown, R. Nash, G. Gibb, E. Belikov, S. Chien, S. Markidis, P. Guillou, J. Tierny, J. Vidal, C. Gueunet, J. Günther, M. Pawlowski, P. Poletti, G. Guzzetta, M. Manica, A. Zardini, J. Chaboureau, M. Mendes, A. Cardil, S. Monedero, J. Ramirez, A. Gerndt
IEEE Access, 11, 87805-87834, 2023.
[bibtex][doi]abstract
Natural disasters and epidemics are unfortunate recurring events that lead to huge societal and economic loss. Recent advances in supercomputing can facilitate simulations of such scenarios in (or even ahead of) real-time, therefore supporting the design of adequate responses by public authorities. By incorporating high-velocity data from sensors and modern high-performance computing systems, ensembles of simulations and advanced analysis enable urgent decision-makers to better monitor the disaster and to employ necessary actions (e.g., to evacuate populated areas) for mitigating these events. Unfortunately, frameworks to support such versatile and complex workflows for urgent decision-making are only rarely available and often lack in functionalities. This paper gives an overview of the VESTEC project and framework, which unifies orchestration, simulation, in-situ data analysis, and visualization of natural disasters that can be driven by external sensor data or interactive intervention by the user. We show how different components interact and work together in VESTEC and describe implementation details. To disseminate our experience three different types of disasters are evaluated: a Wildfire in La Jonquera (Spain), a Mosquito-Borne disease in two regions of Italy, and the magnetic reconnection in the Earth magnetosphere.
Interactive visualization and topology-based analysis of large-scale time-varying remote-sensing data: challenges and opportunities
R. Fellegara, M. Flatken, F. De Zan, A. Gerndt
EGU General Assembly Conference Abstracts, EGU21--11680, 2021.
[bibtex][doi]abstract
Over the last few years, the amount of large and complex data in the public domain has increased enormously and new challenges arose in the representation, analysis and visualization of such data. Considering the number of space missions that provided and will provide remote sensing data, there is still the need of a system that can be dispatched in several remote repositories and being accessible from a single client of commodity hardware. To tackle this challenge, at the DLR Institute for Software Technology we have defined a dual backend frontend system, enabling the interactive analysis and visualization of large-scale remote sensing data. The basis for all visualization and interaction approaches is CosmoScout VR, a visualization tool developed internally at DLR, and publicly available on Github, that allows the visualization of complex planetary data and large simulation data in real-time. The dual component of this system is based on an MPI framework, called Viracocha, that enables the analysis of large data remotely, and allows the efficient network usage about sending compact and partial results for interactive visualization in CosmoScout as soon as they are computed. A node-based interface is defined within the visualization tool, and this lets a domain expert to easily define customized pipelines for processing and visualizing the remote data. Each node of this interface is either linked with a feature extraction module, defined in Viracocha, or to a rendering module defined directly in CosmoScout. Being this interface completely customizable by a user, multiple pipelines can be defined over the same dataset to enhance even more the visualization feedback for analysis purposes. Being an ongoing project, on top of these tools, as a novel strategy in EO data processing and visualization, we plan to define and implement strategies based on Topological Data Analysis (TDA). TDA is an emerging set of technique for processing the data considering its topological features. These include both the geometric information associated to a point, as well all the non-geometric scalar values, like temperature and pressure, to name a few, that can be captured during a monitoring mission. One of the major theories behind TDA is Discrete Morse Theory, that, given a scalar value, is used to define a gradient on such function, extract the critical points, identify the region-of-influence of each critical point, and so on. This strategy is parameter free and enables a domain scientist to process large datasets without a prior knowledge of it. An interesting research question, that it will be investigated during this project is the correlation of changes of critical points at different time steps, and the identification of deformation (or changes) across time in the original dataset.
The Stellar decomposition: A compact representation for simplicial complexes and beyond
R. Fellegara, K. Weiss, L. De Floriani
Computers & Graphics, 98, 322-343, 2021.
[bibtex][doi]abstract
We introduce the Stellar decomposition, a model for efficient topological data structures over a broad range of simplicial and cell complexes. A Stellar decomposition of a complex is a collection of regions indexing the complex's vertices and cells such that each region has sufficient information to locally reconstruct the star of its vertices, i.e., the cells incident in the region's vertices. Stellar decompositions are general in that they can compactly represent and efficiently traverse arbitrary complexes with a manifold or non-manifold domain. They are scalable to complexes in high dimension and of large size, and they enable users to easily construct tailored application-dependent data structures using a fraction of the memory required by a corresponding global topological data structure on the complex. As a concrete realization of this model for spatially embedded complexes, we introduce the Stellar tree, which combines a nested spatial tree with a simple tuning parameter to control the number of vertices in a region. Stellar trees exploit the complex's spatial locality by reordering vertex and cell indices according to the spatial decomposition and by compressing sequential ranges of indices. Stellar trees are competitive with state-of-the-art topological data structures for manifold simplicial complexes and offer significant improvements for cell complexes and non-manifold simplicial complexes. We conclude with a high-level description of several mesh processing and analysis applications that utilize Stellar trees to process large datasets.
Efficient Topology-Aware Simplification of Large Triangulated Terrains
Y. Song, R. Fellegara, F. Iuricich, L. De Floriani
Proceedings of the 29th International Conference on Advances in Geographic Information Systems, 576--587, 2021.
[bibtex][doi]abstract
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.
Tetrahedral Trees: A Family of Hierarchical Spatial Indexes for Tetrahedral Meshes
R. Fellegara, L. De Floriani, P. Magillo, K. Weiss
ACM Transaction on Spatial Algorithms and Systems, 6(4), 2020.
[bibtex][doi]abstract
We address the problem of performing efficient spatial and topological queries on large tetrahedral meshes with arbitrary topology and complex boundaries. Such meshes arise in several application domains, such as 3D Geographic Information Systems (GISs), scientific visualization, and finite element analysis. To this aim, we propose Tetrahedral trees, a family of spatial indexes based on a nested space subdivision (an octree or a kD-tree) and defined by several different subdivision criteria. We provide efficient algorithms for spatial and topological queries on Tetrahedral trees and compare to state-of-the-art approaches. Our results indicate that Tetrahedral trees are an improvement over R*-trees for querying tetrahedral meshes; they are more compact, faster in many queries, and stable at variations of construction thresholds. They also support spatial queries on more general domains than topological data structures, which explicitly encode adjacency information for efficient navigation but have difficulties with domains with a non-trivial geometric or topological shape.
Efficient Homology-Preserving Simplification of High-Dimensional Simplicial Shapes
R. Fellegara, F. Iuricich, L. De Floriani, U. Fugacci
Computer Graphics Forum, 39(1), 244-259, 2020.
[bibtex][doi]abstract
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.
Multi-Level Filtering to Retrieve Similar Trajectories under the FréChet Distance
H. Wei, R. Fellegara, Y. Wang, L. De Floriani, H. Samet
Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 600--603, 2018.
[bibtex][doi]abstract
Computing with trajectories has become an important and practical research topic. In many scenarios, the goal is to find similar trajectories. The Fr\'{e}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\'{e}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.
The Stellar tree: a Compact Representation for Simplicial Complexes and Beyond
R. Fellegara, K. Weiss, L. De Floriani
ArXiv e-prints, 2017.
[bibtex][url]abstract
The efficient representation and management of simplicial and cell complexes is an active research topic in several fields, including geometric modeling, computer graphics, scientific visualization, and geographic data processing. In this paper, we propose the Stellar tree, a topological data structure for performing efficient topological queries on simplicial and non-simplicial complexes. We prove that a Stellar tree provides a scalable, compact and flexible data structure to represent these complexes, using a fraction of the memory required by a corresponding topological data structure on the global complex.
Efficient Representation and Analysis of Triangulated Terrains
R. Fellegara, F. Iuricich, L. De Floriani
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 74:1--74:4, 2017.
[bibtex][doi]abstract
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.
An efficient approach for verifying manifold properties of simplicial complexes
R. Fellegara, K. Weiss, L. De Floriani
Proceedings of the 25th International Meshing Roundtable, 2016.
[bibtex][url]abstract
While the vast majority of mesh processing tools assume a manifold mesh, many available meshes do not satisfy these constraints due to geometric defects and non-manifold singularities. We propose an efficient technique, based on a simple and compact data structure, for verifying topological properties of arbitrary simplicial complexes and experimentally demonstrate its effectiveness.
Analysis of Geolocalized Social Networks Based on Simplicial Complexes
R. Fellegara, U. Fugacci, F. Iuricich, L. De Floriani
Proceedings of the 9th ACM SIGSPATIAL Workshop on Location-based Social Networks, 5:1--5:8, 2016.
[bibtex][doi]abstract
A common issue in network analysis consists in the detection and characterization of the key vertices and communities. To this purpose, visualization tools could be of great help to support domain experts in analyzing this kind of data. However, the size of real networks can seriously affect the practical usage of these tools, thus, requiring the definition of suitable simplification procedures that preserve the core network information. In this work, we focus on geolocalized social networks, and we describe a tool for the analysis of this kind of data based on topological information. Supported by recent trends in network analysis, our approach uses simplicial complexes as a model for social networks. A homology-preserving simplification is used for dealing with the data complexity and for reducing the information to be visualized to the essential. By combining the representation based on simplicial complexes and the simplification tool, we can efficiently retrieve topological information useful for the network analysis. Both the effectiveness and scalability of our approach are experimentally demonstrated.
A spatio-topological approach to the representation of simplicial complexes and beyond
R. Fellegara
Department of Computer Science (DIBRIS), University of Genova, Italy. P.h.D. Thesis, Internal Report DIBRIS-TH-2015-01, 2015.
[bibtex]abstract
The efficient representation and management of simplicial and cell complexes is an active research topic in several fields, including geometric modeling, computer graphics, scientific visualization, and geographic data processing. Managing complexes in three dimensions and higher is not a simple task since the data structures proposed for three dimensions are quite large and become even larger when considering complexes in four dimensions and higher. Furthermore, current implementations cannot always keep large complexes entirely in main memory (in-core) and some out-of-core approaches, for example using a spatial data base, are intrinsically slow. There are two fundamental categories of queries proposed in the literature for interacting with simplicial and cell complexes: those based on spatial locality and those based on topological connectivity. Spatial information can be retrieved through spatial queries, such as point location queries, box queries (i.e., finding the cells of the complex inside a rectangle or a parallelepiped) and ray intersection queries (i.e, finding the intersection of a ray with the cells of the complex). Spatial queries are required to understand the relation between the cells of the complex and arbitrary regions in space, and are thus based on geometric information. Topological connectivity information can be retrieved through topological queries. Examples of topological queries are, for instance in a triangle mesh, finding the triangles adjacent to a given triangle through an edge or a vertex; or finding all triangles incident to a given vertex or edge. Thus, topological queries are necessary to perform navigation over the complex (e.g., iso-surface extraction or path computation). Several topological data structures have been proposed in the literature, however, such data structures do not efficiently support spatial queries. We propose here a spatio-topological approach to modeling simplicial complexes and certain class of cell complexes, and we call the resulting data structure a Stellar tree. In a Stellar tree the embedding space of the complex is decomposed using a hierarchical spatial index, such as a quadtree, octree or kD-tree, and the topological queries are efficiently answered by reconstructing the local topology. The Stellar tree is a flexible model that can efficiently represent complexes with cells of different types and dimensions, with irregular and non-manifold connectivity and using different spatial subdivision approaches. An advantage of this formulation is that we can locally reconstruct the optimal application-dependent topological data structure to solve the task at hand using a fraction of the memory required by the corresponding global topological data structure. Stellar trees are well suited for applications where we efficiently extract local topological relations, locally traverse and update the complex, and they do not require maintaining the topological connectivity of the full complex. We demonstrate the compactness of the Stellar tree and its efficiency in a variety of local and global processing applications, such as the computation of discrete curvature, validation and simplification of the complex, computation and simplification of the discrete Morse gradient, morphological segmentation of scalar fields through discrete Morse complexes. We also propose a family of spatial indexes for a specific instance of a simplicial complex, a tetrahedral mesh, that we call Tetrahedral trees. We address the problem of performing spatial and local topological queries on such meshes. Tetrahedral trees are based on a subdivision of a cubic domain containing the mesh through a regular nested subdivision (an octree or a kD-tree). We develop four variants of the spatial index depending on four different subdivision criteria. Moreover, we spatially reorganize the index to have a spatial coherence of the indexed data and we define a new compact encoding for the block nodes which drastically reduce the storage requirements of the data structure.
Efficient Computation and Simplification of Discrete Morse Decompositions on Triangulated Terrains
R. Fellegara, F. Iuricich, L. De Floriani, K. Weiss
Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 223--232, 2014.
[bibtex][doi]abstract
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.
A primal/dual representation for discrete Morse complexes on tetrahedral meshes
K. Weiss, F. Iuricich, R. Fellegara, L. De Floriani
Computer Graphics Forum (Proceedings of Eurovis 2013), 32(3), 361--370, 2013.
[bibtex][doi]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.
Spatial Indexes for Simplicial and Cellular Meshes
R. Fellegara
New Trends in Databases and Information Systems, 373--382, 2014.
[bibtex]abstract
The efficient representation of simplicial meshes is an active research topic in several fields, including geometric modeling, computer graphics, scientific visualization, and geographic data processing. Managing complexes in three dimensions and higher is not a simple task since the data structures proposed for three dimensions are quite large and are even larger when considering complexes in four dimensions and higher. Simplicial meshes have received great attention, since their combinatorial properties make them easier to understand, represent and manipulate than more general cell complexes. Furthermore, current implementations cannot always keep large complexes entirely in system memory (in-core) and some out-of-core approaches, for example using a spatial data base, are intrinsically slow. There are two fundamental categories of queries proposed in the literature for interacting with simplicial meshes: those based on spatial locality and those based on topological connectivity. Spatial information can be retrieved through spatial queries, that are accelerated through the use of a spatial indexing structure, a data structure that supports the efficient organization of spatially near complexes. Topological connectivity information can be retrieved through topological queries. These are accelerated by using a topological data structure, a data structure that supports the efficient reconstruction of a subset of the local topological connectivity of the mesh as well as navigation. In general, topological data structures tend to be inefficient for spatial queries, while spatial indexes exhibit a high overhead when executing topological queries. The aim my research is to develop new data structures for simplicial and cellular meshes in three dimensions and higher, based on spatial indexes and topological data structures. The final goal is to find optimized data structures that combine the features of the topological and spatial approach in a common framework.
A Spatial Approach to Morphological Feature Extraction from Irregularly Sampled Scalar Fields
L. De Floriani, F. Iuricich, R. Fellegara, K. Weiss
Proceedings of the Third ACM SIGSPATIAL International Workshop on GeoStreaming, 40--47, 2012.
[bibtex][doi]abstract
Several algorithms have recently been introduced for morphological analysis of scalar fields (terrains, static and dynamic volume data) based on a discrete version of Morse theory. However, despite the applicability of the theory to very general discretized domains, memory constraints have limited its practical usage to scalar fields defined on regular grids, or to relatively small simplicial complexes. We propose an efficient and effective data structure for the extraction of morphological features, such as critical points and their regions of influence, based on the PR-star octree data structure, which uses a spatial index over the embedding space of the complex to locally reconstruct the connectivity among its cells. We demonstrate the effectiveness and scalability of our approach over irregular simplicial meshes in 2D and in 3D with a set of streaming algorithms which extract topological features of the associated scalar field from its locally computed discrete gradient field. Specifically, we extract the critical points of the scalar field, their corresponding regions in the Morse decomposition of the field domain induced by the gradient field, and their connectivity.
The PR-star Octree: A Spatio-topological Data Structure for Tetrahedral Meshes
K. Weiss, R. Fellegara, L. De Floriani, M. Velloso
Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 92--101, 2011.
[bibtex][doi]abstract
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.
Spatial Indexing on Tetrahedral Meshes
L. De Floriani, R. Fellegara, P. Magillo
Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 506--509, 2010.
[bibtex][doi]abstract
We address the problem of performing spatial queries on tetrahedral meshes. These latter arise in several application domains including 3D GIS, scientific visualization, finite element analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral trees. Tetrahedral trees subdivide a cubic domain containing the mesh in an octree or 3D kd-tree fashion, with three different subdivision criteria. Here, we present and compare such indexes, their memory usage, and spatial queries on them.