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.

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.

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.

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.

We consider the problem of efficiently computing a discrete Morse complex on simplicial complexes of arbitrary dimension and very large size. Based on a common graph-based formalism, we analyze existing data structures for simplicial complexes, and we define an efficient encoding for the discrete Morse gradient on the most compact of such representations. We theoretically compare methods based on reductions and coreductions for computing a discrete Morse gradient, proving that the combination of reductions and coreductions produces new mutually equivalent approaches. We design and implement a new algorithm for computing a discrete Morse complex on simplicial complexes. We show that our approach scales very well with the size and the dimension of the simplicial complex also through comparisons with the only existing public-domain algorithm for discrete Morse complex computation. We discuss applications to the computation of multi-parameter persistent homology and of extremum graphs for visualization of time-varying 3D scalar fields.

Presents the introductory editorial for this issue of the publication.

Introduces the new editorial staff for this issue of the publication.

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.

Welcome to the January 2018 issue of the IEEE Transactions on Visualization and Computer Graphics (TVCG)! I am pleased to introduce this special issue containing 99 papers presented at IEEE VIS 2017, which includes the Conference on Visual Analytics Science and Technology (IEEE VAST 2017), the IEEE Information Visualization Conference (IEEE InfoVis 2017), and the IEEE Scientific Visualization Conference (IEEE SciVis 2017), held in Phoenix, USA, from the 1st to the 6th of October 2017. These papers, selected from 467 submissions, were recommended for acceptance by the Program Committees of these three conferences, after having undergone a rigorous and competitive two-round review process. The cooperation between TVCG and IEEE VIS has been considerably growing over the years in terms of the number of publications in the TVCG IEEE VIS special issue, and of the size of attendance to IEEE VIS. This special hybrid publication model enables timely dissemination of many high-quality research results from the world’s top visualization conferences to TVCG readership, while improving the overall visibility and quality of IEEE VIS publications through a rigorous journal-style review. Since 2011, the authors of TVCG regular papers have been invited to give an oral presentation of their recent work at IEEE VIS, thus providing a unique opportunity for the VIS audience to keep abreast of high-quality visualization research featured in regular issues of TVCG, and encouraging more TVCG authors to attend IEEE VIS. This closely coupled relation-ship between TVCG and VIS has been leading to a more timely exchange of new ideas, to a rapid dissemination of visualization research via an integrated forum for both publications and presentations, and to further expanding our visualization community.

Presents information on the current status of the journal.

Presents the recipients of select Computer Society awards for Best Associate Editor and Best Reviewer.

Presents the introductory editorial for this issue of the publication.

This special issue of IEEE Transactions on Visualization and Computer Graphics (TVCG) contains the 29 full papers selected for the IEEE Virtual Reality and 3D User Interfaces (IEEE VR 2018) Conference held in Reutlingen, Germany, March 18-22, 2017. Since its inception in 1993, IEEE VR has been the premier venue to present new research results in the field of Virtual Reality (VR). The strong current trends toward VR systems for consumer audiences heightens the importance of this event. This fact is reflected in the cooperation between TVCG and IEEE VR, which is in its seventh year and is one cornerstone of the strategy of TVCG to combine computer graphics and data visualization in its scope with virtual and augmented reality. The special issue format combines speed of publication with all the established advantages of an archival journal. To that end, a rigorous and competitive two-round review process was performed to ensure the highest quality.

Wwelcome to the November 2018 issue of theIEEE Transactions on Visualization and Computer Graphics (TVCG). This issue contains selected papers accepted at the IEEE International Symposium on Mixed and Augmented Reality (ISMAR), held this year in Munich, Germany, from October 16 to October 20, 2018.

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.

Presents the message from the editor-in-chief for this issue of the publication.

Presents the current state of the journal, its scope, and outlook toward the future.

Presents the introductory editorial for this issue of the publication.

Presents the introductory editorial for this issue of this publication.

The papers in this special issue were presented at the IEEE Virtual Reality (VR) Conference that was held in Los Angeles, CA, from March 18-22, 2017.

Welcome the November 2017 issue of the IEEE Transactions on Visualization and Computer Graphics (TVCG). This issue contains selected papers accepted at the IEEE International Symposium on Mixed and Augmented Reality (ISMAR), held this year in Nantes, France, from September 9 to September 13, 2017.

Abstract This paper presents the state of the art in the area of topology‐based visualization. It describes the process and results of an extensive annotation for generating a definition and terminology for the field. The terminology enabled a typology for topological models which is used to organize research results and the state of the art. Our report discusses relations among topological models and for each model describes research results for the computation, simplification, visualization, and application. The paper identifies themes common to subfields, current frontiers, and unexplored territory in this research area.

Presents the introductory editorial for this issue of the publication.

Presents the introductory editorial for this issue of the publication.

Presents the introductory editorial for this issue of the publication.

Abstract Morse theory offers a natural and mathematically‐sound tool for shape analysis and understanding. It allows studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete Morse theory and on algorithms based on it.

Presents a message from the new Editor-In-Chief.

Presents the introductory editorial for this issue of the publication

Presents the introductory editorial for this issue of the publication.

Presents the introductory editorial for this issue of the publication.

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.

Abstract In the field of computer vision, the introduction of a low‐level preprocessing step to oversegment images into superpixels – relatively small regions whose boundaries agree with those of the semantic entities in the scene – has enabled advances in segmentation by reducing the number of elements to be labeled from hundreds of thousands, or millions, to a just few hundred. While some recent works in mesh processing have used an analogous oversegmentation, they were not intended to be general and have relied on graph cut techniques that do not scale to current mesh sizes. Here, we present an iterative superfacet algorithm and introduce adaptations of undersegmentation error and compactness, which are well‐motivated and principled metrics from the vision community. We demonstrate that our approach produces results comparable to those of the normalized cuts algorithm when evaluated on the Princeton Segmentation Benchmark, while requiring orders of magnitude less time and memory and easily scaling to, and enabling the processing of, much larger meshes.

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.

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 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.

Abstract Hierarchical spatial decompositions are a basic modelling tool in a variety of application domains. Several papers on this subject deal with hierarchical simplicial decompositions generated throughregular simplex bisection. Such decompositions, originally developed for finite elements, are extensively used as the basis for multi‐resolution models of scalar fields, such as terrains, and static or time‐varying volume data. They have also been used as an alternative to quadtrees and octrees as spatial access structures. The primary distinction among all such approaches is whether they treat the simplex or clusters of simplices, called diamonds, as the modelling primitive. This leads to two classes of data structures and to different query approaches. We present the hierarchical models in a dimension‐independent manner, and organize the description of the various applications, primarily interactive terrain rendering and isosurface extraction, according to the dimension of the domain.

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 address the problem of morphological analysis of real terrains. We describe a morphological model for a terrain by considering extensions of Morse theory to the discrete case. We propose a two-level model of the morphology of a terrain based on a graph joining the critical points of the terrain through integral lines. We present a new set of generalization operators specific for discrete piece-wise linear terrain models, which are used to reduce noise and the size of the morphological representation. We show results of our approach on real terrains.

We consider a model of a 3D image obtained by discretizing it into a multiresolution tetrahedral mesh known as a hierarchy of diamonds. This model enables us to extract crack-free approximations of the 3D image at any uniform or variable resolution, thus reducing the size of the data set without reducing the accuracy. A 3D intensity image is a scalar field (the intensity field) defined at the vertices of a 3D regular grid and thus the graph of the image is a hypersurface in R4. We measure the discrete distortion, a generalization of the notion of curvature, of the transformation which maps the tetrahedralized 3D grid onto its graph in R4. We evaluate the use of a hierarchy of diamonds to analyze properties of a 3D image, such as its discrete distortion, directly on lower resolution approximations. Our results indicate that distortion-guided extractions focus the resolution of approximated images on the salient features of the intensity image.

We address the problem of representing the geometry and the morphology of a triangulated surface endowed with a scalar field in a combined geometric and topological multiresolution model. The model, called a Multiresolution Morse Triangulation (MMT), is composed of a multiresolution triangle mesh, and of a multiresolution Morse complex describing the morphology of the field. The MMT is built through a combined morphological and geometrical generalization, and supports queries to extract consistent geometrical and morphological representations of the field at both uniform and variable resolutions.

Efficient multiresolution representations for isosurfaces and interval volumes are becoming increasingly important as the gap between volume data sizes and processing speed continues to widen. Our multiresolution scalar field model is a hierarchy of tetrahedral clusters generated by longest edge bisection that we call a hierarchy of diamonds. We propose two multiresolution models for representing isosurfaces, or interval volumes, extracted from a hierarchy of diamonds which exploit its regular structure. These models are defined by subsets of diamonds in the hierarchy that we call isodiamonds, which are enhanced with geometric and topological information for encoding the relation between the isosurface, or interval volume, and the diamond itself. The first multiresolution model, called a relevant isodiamond hierarchy, encodes the isodiamonds intersected by the isosurface, or interval volume, as well as their nonintersected ancestors, while the second model, called a minimal isodiamond hierarchy, encodes only the intersected isodiamonds. Since both models operate directly on the extracted isosurface or interval volume, they require significantly less memory and support faster selective refinement queries than the original multiresolution scalar field, but do not support dynamic isovalue modifications. Moreover, since a minimal isodiamond hierarchy only encodes intersected isodiamonds, its extracted meshes require significantly less memory than those extracted from a relevant isodiamond hierarchy. We demonstrate the compactness of isodiamond hierarchies by comparing them to an indexed representation of the mesh at full resolution.

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.

Non-manifold models are frequently encountered in engineering simulations and design as well as in computer graphics. However, these models lack shape characterization for modelling and searching purposes. Topological properties act as a kernel for deriving key features of objects. Here we propose a classification for the non-manifold singularities of non-manifold objects through continuous shape transformations of 2-manifolds without boundary up to the creation of non-manifold singularities. As a result, the non-manifold objects thus created can be categorized and contribute to the definition of a general purpose taxonomy for non-manifold shapes.

Abstract Nested simplicial meshes generated by the simplicial bisection decomposition proposed by Maubach [ Mau95 ] have been widely used in 2D and 3D as multi‐resolution models of terrains and three‐dimensional scalar fields, They are an alternative to octree representation since they allow generating crack‐free representations of the underlying field. On the other hand, this method generates conforming meshes only when all simplices sharing the bisection edge are subdivided concurrently. Thus, efficient representations have been proposed in 2D and 3D based on a clustering of the simplices sharing a common longest edge in what is called a diamond. These representations exploit the regularity of the vertex distribution and the diamond structure to yield an implicit encoding of the hierarchical and geometric relationships among the triangles and tetrahedra, respectively. Here, we analyze properties ofd‐dimensional diamonds to better understand the hierarchical and geometric relationships among the simplices generated by Maubach's bisection scheme and derive closed‐form equations for the number of vertices, simplices, parents and children of each type of diamond. We exploit these properties to yield an implicit pointerless representation ford‐dimensional diamonds and reduce the number of required neighbor‐finding accesses fromO(d!) toO(d).

Volumetric datasets are often modeled using a multiresolution approach based on a nested decomposition of the domain into a polyhedral mesh. Nested tetrahedral meshes generated through the longest edge bisection rule are commonly used to decompose regular volumetric datasets since they produce highly adaptive crack-free representations. Efficient representations for such models have been achieved by clustering the set of tetrahedra sharing a common longest edge into a structure called a diamond. The alignment and orientation of the longest edge can be used to implicitly determine the geometry of a diamond and its relations to the other diamonds within the hierarchy. We introduce the supercube as a high-level primitive within such meshes that encompasses all unique types of diamonds. A supercube is a coherent set of edges corresponding to three consecutive levels of subdivision. Diamonds are uniquely characterized by the longest edge of the tetrahedra forming them and are clustered in supercubes through the association of the longest edge of a diamond with a unique edge in a supercube. Supercubes are thus a compact and highly efficient means of associating information with a subset of the vertices, edges and tetrahedra of the meshes generated through longest edge bisection. We demonstrate the effectiveness of the supercube representation when encoding multiresolution diamond hierarchies built on a subset of the points of a regular grid. We also show how supercubes can be used to efficiently extract meshes from diamond hierarchies and to reduce the storage requirements of such variable-resolution meshes.

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.

Abstract We introduce a novel notion, that we call discrete distortion, for a triangulated 3‐manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3‐manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3‐manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R 4 defined by a scalar field on a 3D mesh. distance fields.

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.

Modeling and understanding complex non-manifold shapes is a key issue in shape analysis. Geometric shapes are commonly discretized as two- or three-dimensional simplicial complexes embedded in the 3D Euclidean space. The topological structure of a nonmanifold simplicial shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we present a topological decomposition of a shape at two different levels, with different degrees of granularity. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.

We propose a new data structure for the compact encoding of a level-of detail (LOD) model of a three-dimensional scalar field based on unstructured tetrahedral meshes. Such data structure, called a half-edge tree (HET), is built through the iterative application of a half-edge collapse, i.e. by contracting an edge to one of its endpoints. We also show that selective refined meshes extracted from an HET contain on average about 34% and up to 75% less tetrahedra than those extracted from an LOD model built through a general edge collapse.

We consider a recursive decomposition of a four-dimensional hypercube into a hierarchy of nested 4-dimensional simplexes, that we call pentatopes. The paper presents an algorithm for finding the neighbors of a pentatope along its five tetrahedral faces in constant time. To this aim, we develop a labeling technique for nested pentatopes that enables their identification by using location codes. The constant-time behavior is achieved through bit manipulation operations, thus avoiding traversing the simplicial hierarchy via pointer following. We discuss an application of this representation to multi-resolution representations of four-dimensional scalar fields. Extracting adaptive continuous approximations of the scalar field from such a model requires generating conforming meshes, i.e., meshes in which the pentatopes match along their tetrahedral faces. Our neighbor finding algorithm enables computing face-adjacent pentatopes efficiently.

In this paper, we address the problem of the efficient visualization of large irregular volume data sets by exploiting a multiresolution model based on tetrahedral meshes. Multiresolution models, also called Level-Of-Detail (LOD) models, allow encoding the whole data set at a virtually continuous range of different resolutions. We have identified a set of queries for extracting meshes at variable resolution from a multiresolution model, based on field values, domain location, or opacity of the transfer function. Such queries allow trading off between resolution and speed in visualization. We define a new compact data structure for encoding a multiresolution tetrahedral mesh built through edge collapses to support selective refinement efficiently and show that such a structure has a storage cost from 3 to 5.5 times lower than standard data structures used for tetrahedral meshes. The data structures and variable resolution queries have been implemented together with state-of-the art visualization techniques in a system for the interactive visualization of three-dimensional scalar fields defined on tetrahedral meshes. Experimental results show that selective refinement queries can support interactive visualization of large data sets.

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 deal with the problem of analyzing and visualizing large-size volume data sets. To this aim, we consider multiresolution representations based on a decomposition of the field domain into tetrahedral cells. We compare two types of multiresolution representations that differ on the rule applied to refine an initial coarse mesh: one is based on tetrahedron bisection, and one based on vertex split. The two representations can be viewed as instances of a common multiresolution model, that we call a multiresolution mesh. Encoding data structures for the two representations are briefly described. An experimental comparison on structured volume data sets is presented.

Techniques are presented for moving between adjacent tetrahedra in a tetrahedral mesh. The tetrahedra result from a recursive decomposition of a cube into six initial congruent tetrahedra. A new technique is presented for labeling the triangular faces. The labeling enables the implementation of a binary-like decomposition of each tetrahedron which is represented using a pointerless representation. Outlines of algorithms are given for traversing adjacent triangular faces of equal size in constant time.

We present a new data structure, called the Multi-Sculpture, to represent 3D shapes at multiple levels of detail. The input shape at high resolution is described as a mesh of triangles. A coarse approximation of this shape is provided by the convex hull of the mesh, while intermediate approximations are obtained by sculpturing the space that separates the convex hull from the mesh. A higher level of detail corresponds to a higher degree of concavity in the shape approximation. The data structure supports online extraction of a shape representation at a user-defined level of detail, possibly varing over different parts of the shape. This mechanism allows speeding up recognition, classification, collision detection, and planning of manipulation tasks.

We address the problem of reconstructing the shape of a solid object from sparse data, and of representing it at multiple levels of detail. We provide a multiresolution model, based on a set of local sculpturing updates on an initial tetrahedral mesh, which supports extraction of representations at an arbitrary level of detail. We present a new sculpturing algorithm that we use to build the multiresolution model.

Multi-triangulation (MT) is a general framework for managing the level-of-detail in large triangle meshes, which we have introduced in our previous work. In this paper, we describe an efficient implementation of an MT based on vertex decimation. We present general techniques for querying an MT, which are independent of a specific application, and which can be applied for solving problems, such as selective refinement, windowing, point location, and other spatial interference queries. We describe alternative data structures for encoding an MT, which achieve different trade-offs between space and performance. Experimental results are discussed.

The authors consider the multi-triangulation, a general model for representing surfaces at variable resolution based on triangle meshes. They analyse characteristics of the model that make it effective for supporting basic operations such as extraction of a surface approximation, and point location. An interruptible algorithm for extracting a representation at a resolution variable over the surface is presented. Different heuristics for building the model are considered and compared. Results on both the construction and the extraction algorithm are presented.

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.

A new hierarchical triangle-based model for representing surfaces over sampled data is proposed, which is based on the subdivision of the surface domain into nested triangulations, called a hierarchical triangulation (HT) . The model allows compression of spatial data and representation of a surface at successively finer degrees of resolution. An HT is a collection of triangulations organized in a tree, where each node, except for the root, is a triangulation refining a face belonging to its parent in the hierarchy. We present a topological model for representing an HT, and algorithms for its construction and for the extraction of a triangulation at a given degree of resolution. The surface model, called a hierarchical triangulated surface (HTS) is obtained by associating data values with the vertices of triangles, and by defining suitable functions that describe the surface over each triangular patch. We consider an application of a piecewise-linear version of the HTS to interpolate topographical data, and we describe a specialized version of the construction algorithm that builds an HTS for a terrain starting from a high-resolution rectangular grid of sampled data. Finally, we present an algorithm for extracting representations of terrain at variable resolution over the domain.

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.

Abstract The Hierarchical Triangulated Irregular Network (HTIN) is a structure for representing 2½‐dimensional surfaces at different levels of detail through piecewise‐linear approximations based on triangulations of the surface domain. In this paper, we present two algorithms that allow extracting a representation of the surface and contour lines at a given level of detail, directly from the HTIN.

Modular boundary models are a class of solid models which describe a solid object as a collection of face-abutting object parts, called components. The Face-to-Face Composition (FFC) model is a specific model of this class, which encodes both the connection and the interference information among object components. Necessary and sufficient conditions for an FFC model to be valid are defined in terms of a representation of the FFC model, called the FFC graph. The problem of producing valid FFC models from the decomposition of the FFC model of a given object into subobjects is studied in connection with the generation of a production graph.

HIDEL (HIerarchical DEscription Language) is a new language for structural description of hardware systems. The use of HIDEL allows a modular and hierarchical description of a hardware system. HIDEL can be integrated with a data model, called the Hierarchical Hypergraph with Ports (HHP), which provides a graph-based description of a VLSI object at different levels of specification. The possibility of extending the HIDEL-HHP environment with functional description for simulation is also investigated.

The authors briefly recapitulate the face-to-face composition (FFC) model for the representation and manipulation of topological and geometric entities. They then summarize L.S. Homem de Mello's and A. Sanderson's (1988) proposal for assembly planning. It is shown that the assembly AND/OR graph proposed by L.S. Homem de Mello and A. Sanderson for task planning is an efficient data structure showing all possible assembly sequences. It can be obtained directly from the FFC model by a sequence of component-merging operations.>

An algorithm for extracting certain classes of form features from a relational boundary model of an object, called the generalized edge-face graph (GEFG), is described. The GEFG provides a face-based topological description of the object boundary and encodes the minimum number of relations needed in the recognition process. The feature identification and classification are based on the analysis of the connectivity properties of the edge-face graph associated with the GEFG and on some geometric considerations. The result is a hierarchical graph decomposition of the object boundary into components representing form features.>

The problem of building a constrained Delaunay triangulation (CDT) at different levels of resolution is considered for the hierarchical description of topographic surfaces. The surface is approximated at each level by a network of planar triangular faces having vertices at a subset of surface-specific points, such as peaks, pits, or passes, and including edges that describe surface-specific lines, such as ridges or valleys. Each approximation is built based on a Delaunay triangulation of the data points that includes the given constraint segments. A dynamic algorithm for constrained Delaunay triangulation is proposed. The algorithm is based on the stepwise refinement of a CDT by the incremental insertion of points and constraint segments.>

The face-to-face composition (FFC) graph is the formal representation of a family of models of solid objects for advanced engineering applications. It is a multirooted hierarchical structure based on boundary representation and is capable of accommodating different conceptual views of the same object or assembly. A node of the FFC graph describes a volumetric object component consisting of a single shell, while its arcs correspond to connection faces between pairs of single components. Operators are available both for modifying the object and for changing the representation. Node groups define a correct order of evaluation of the FFC graph which produces a valid solid object at each step. The model also includes a formal definition of the notion 'feature-of' as an open subgraph corresponding to constructs not necessarily realizable on their own, such as rivet holes with pads.>

A new hierarchical model for solid object representation is described. This model, called a hierarchical face adjacency hypergraph (HFAH), is based on a relational description of the object boundary, called a face adjacency hypergraph (FAH), which considers faces as the primary topological entities defining the object boundary. The HFAH consists of a hierarchy of FAHs describing the decomposition of the boundary of an object into form features. In this paper the HFAH is described together with its internal encoding structure. Two basic transformations, called refinement and abstraction , are defined on the hierarchical model; these allow effective and efficient modifications of the hierarchical boundary model.

Shape features, such as protrusions or depressions on faces, and through-holes or handles, are extracted from a boundary model of a solid object, called a Generalized Edge-Face Graph (GEFG). This graph provides a face-based topological description of the object boundary. The feature identification and classification are based on the analysis of the connectivity properties of the edge-face graph associated with the GEFG and on some geometric considerations. The result is a hierarchical graph decomposition of the object boundary into components representing features.

A structured graph is a hierarchy of graphs which provides a representation of a graph at variable detail levels. In this paper we investigate the path problem in a structured graph. The concept of structured graph is defined, and a formal definition of path in such a structure is given. The relationship between structured paths and canonical ones in the graph represented by a structured graph is investigated. Algorithms to construct paths and to compute a structured path from a given canonical one are presented.

A relational graph structure based on a boundary representation of solid objects is described. In this structure, called face adjacency graph, nodes represent object faces, whereas edges and vertices are encoded into arcs and hyperarcs. Based on the face adjacency graph, we define a set of primitive face-oriented Euler operators, and a set of macrooperators for face manipulation, which allow a compact definition and an efficient updating of solid objects. We briefly describe a hierarchical graph structure based on the face adjacency graph, which provides a representation of an object at different levels of detail. Thus it is consistent with the stepwise refinement process through which the object description is produced.

Abstract We propose a relational scheme for representing and modelling regular objects, which is based on the adjacency relations between faces and edges. In this structure, called edge‐face graph, the nodes represent the faces and the arcs the edges of the corresponding object. Other topological entities, such as vertices, loops of edges, and shells, can be obtained from this relational scheme. We give a formal description of the edge‐face graph, and the relationships between its properties and the topological entities of the object are analyzed in detail. Furthermore, a set of basic Euler operators based on the edge‐face adjacency relation is denned, which allow the incremental manipulation of boundary representations of solid objects.

Abstract A C1 interpolation scheme is described, which is defined over triangular grids. The interpolant is computed on the basis of curves with tension, which permit local control over the shape of the resulting surface.

Abstract We present the results of our experience in introducing modularity into the programming language Pascal in order to aid the creation and use of library modules. Our system performs the symbolic linking of source language modules producing a single Pascal text ready for compilation; performing the link phase before compilation anticipates interface consistency checks, and suggests a possible improvement of program development systems. Our extension is implemented in a preprocessor which ensures a complete compatibility with any standard Pascal compiler. In this paper we examine the main features of some high‐level programming languages which support modularization and data abstraction and some experiences in introducing modularity into Pascal; on this basis we describe our choice in detail. The design and implementation details are discussed and some examples are presented.

This paper describes a method for constructing a surface representation model from a given set of data points.A Triangulated Irregular. Network has been chosen as data structure, thus representing the surface as a set of contiguous non -overlapping and irregurarly shaped triangular facets.The proposed method makes use of a Delaunay triangular grid adapted to non-convex domains. Using only representative subsets of the given set of points, the method allows the construction of approximating surfaces which rest within a predefined tolerance.