Individual Tree Mapping from LiDAR point clouds based on topological tools
Federico Iuricich, Xin Xu and Leila De Floriani
Shape Modeling International 2017 - poster
[bibtex] [poster]

Hierarchical Forman Triangulation: A multiscale model for scalar field analysis
Federico Iuricich and Leila De Floriani
Computers & Graphics
[bibtex] [paper] [doi]

abstract We consider the problem of analyzing the topology of scalar fields defined on a triangulated shape by using a multi-scale approach, which allows reducing storage costs and computation times, and supports interactive inspection and classification of topological features. We define and implement a multi-scale model that we call a Hierarchical Forman Triangulation (HFT) , where a 3D shape or a terrain is discretized as a triangle mesh, and its topology is described by defining a discrete Morse gradient field based on function values given at the vertices of the mesh. We introduce a new edge contraction operator, which does not change the behavior of the gradient flow and does not create new critical points, and we apply it in combination with a topological simplification operator which eliminates critical elements in pair. By combining the two operators in a sequence, we generate the HFT . We discuss and implement a compact encoding for the HFT that has a lower storage cost with respect to the triangle mesh at full resolution. We show the effectiveness of this new hierarchical model by extracting representations of terrains and shapes endowed with a scalar field at different, uniform and variable, scales and by efficiently computing topological features and segmentations.

The Stellar tree: a Compact Representation for Simplicial Complexes and Beyond
Riccardo Fellegara, Kenneth Weiss and Leila De Floriani
ArXiv e-prints
[bibtex] [paper] [doi]

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
Riccardo Fellegara, Federico Iuricich and Leila De Floriani
ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '17)
[bibtex] [paper] [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.

Analysis of geolocalized social networks based on simplicial complexes
Riccardo Fellegara, Ulderico Fugacci, Federico Iuricich and Leila De Floriani
9th ACM SIGSPATIAL International Workshop on Location-Based Social Networks (LBSN), 2016
[bibtex] [paper] [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 Discrete Morse-based Approach to Multivariate Data Analysis
F. Iuricich, S. Scaramuccia, C. Landi and L. De Floriani
SIGGRAPH ASIA 2016 Symposium on Visualization, vol. 5, pages 1 - 8, 2016
[bibtex] [paper] [doi]

abstract Multivariate data are becoming more and more popular in several applications, including physics, chemistry, medicine, geography, etc. A multivariate dataset is represented by a cell complex and a vector-valued function defined on the complex vertices. The major challenge arising when dealing with multivariate data is to obtain concise and effective visualizations. The usability of common visual elements (e.g., color, shape, size) deteriorates when the number of variables increases. Here, we consider Discrete Morse Theory (DMT) for computing a discrete gradient field on a multivariate dataset. We propose a new algorithm, well suited for parallel and distribute implementations. We discuss the importance of obtaining the discrete gradient as a compact representation of the original complex to be involved in the computation of multidimensional persistent homology. Moreover, the discrete gradient field that we obtain is at the basis of a visualization tool for capturing the mutual relationships among the different functions of the dataset.

An efficient approach for verifying manifold properties of simplicial complexes
Riccardo Fellegara, Kenneth Weiss Leila De Floriani
25th International Meshing Roundtable (IMR '16), 2016
[bibtex] [paper] [doi]

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.

Homological Shape Analysis Through Discrete Morse Theory
L. De Floriani, U. Fugacci and F. Iuricich
Perspectives in Shape Analysis: 187-209, 2016
[bibtex] [paper] [doi]

abstract Homology and persistent homology computation are fundamental tools for shape analysis and understanding that recently gathered a lot of interest, in particular for analyzing multidimensional data. In this context discrete Morse theory, a combinatorial counterpart of smooth Morse theory, provides an excellent basis for reducing computational complexity in homology detection. A discrete Morse complex, computed over a given complex discretizing a shape, drastically reduces the number of cells of the latter while maintaining the same homology. Here, we consider the problem of shape analysis through discrete Morse theory, and we review and analyze algorithms for computing homology and persistent homology based on such theory.

A Survey of Topology-based Methods in Visualization
C. Heine, H. Leitte, M. Hlawitschka, F. Iuricich, L. De Floriani, G. Scheuermann, H. Hagen, C. Garth
Computer Graphics Forum, Volume 35, Number 3: 643-667, 2016
[bibtex] [doi]

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.

Computing a discrete Morse gradient from a watershed decomposition
L. Comic, L. De Floriani, F. Iuricich and P. Magillo
In Computers and Graphics, vol. 58, pages 43 - 52, Shape Modeling International - Berlin, Germany - June 20-24, 2016
[bibtex] [paper] [doi]

abstract We consider the problem of segmenting triangle meshes endowed with a discrete scalar function ff based on the critical points of ff. The watershed transform induces a decomposition of the domain of function ff into regions of influence of its minima, called catchment basins. The discrete Morse gradient induced by ff allows recovering not only catchment basins but also a complete topological characterization of the function and of the shape on which it is defined through a Morse decomposition. Unfortunately, discrete Morse theory and related algorithms assume that the input scalar function has no flat areas, whereas such areas are common in real data and are easily handled by watershed algorithms. We propose here a new approach for building a discrete Morse gradient on a triangulated 3D shape endowed by a scalar function starting from the decomposition of the shape induced by the watershed transform. This allows for treating flat areas without adding noise to the data. Experimental results show that our approach has significant advantages over existing ones, which eliminate noise through perturbation: it is faster and always precise in extracting the correct number of critical elements.

Analysis of geolocalized social networks based on simplicial complexes
Riccardo Fellegara, Ulderico Fugacci, Federico Iuricich and Leila De Floriani
9th ACM SIGSPATIAL International Workshop on Location-Based Social Networks (LSBN), 2016
[bibtex] [paper] [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.

Topologically-consistent simplification of discrete Morse complex
F. Iuricich, U. Fugacci and L. De Floriani
In Computer and Graphics, vol. 34, pages 157 - 166, 2015
[bibtex] [paper] [doi] [presentation]

Honorable Mention
abstract We address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm.

Supertetras: a Superpixel Analog for Tetrahedral Mesh Oversegmentation
G. Picciau, P. Simari, F. Iuricich, L. De Floriani
18th International Conference on Image Analysis and Processing, 7-11 September 2015, Genova, Italy.
[bibtex] [paper] [doi]

abstract Over the past decade, computer vision algorithms have transitioned from relying on the direct, pixel-based representation of images to the use of superpixels, small regions whose boundaries agree with image contours. This intermediate representation improves the tractability of image understanding because it reduces the number of primitives to be taken under consideration from several million to a few hundred. Despite the improvements yielded in the area of image segmentation, the concept of an oversegmentation as an intermediate representation has not been adopted in volumetric mesh processing. We take a first step in this direction, adapting a fast and efficient superpixel algorithm to the tetrahedral mesh case, present results which demonstrate the quality of the output oversegmentation, and illustrate its use in a semantic segmentation application.

Morse complexes for shape segmentation and homological analysis: discrete models and algorithms
L. De Floriani, U. Fugacci, F. Iuricich, P. Magillo
In Computer Graphics Forum 34(2), pages 761--785, 2015.
[bibtex] [paper] [doi] [presentation]

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.

A Combined Geometrical and Topological Simplification Hierarchy for Terrain Analysis
F. Iuricich and L. De Floriani
22st International Conference on Advances in Geographic Information Systems (SIGSPATIAL), Dallas, Texas, USA, November 4-7 2014, (2014)
[bibtex] [paper] [doi] [poster]

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

Efficient computation and simplification of discrete Morse decompositions on triangulated terrains
R. Fellegara, F. Iuricich, L. De Floriani and K. Weiss
22st International Conference on Advances in Geographic Information Systems (SIGSPATIAL), Dallas, Texas, USA, November 4-7 2014, (2014)
[bibtex] [paper] [doi] [presentation]

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.

Representing Simplicial Complexes with Mangroves
David Canino, Leila De Floriani
22nd International Meshing Roundtable, 2014
[bibtex] [doi]

abstract Simplicial complexes are extensively used for discretizing digital shapes in two, three, and higher dimensions within a variety of application domains. There have been many proposals of topological data structures, which represent the connectivity information among simplices. We introduce the Mangrove Topological Data Structure (Mangrove TDS) framework, a tool which supports the efficient implementation of data structures for simplicial complexes of any dimension under the same application interface. Our framework is based on a graph-based representation of connectivity relations, that we call the mangrove. It can be customized in order to simulate the content of any topological data structure with a negligible overhead. Thus, the Mangrove TDS framework is extensible, and supports the most diverse modeling needs. We also provide implicit representations of those simplices, which are not directly encoded in a specific topological data structure. Our tests show that these representations, that we call ghost simplices, improve the expressive power and the efficiency of topological queries. In order to prove the validity of our approach, we design two topological data structures, specificc for non-manifold complexes, within our framework. We perform comparisons with some widely-used representations in the literature as well as with libraries available in the public domain

Topological modifications and hierarchical representation of cell complexes in arbitrary dimensions
L. Comic, L. De Floriani, F. Iuricich and U. Fugacci
Computer Vision and Image Understanding, 121: 2-12 (2014).
[bibtex] [paper] [doi]

abstract We propose a set of atomic modeling operators for simplifying and refining cell complexes in arbitrary dimensions. Such operators either preserve the homology of the cell complex, or they modify it in a controlled way. We show that such operators form a minimally complete basis for updating cell complexes, and we compare them with various operators previously proposed in the literature. Based on the new operators, we define a hierarchical model for cell complexes, that we call a Hierarchical Cell Complex (HCC), and we discuss its properties. An HCC implicitly encodes a virtually continuous set of complexes obtained from the original complex through the application of our operators. Then, we describe the implementation of a version of the HCC based on the subset of the proposed modeling operators which preserve homology. We apply the homology-preserving HCC to enhance the efficiency in extracting homology generators at different resolutions. To this aim, we propose an algorithm which computes homology generators on the coarsest representation of the original complex, and uses the hierarchical model to propagate them to complexes at any intermediate resolution, and we prove its correctness. Finally, we present experimental results showing the efficiency and effectiveness of the proposed approach.

Efficient Computation of Simplicial Homology Through Acyclic Matching
U. Fugacci, L. De Floriani, F. Iuricich
16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014, Timisoara, Romania, September 22-25, 2014
[bibtex] [paper] [doi] [presentation]

abstract We consider the problem of efficiently computing homology with Z coefficients as well as homology generators for simplicial complexes of arbitrary dimension. We analyze, compare and discuss the equivalence of different methods based on combining reductions, coreductions and discrete Morse theory. We show that the combination of these methods produces theoretically sound approaches which are mutually equivalent. One of these methods has been implemented for simplicial complexes by using a compact data structure for representing the complex and a compact encoding of the discrete Morse gradient. We present experimental results and discuss further developments.

Fast and Scalable Mesh Superfacets
Patricio Simari, Giulia Picciau, Leila De Floriani
Computer Graphics Forum, 2014
[bibtex] [doi]

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.

Morphological Modeling of Terrains and Volume Data
L. Comic, L. De Floriani, P. Magillo and F. Iuricich
Springer Briefs in Computer Science, Springer 2014. ISBN: 978-1-4939-2148-5
[bibtex] [doi]

abstract Scalar fields are real-valued functions defined point-wise within a $d$-dimensional domain. They appear in many applications, including physics, chemistry, medicine, geography, etc., and represent real or simulated phenomena characterized by a spatial extension. The most common example are height fields which describe terrains and have been studied extensively in Geographic Information Systems (GISs) and scientific visualization. Scalar fields can also be defined on shapes (which describe the surface of an object in 3D) to represent some point-wise defined property on them (such as curvature). As $d$-dimensional domains are discretized (e.g., as d-dimensional images composed of voxels) and so are shapes (e.g., a surface tessellated as a mesh of triangles), scalar fields defined on them have a discrete representation: usually, field values are associated with the voxels of an image or with the vertices of a mesh. This provides a detailed representation of the scalar field. Thanks to hardware and software development, available data representing both the field and its domain are increasing in size and complexity. On the other hand, a detailed representation is verbose and not suitable to analysis tasks such as recognition and classification. Therefore, the issue arises to switch from representation to description of a scalar field. While a representation provides all details necessary to know the field point-wise, a description is more abstract and has the purpose of showing the main characteristics of the field, such as, for instance, its maxima/minima/saddles and their relative positions. This book focuses on morphological descriptions of scalar fields, mainly in 2D (height fields, or terrains) and 3D (volume data). Specifically, we consider morphological descriptions based on identifying maxima, minima and saddles, finding their influence zones, and encoding their mutual spatial relations. All this is formalized through Morse theory, Morse and Morse-Smale complexes. We provide the mathematical background, which has been formally defined for smooth functions and then transposed into a discrete setting in different ways. We introduce the main algorithmic approaches and their characteristics, and present algorithms for discrete scalar fields in two and three dimensions, and (where possible) in general dimensions. Although morphological descriptions based on Morse and Morse-Smale complexes represent scalar fields in a much more compact way than the initial geometric representation, simplification of these complexes is often necessary. Simplification allows disregarding less meaningful morphological features, or spurious features, due to noise in the data, as well as adapting the level of abstraction of the description to the current application task. Therefore, we present simplification operators which act on the morphological description of a scalar field. The issue of simplification comes along with that of multi-resolution, which requires being able to build a compact model encompassing different levels of detail (corresponding to different degrees of simplification), in such a way that the appropriate level of detail can be extracted on the fly according to user-defined criteria. This book is organized as follows. Chapter 1 contains the necessary mathematical background on Morse theory in the smooth and in the discrete case. Chapter 2 presents a classification of existing algorithms for morphological computation based on different and often orthogonal criteria, where the main criterion is the algorithmic approach they use. Such a criterion identifies boundary-based and region-growing methods (which essentially deal with 2D and 3D scalar fields), watershed-based and methods based on a discrete Morse theory due to Forman (which are dimension-independent). The next three chapters present a survey of algorithms belonging to the first two classes (Chap.3), of watershed-based algorithms (Chap.4) and of Forman-based algorithms (Chap.5). Chapter 6 considers the issues related to simplification and multi-resolution. Finally, Chap.7 presents experimental comparisons and draw concluding remarks.

Generalized extrinsic distortion and applications
P. D. Simari, L. De Floriani, F. Iuricich and M. M. Mesmoudi
Computers and Graphics 37(6): 582-588 (2013).
[bibtex] [paper] [doi]

abstract Curvature is a key feature in shape analysis and its estimation on discrete simplicial complexes benefits many geometry processing applications. However, its study has mostly remained focused on 2D manifolds and computationally practical extensions to higher dimensions remain an active area of computer science research. We examine the existing notions of distortion, an analog of curvature in the discrete setting, and classify them into two categories: intrinsic and extrinsic, depending on whether they use the interior or the dihedral angles of the tessellation. We then propose a generalization of extrinsic distortion to D and derive a weighting that can be used to compute mean curvature on tessellated hypersurfaces. We analyze the behavior of the operator on 3-manifolds in 4D and compare it to the well-known Laplace–Beltrami operator using ground truth hypersurfaces defined by functions of three variables, and a segmentation application, showing it to behave as well or better while being intuitively simple and easy to implement

Morphologically-aware elimination of flat edges from a TIN
P. Magillo, L. De Floriani and F. Iuricich
21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2013): 244-253. November 5-8, 2013, Orlando, Florida, USA
[bibtex] [paper] [doi]

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

Simplification Operators on a Dimension-Independent Graph-Based Representation of Morse Complexes
L. Comic, L. De Floriani and F. Iuricich
11th International Symposium on Mathematical Morphology: 13-24. May 27-29 2013, Uppsala, Sweden.
[bibtex] [paper] [doi]

abstract Ascending and descending Morse complexes are defined by the critical points and integral lines of a scalar field f defined on a manifold M. They induce a subdivision of M into regions of uniform gradient flow, thus providing a compact description of the topology of M and of the behavior of f over M. We represent the ascending and descending Morse complexes of f as a graph, that we call the Morse incidence graph (MIG). We have defined a simplification operator on the graph- based representation, which is atomic and dimension-independent, and we compare this operator with a previous approach to the simplification of 3D Morse complexes based on the cancellation operator. We have developed a simplification algorithm based on a simplification operator, which operates on the MIG, and we show results from this implementation as well as comparisons with the cancellation operator in 3D.

Discrete Morse versus Watershed Decompositions of Tessellated Manifolds
L.De Floriani, F. Iuricich, P. Magillo and P. D. Simari
International Conference on Image Analysis and Processing (ICIAP-2013): 339-348. September 9-13, 2013. Naples, Italy
[bibtex] [paper] [doi]

abstract With improvements in sensor technology and simulation methods, datasets are growing in size, calling for the investigation of efficient and scalable tools for their analysis. Topological methods, able to extract essential features from data, are a prime candidate for the development of such tools. Here, we examine an approach based on discrete Morse theory and compare it to the well-known watershed approach as a means of obtaining Morse decompositions of tessellated manifolds endowed with scalar fields, such as triangulated terrains or tetrahedralized volume data. We examine the theoretical aspects as well as present empirical results based on synthetic and real-world data describing terrains and 3D scalar fields. We will show that the approach based on discrete Morse theory generates segmentations comparable to the watershed approach while being theoretically sound, more efficient with regard to time and space complexity, easily parallelizable, and allowing for the computation of all descending and ascending i-manifolds and the topological structure of the two Morse complexes.

A Compact Representation for Topological Decompositions of Non-manifold Shapes
David Canino, Leila De Floriani
GRAPP/IVAPP, 2013
[bibtex]

abstract Simplicial complexes are extensively used for discretizing digital shapes in several applications. A structural description of a non-manifold shape can be obtained by decomposing the input shape into a collection of meaningful components with a simpler topology. Here, we consider a unique and dimension-independent decomposition of a non-manifold shape into nearly manifold components, known as the Manifold-Connected (MC-) decomposition. We present the Compact Manifold-Connected (MC-) graph, an efficient graph-based representation for the MC-decomposition, which can be combined with any topological data structure for encoding the underlying components. We present the main properties of this representation as well as algorithms for its generation. We also show that this representation is more compact than several topological data structures, which do not explicitly describe the non-manifold structure of a shape

A primal/dual representation for discrete Morse complexes on tetrahedral meshes
K. Weiss, F. Iuricich, R. Fellegara and L. De Floriani
Comput. Graph. Forum 32(3): 361-370.
[bibtex] [paper] [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.

Multi-resolution Cell Complexes Based on Homology-Preserving Euler Operators
L. Comic, L. De Floriani and F. Iuricich
Discrete Geometry for Computer Imagery (DGCI 2013), pages 323-334, 2013
[bibtex] [paper] [doi]

abstract We have proposed a complete set of basis Euler operators for updating cell complexes in arbitrary dimensions, which can be classified as homology-preserving and homology-modifying. Here, we define the effect of homology-preserving operators on the incidence graph representation of cell complexes. Based on these operators, we build a multi- resolution model for cell complexes represented in the form of the incidence graph, and we compare its 2D instance with the pyramids of 2-maps, designed for images.

Modeling Three-Dimensional Morse and Morse-Smale Complexes
L. Comic, L. De Floriani and F. Iuricich
Innovations for Shape Analysis, Models and Algorithms 2013: 3-34.
[bibtex] [paper] [doi]

abstract Morse and Morse-Smale complexes have been recognized as a suitable tool for modeling the topology of a manifold M through a decomposition of M induced by a scalar field f defined over M. We consider here the problem of representing, constructing and simplifying Morse and Morse-Smale complexes in 3D. We first describe and compare two data structures for encoding 3D Morse and Morse-Smale complexes. We describe, analyze and compare algorithms for computing such complexes. Finally, we consider the simplification of Morse and Morse-Smale complexes by applying coarsening operators on them, and we discuss and compare the coarsening operators on Morse and Morse-Smale complexes described in the literature.

Discrete Distortion for 3D Data Analysis
L. De Floriani, F. Iuricich, P. Magillo, M. M. Mesmoudi and K. Weiss
Visualization in Medicine and Life Sciences II 2012: 3-25.
[bibtex] [paper] [doi]

abstract We investigate a morphological approach to the analysis and understanding of three-dimensional scalar fields, and we consider applications to 3D medical and molecular images as examples. We consider a discrete model of the scalar field obtained by discretizing its 3D domain into a tetrahedral mesh. In particular, our meshes correspond to approximations at uniform or variable resolution extracted from a multi-resolution model of the 3D scalar field, that we call a hierarchy of diamonds. We analyze the images based on the concept of discrete distortion, that we have introduced in [26], and on segmentations based on Morse theory. Discrete distortion is defined by considering the graph of the discrete 3D field, which is a tetrahedral hypersurface in R4, and measuring the distortion of the transformation which maps the tetrahedral mesh discretizing the scalar field domain into the mesh representing its graph in R4. We describe a segmentation algorithm to produce Morse decompositions of a 3D scalar field which uses a watershed approach and we apply it to 3D images by using as scalar field both intensity and discrete distortion. We present experimental results by considering the influence of resolution on distortion computation. In particular, we show that the salient features of the distortion field appear prominently in lower resolution approximations to the dataset.

Dimension-independent multi-resolution Morse complexes
L. Comic, L. De Floriani and F. Iuricich
Computers and Graphics 36(5): 541-547.
[bibtex] [paper] [doi]

abstract Morse and Morse–Smale complexes have been recognized as a suitable model for representing topological information extracted from discrete scalar fields. Here, we propose a dimension-independent multi-resolution model for Morse complexes built on a graph representation of the complexes, that we call a Multi-Resolution Morse Incidence Graph (MMIG). We define data structures for encoding the MMIG and we discuss how to extract from an MMIG topological representations of the scalar field over its domain M at both uniform and variable resolutions. We present experimental results evaluating the storage cost of the data structures encoding the MMIG, and timings for building and querying an MMIG.

A Spatial Approach to Morphological Feature Extraction from Irregularly Sampled Scalar Fields
L. De Floriani, F. Iuricich, R. Fellegara and K. Weiss
Proceedings of the Third ACM SIGSPATIAL International Workshop on GeoStreaming (IWGS 2012) 8: 40-47, Redondo Beach, California, USA
[bibtex] [paper] [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.

Analysis and Comparison of Algorithms for Morse Decompositions on Triangulated Terrains
M. Vitali, L. De Floriani, P. Magillo
Technical report DISI-TR-12-03. DISI, University of Genova, 2012
[bibtex] [paper]

abstract We consider the problem of extracting the morphology of a terrain represented as a Triangulated Irregular Network (TIN). Our reference framework to model terrain morphology is given by the descending and the ascending Morse complexes, which define a decomposition of the terrain through its critical points and integral lines. We review several algorithms proposed in the literature to extract descending and ascending Morse complexes, which we have implemented for TINs. We analyze the behavior of such algorithms on real data sets by comparing the output decomposition they produce, based on different metrics.

Topological Operators on Cell Complexes in Arbitrary Dimensions
Lidija Comic, Leila De Floriani
Computational Topology in Image Context, 2012
[bibtex] [doi]

abstract Cell complexes have extensively been used as a compact representation of both the geometry and topology of shapes. They have been the basis modeling tool for boundary representations of 3D shapes, and several dimension-specific data structures and modeling operators have been proposed in the literature. Here, we propose basic topological modeling operators for building and updating cell complexes in arbitrary dimensions. These operators either preserve the topology of the cell complex, or they modify it in a controlled way. We compare these operators with the existing ones proposed in the literature, in particular with handle operators and various Euler operators on 2D and 3D cell complexes.

Concentrated Curvature for Mean Curvature Estimation in Triangulated Surfaces
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
4th International Workshop, CTIC, 2012
[bibtex] [doi]

abstract We present a mathematical result that allows computing the discrete mean curvature of a polygonal surface from the so-called concentrated curvature generally used for Gaussian curvature estimation. Our result adds important value to concentrated curvature as a geometric and metric tool to study accurately the morphology of a surface.

Discrete Curvature Estimation Methods for Triangulated Surfaces
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
Applications of Discrete Geometry and Mathematical Morphology, 2012
[bibtex] [doi]

abstract We review some recent approaches to estimate discrete Gaussian and mean curvatures for triangulated surfaces, and discuss their characteristics. We focus our attention on concentrated curvature which is generally used to estimate Gaussian curvature. We present a result that shows that concentrated curvature can also be used to estimate mean curvature and hence principal curvatures. This makes concentrated curvature one of the fundamental notions in discrete computational geometry.

Modeling and Simplifying Morse Complexes in Arbitrary Dimensions
Lidija Comic, Leila De Floriani
Topological Methods in Data Analysis and Visualization, 2011
[bibtex] [doi]

abstract Ascending and descending Morse complexes, defined by a scalar function f over a manifold domain M, decompose M into regions of influence of the critical points of f, thus representing themorphology of the scalar function f over M in a compact way. Here, we introduce two simplification operators on Morse complexes which work in arbitrary dimensions and we discuss their interpretation as n-dimensional Euler operators. We consider a dual representation of the two Morse complexes in terms of an incidence graph and we describe how our simplification operators affect the graph representation. This provides the basis for defining a multi-scale graph-based model of Morse complexes in arbitrary dimensions.

IA*: An adjacency-based representation for non-manifold simplicial shapes in arbitrary dimensions
David Canino, Leila De Floriani, Kenneth Weiss
Shape Modeling International (SMI) Conference, 2011
[bibtex] [doi]

abstract We propose a compact, dimension-independent data structure for manifold, non-manifold and non-regular simplicial complexes, that we call the Generalized Indexed Data Structure with Adjacencies (IA* data structure). It encodes only top simplices, i.e. the ones that are not on the boundary of any other simplex, plus a suitable subset of the adjacency relations. We describe the IA⁎ data structure in arbitrary dimensions, and compare the storage requirements of its 2D and 3D instances with both dimension-specific and dimension-independent representations. We show that the IA* data structure is more cost effective than other dimension-independent representations and is even slightly more compact than the existing dimension-specific ones. We present efficient algorithms for navigating a simplicial complex described as an IA* data structure. This shows that the IA* data structure allows retrieving all topological relations of a given simplex by considering only its local neighborhood and thus it is a more efficient alternative to incidence-based representations when information does not need to be encoded for boundary simplices.

The PR-star Octree: A spatio-topological data structure for tetrahedral meshes
Kenneth Weiss, Riccardo Fellegara, Leila De Floriani, Marcelo Velloso
ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '11), 2011
[bibtex] [paper] [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.

Simplifying morphological representations of 2D and 3D scalar fields
L. Comic, L. De Floriani and F. Iuricich
19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2011:437-440.
[bibtex] [paper] [doi] [poster]

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

Modeling Multiresolution 3D Scalar Fields through Regular Simplex Bisection
Kenneth Weiss, Leila De Floriani
Scientific Visualization: Interactions, Features, Metaphors, 2011
[bibtex] [doi]

abstract We review modeling techniques for multiresolution three-dimensional scalar fields based on a discretization of the field domain into nested tetrahedral meshes generated through regular simplex bisection. Such meshes are described through hierarchical data structures and their representation is characterized by the modeling primitive used. The primary conceptual distinction among the different approaches proposed in the literature is whether they treat tetrahedra or clusters of tetrahedra, called diamonds, as the modeling primitive. We first focus on representations for the modeling primitive and for nested meshes. Next, we survey the applications of these meshes to modeling multiresolution 3D scalar fields, with an emphasis on interactive visualization. We also consider the relationship of such meshes to octrees. Finally, we discuss directions for further research.

Computing morse decompositions for triangulated terrains: an analysis and an experimental evaluation
Maria Vitali, Leila De Floriani, Paola Magillo
Image Analysis and Processing--ICIAP, 2011
[doi]

abstract We consider the problem of extracting the morphology of a terrain discretized as a triangle mesh. We discuss first how to transpose Morse theory to the discrete case in order to describe the morphology of triangulated terrains. We review algorithms for computing Morse decompositions, that we have adapted and implemented for triangulated terrains. We compare the the Morse decompositions produced by them, by considering two different metrics.

Dimension-independent simplification and refinement of Morse complexes
Lidija Comic, Leila De Floriani
Graphical Models, 2011
[bibtex] [doi]

abstract Ascending and descending Morse complexes, determined by a scalar field f defined over a manifold M, induce a subdivision of M into regions associated with critical points of f, and compactly represent the topology of M. We define two simplification operators on Morse complexes, which work in arbitrary dimensions, and we define their inverse refinement operators. We describe how simplification and refinement operators affect Morse complexes on M, and we show that these operators form a complete set of atomic operators to create and update Morse complexes on M. Thus, any operator that modifies Morse complexes on M can be expressed as a suitable sequence of the atomic simplification and refinement operators we have defined. The simplification and refinement operators also provide a suitable basis for the construction of a multi-resolution representation of Morse complexes.

A Decomposition-based Approach to Modeling and Understanding Arbitrary Shapes
David Canino, Leila De Floriani
Eurographics Italian Chapter Conference, 2011
[bibtex] [doi]

abstract Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a representation for arbitrary shapes, that we call Manifold-Connected Decomposition (MC-decomposition), which is based on a unique decomposition of the shape into nearly manifold parts. We present efficient and powerful two-level representations for non-manifold shapes based on the MC-decomposition and on an efficient and compact data structure for encoding the underlying components. We describe a dimension-independent algorithm to generate such decomposition. We also show that the MC-decomposition provides a suitable basis for geometric reasoning and for homology computation on non-manifold shapes. Finally, we present a comparison with existing representations for arbitrary shapes.

GPU algorithms for diamond-based multiresolution terrain processing
M Adil Yalcin, Kenneth Weiss, Leila De Floriani
Eurographics Symposium on Parallel Graphics and Visualization, 2011
[bibtex] [doi]

abstract We present parallel algorithms for processing, extracting and rendering adaptively sampled regular terrain datasets represented as a multiresolution model defined by a super-square-based diamond hierarchy. This model represents a terrain as a nested triangle mesh generated through a series of longest edge bisections and encoded in an implicit hierarchical structure, which clusters triangles into diamonds and diamonds into super-squares. We decompose the problem into three parallel algorithms for performing: generation of the diamond hierarchy from a regularly distributed terrain dataset, selective refinement on the diamond hierarchy and generation of the corresponding crack-free triangle mesh for processing and rendering. We avoid the data transfer bottleneck common to previous approaches by processing all data entirely on the GPU. We demonstrate that this parallel approach can be successfully applied to interactive terrain visualization with a high tessellation quality on commodity GPUs.

Smale-Like Decomposition and Forman Theory for Discrete Scalar Fields
Lidija Comic, Mohammed Mostefa Mesmoudi, Leila De Floriani
Discrete Geometry for Computer Imagery, 2011
[bibtex] [doi]

abstract Forman theory, which is a discrete alternative for cell complexes to the well-known Morse theory, is currently finding several applications in areas where the data to be handled are discrete, such as image processing and computer graphics. Here, we show that a discrete scalar field f, defined on the vertices of a triangulated multidimensional domain Σ, and its gradient vector field Grad f through the Smale-like decomposition of f [6], are both the restriction of a Forman function F and its gradient field Grad F that extends f over all the simplexes of Σ. We present an algorithm that gives an explicit construction of such an extension. Hence, the scalar field f inherits the properties of Forman gradient vector fields and functions from field Grad F and function F.

Simplex and Diamond Hierarchies: Models and Applications
Kenneth Weiss, Leila De Floriani
Computer Graphics Forum, 2011
[bibtex] [doi]

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

An iterative algorithm for homology computation on simplicial shapes
Dobrina Boltcheva, David Canino, Sara Merino Aceituno, Jean-Claude Léon, Leila De Floriani, Franck Hétroy
Computer-Aided Design, 2011
[bibtex] [doi]

abstract We propose a new iterative algorithm for computing the homology of arbitrary shapes discretized through simplicial complexes. We demonstrate how the simplicial homology of a shape can be effectively expressed in terms of the homology of its sub-components. The proposed algorithm retrieves the complete homological information of an input shape including the Betti numbers, the torsion coefficients and the representative homology generators. To the best of our knowledge, this is the first algorithm based on the constructive Mayer–Vietoris sequence, which relates the homology of a topological space to the homologies of its sub-spaces, i.e. the sub-components of the input shape and their intersections. We demonstrate the validity of our approach through a specific shape decomposition, based only on topological properties, which minimizes the size of the intersections between the sub-components and increases the efficiency of the algorithm.

Concentrated Curvature for Mean Curvature Estimation
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
WADGMM, 2010
[bibtex]

abstract We present a mathematical result that allows computing the discrete mean curvature of a polygonal surface from the so-called concentrated curvature generally used for Gaussian curvature estimation. Our result adds important value to concentrated curvature as a geometric and metric tool to study accurately the morphology of a surface.

Nested refinement domains for tetrahedral and diamond hierarchies
Kenneth Weiss, Leila De Floriani
IEEE Visualization, 2010
[bibtex] [doi]

abstract We investigate several families of polyhedra defining nested refinement domains for hierarchies generated through longest edge tetrahedral bisection. We define the descendant domain of a tetrahedron as the domain covered by all possible descendants generated by conforming bisections. Due to the fractal nature of these shapes, we propose two simpler approximations to the descendant domain that are relatively tight with respect to the descendant domain and can be implicitly computed at runtime. We conclude with a brief discussion of the applications of these shapes for interactive view-dependent volume visualization and isosurface extraction.

Isodiamond hierarchies: An efficient multiresolution representation for isosurfaces and interval volumes
Kenneth Weiss, Leila De Floriani
IEEE Transactions on Visualization and Computer Graphics, 2010
[bibtex] [doi]

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

Spatial Indexing on Tetrahedral Meshes
Leila De Floriani, Riccardo Fellegara and Paola Magillo
ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '10), 2010
[bibtex] [paper] [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.

Bisection-based triangulations of nested hypercubic meshes
Kenneth Weiss, Leila De Floriani
Proceedings of the 19th International Meshing Roundtable, 2010
[bibtex] [doi]

abstract Hierarchical spatial decompositions play a fundamental role in many disparate areas of scientific and mathematical computing since they enable adaptive sampling of large problem domains. Although the use of quadtrees, octrees, and their higher dimensional analogues is ubiquitous, these structures generate meshes with cracks, which can lead to discontinuities in functions defined on their domain. In this paper, we propose a dimension-independent triangulation algorithm based on regular simplex bisection to locally decompose adaptive hypercubic meshes into high quality simplicial complexes with guaranteed geometric and adaptivity constraints.

A dimension-independent data structure for simplicial complexes
Leila De Floriani, Annie Hui, Daniele Panozzo, David Canino
Proceedings of the 19th International Meshing Roundtable, 2010
[bibtex] [doi]

abstract We consider here the problem of representing non-manifold shapes discretized as d-dimensional simplicial Euclidean complexes. To this aim, we propose a dimension-independent data structure for simplicial complexes, called the Incidence Simplicial (IS) data structure, which is scalable to manifold complexes, and supports efficient navigation and topological modifications. The IS data structure has the same expressive power and exibits performances in query and update operations as the incidence graph, a widely-used representation for general cell complexes, but it is much more compact. Here, we describe the IS data structure and we evaluate its storage cost. Moreover, we present efficient algorithms for navigating and for generating a simplicial complex described as an IS data structure. We compare the IS data structure with the incidence graph and with dimension-specific representations for simplicial complexes.

Modeling and generalization of discrete Morse terrain decompositions
Leila De Floriani, Paola Magillo, Maria Vitali
20th International Conference on Pattern Recognition (ICPR), 2010
[bibtex] [doi]

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

Multiresolution analysis of 3D images based on discrete distortion
Kenneth Weiss, Leila De Floriani, Mohammed Mostefa Mesmoudi
20th International Conference on Pattern Recognition (ICPR), 2010
[bibtex] [doi]

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

TopMesh - A Tool for Extracting Topological Information from Non-manifold Objects
Leila De Floriani, Laura Papaleo, Annie Hui
Proceedings of the International Conference on Computer Graphics Theory and Applications, 2010
[bibtex] [paper]

abstract We present TopMesh, a tool for extracting topological information from non-manifold three-dimensional objects with parts of non-uniform dimensions. The boundary of such objects is discretized as a mesh of triangles and of dangling edges, representing one-dimensional parts of the object. The geometrical and topological information extracted include the number of elements in the mesh, the number of non-manifold singularities and the Betti numbers, which characterize the topology of an object independently of the discretization of its boundary. TopMesh also computes a decomposition of the mesh into connected parts of uniform dimension, into edge-connected components formed by triangles, and into oriented edge-connected sub-meshes. We describe the functionalities of TopMesh and the algorithms implementing them.

A Geometric Approach to Curvature Estimation on Triangulated 3D Shapes
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
International Conference on Computer Graphics Theory and Applications, 2010
[bibtex] [paper]

abstract We present a geometric approach to define discrete normal, principal, Gaussian and mean curvatures, that we call Ccurvature. Our approach is based on the notion of concentrated curvature of a polygonal line and a simulation of rotation of the normal plane of the surface at a point. The advantages of our approach is its simplicity and its natural meaning. A comparison with widely-used discrete methods is presented

Manual Segmentation and Semantic-based Hierarchical Tagging of 3D models
Laura Papaleo, Leila De Floriani
Eurographics Italian Chapter Conference, 2010
[bibtex] [doi]

abstract Today 3D objects have become widely available in different application domains, thus it is becoming fundamental to use, integrate and develop techniques for extracting and maintaining their implicit knowledge. These techniques should be encapsulated in intelligent systems able to semantically annotate the 3D models, thus improving their usability and indexing, especially in innovative web cooperative environments. In our work, we are moving in this direction, by defining and developing data structures, methods and interfaces for structuring and semantically annotating 3D complex models (and scenes), even changing over time, according to ontology-driven metadata. In this paper, we focus on tools and methods for manually segmenting manifold 3D models and on the underline structural representation that we build and manipulate. We present also an interface from which the user can inspect and browse the segmentation, describing also the first prototype of an annotation tool which allows a hierarchical semantic-driven tagging of the segmented model.

Building and Generalizing Morphological Representations for 2D and 3D Scalar Fields
L. Comic,L. De Floriani and F. Iuricich
Eurographics Italian Chapter Conference 2010: 103-110, Genova, Italy
[bibtex] [paper] [doi]

abstract Ascending and descending Morse complexes, defined by the critical points and integral lines of a scalar field f defined on a manifold domain D, induce a subdivision of D into regions of uniform gradient flow, and thus provide a compact description of the morphology of f on D. Here, we propose a dimension independent representation for the ascending and descending Morse complexes, and a data structure which assumes a discrete representation of the field as a simplicial mesh, that we call the incidence-based data structure. We present algorithms for building such data structure for 2D and 3D scalar fields, which make use of a watershed approach to compute the cells of the Morse decompositions. We describe generalization operators for Morse complexes in arbitrary dimensions, we discuss their effect and present results of our implementation of their 2D and 3D instances both on the Morse complexes and on the incidence-based data structure.

Multiresolution morse triangulations
Emanuele Danovaro, Leila De Floriani, Paola Magillo, Maria Vitali
Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, 2010
[bibtex] [doi]

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

Spatial Indexing on Tetrahedral Meshes
Leila De Floriani, Riccardo Fellegara and Paola Magillo
ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '10)
[bibtex] [paper] [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.

Supercubes: A high-level primitive for diamond hierarchies
Kenneth Weiss, Leila De Floriani
IEEE Transactions on Visualization and Computer Graphics, 2009
[bibtex] [doi]

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

Classification of non-manifold singularities from transformations of 2-manifolds
J.-C. Leon, L. De Floriani, F. Hetroy
IEEE International Conference on Shape Modeling and Applications, 2009
[bibtex] [doi]

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

Morphology analysis of 3D scalar fields based on Morse theory and discrete distortion
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009
[bibtex] [doi]

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

Semantic-based segmentation and annotation of 3D models
Laura Papaleo, Leila De Floriani
Image Analysis and Processing--ICIAP, 2009
[bibtex] [doi]

abstract 3D objects have become widely available and used in different application domains. Thus, it is becoming fundamental to use, integrate and develop techniques for extracting and maintaining their embedded knowledge. These techniques should be encapsulated in portable and intelligent systems able to semantically annotate the 3D object models in order to improve their usability and indexing, especially in innovative web cooperative environments. Lately, we are moving in this direction, with the definition and development of data structures, methods and interfaces for structuring and semantically annotating 3D complex models (and scenes) - even changing in time - according to ontology-driven metadata and following ontology-driven processes. Here, we concentrate on the tools for segmenting manifold 3D models and on the underline structural representation that we build and manipulate. We also describe the first prototype of an annotation tool which allows a hierarchical semantic-driven tagging of the segmented model and provides an interface from which the user can inspect and browse the entire segmentation graph.

Discrete Distortion for Surface Meshes
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
Image Analysis and Processing--ICIAP, 2009
[bibtex] [doi]

abstract Discrete distortion for two- and three-dimensional combinatorial manifolds is a discrete alternative to Ricci curvature known for differentiable manifolds. Here, we show that distortion can be successfully used to estimate mean curvature at any point of a surface. We compare our approach with the continuous case and with a common discrete approximation of mean curvature, which depends on the area of the star of each vertex in the triangulated surface. This provides a new, area-independent, tool for curvature estimation and for morphological shape analysis. We illustrate our approach through experimental results showing the behavior of discrete distortion.

Computing and Visualizing a Graph-Based Decomposition for Non-manifold Shapes
Leila De Floriani, Daniele Panozzo, Annie Hui
Graph-Based Representations in Pattern Recognition, 2009
[bibtex] [doi]

abstract Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an effective support to modeling, analyzing and understanding non-manifold shapes.

Digital Elevation Models
Leila De Floriani, Paola Magillo
Encyclopedia of Database Systems, 2009
[bibtex] [doi]

Tree-Based Encoding for Cancellations on Morse Complexes
Lidija Čomić, Leila De Floriani
Combinatorial Image Analysis, 2009
[bibtex] [doi]

abstract A scalar function f, defined on a manifold M, can be simplified by applying a sequence of removal and contraction operators, which eliminate its critical points in pairs, and simplify the topological representation of M, provided by Morse complexes of f. The inverse refinement operators, together with a dependency relation between them, enable a construction of a multi-resolution representation of such complexes. Here, we encode a sequence of simplification operators in a data structure called an augmented cancellation forest, which will enable procedural encoding of the inverse refinement operators, and reduce the dependency relation between modifications of the Morse complexes. In this way, this representation will induce a high flexibility of the hierarchical representation of the Morse complexes, producing a large number of Morse complexes at different resolutions that can be obtained from the hierarchy.

Diamond hierarchies of arbitrary dimension
Kenneth Weiss, Leila De Floriani
Computer Graphics Forum, 2009
[bibtex] [doi]

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 of d-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 for d-dimensional diamonds and reduce the number of required neighbor-finding accesses from O(d!) to O(d).

A Java3D framework for inspecting and segmenting 3D models
Leila De Floriani, Laura Papaleo, Nicolo' Carissimi
Web3D '08 Proceedings of the 13th international symposium on 3D web technology, 2008
[bibtex] [doi]

abstract Models of 3D objects have become widely accessible in several disciplines within academia and industry, spanning from scientific visualization to entertainment. In the last few years, 3D models are often organized into digital libraries accessible over the network, and thus semantic annotation of such models becomes an important issue. A fundamental step in annotating a 3D model is to segment it into meaningful parts. In this work, we present a Java3D framework for inspecting and segmenting 3D objects represented in X3D format. In particular, we present a combination of segmentation and merging techniques for producing a feasible decomposition of the boundary of a 3D object. We represent such decomposition as a graph, that we call the segmentation graph which is the basis for semantic annotation. We describe also the interface we have developed to allow visualization and browsing of both the decomposition and the segmentation graph in order to understand the topological structure of the resulting decomposition.

Multiresolution interval volume meshes
Kenneth Weiss, Leila De Floriani
Proceedings of the Fifth Eurographics/IEEE VGTC conference on Point-Based Graphics, 2008
[bibtex] [doi]

abstract Interval volumes are a generalization of isosurfaces that represent the set of points between two surfaces. In this paper, we present a compact multi-resolution representation for interval volume meshes extracted from regularly sampled volume data sets. The multi-resolution model is a hierarchical tetrahedral mesh whose updates are based on the longest edge bisection (LEB) subdivision strategy for tetrahedra. Although our representation is decoupled from the scalar field, it maintains the implicit structure of the LEB model to efficiently encode mesh updates. Our representation efficiently supports selective refinement queries and requires significantly less storage than an encoding of the interval volume mesh at full resolution.

Morphological analysis of terrains based on discrete curvature and distortion
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008
[bibtex] [doi]

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

Sparse terrain pyramids
Kenneth Weiss, Leila De Floriani
Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008
[bibtex] [doi]

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

Modeling and Visualization Approaches for Time-Varying Volumetric Data
K Weiss, L. De Floriani
4th International Symposium, ISVC 2008
[bibtex] [doi]

abstract Time-varying volumetric data arise in a variety of application domains, and thus several techniques for dealing with such data have been proposed in the literature. A time-varying dataset is typically modeled either as a collection of discrete snapshots of volumetric data, or as a four-dimensional dataset. This choice influences the operations that can be efficiently performed on such data. Here, we classify the various approaches to modeling time-varying scalar fields, and briefly describe them. Since most models of time-varying data have been abstracted from well-known approaches to volumetric data, we review models of volumetric data as well as schemes to accelerate isosurface extraction and discuss how these approaches have been applied to time-varying datasets. Finally, we discuss multi-resolution approaches which allow interactive processing and visualization of large time varying datasets.

Multi-Scale 3D Morse Complexes
Lidija Comic, Leila De Floriani
International Conference on Computational Sciences and Its Applications (ICCSA'08), 2008
[bibtex] [doi]

abstract Morse theory studies the relationship between the topology of a manifold M and the critical points of a scalar function f defined over M. Morse and Morse-Smale complexes, defined by critical points and integral lines of f, induce a subdivision of M into regions of uniform gradient flow, representing the morphology of M in a compact way. Function f can be simplified by canceling its critical points in pairs, thus simplifying the morphological representation of M, given by Morse and Morse-Smale complexes of f. Here, we propose a compact representation for the two Morse complexes in 3D, which is based on encoding the incidence relations of their cells, and on exploiting the duality among the complexes. We define cancellation operations, and their inverse expansion operations, on the Morse complexes and on their dual representation. We propose a multi-scale representation of the Morse complexes which provides a description of such complexes, and thus of the morphology of a 3D scalar field, at different levels of abstraction. This representation allows us also to perform selective refinement operations to extract description of the complexes which varies in different parts of the domain, thus improving efficiency on large data sets, and eliminating the noise in the data through topology simplification.

Visualizing Multiple Scalar Fields on a Surface
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paola Magillo
3rd International Conference on Computer Graphics Theory and Applications (GRAPP), 2008
[bibtex] [paper]

abstract We present a new technique for the simultaneous visualization of an arbitrary number of scalar fields defined on a surface. The technique is called Generalized Atmosphere Upper Bound Level (GAUBL), since it is an evolution of our previous AUBL technique, that allowed for the visualization of a single scalar field. The generalized AUBL can highlight the dependencies and interactions between many scalar fields, and can handle a multi-valued scalar field as a special case. We have implemented the GAUBL into a visualization tool that handles triangle-based surface models, and we show here some experimental results.

A Hierarchical Spatial Index for Triangulated Surfaces
Leila De Floriani, Marianna Facinoli, Paola Magillo, Debora Dimitri
3rd International Conference on Computer Graphics Theory and Applications (GRAPP), 2008
[bibtex] [paper]

abstract We present the PM2-Triangle quadtree (PM2T-quadtree), a new hierarchical spatial index for triangle meshes which has been designed for performing spatial queries on triangle-based terrain models. The PM2T-quadtree is based on a recursive space decomposition into square blocks. Here, we propose a highly compact data structure encoding a PM2T-quadtree, which decouples the spatial indexing structure from the combinatorial description of the mesh. We compare the PM2T-quadtree against other spatial indexes by considering the structure of the underlying domain subdivision, the storage costs of their data structures and the performance in geometric queries.

Combining Segmentations for Understanding and Annotating 3D Objects
Laura Papaleo, Nicolo' Carissimi, Leila De Floriani
Eurographics Italian Chapter Conference, 2008
[bibtex]

Cancellation of critical points in 2D and 3D Morse and Morse-Smale complexes
Lidija Čomić, Leila De Floriani
Discrete Geometry for Computer Imagery, 2008
[bibtex] [doi]

abstract Morse theory studies the relationship between the topology of a manifold M and the critical points of a scalar function f defined on M. The Morse-Smale complex associated with f induces a subdivision of M into regions of uniform gradient flow, and represents the topology of M in a compact way. Function f can be simplified by cancelling its critical points in pairs, thus simplifying the topological representation of M, provided by the Morse-Smale complex. Here, we investigate the effect of the cancellation of critical points of f in Morse-Smale complexes in two and three dimensions by showing how the change of connectivity of a Morse-Smale complex induced by a cancellation can be interpreted and understood in a more intuitive and straightforward way as a change of connectivity in the corresponding ascending and descending Morse complexes. We consider a discrete counterpart of the Morse-Smale complex, called a quasi-Morse complex, and we present a compact graph-based representation of such complex and of its associated discrete Morse complexes, showing also how such representation is affected by a cancellation.

A Discrete Approach to Compute Terrain Morphology
Paola Magillo, Emanuele Danovaro, Leila De Floriani, Laura Papaleo, Maria Vitali
Computer Vision and Computer Graphics. Theory and Applications, 2008
[bibtex] [doi]

abstract We consider the problem of extracting morphology of a terrain represented as a Triangulated Irregular Network (TIN). We propose a new algorithm and compare it with representative algorithms of the main approaches existing in the literature to this problem. The new algorithm has the advantage of being simple, using only comparisons (and no floating-point computations), and of being suitable for an extension to higher dimensions. Our experiments consider both real data and artificial test data. We evaluate the difference in the results produced on the same terrain data, as well as the impact of resolution level on such a difference, by considering representations of the same terrain at different resolutions.

Describing shapes by geometrical-topological properties of real functions
S. Biasotti, L. De Floriani, B. Falcidieno, P. Frosini, D. Giorgi, C. Landi, L. Papaleo, M. Spagnuolo
ACM Computing Surveys (CSUR), 2008
[bibtex] [doi]

abstract Differential topology, and specifically Morse theory, provide a suitable setting for formalizing and solving several problems related to shape analysis. The fundamental idea behind Morse theory is that of combining the topological exploration of a shape with quantitative measurement of geometrical properties provided by a real function defined on the shape. The added value of approaches based on Morse theory is in the possibility of adopting different functions as shape descriptors according to the properties and invariants that one wishes to analyze. In this sense, Morse theory allows one to construct a general framework for shape characterization, parametrized with respect to the mapping function used, and possibly the space associated with the shape. The mapping function plays the role of a lens through which we look at the properties of the shape, and different functions provide different insights. In the last decade, an increasing number of methods that are rooted in Morse theory and make use of properties of real-valued functions for describing shapes have been proposed in the literature. The methods proposed range from approaches which use the configuration of contours for encoding topographic surfaces to more recent work on size theory and persistent homology. All these have been developed over the years with a specific target domain and it is not trivial to systematize this work and understand the links, similarities, and differences among the different methods. Moreover, different terms have been used to denote the same mathematical constructs, which often overwhelm the understanding of the underlying common framework. The aim of this survey is to provide a clear vision of what has been developed so far, focusing on methods that make use of theoretical frameworks that are developed for classes of real functions rather than for a single function, even if they are applied in a restricted manner. The term geometrical-topological used in the title is meant to underline that both levels of information content are relevant for the applications of shape descriptions: geometrical, or metrical, properties and attributes are crucial for characterizing specific instances of features, while topological properties are necessary to abstract and classify shapes according to invariant aspects of their geometry. The approaches surveyed will be discussed in detail, with respect to theory, computation, and application. Several properties of the shape descriptors will be analyzed and compared. We believe this is a crucial step to exploit fully the potential of such approaches in many applications, as well as to identify important areas of future research.

Discrete Distortion in Triangulated 3-Manifolds
Mohammed Mostefa Mesmoudi, Leila De Floriani, Umberto Port
Computer Graphics Forum, 2008
[bibtex] [doi]

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 R4 defined by a scalar field on a 3D mesh. distance fields.

Contribution to a Taxonomy of Non-Manifold Models Based on Topological Properties
Jean-Claude Léon and Leila De Floriani
ASME 2008 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 2008
[bibtex] [doi]

abstract Non-manifold models have classically been used in Finite Element (FE) simulations to describe the shape of a mechanical part. Sketching the shape of an object is also important in a design stage, where non-manifold models could be of help for the designer. The purpose of the taxonomy proposed here is to be able either to accept or reject them based on the design context and on the type of product. This will contribute to model non-manifold objects and to their binary classification. The proposed taxonomy is also based on the topological properties of non-manifold objects, and especially on topological invariants. We will classify several topological properties as local or global ones, and we will illustrate how such properties can help either modelling these objects or searching for them in industrial data bases when large numbers of FE models have been stored.

Identification of Form Features in Non-Manifold Shapes through a Decomposition Approach
Leila De Floriani, Annie Hui, Franca Giannini
ASME 2008 9th Biennial Conference on Engineering Systems Design and Analysis, 2008
[bibtex]

abstract In Computer-Aided Design (CAD), the idealization process reduces the complexity of the model of a solid object, thus resulting in a simplified representation which captures only the essential elements of its shape. Form features extraction is a relevant issue in order to recover semantic information from an idealized object model, since such information is typically lost during the idealization process. An idealized model is usually composed of non-manifold parts, whose topology carries significant structural information about the object shape. To this aim, we define form features for non-manifold object by extending the taxonomy of form features provided by STEP [19]. We describe an approach for the identification of features, which interact with non-manifold singularities in the object, based on a decomposition of a non-manifold object into nearly manifold components and on the properties of the graph representing such decomposition.

Theoretical foundations of 3D scalar field visualization
Mohammed Mostefa Mesmoudi, Leila De Floriani, Paolo Rosso
VISAPP (Special Sessions), 2007
[bibtex]

A semantic-oriented decomposition for non-manifold shapes
Leila De Floriani, Annie Hui
Proceedings Israel-Italy Bi-National Conference on Shape Modeling and Reasoning for Industrial and Biomedical Applications, 2007
[bibtex]

A semantic web environment for digital shapes understanding
Leila De Floriani, Annie Hui, Laura Papaleo, May Huang, James Hendler
Semantic Multimedia, 2007
[bibtex] [doi]

abstract In the last few years, the volume of multimedia content available on the Web significantly increased. This led to the need for techniques to handle such data. In this context, we see a growing interest in considering the Semantic Web in action and in the definition of tools capable of analyzing and organizing digital shape models. In this paper, we present a Semantic Web environment, be-SMART, for inspecting 3D shapes and for structuring and annotating such shapes according to ontology-driven metadata. Specifically, we describe in details the first module of be-SMART, the Geometry and Topology Analyzer, and the algorithms we have developed for extracting geometrical and topological information from 3D shapes. We also describe the second module, the Topological Decomposer, which produces a graph-based representation of the decomposition of the shape into manifold components. This is successively modified by the third and the fourth modules, which perform the automatic and manual segmentation of the manifold parts.

Multi-scale dual morse complexes for representing terrain morphology
Emanuele Danovaro, Leila De Floriani, Maria Vitali, Paola Magillo
Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, 2007
[bibtex] [doi]

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

Out-of-core multiresolution terrain modeling
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, Hanan Samet
Spatial Data on the Web, 2007
[bibtex]

Morphological Representations of Scalar Fields
Silvia Biasotti, Leila De Floriani, Bianca Falcidieno, Laura Papaleo
Shape Analysis and Structuring, 2007
[bibtex] [doi]

abstract We consider the problem of representing and extracting morphological information from scalar fields. We focus on the analysis and comparison of algorithms for morphological representation of both 2D and 3D scalar fields. We review algorithms which compute a decomposition of the domain of a scalar field into a Morse and Morse-Smale complex and algorithms which compute a topological representation of the level sets of a scalar field, called a contour tree. Extensions of the morphological representations discussed in the chapter are briefly discussed.

Multi-resolution Morse-Smale complexes for terrain modeling
Emanuele Danovaro, Leila De Floriani, Maria Vitali
14th International Conference on Image Analysis and Processing, 2007
[bibtex] [doi]

abstract We propose a hierarchical representation for the morphology of a terrain. The basis of our morphological model is a decomposition of the terrain model, composed of the stable and unstable manifolds defined by its critical points, called a Morse-Smale complex. We propose a compact dual representation of the Morse-Smale complex and we define new simplification operators of the terrain morphology, which act on such representation. Based on these operators, we define a hierarchical morphology-based representation for a terrain, that we call a Multi-resolution Morse-Smale Complex (MMSC). Results from our implementation of the MMSC are shown.

Morphology-based representations of discrete scalar fields
Mohammed Mostefa Mesmoudi, Leila De Floriani
GRAPP (GM/R), 2007
[bibtex]

Extracting terrain morphology-a new algorithm and a comparative evaluation
Paola Magillo, Emanuele Danovaro, Leila De Floriani, Laura Papaleo, Maria Vitali
2nd International Conference on Computer Graphics Theory and Applications (GRAPP'07), 2007
[bibtex] [paper]

abstract We consider the problem of extracting morphology of a terrain represented as a Triangulated Irregular Network (TIN). We propose a new algorithm and compare it with representative algorithms of the main approaches existing in the literature to this problem.

Form Features in Non-manifold Shapes: A First Classification and Analysis
Chiara Crovetto, Leila De Floriani, Franca Giannini
Eurographics Italian Chapter Conference, 2007
[bibtex]

abstract During the industrial design process, a product model undergoes several analyses. One of the most common ones is the finite element analysis. This kind of analysis needs a simplified model, which can include idealised parts, and thus it is usually non-manifold and non-regular. During the idealisation process, the semantic information attached to the CAD model, such as features or surface types, or information used for model simplification, e.g. assumptions on the behavior type, is usually lost, thus making more difficult re-using, or, at least taking advantage, of performed simulations and models. This would be made easier if a meaningful interpretation of the object sub-parts is available. To this aim, in this paper, we provide a taxonomy of form features in non-manifold shapes and we describe an approach for their identification based on a decomposition of a non-manifold shapes into uniformly dimensional components proposed in [DHH06]. The process presented is the first step towards the identification of form features, since it analyzes those features containing non-manifold singularities.

Shape representations based on cell and simplicial complexes
Leila De Floriani, Annie Hui
Eurographics 2007, State-of-the-art Report
[bibtex]

Bridging Semantic Web and Digital Shapes
L. Papaleo, L. De Floriani, J. Hendler
Proceedings of Eurographics Conference, 2007
[bibtex]

abstract Since the volume of multimedia content available on the Web is continuously increasing, a clear need for advanced techniques capable of performing an effective retrieval and management of such data. In this context, in order to reason on digital shapes and their associated semantic, we see a growing interest in exploiting the potential of the Semantic Web in different research fields. We present here the design and initial development of our new system, that we call be-SMART for inspecting digital 3D shapes by extracting geometrical and topological in formation from them and for structuring and annotating these shapes using ontology-driven metadata. We describe the general structure of the system, its modules and their mutual relations. We also provide motivations for further work in developing new techniques for managing 3D models on the Web.

Towards a semantic web system for understanding real world representations
Laura Papaleo, Leila De Floriani, James Hendler, Annie Hui
Proceedings of the Tenth International Conference on Computer Graphics and Artificial Intelligence, 2007
[bibtex]

abstract As the volume of multimedia content available on the Web continues to increase, there is a clear need for more advanced techniques for effective retrieval and management of such data. In this context, we see a growing interest in exploiting the potential of the Semantic Web in different research fields. But, on the other hand, there is a general lack of tools able to analyse, organize and understand digital shape models (especially 3D models) for easily populating repositories with complete and well-detailed metadata. Several steps are necessary to create and associate semantics with a shape and some of them are clearly context-dependent. In this paper, we present the design details of our new system, that we call be-SMART, for inspecting digital 3D shapes by extracting geometrical and topological information from them and for structuring and annotating these shapes using ontology-driven metadata. In particular, we describe the general structure of the system, the different modules and their mutual relations. We then concentrate on the first two modules of the system showing how the 3D models are annotated following ontology-driven metadata. We also provide motivations for further work in developing new techniques for both annotating and managing 3D models on the Web

Shape analysis and structuring
Leila De Floriani, Michela Spagnuolo
Springer, 2007
[bibtex]

A two-level topological decomposition for non-manifold simplicial shapes
Annie Hui, Leila De Floriani
Proceedings of the 2007 ACM symposium on Solid and physical modeling
[bibtex] [doi]

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

Topology-based reasoning on non-manifold shapes
Leila De Floriani, Annie Hui, Laura Papaleo
Proceedings of the 1st International Symposium on Shapes and Semantics, 2006
[bibtex]

abstract Topological information is a promising resource to research in shape-understanding as it provides a high-level description of the characteristics of a shape, and such high-level description often has strong association with the semantics of an object. The Shape Acquisition and Processing (SAP) ontology has been designed to maintain useful information of a model. We propose here an extension to the SAP ontology, that addresses the non-manifold properties of a model. Useful information about the connectivity of an object can be obtained based on an analysis of its non-manifold properties, because the structure of a non-manifold object can be considered as a graph of manifold parts connected together at non-manifold joints. The manifold parts are often pieces that have strong semantic associations. In this work, we describe the type of non-manifold properties, the various types of connected components in a non-manifold object and their semantical significance. We address how the Euler’ characteristics of a non-manifold object can be found based on such information. All such information are extractable from a model using TopMesh, a tool that we have developed. In this work, we also describe the features of TopMesh, namely, all the topological properties it extracts.

A multi-resolution representation for terrain morphology
Emanuele Danovaro, Leila De Floriani, Laura Papaleo, Maria Vitali
Geographic information science, 2006
[bibtex] [doi]

abstract Mesh-based terrain representations provide accurate descriptions of a terrain, but fail in capturing its morphological structure. The morphology of a terrain is defined by its critical points and by the critical lines joining them, which form a so-called surface network. Because of the large size of current terrain data sets, a multi-resolution representation of the terrain morphology is crucial. Here, we address the problem of representing the morphology of a terrain at different resolutions. The basis of the multi-resolution terrain model, that we call a Multi-resolution Surface Network (MSN), is a generalization operator on a surface network, which produces a simplified representation incrementally. An MSN is combined with a multi-resolution mesh-based terrain model, which encompasses the terrain morphology at different resolutions. We show how variable-resolution representations can be extracted from an MSN, and we present also an implementation of an MSN in a compact encoding data structure.

Multi-resolution Morphological Representation of Terrains
E. Danovaro, L. De Floriani, M.Vitali, L.Papaleo
Eurographics Italian Chapter Conference, 2006
[bibtex]

abstract Mesh-based terrain representations provide accurate descriptions of a terrain, but fail in capturing its morphological structure. The morphology of a terrain is defined by its critical points and by the critical lines joining them, which form a so-called surface network. Besides being compact, a morphological terrain description supports a knowledge-based approach to the analysis, visualization and understanding of a terrain dataset. Moreover, because of the large size of current terrain data sets, a multi-resolution representation of the terrain morphology is crucial. Here, we address the problem of representing the morphology of a terrain at different resolutions. The basis of the multi-resolution terrain model, that we call a Multi-resolution Surface Network (MSN), is a generalization operator on a surface network, which produces a simplified representation incrementally. An MSN is combined with a multi-resolution mesh-based terrain model, which encompasses the terrain morphology at different resolutions. We show how variable-resolution representations can be extracted from an MSN, and we present also an implementation of an MSN in a compact encoding data structure.

A Dimension-Independent Representation for Multiresolution Nonmanifold Meshes
Leila De Floriani, Annie Hui
Journal of computing and information science in engineering, 2006
[bibtex]

abstract We consider the problem of representing and manipulating nonmanifold objects of any dimension and at multiple resolutions. We present a modeling scheme based on (1) a multiresolution representation, called the vertex-based nonmanifold multitessellation, (2) a compact and dimension-independent data structure, called the Simplified Incidence Graph (SIG), and (3) an atomic mesh update operator, called vertex-pair contraction/vertex expansion. We propose efficient algorithms for performing the vertex-pair contraction on a simplicial mesh encoded as a SIG, and an effective representation for encoding this multiresolution model based on a compact encoding of vertex-pair contractions and vertex expansions.

Level-of-detail for data analysis and exploration: A historical overview and some new perspectives
E. Danovaro, L. De Floriani, P. Magillo, E. Puppo, D. Sobrero
Computers and Graphics, 2006
[bibtex] [doi]

abstract Level-of-detail (LOD) techniques have been studied for many years in computer graphics. Research in this area has reached maturity and several effective tools in LOD modeling are now available. However, most models and tools proposed in the literature are oriented to rendering. This is just one among many tasks that LOD should support in the context of applications involving geometric meshes of large size. Our approach to the research on LOD has always been to develop models and data structures that can support a range of spatial queries, rather than being optimized for rendering. Here, we present a historical overview, by highlighting the impact of this approach in the design of LOD models and data structures, and we briefly describe our current research, outlining new challenges in which LOD finds important applications.

A decomposition-based representation for 3D simplicial complexes
Annie Hui, Lucas Vaczlavik, Leila De Floriani
ACM International Conference Proceeding Series, 2005
[bibtex]

abstract We define a new representation for non-manifold 3D shapes described by three-dimensional simplicial complexes, that we call the Double-Level Decomposition (DLD) data structure. The DLD data structure is based on a unique decomposition of the simplicial complex into nearly manifold parts, and encodes the decomposition in an efficient and powerful two-level representation. It is compact, and it supports efficient topological navigation through adjacencies. It also provides a suitable basis for geometric reasoning on non-manifold shapes. We describe an algorithm to decompose a 3D simplicial complex into nearly manifold parts. We discuss how to build the DLD data structure from a description of a 3D complex as a collection of tetrahedra, dangling triangles and wire edges, and we present algorithms for topological navigation. We present a thorough comparison with existing representations for 3D simplicial complexes.

Clustering Techniques for Out-of-Core Multi-resolution Modeling
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, Hanan Samet
Visualization Conference, IEEE, 2005
[bibtex] [doi]

abstract Thanks to improvements in simulation tools, high resolution scanning facilities and multidimensional medical imaging, huge datasets are commonly available. Multi-resolution models manage the complexity of such data sets, by varying resolution and focusing detail in specific areas of interests. Since many currently available data sets cannot fit in main memory, the need arises to design data structures, construction and query algorithms for multi-resolution models which work in secondary memory.

The half-edge tree: A compact data structure for level-of-detail tetrahedral meshes
E. Danovaro, L. De Floriani, P. Magillo, E. Puppo, D. Sobrero, N. Sokolovsky
Shape Modeling and Applications, 2005 International Conference
[bibtex] [doi]

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

Morse-Smale Decompositions for Modeling Terrain Knowledge
Lidija Čomić, Leila De Floriani, Laura Papaleo
Spatial Information Theory, 2005
[bibtex] [doi]

abstract In this paper, we describe, analyze and compare techniques for extracting spatial knowledge from a terrain model. Specifically, we investigate techniques for extracting a morphological representation from a terrain model based on an approximation of a Morse-Smale complex. A Morse-Smale complex defines a decomposition of a topographic surface into regions with vertices at the critical points and bounded by integral lines which connect passes to pits and peaks. This provides a terrain representation which encompasses the knowledge on the salient characteristics of the terrain. We classify the various techniques for computing a Morse-Smale complexe based on the underlying terrain model, a Regular Square Grid (RSG) or a Triangulated Irregular Network (TIN), and based on the algorithmic approach they apply. Finally, we discuss hierarchical terrain representations based on a Morse-Smale decomposition.

Data structures for simplicial complexes: an analysis and a comparison
Leila De Floriani, Annie Hui
Proceedings of the third Eurographics symposium on Geometry processing, 2005
[bibtex]

abstract In this paper, we review, analyze and compare representations for simplicial complexes. We classify such representations, based on the dimension of the complexes they can encode, into dimension-independent structures, and data structures for three- and for two-dimensional simplicial complexes. We further classify the data structures in each group according to the basic kinds of the topological entities they represent. We present a description of each data structure in terms of the entities and topological relations encoded, and we evaluate it based on its expressive power, on its storage cost and on the efficiency in supporting navigation inside the complex, i.e., in retrieving topological relations not explicitly encoded. We compare the various data structures inside each category based on the above features.

Generating, Representing and Querying Level-Of-Detail Tetrahedral Meshes
Leila De Floriani, Emanuele Danovaro
Scientific Visualization: The Visual Extraction of Knowledge from Data, 2005
[bibtex] [doi]

abstract In this paper, we survey techniques for building, encoding and querying Level-Of-Detail (LOD) models of three-dimensional scalar fields based on a domain decomposition into tetrahedral meshes. We focus on continuous LOD models, and we classify them into unstructured (irregular) and regular nested LOD models depending on the mesh subdivision pattern and on the distribution of the data points. Within each class, we review data structures, construction algorithms, as well as techniques for extracting adaptively refined field representations from an LOD model.

Representing Non-Manifold Shapes in Arbitrary Dimensions
Leila De Floriani, Annie Hui
Israel-Korean Bi-national Conference on New Technologies and Visualization Methods for Product Development on Design and Reverse Engineering, 2005
[bibtex]

abstract In this paper, we describe and analyze several representations for complex shapes, i.e., multi-dimensional, non-manifold objects with parts of mixed dimensionality, based on simplicial complexes. We review our work on compact and scalable representations for 2D and 3D simplicial complexes embedded in 3D Euclidean space. We propose a dimension-independent representation for simplicial complexes in which all the simplexes are uniquely and explicitly encoded. Finally, we describe a decomposition approach to the representation of non-manifold objects in arbitrary dimensions based on their decomposition into nearly manifold components.

An Algorithm for Decomposing Multi-dimensional Non-manifold Objects into Nearly Manifold Components
M. Mostefa Mesmoudi, Leila De Floriani, Franco Morando, Enrico Puppo
Advances in Multiresolution for Geometric Modelling, 2005
[bibtex] [paper] [doi]

abstract In this paper we address the problem of building valid representations for non-manifold d-dimensional objects. To this aim, we have developed a combinatorial approach based on decomposing a non-manifold d-dimensional object into an assembly of more regular components, that we call initial quasi-manifolds. We present a decomposition algorithm, whose complexity is slightly super-linear in the total number of simplexes. Our approach provides a rigorous basis for designing efficient dimension-independent data structures for describing non-manifold objects.

Encoding Level-of-Detail Tetrahedral Meshes
Neta Sokolovsky, Emanuele Danovaro, Leila De Floriani, Paola Magillo
Advances in Multiresolution for Geometric Modelling, 2005
[bibtex] [doi]

abstract Level-Of-Detail (LOD) techniques can be a valid support to the analysis and visualisation of volume data sets of large size. In our previous work, we have defined a general LOD model for d-dimensional simplicial meshes, called a Multi-Tessellation (MT), which consists of a partially ordered set of mesh updates. Here, we consider an instance of the MT for tetrahedral meshes, called a Half-Edge MT, which is built through a common simplification operation, half-edge collapse. We discuss two compact encodings for a Half-Edge MT, based on alternative ways to represent the partial order.

Multi-Scale Geographic Maps
Raquel Viaña, Paola Magillo, Enrico Puppo
Advances in Multiresolution for Geometric Modelling, 2005
[bibtex] [doi]

abstract We consider geographic maps represented as plane graphs, which undergo a process of generalisation performed through sequences of local updates. Generalisation transforms a highly detailed map into one with fewer details, spanning many different scales of representation through the sequence of updates. We study intrinsic dependency relations among updates in the sequence and, on this basis, we derive a multi-scale model that supports efficient retrieval of maps at different scales, possibly variable through the domain.

Multi-resolution out-of-core modeling of terrain and teological data
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, Hanan Samet
Proceedings of the 13th annual ACM international workshop on Geographic information systems, 2005
[bibtex] [doi]

abstract Multi-resolution is a useful tool for managing the complexity of huge terrain and geological data sets. Since encoding large data sets may easily exceed main memory capabilities, data structures and algorithms capable of efficiently working in external memory are needed. In our work, we aim at developing an out-of-core multi-resolution model dimension-independent, that can be used for both terrains, represented by Triangulated Irregular Networks(TINs), and 3D data, such as geological data, represented by tetrahedral meshes. We have based our approach on a general multi-resolution model, that we have proposed in our previous work, which supports the extraction of variable-resolution representations. As first step, we have developed, in a prototype simulation system, a large number of clustering techniques for the modifications in a multi-resolution model. Here, we describe such techniques, and analyze and evaluate them experimentally. The result of this investigation has led us to select a specific clustering approach as the basis for an efficient out-of-core data structure.

Selective refinement queries for volume visualization of unstructured tetrahedral meshes
P. Cignoni, L. De Floriani, P. Magillo, E. Puppo, R. Scopigno
IEEE Transactions on Visualization and Computer Graphics, 2004
[bibtex] [paper] [doi]

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

Update operations on 3D simplicial decompositions of non-manifold objects
Leila De Floriani, Annie Hui
Proceedings of the ninth ACM symposium on Solid Modeling and Applications, 2004
[bibtex] [paper]

abstract We address the problem of updating non-manifold mixed-dimensional objects, described by three-dimensional simplicial complexes embedded in 3D Euclidean space. We consider two local update operations, edge collapse and vertex split, which are the most common operations performed for simplifying a simplicial complex. We examine the effect of such operations on a 3D simplicial complex, and we describe algorithms for edge collapse and vertex split on a compact representation of a 3D simplicial complex, that we call the Non-Manifold Indexed data structure with Adjacencies (NMIA). We also discuss how to encode the information needed for performing a vertex split and an edge collapse on a 3D simplicial complex. The encoding of such information together with the algorithms for updating the NMIA data structure form the basis for defining progressive as well as multi-resolution representations for objects described by 3D simplicial complexes and for extracting variable-resolution object descriptions.

Constant-time navigation in four-dimensional nested simplicial meshes
M. Lee, L. De Floriani, H. Samet
Proceedings of the 2004 International Conference on Shape Modeling and Applications
[bibtex] [paper] [doi]

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

A data structure for non-manifold simplicial d-complexes
Leila De Floriani, David Greenfieldboyce, Annie Hui
Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing
[bibtex] [paper] [doi]

abstract We propose a data structure for d-dimensional simplicial complexes, that we call the Simplified Incidence Graph (SIG). The simplified incidence graph encodes all simplices of a simplicial complex together with a set of boundary and partial co-boundary topological relations. It is a dimension-independent data structure in the sense that it can represent objects of arbitrary dimensions. It scales well to the manifold case, i.e. it exhibits a small overhead when applied to simplicial complexes with a manifold domain, Here, we present efficient navigation algorithms for retrieving all topological relations from a SIG, and an algorithm for generating a SIG from a representation of the complex as an incidence graph. Finally, we compare the simplified incidence graph with the incidence graph, with a widely-used data structure for d-dimensional pseudo-manifold simplicial complexes, and with two data structures specific for two-and three-dimensional simplicial complexes.

Selective Refinement on Nested Tetrahedral Meshes
Leila De Floriani, Michael Lee
Geometric Modeling for Scientific Visualization, 2004
[bibtex] [doi]

abstract We consider a multi-resolution representation based on a decomposition of the field domain into nested tetrahedral cells generated by recursive tetrahedron bisection, that we call a Hierarchy of Tetrahedra (HT) We describe our implementation of an HT, and discuss how to extract conforming meshes from an HT so as to avoid discontinuities in the approximation of the associated scalar field. We describe algorithms for selective refinement, which either extract a variable-resolution mesh from scratch through a depth-first, or through a priority-based traversal technique, or which locally refine and coarsen a previously-extracted adaptive mesh through an incremental approach. We show experimental results in connection with a set of basic queries for performing analysis and visualization of a volume data set at different levels of detail.

Multi-resolution modeling, visualization and streaming of volume meshes},
P. Cignoni, L. De Floriani, P. Lindstrom, V. Pascucci, J. Rossignac, C. Silva
Eurographics 2004, Tutorials 2: Multi-resolution Modeling, Visualization and Streaming of Volume Meshes
[bibtex]

A multi-resolution topological representation for non-manifold meshes
Leila De Floriani, Paola Magillo, Enrico Puppo, Davide Sobrero
Computer Aided Systems, 2004
[bibtex] [paper] [doi]

abstract We address the problem of representing and processing 3D objects, described through simplicial meshes, which consist of parts of mixed dimensions, and with a non-manifold topology, at different levels of detail. First, we describe a multi-resolution model, that we call a non-manifold multi-tessellation (NMT), and we consider the selective refinement query, which is at the heart of several analysis operations on multi-resolution meshes. Next, we focus on a specific instance of a NMT, generated by simplifying simplicial meshes based on vertex-pair contraction, and we describe a compact data structure for encoding such a model. We also propose a new data structure for two-dimensional simplicial meshes, capable of representing both connectivity and adjacency information with a small memory overhead, which is used to describe the mesh extracted from an NMT through selective refinement. Finally, we present algorithms to efficiently perform updates on such a data structure.

A Survey on Data Structures for Level-of-Detail Models
Leila De Floriani, Leif Kobbelt, Enrico Puppo
Advances in Multiresolution for Geometric Modelling, 2004
[bibtex] [paper] [doi]

abstract In this paper we survey some of the major data structures for encoding Level Of Detail (LOD) models. We classify LOD data structures according to the dimensionality of the basic structural element they represent into point-, triangle-, and tetrahedron-based data structures. Within each class we will review single-level data structures, general data structures for LOD models based on irregular meshes as well as more specialised data structures that assume a certain (semi-) regularity of the data.

Representation of Non-manifold Objects Through Decomposition into Nearly Manifold Parts
Leila De Floriani, Franco Morando, Enrico Puppo
Proceedings of the eighth ACM symposium on Solid modeling and applications, pages 304--309, 2003
[bibtex] [paper] [doi]

abstract In our previous work [2], we have shown that a non-manifold, mixed-dimensional object described by simplicial complexes can be decomposed in a unique way into regular components, all belonging to a well-understood class. Based on such decomposition, we define here a two-level topological data structure for representing non-manifold objects in any dimension: the first level represents components; while the second level represents the connectivity relation among them. The resulting data structure is compact and scalable, allowing for the efficient treatment of singularities without burdening well-behaved parts of a complex with excessive space overheads.

Morphology-driven simplification and multiresolution modeling of terrains
Emanuele Danovaro, Leila De Floriani, Paola Magillo, Mohammed Mostefa Mesmoudi, Enrico Puppo
Proceedings of the 11th ACM international symposium on Advances in geographic information systems, pages 63--70, 2003
[bibtex] [paper] [doi]

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

A scalable data structure for three-dimensional non-manifold objects
Leila De Floriani, Annie Hui
Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 72--82, 2003
[bibtex] [paper]

abstract In this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the design and the implementation of a new data structure, that we call the non-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.

Topological Analysis and Characterization of Discrete Scalar Fields
Emanuele Danovaro, Leila De Floriani, Mohammed Mostefa Mesmoudi
Geometry, Morphology, and Computational Imaging, pages 386--402, 2003
[bibtex] [paper] [doi]

abstract In this paper, we address the problem of analyzing the topology of discrete scalar fields defined on triangulated domains. To this aim, we introduce the notions of discrete gradient vector field and of Smalelike decomposition for the domain of a d-dimensional scalar field. We use such notions to extract the most relevant features representing the topology of the field. We describe a decomposition algorithm, which is independent of the dimension of the scalar field, and, based on it, methods for extracting the critical net of a scalar field. A complete classification of the critical points of a 2-dimensional field that corresponds to a piecewise differentiable field is also presented.

Algorithms for visibility computation on terrains: a survey
Leila De Floriani, Paola Magillo
Environment and Planning B, vol. 30(5), pages 709--728, 2003
[bibtex] [paper] [doi]

abstract Several environment applications require the computation of visibility information on a terrain. Examples are optimal placement of observation points, line-of-sight communication, and computation of hidden as well as scenic paths. Visibility computations on a terrain may involve either one or many viewpoints, and range from visibility queries (for example, testing whether a given query point is visible), to the computation of structures that encode the visible portions of the surface. In this paper, the authors consider a number of visibility problems on terrains and present an overview of algorithms to tackle such problems on triangulated irregular networks and regular square grids.

Data structures for 3D Multi-Tessellations: an overview
Emanuele Danovaro, Leila De Floriani, Paola Magillo, Enrico Puppo
Data Visualization, pages 239--255, 2003
[bibtex] [paper] [doi]

abstract Multiresolution models support the interactive visualization of large volumetric data through selective refinement, an operation which permits to focus resolution only on the most relevant portions of the domain, or in the proximity of interesting field values. A 3D Multi-Tessellation (MT) is a multiresolution model, consisting of a coarse tetrahedral mesh at low resolution, and of a set of updates refining such a mesh, arranged as a partial order. In this paper, we describe and compare different data structures which permit to encode a 3D MT and to support selective refinement.

A Representation for Abstract Simplicial Complexes: An Analysis and a Comparison
Leila De Floriani, Franco Morando, Enrico Puppo
Discrete Geometry for Computer Imagery, pages 454--464, 2003
[bibtex] [paper] [doi]

abstract Abstract simplicial complexes are used in many application contexts to represent multi-dimensional, possibly non-manifold and non-uniformly dimensional, geometric objects. In this paper we introduce a new general yet compact data structure for representing simplicial complexes, which is based on a decomposition approach that we have presented in our previous work [3]. We compare our data structure with the existing ones and we discuss in which respect it performs better than others.

Multiresolution mesh representation: Models and data structures
Leila De Floriani, Paola Magillo
Tutorials on Multiresolution in Geometric Modelling, pages 363--417, 2002
[bibtex] [paper] [doi]

abstract Multiresolution meshes are a common basis for building representations of a geometric shape at different levels of detail. The use of the term multiresolution depends on the remark that the accuracy (or, level of detail) of a mesh in approximating a shape is related to the mesh resolution, i.e., to the density (size and number) of its cells. A multiresolution mesh provides several alternative mesh-based approximations of a spatial object (e.g., a surface describing the boundary of a solid object, or the graph of a scalar field). A multiresolution mesh is a collection of mesh fragments, describing usually small portions of a spatial object with different accuracies, plus suitable relations that allow selecting a subset of fragments (according to user-defined accuracy criteria), and combining them into a mesh covering the whole object, or an object part. Existing multiresolution models differ in the type of mesh fragments they consider and in the way they define relations among such fragments. In this chapter, we introduce a framework for multiresolution meshes in order to analyze and compare existing models proposed in the literature on a common basis. We have identified two sets of basic queries on a multiresolution meshes, that we call selective refinement and spatial selection. We describe two approaches for answering such queries, and discuss the primitives involved in them, which must be efficiently supported by any data structure implementing a multiresolution mesh. We then describe and analyze data structures proposed in the literature for encoding multiresolution meshes.

Multiresolution tetrahedral meshes: an analysis and a comparison
Emanuele Danovaro, Leila De Floriani, Michael Lee, Hanan Samet
Proceedings of the Shape Modeling International, pages 83--91, 2002
[bibtex] [paper] [doi]

abstract 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

Regular and irregular multi-resolution terrain models: a comparison
Leila De Floriani, Paola Magillo
Proceedings of the 10th ACM international symposium on Advances in geographic information systems, pages 143--148, 2002
[bibtex] [paper] [doi]

abstract The paper deals with the problem of modeling large-size terrain data sets. To this aim, we consider multi-resolution models based on triangle meshes. We analyze and compare two multi-resolution terrain models based on regular and irregular meshes. The two models are viewed as instances of a common multi-resolution model, that we call a multi-resolution triangle mesh. Our comparison takes into account the space requirements of the data structures implementing the two models as well their effectiveness in supporting the extraction of variable-resolution terrain representations.

Half-Edge Multi-Tessellation: A Compact Representation for Multi-Resolution Tetrahedral Meshes
Emanuele Danovaro, Leila De Floriani
International Symposium on 3D Data Processing Visualization and Transmission, 2002
[bibtex] [paper] [doi]

abstract This paper deals with the problem of analyzing and visualizing volume data sets of large size. To this aim, we define a three-dimensional multi-resolution model based on unstructured tetrahedral meshes, and built through a half-edge-collapse simplification strategy, that we call a Half-Edge Multi-Tessellation (MT). We propose a new compact data structure for a half-edge MT, and we analyze it with respect to both its space requirements and its efficiency in supporting Level-Of-Detail (LOD) queries based on selective refinement.

A Smale-like decomposition for discrete scalar fields
Leila De Floriani, Mohammed Mostefa Mesmoudi, Emanuele Danovaro
Proceedings. 16th International Conference on Pattern Recognition, pages 184--187, 2002
[bibtex] [paper] [doi]

abstract In this paper we address the problem of representing the structure of the topology of a d-dimensional scalar field as a basis for constructing a multiresolution representation of the structure of such afield. To this aim, we define a discrete decomposition of a triangulated d-dimensional domain, on whose vertices the values of the field are given. We extend a Smale decomposition, defined by Thom (1949) and Smale (1960) for differentiable functions, to the discrete case, to what we call a Smale-like decomposition. We introduce the notion of discrete gradient vector field, which indicates the growth of the scalar field and matches with our decomposition. We sketch an algorithm for building a Smale-like decomposition and a graph-based representation of this decomposition. We present results for the case of two-dimensional fields.

Extraction of critical nets based on a discrete gradient vector field
Leila De Floriani, Mohammed Mostefa Mesmoudi, Emanuele Danovaro
Proceedings of Eurographics, 2002
[bibtex] [paper]

abstract In this paper we address the problem of representing the topology of discrete scalar fields defined on triangulated domains in two and three dimensions. To this aim, we use the notion of discrete gradient vector field that we have introduced in [3] to classify critical points and extract a critical net representing the main features of a scalar field defined on a two-dimensional domain. The nature of the critical points provided by the discrete gradient vector field is quite different from those obtained in the differentiable case. Thus, we show that our critical net generalizes classical critical nets corresponding to (the classical differentiable) Morse functions.

Non-manifold Decomposition in Arbitrary Dimensions
Leila De Floriani, Mostefa Mohammed Mesmoudi, Franco Morando, Enrico Puppo
Discrete Geometry for Computer Imagery, pages 69--80, 2002
[bibtex] [paper] [doi]

abstract In this paper we consider the problem of decomposing a nonmanifold n-dimensional object described by an abstract simplicial complex into an assembly of ‘more-regular’ components. Manifolds, which would be natural candidates for components, cannot be used to this aim in high dimensions because they are not decidable sets. Therefore, we define d-quasi-manifolds, a decidable superset of the class of combinatorial d-manifolds that coincides with d-manifolds in dimension less or equal than two. We first introduce the notion of d-quasi-manifold complexes, then we sketch an algorithm to decompose an arbitrary complex into an assembly of quasi-manifold components abutting at non-manifold joints. This result provides a rigorous starting point for our future work, which includes designing efficient data structures for non-manifold modeling, as well as defining a notion of measure of shape complexity of such models.

Triangle-based multi-resolution models for height fields
Leila De Floriani, Paola Magillo
Curve and Surface Fitting, pages 97--106, 2002
[paper]

abstract Large-size data sets describing height fields (e.g., terrains) can be handled with multi-resolution models. We analyze and compare two multi-resolution models for height fields based on regular and irregular triangle meshes, respectively. Our comparison takes into account the space required by the data structures and the effectiveness in extracting variable-resolution surface representations.

A multi-resolution topological representation for non-manifold meshes
Leila De Floriani, Paola Magillo, Enrico Puppo, Davide Sobrero
Computer-Aided Design, vol. 36(2), pages 141--159, 2002
[bibtex] [paper] [doi]

abstract We address the problem of representing and processing 3D objects, described through simplicial meshes, which consist of parts of mixed dimensions, and with a non-manifold topology, at different levels of detail. First, we describe a multi-resolution model, that we call a non-manifold multi-tessellation (NMT), and we consider the selective refinement query, which is at the heart of several analysis operations on multi-resolution meshes. Next, we focus on a specific instance of a NMT, generated by simplifying simplicial meshes based on vertex-pair contraction, and we describe a compact data structure for encoding such a model. We also propose a new data structure for two-dimensional simplicial meshes, capable of representing both connectivity and adjacency information with a small memory overhead, which is used to describe the mesh extracted from an NMT through selective refinement. Finally, we present algorithms to efficiently perform updates on such a data structure.

Non-manifold multi-tessellation: From meshes to iconic representations of objects
Leila De Floriani, Paola Magillo, Franco Morando, Enrico Puppo
Visual Form 2001, pages 654--664, 2001
[bibtex] [paper] [doi]

abstract This paper describes preliminary research work aimed at obtaining a multi-level iconic representation of 3D objects from geometric meshes. A single-level iconic model describes an object through parts of different dimensions connected to form a hypergraph. The multi-level iconic model, called Non-manifold Multi-Tessellation, incorporates decompositions of an object into parts at different levels of abstraction, and permits to refine an iconic representation selectively.

Constant-time neighbor finding in hierarchical tetrahedral meshes
Michael Lee, Leila De Floriani, Hanan Samet
International Conference on Shape Modeling and Applications, pages 286--295, 2001
[bibtex] [paper] [doi]

abstract 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

Multiresolution modeling of three-dimensional shapes
Leila De Floriani, Paola Magillo
3D synthetic environment reconstruction, pages 35--59, 2001
[bibtex] [paper] [doi]

abstract Multiresolution models can provide representations of a geometric shape at different degrees of accuracy and complexity, based on user requirements. They have an impact in many applications, which require the manipulation of complex three-dimensional objects. In this chapter, we present a survey of existing multiresolution techniques. A comprehensive framework for multiresolution modeling is introduced, and existing models are presented, interpreted and compared by referring to such framework.

Representing vertex-based simplicial multi-complexes
Emanuele Danovaro, Leila De Floriani, Paola Magillo, Enrico Puppo
Lecture notes in computer science, pages 129--149, 2001
[bibtex] [paper]

abstract In this paper, we consider the problem of representing a multiresolution geometric model, called a Simplicial Multi-Complex (SMC), in a compact way. We present encoding schemes for both two- and three- dimensional SMCs built through a vertex insertion (removal) simplification strategy. We show that a good compression ratio is achieved not only with respect to a general-purpose data structure for a SMC, but also with respect to just encoding the complex at the maximum resolution.

Compressing Multiresolution Triangle Meshes
Emanuele Danovaro, Leila De Floriani, Paola Magillo, Enrico Puppo
Advances in Spatial and Temporal Databases, pages 345--364, 2001
[bibtex] [paper] [doi]

abstract In this paper, we consider triangle-based two-dimensional multiresolution complexes, called Multi-Triangulations (MTs), constructed based on a vertex-removal simplification strategy, which is the most common strategy used to build simplified representations of surfaces, e.g., terrains. We describe and compare compact encoding structures for such MTs. We show that these structures provide good compression ratios not only with respect to an economical data structure for general MTs, but also with respect to encoding the original mesh (i.e., the mesh at the full resolution). We also analyze the basic atomic operations needed for performing selective refinement on an MT, and we show that such operations are efficiently supported by the data structures described.

On-line space sculpturing for 3d shape manipulation
L. De Floriani, P. Magillo, E. Puppo
Proceedings of 15th International Conference on Pattern Recognition, vol. 1, pages 105--108, 2000
[bibtex] [paper] [doi]

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

Triangle-based surface models
L. De Floriani, S. Bussi, P. Magillo
Intelligent Systems and Robotics, pages 340--73, 2000
[bibtex] [paper]

abstract The problem of reconstructing a digital model of a surface from a finite set of sampled points is fundamental in many different application domains, including computer graphics, geographic data processing, computer vision and computer aided design. A triangulated surface model is often used, because of the possibility of including surface features, and of the simplicity of the topological structure. The definition of a triangle-based surface model relies on the concept of triangulation. In this paper, we discuss the basic properties of triangulations, Delaunay triangulations, constrained and conforming triangulations. We present a survey of algorithms for building these kinds of triangulations, which represent the first step in the construction of a surface model. A special attention is given to the surface reconstruction problem in 2 12 dimensions, which is connected to digital terrain modeling in geographic information systems. The more general problem of reconstructing the bounding surface of a solid object from three dimensional scattered data is also considered, and a brief survey of the main approaches proposed in the literature is presented.

Volume visualization of large tetrahedral meshes on low cost platforms
Paolo Cignoni, Leila De Floriani, Paola Magillo, Enrico Puppo, Roberto Scopigno
Proceedings NSF/DoE Lake Tahoe Workshop on Hierarchical Approximation and Geometrical Methods for Scientific Visualization, 2000
[bibtex] [paper]

abstract In this paper, we present an interactive system for visualization of three-dimensional scalar fields. The system has been designed in order to overcome some of the problems posed by very large volume data sets. The adopted solution exploits an efficient multiresolution data structure based on a tetrahedral domain decomposition. The mesh to be rendered can be selectively refined over areas that the user considers more critical, on the basis of either field values or domain locations. The system supports different rendering techniques, such as isosurface fitting and Direct Volume Rendering (DVR).

Compressing triangulated irregular networks
Leila De Floriani, Paola Magillo, Enrico Puppo
GeoInformatica, vol. 4(1), pages 67--88, 2000
[bibtex] [paper] [doi]

abstract We address the problem of designing compact data structures for encoding a Triangulated Irregular Network (TIN). In particular, we study the problem of compressing connectivity, i.e., the information describing the topological structure of the TIN, and we propose two new compression methods which have different purposes. The goal of the first method is to minimize the number of bits needed to encode connectivity information: it encodes each vertex once, and at most two bits of connectivity information for each edge of a TIN; algorithms for coding and decoding the corresponding bitstream are simple and efficient. A practical evaluation shows compression rates of about 4.2 bits per vertex, which are comparable with those achieved by more complex methods. The second method compresses a TIN at progressive levels of detail and it is based on a strategy which iteratively removes a vertex from a TIN according to an error-based criterion. Encoding and decoding algorithms are presented and compared with other approaches to progressive compression. Our method can encode more general types of triangulations, such as those constrained by topographic features, at the cost of a slightly longer bitstream.

VARIANT: A System for Terrain Modeling at Variable Resolution
L. De Floriani, P. Magillo, E. Puppo
GeoInformatica, vol 4(3), pages 287--315, 2000
[bibtex] [paper] [doi]

abstract We describe VARIANT (VAriable Resolution Interactive ANalysis of Terrain), an extensible system for processing and visualizing terrains represented through Triangulated Irregular Networks (TINs), featuring the accuracy of the representation, possibly variable over the terrain domain, as a further parameter in computation. VARIANT is based on a multiresolution terrain model, which we developed in our earlier research. Its architecture is made of a kernel, which provides primitive operations for building and querying the multiresolution model; and of application programs, which access a terrain model based on the primitives in the kernel. VARIANT directly supports basic queries (e.g., windowing, buffering, computation of elevation at a given point, or along a given line) as well as high-level operations (e.g., ̄y-over visualization, contour map extraction, viewshed analysis). However, the true power of VARIANT lies in the possibility of extending it with new applications that can exploit its multiresolution features in a transparent way.

A Library for Multiresolution Modeling of Field Data in GIS
Paola Magillo, Leila De Floriani, Enrico Puppo
Swiss Federal Institute of Technology, Lausanne, 2000
[bibtex] [paper]

abstract In this paper, we present an object-oriented library which provides an open-ended tool for handling multiresolution representations of field data in arbitrary dimensions. The library is fully parametric on the dimensions of the field domain and co-domain, on the attributes that can be associated with the model, on the criteria used for building the model, and on the criteria used for extracting representations at variable resolution from it. The library offers a basis for the development of GIS applications involving both two-dimensional and three-dimensional data, which can benefit from the use of multiresolution techniques.

A dimension and application-independent library for multiresolution geometric modeling
Paola Magillo, Leila De Floriani, Enrico Puppo
Tech. Rep. DISI-TR-00-11, University of Genova, Italy, 2000
[bibtex] [paper]

abstract We present a general-purpose software library for multiresolution geometric modeling in arbitrary dimensions. The core of the library is the Multi-Tesselation (MT), a general multiresolution model for representing k -dimensional geometric objects through simplicial complexes. An MT provides both simple and general methods for handling representations at variable resolution eÆciently, thus offering a basis for applications that need to manage the level-of-detail of complex objects. The library is fully parametric on dimensions of the simplicial complex and of the space embedding it, on the attributes that can be associated with its vertices and tiles, on the algorithms used for building the model, and on the criteria used for extracting variable-resolution representations from it.

Dynamic view-dependent multiresolution on a client--server architecture
L. De Floriani, P. Magillo, F. Morando, E. Puppo
Computer-Aided Design, vol 32(13), pages 805--823, 2000
[bibtex] [paper] [doi]

abstract We consider the problem of transmitting huge triangle meshes in the context of a Web-like client–server architecture. Approximations of the original mesh are transmitted by applying selective refinement. A multiresolution geometric model is maintained by the server. A client may query the server for a mesh at an arbitrary, continuously variable, level of detail. The client makes repeated queries over time with different query parameters. The server answers to queries by traversing the multiresolution model and transmitting updates to the client, which uses them to progressively modify a current mesh. We study this problem in the context of a vertex-based multiresolution model, which is a special instance of the Multi-Triangulation (a model that was developed in an earlier work), based on vertex insertion and removal. We define a compact data structure for such a model that exploits the specific update rule. We propose a dynamic algorithm for selective refinement and we discuss in detail its implementation as a client–server application. In order to reduce memory requirements and channel traffic, we develop a compressed representation which allows us to express mesh updates with a code of small size. We also address client caching to further limit bandwidth occupancy. Experimental results show that the Multi-Triangulation can be a key Web technology for triangle mesh manipulation.

Data structures for simplicial multi-complexes
Leila De Floriani, Paola Magillo, Enrico Puppo
Advances in Spatial Databases, pages 33--51, 1999
[bibtex] [paper]

abstract The Simplicial Multi-Complex (SMC) is a general multiresolution model for representing k -dimensional spatial objects through simplicial complexes. An SMC integrates several alternative representations of an object and offers simple methods for handling representations at variable resolution efficiently, thus providing a basis for the development of applications that need to manage the level-of-detail of complex objects. In this paper, we present general query operations on such models, we describe and classify alternative data structures for encoding an SMC, and we discuss the cost and performance of such structures.

Applications of computational geometry to geographic information systems
Leila De Floriani, Paola Magillo, Enrico Puppo
Handbook of computational geometry, pages 333--388, 1999
[bibtex] [paper]

Intervisibility on terrains
Leila De Floriani, Paola Magillo
Geographical information systems, vol. 1, pages 543--556, 1999
[bibtex] [paper]

abstract Many interesting application problems on terrains involve visibility computations; for example, the search for optimal locations of observation points, line-of-sight communication problems, and the computation of hidden or scenic paths. The solution of such problems needs techniques to answer visibility queries on a terrain efficiently, and/or the development of data structures encoding the visibility of a terrain from one or several viewpoints. In this Chapter, we introduce visibility structures such as the viewshed (representing the portions of a terrain visible from a single viewpoint) and the horizon (describing the distal boundary of the viewshed), as well as visibility structures related to several viewpoints. All these structures admit continuous and discrete encodings (mainly used on TINs and RSGs, respectively). We provide an overview of algorithms for building visibility structures on TINs and RSGs as well as for answering visibility queries on a terrain. Finally, we illustrate some application-specific problems involving visibility computation.

Multiresolution Representation of Shapes Based on Cell Complexes
Leila De Floriani, Paola Magillo, Enrico Puppo
Discrete Geometry for Computer Imagery, pages 3--18, 1999
[bibtex] [paper] [doi]

abstract This paper introduces a dimension-independent multiresolution model of a shape, called the Multi-Complex (MC), which is based on decomposition into cells. An MC describes a shape as an initial cell complex approximating it, plus a collection of generic modification patterns to such complex arranged according to a partial order. The partial order is essential to extract variable-resolution shape descriptions in real time. We show how existing multiresolution models reduce to special cases of MCs characterized by specific modification patterns. The MC acts as a unifying framework that is also useful for comparing and evaluating the expressive power of different approaches.

Efficient implementation of multi-triangulations
Leila De Floriani, Paola Magillo, Enrico Puppo
Visualization '98. Proceedings, pages 43--50, 1998
[bibtex] [paper] [doi]

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

Managing the level of detail in 3d shape reconstruction and representation
Leila De Floriani, Paola Magillo, Enrico Puppo
Proceedings 14th International Conference on Pattern Recognition, 1998
[bibtex] [paper] [doi]

abstract The problem of reconstructing and representing the shape of a three-dimensional object from sparse data is considered, with special emphasis on the level of detail of the representation. To this aim, we provide a model that support a multiresolution representation of a shape, which is based on a set of local sculpturing updates on an initial tetrahedral mesh of the convex hull of the given data points. We provide an efficient algorithm for extracting representations of the shape at different levels of detail, possibly variable over different portion of the object, as well as a new sculpturing algorithm for building the multiresolution model from the initial dataset. No limitation on the genus of the reconstructed shape is imposed.

Virtual environment generation by CAD-based methodology for underwater vehicle navigation
Leila De Floriani, Vittorio Murino, Goffredo G. Pieroni, Enrico Puppo
Proceedings IX European Signal Processing Conference, 1998
[bibtex] [paper]

abstract We describe a recognition framework to generate a virtual environment through CAD-based vision techniques applied to optical data. Descriptions of objects of the environment in terms of aspect graphs, and suitable recognition strategies for them are compiled off-line. A relational graph of image features is obtained on-line by processing optical data, and matching occurs between such a graph, and descriptions of objects in the framed scene. Multiresolution techniques are used in order to adapt recognition strategies to the distance and relevance of objects within the field of view.

Selective Refinement of Surface Meshes: Data Structures and Algorithms
L. De Floriani, P. Magillo, E. Puppo
Technical Report PDISI-98-02, Computer and Information Science Department (DISI), University of Genova, 1998
[bibtex] [paper]

abstract Selective refinement is an operation acting on multiresolution surface models, aimed to provide a mesh approximation with a resolution variable over the surface. We address some effciency issues related to selective refinement, and we present some results on data structures and algorithms that work on a multiresolution triangle-based model, called a Multi-Triangulation. In particular, we analyze the trade-off between storage costs of data structures, and computational effciency of algorithms they can support; and we propose algorithms for variants of selective refinement, combined with some spatial queries of interest in the applications.

Power Diagram Depth Sorting
Paolo Cignoni, Leila De Floriani
Proceedings 10th Canadian Conference on Computational Geometry, 1998
[bibtex] [paper]

Compressing TINs
Leila De Floriani, Paola Magillo
Proceedings 6th ACM Symposium on Geographic Information Systems, pages 145--150, 1998
[bibtex] [paper] [doi]

abstract We address the problem of designing compact data structures for encoding a Triangulated IrreguIar Network (TIN) as a sequential bltstrearn. In particular, we study the problem of compressing connectivity, i.e., the information describing the topological structure of the TIN and we propose two new compression methods which have different purposes. The goal of the first method is to minimize the number of bits needed to encode connectivity information it encodes each wrtaY once, and requires two lits of connectivity information for each edge of a TIN. We present efficient algorithms for coding and decoding the corresponding bitstream and show some practical evaluation of the method. The second method compresses a TIN at progressive levels of detail and is based on a strategy which iteratively removes a vertex from a TIN according to an error-based criterion. Encoding and decoding algorithms are presented and compared with other approaches to progressive compression.

Building and traversing a surface at variable resolution
Leila De Floriani, Paola Magillo, Enrico Puppo
Proceedings Visualization'97, pages 103--110, 1997
[bibtex] [paper] [doi]

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

Visualizing parametric surfaces at variable resolution
Leila De Floriani, Paola Magillo, Enrico Puppo
Image Analysis and Processing, pages 308--315, 1997
[bibtex] [paper] [doi]

abstract A multiresoltion model is presented capable of handling different piecewise-linear approximations of a boundary representation of a solid object where faces are described by parametric surfaces. The level of detail of an approximation may be variable over different portions of the boundary, and the continuity of the surface across different patches is guaranteed.

A formal approach to multiresolution hypersurface modeling
Leila De Floriani, Enrico Puppo, Paola Magillo
Geometric Modeling: Theory and Practice, pages 302--323, 1997
[bibtex] [paper] [doi]

abstract Multiresolution geometrie models support the representation and processing of geometric entities at different levels of detail, and are useful in several application fields, such as geographic information systems, CAD systems and scientific visualization. The aim of this paper is to provide a framework for multiresolution geometric modeling, independent both of the dimension of spatial objects under consideration, and of the specific application. This paper introduces a formal model, called the Multiresolution Simplicial Model (MSM), capable of capturing the characteristics of most multiresolution models proposed in the literature. The paper provides an analysis of the relationships between the intrinsic structures of different multiresolution models, as well as a definition of relevant application-independent operations on them. Major data structures used to encode multiresolution models are reviewed, as well as algorithms which implement the operations on each data structure.

Visibility computations on hierarchical triangulated terrain models
Leila De Floriani, Paola Magillo
GeoInformatica, vol. 1(3), pages 219--250, 1997
[bibtex] [paper] [doi]

abstract Hierarchical terrain models provide a multiresolution description of a topographic surface based on a nested partition of the domain. The tree-like structure of these models is an effective support to processing spatial operations. In this paper, we consider visibility computations on hierarchical terrain models based on triangular subdivisions, called Hierarchical Triangulated Irregular Networks (HTINs). We address two basic problems in visibility computation, namely determining the visibility of a query object, and computing the viewshed of a given viewpoint. We propose algorithms for performing such operations on an HTIN at variable resolution. A general drawback of hierarchical models is in the inconsistency of representations at variable resolution obtained from them, since vertical gaps may occur at edges where different resolutions meet. The algorithms proposed here avoid this undesired effect. A related, but independent, contribution of this paper is also a new algorithm for extracting a consistent terrain representation at variable resolution from an HTIN.

Multiresolution representation and reconstruction of triangulated surfaces
Leila De Floriani, Paola Magillo, Enrico Puppo
Advances in Visual Form Analysis, Singapore, pages 140--149, 1997
[bibtex] [paper]

abstract A multiresolution triangle mesh is a geometric model providing representations of a surface at different levels of detail. A fairly general model is proposed, called a multiresolution triangulation (MT), capable of efficiently encoding a wide range of levels of detail. An MT supports efficient extraction of a representation of minimum size for a given application-dependent level of detail, which may be variable over the surface. The model is based on a collection of mesh fragments arranged into a partial order. Different levels of detail are obtained by combining different fragments according to rules controlled by the partial order. We illustrate general construction and extraction techniques, as well as applications of the MT in a variety of situations, ranging from the approximation of CAD surfaces to the reconstruction of unknown surfaces from scattered data.

VARIANT—processing and visualizing terrains at variable resolution
Leila De Floriani, Paola Magillo, Enrico Puppo
Proceedings of the 5th ACM international workshop on Advances in geographic information systems, pages 15--19, 1997
[bibtex] [paper] [doi]

abstract We describe VARIANT (VAriabIe Resolution Interactive Analysis of Terrains), a prototype system for processing and visualizing terrains nt variable resolution, which is based on a multiresolution terrain model, called a Multi-Triangulation (MT).

Multiresolution models for topographic surface description
Leila De Floriani, Paola Marzano, Enrico Puppo
The Visual Computer, vol. 12(7), pages 317--345, 1996
[bibtex] [paper]

abstract Multiresolution terrain models describe a topographic surface at various levels of resolution. Besides providing a data compression mechanism for dense topographic data, such models enable us to analyze and visualize surfaces at a variable resolution. This paper provides a critical survey of multiresolution terrain models. Formal definitions of hierarchical and pyramidal models are presented. Multiresolution models proposed in the literature (namely, surface quadtree, restricted quadtree, quaternary triangulation, ternary triangulation, adaptive hierarchical triangulation, hierarchical Delaunay triangulation, and Delaunay pyramid) are described and discussed within such frameworks. Construction algorithms for all such models are given, together with an analysis of their time and space complexities.

Multiresolution modeling in geographical information systems
Leila De Floriani, Paola Marzano, Enrico Puppo
Spatial Analytical Perspectives on GIS, GISDATA Series, vol. 4, pages 9--19, 1996
[bibtex]

Representing the visibility structure of a polyhedral terrain through a horizon map
Leila De Floriani, Paola Magillo
International Journal of Geographical Information Systems, vol. 10(5), pages 541--561, 1996
[bibtex] [paper] [doi]

abstract 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 Comprehensive Framework for Spatial Operations on Hierarchical Terrain Models
Leila De Floriani, Paola Magillo
DISI-TR-96-15, Dipartimento di Informatica e Scienze dell'Informazione, Universita' di Genova, 1996
[bibtex] [paper]

abstract In this paper we provide an overview of the state-of-the-art about data structures and algorithms for spatial operations on hierarchical models of terrains. Hierarchical terrain models provide a multiresolution description of a topographic surface based on a nested partition of the domain; they are different from quadtree-based terrain models, which are also based on the principle of a recursive decomposition, since the decomposition in hierarchical terrains is accuracy-driven, i.e., each level of refinement in the model corresponds to a terrain approximation within a predefined error tolerance. The tree-like structure of a hierarchical terrain model provides an effective support to processing spatial operations. Spatial operations can be classified into general-purpose and application-specific operations. General-purpose operations on hierarchical terrain models correspond to basic functions, which must be supported in any environment, and include the extraction of a terrain representation at a user-defined level of resolution, and answering interference queries (e.g., point location, segment and region intersection), at a certain resolution. Application-dependent operations considered in this paper are overlay computation and visibility determination. In this paper we overview the methods for solution of the above mentioned spatial operations, within the various types of existing data structures, proposed for representing hierarchical terrain models. Some experimental results from implementations within a prototype system are reported.

Maintaining Multiple Levels of Detail in the Overlay of Hierarchical Sub Divisions
P. Magillo, L. De Floriani
Proceedings Canadian Conference on Computational Geometry 1996
[bibtex] [paper]

abstract In this paper, we consider the problem of obtaining a hierarchical structure representing the overlay of two hierarchical subdivisions at multiple resolutions. This problem has an impact in geographic information systems, where the issue of overlapping two maps at multiple resolutions has a relevant importance. We provide a formal definition of such an overlay hierarchy, and propose an efficient bottom-up algorithm to compute it.

Generating assembly and machining sequences from the Face-to-Face Composition model
Michela Bertolotto, Elisabetta Bruzzone, Leila De Floriani, George Nagy
Computer-Aided Design, vol. 28(2), pages 101--112, 1996
[bibtex] [paper] [doi]

abstract Modular boundary models are a class of solid models which describe solids as collections of face-abutting object parts. The Face-to-Face Composition (FFC) model is a specific model belonging to this class which contains explicit information about connection and interference among object components. In the FFC model, juxtaposition and interference are represented through a graph-theoretic structure, in which nodes describe object components and hyperarcs connection and internal portions of the component boundaries. Necessary and sufficient conditions for an FFC model to be valid are defined in terms of its graph representation. The problem of producing valid FFC models from the decomposition of the FFC model of a given object into subparts is studied in connection with the generation of a production graph, which describes assembly and machining sequences, that can be extracted from an FFC model, in the form of an and/or graph.

Variable resolution operators on a multiresolution terrain model
L. De Floriani, P. Magillo, E. Puppo, M. Bertolotto
Proceedings of the 4th ACM international workshop on Advances in geographic information systems, pages 121--128, 1996
[bibtex] [paper] [doi]

abstract Multiresolution terrain models provide a compact description of a topographic surface at multiple levels of accuracy, and they are useful in several applications to access terrain representations where the resolution in each area is defined based on application needs. In this paper we focus on a model, called the Multiresolution Triangular Model (MTM), which generalizes many other multiresolution models proposed in the literature, and is based on a collection of fragments of plane triangulations organized into a directed acyclic graph. We consider a set of basic spatial operations, which include the extraction of a terrain representation at a user-defined level of resolution, as well as answering interference (e.g., point location, segment and region intersection) and navigation queries, at a certain resolution. We present two data structures to encode the MTM, and related algorithms to perform the above operations. Experimental results from implementation within a prototype system are reported.

Horizon computation on a hierarchical triangulated terrain model
Leila De Floriani, Paola Magillo
The Visual Computer, vol. 11(3), pages 134--149, 1995
[bibtex] [paper]

abstract Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon computation problem on a hierarchical polyhedral terrain (in particular, on a hierarchical triangulated irregular network), which involves extracting the horizon of a viewpoint at a given resolution and updating it as the resolution increases. We present an overview of horizon computation algorithms on a nonhierarchical polyhedral terrain. We extend such algorithms to the hierarchical case by describing a method which extracts the terrain edges at a given resolution, and proposing a randomized algorithm for dynamically updating a horizon under insertions and deletions of terain edges.

Hierarchical triangulation for multiresolution surface description
Leila De Floriani, Enrico Puppo
ACM Transactions on Graphics (TOG), vol. 14(4), pages 363--411, 1995
[bibtex] [paper] [doi]

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

Pyramidal simplicial complexes
Michela Bertolotto, Leila De Floriani, Paola Marzano
Proceedings of the third ACM symposium on Solid modeling and applications, pages 153--162, 1995
[bibtex] [paper] [doi]

A unifying framework for multilevel description of spatial data
Michela Bertolotto, Leila De Floriani, Paola Marzano
Spatial Information Theory A Theoretical Basis for GIS, pages 259--278, 1995
[bibtex] [paper] [doi]

abstract Defining a unifying model for describing spatial data at different levels of resolution is a relevant issue in several applications involving spatial data handling. Also, dimension-independence is becoming fundamental in many application contexts. We propose a unifying model for multiresolution description of spatial data which works in arbitrary dimension. Graph-based representations for encoding different instances of the abstract model are described.

Updating visibility information on multiresolut ion terrain models
Paola Magillo, Leila De Floriani, Elisabetta Bruzzone
Spatial Information Theory A Theoretical Basis for GIS, pages 279--296, 1995
[bibtex] [paper]

abstract We propose a new randomized incremental approach to visibility update on a terrain model when varying the level of resolution. In particular, we consider visibility update on multiresolution terrain models, which encode surface descriptions at different resolution degrees. Randomized dynamic algorithms for upper envelope of triangles and segments are used for updating the visible image and the horizon, respectively. In this paper, we propose a new randomized dynamic algorithm for upper envelope of triangles, which is an extension of the semi-dynamic algorithm by Boissonnat and Dobrindt. A dynamic algorithm for computing the upper envelope of segments was proposed in a previous paper. It is shown that, under suitable conditions, the update of visibility information by means of these algorithms is more convenient than a complete recomputation.

Overlapping Hierarchical Maps
Michela Bertolotto, Paola Magillo, Leila De Floriani
Proceedings ACM International Workshop on Advances in Geographic Information Systems, 1995
[bibtex] [paper]

abstract We have extended the classical map overlay problem to the case in which the two maps are described by hierarchies of subdivisions. We propose two different algorithms for solving the hierarchical map overlay problem, which are based on an extension of existing classical algorithms. The main contribution of this work is in the definition of a sweep-line algorithm for hierarchical overlay, which exhibits a reduced time and space complexity in practical cases by exploiting the hierarchical structure of the given maps.

Multiresolution representation of volume data through hierarchical simplicial complexes
M. Bertolotto, L. De Floriani, E. Bruzzone, E. Puppo
Aspects of visual form processing, pages 73--82, 1994
[bibtex]

Spatial Queries on a Hierarchical Terrain Model
Leila De Floriani, Giacomo Gattorna, Paola Marzano, Enrico Puppo
Proceedings 6th International Symposium on Spatial Data Handling, pages 819--834, 1994
[bibtex] [paper]

abstract In this paper we consider the problem of defining and answering spatial queries on hierarchical terrain models that provide a multiresolution representation. In particular, we focus our attention on interference queries in which the query object is a spatial entity not belonging to the model. We propose algorithms for efficiently answering such queries on a triangle-based hierarchical model.

Computing point visibility on a terrain based on a nested horizon structure
Leila De Floriani, Paola Magillo
Proceedings ACM Symposium on Applied Computing '94, vol. 94, pages 318--322, 1994
[bibtex] [paper]

abstract In this paper, we define the concepts of horizons and shadows with respect to a fixed viewpoint. We introduce a model, called the in infuence map, for describing the visibility of a terrain from a viewpoint, based on a sequence of nested horizons. The influence map can be encoded as a balanced tree, called the influence tree, which has a spatial complexity of O ( n 2 log n ) for a polyhedral terrain with n vertices. We show that a point visibility query on such structure can be answered in O (log 2 n ) time.

Hierarchical hypersurface modeling
Michela Bertolotto, Leila De Floriani, Enrico Puppo
IGIS '94: Geographic Information Systems, pages 88--97, 1994
[bibtex] [paper] [doi]

abstract We propose a new model for representing a hypersurface describing a scalar field in any dimension at different levels of detail. The model is based on a decomposition of the domain into a hierarchy of simplicial complexes. We present a data structure for encoding such model as well as an algorithm for building a multiresolution representation of a hypersurface based on a decreasing sequence of tolerance values.

Line-of-sight communication on terrain models
Leila De Floriani, Paola Marzano, Enrico Puppo
International Journal of Geographical Information Systems, vol. 8(4), pages 329--342, 1994
[bibtex] [doi]

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

Parallelizing visibility computations on triangulated terrains
L. De Floriani, C. Montani, R. Scopigno
International Journal of Geographical Information Systems, vol. 8(6), pages 515--531, 1994
[bibtex] [paper] [doi]

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

Visibility algorithms on triangulated digital terrain models
Leila De Floriani, Paola Magillo
International Journal of Geographical Information Systems, vol. 8(1), pages 13--41, 1994
[bibtex] [paper] [doi]

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

An efficient representation for pyramidal terrain models
Michela Bertolotto, Leila De Floriani, Paola Marzano
Proceedings 2nd ACM Symposium on Advances in GIS, 1994
[bibtex]

Computing visibility maps on hierarchical terrain models
Leila De Floriani, Paola Magillo
Proc. 2nd ACM Workshop on Advances in GIS, 1994
[bibtex] [paper]

abstract Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution representation as well as a data compression mechanism. Visibility problems on hierarchical terrain models present two aspects: visibility, related to a terrain representation at a certain resolution level, and visibility, as the required resolution changes. Here, we address the first aspect of the problem: the specific visibility problem considered consists of determining the portions of the surface of a terrain which are visible from a predefined viewpoint. In our solutions, visibility is computed through a of the multilevel structure of a hierarchical terrain model, thus avoiding a pre-computation of an explicit model representing the surface at the given resolution. We describe a hierarchical extension of two widely used approaches to visibility computation on polyhedral terrains: the method based a front-to-back traversal of the terrain, and the sweep-line method. We show how a procedure which traverses the structure of a hierarchical model can be incorporated into any algorithm working with one of these approaches without increasing its time or space complexity.

Multiresolution Topological Maps
M. Bertolotto, L. De Floriani, E. Puppo
Advanced Geographic Data Modelling - SpatialData Modelling and Query Languages for 2D and 3D Applications, 1994
[bibtex]

Spatial queries and data models
Leila De Floriani, Paola Marzano, Enrico Puppo
Spatial Information Theory A Theoretical Basis for GIS, pages 113--138, 1993
[bibtex] [paper] [doi]

abstract We present a unified framework for classifying and answering spatial queries relevant to a Geographic Information System. We classify spatial queries into topological, set-theoretic, and metric queries, on the basis of the kind of relationships between the query object and entities in the search space involved. For answering such queries, we propose an approach that combines an object-based description of spatial entities, provided by a topological model, with a partition of the space embedding such entities, given by a spatial index. In particular, we propose a new unified topological model, called the Plane Euclidean Graph (PEG), that is capable of describing point, line, and region data, and that incorporates relational operators on such entities. We briefly describe major techniques, rooted in computational geometry, for solving interference queries and overlays on such a data model. Finally, we describe the use of a superimposed spatial index for speeding up searches and answering queries involving distances.

Computing visibility maps on a digital terrain model
Leila De Floriani, Paola Magillo
Spatial Information Theory A Theoretical Basis for GIS, pages 248--269, 1993
[bibtex] [paper] [doi]

abstract In this paper, we present a model based on a collection of nested horizons to describe the visibility of a terrain with respect to a viewpoint. We introduce first a formalization of mathematical and digital terrain models, and some background notions for visibility problems on terrains. Then, we define horizons and shadows on a polyhedral terrain, and introduce a few horizon-based visibility maps of a terrain. Finally, we present two algorithms for building the nested horizons on a polyhedral terrain. An application to the solution of point-to-point visibility queries are briefly discussed.

Algorithms for visibility computation on digital terrain models
Leila De Floriani, Paola Magillo
Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing, pages 380--387, 1993
[bibtex] [paper] [doi]

abstract In the paper, we consicler the problem of computing visibility information on cligit al terrain models. Visibility problems on polyhedral terrains are classified according to the kind of visibility information computed into point visibility, line visibility and region visibility. A survey of the stateof-the-art of the algorithlns for computing visibility is presented, according to the chssification introduced.

Extracting contour lines from a hierarchical surface model
Leila De Floriani, Daniela Mirra, Enrico Puppo
Computer Graphics Forum, vol. 12(3), pages 249--260, 1993
[bibtex] [doi]

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.

Acyclic Hierarchical Cell Complexes
M. Bertolotto, E. Bruzzone, L. De Floriani
Proceedings 5th Canadian Conference on Computational Geometry, pages 279--284, 1993
[bibtex]

Extraction and Representation of Shape Features for CAD/CAM Applications
L. De Floriani, E. Puppo
Visual Form, pages 187--196, 1992
[bibtex] [doi]

abstract We consider the two issues of recognizing and representing shape features in the context of a CAD/CAM application. A definition of shape feature is introduced and a classification is attempted. The major approaches to automatic recognition of shape features are classified, and some representative methods are described. Finally, the problem of shape feature description is discussed, and modular boundary models are proposed as an effective support for feature-based object description.

A hierarchical triangle-based model for terrain description
Leila De Floriani, Enrico Puppo
Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, pages 236--251, 1992
[bibtex] [paper] [doi]

abstract This article describes a new hierarchical model for representing a terrain. The model, called a Hierarchical Triangulated Irregular Network (HTIN), is a method for compression of spatial data and representation of a topographic surface at successively finer levels of detail. A HTIN is a hierarchy of triangle-based surface approximations, where each node, except for the root, is a triangulated irregular network refining a triangle face belonging to its parent in the hierarchy. In this paper we present an encoding structure for a HTIN and we describe an algorithm for its construction.

Visibility-related image features
L. De Floriani, P. Jeanne, G. Nagy
Pattern Recognition Letters, vol. 13(6), pages 463--470, 1992
[bibtex] [doi]

abstract The intervisibility of two points in a digital grey-scale image array is defined by analogy between the intensity values of the picture elements and surface elevation on topographic surfaces. The distributions of the pairwise visibility (a boolean function) between image points, of the visibility count of the number of points visible from each point, and of the distance of the horizon from each point in selected directions, reveal significant image characteristics. These features allow the classification of images according to type, and subregions according to content and environment. The discriminating power of these features is augmented by the introduction of an observation height that allows shifting emphasis from local to global characteristics.

Visibility computation on a triangulated terrain
M. Cazzanti, L. De Floriani, E. Puppo, G. Nagy
Progress in Image Analysis and Processing II, pages 721--728, 1992
[bibtex]

Applying two-dimensional delaunay triangulation to stereo data interpolation
E. Bruzzone, M. Cazzanti, L. De Floriani, F. Mangili
Computer Vision — ECCV'92, pages 368--372, 1992
[bibtex] [paper] [doi]

abstract Interpolation of 3D segments obtained through a trinocular stereo process is achieved by using a 2D Delaunay triangulation on the image plane of one of the vision system cameras. The resulting two-dimensional triangulation is backprojected into the 3D space, generating a surface description in terms of triangular faces. The use of a constrained Delaunay triangulation in the image plane guarantees the presence of the 3D segments as edges of the surface representation.

An on-line algorithm for constrained Delaunay triangulation
L. De Floriani, E. Puppo
CVGIP: Graphical Models and Image Processing, vol. 54(4), pages 290--300, 1992
[bibtex] [doi]

abstract A constrained Delaunay triangulation is a Delaunay triangulation of a set of points and straight-line segments. A constrained Delaunay triangulation is a basic tool for describing a topographic surface in several applications. In this paper, the definition of constrained Delaunay triangulation is introduced and its basic properties are discussed. Existing algorithms for constrained Delaunay triangulation are briefly analyzed. A new on-line algorithm for constrained Delaunay triangulation that is based on the stepwise refinement of an existing triangulation by the incremental insertion of points and constraint segments is proposed.

Hybrid Models and Conversion Algorithms for Solid Object Representation
Leila De Floriani, Enrico Puppo
Scientific Visualization of Physical Phenomena, pages 457--483, 1991
[bibtex] [doi]

abstract Traditional object representation schemes are often inadequate for supporting the variety of object manipulation tasks required in a modern solid modeling system. Hybrid schemes try to achieve a higher representative power by embedding the characteristics of several traditional models. The schemes we consider are Modular Boundary Models (MBMs), which describe the boundary of a solid object as the combination of face-abutting object parts represented in a boundary form, PM-Octrees, which are a combination of octrees and boundary representation, and PM-CSG trees, which are essentially octrees whose leaves represent CSG primitives. In particular, we will focus our attention on an MBM, called the Face-to-Face Composition (FFC) model, which also stores interference information useful to perform Boolean operations. We discuss the problems involved in conversion algorithms which operate between traditional models, and we review conversion algorithms on PM-Octrees and PM-CSG trees. We present a new algorithm for boundary evaluation of an FFC model, and discuss the problem of producing an FFC model from a boundary representation.

Validity issues for modular boundary models
E.Bruzzone, L. De Floriani
Proceedings Eurographics, vol. 91, pages 115--126, 1991
[bibtex]

Structured graph models: An efficient tool for VLSI design
M. Ancona, K. S. Bagga, E. Bruzzone, L. De Floriani, J. S. Deogun
Computing in the 90's, pages 307--312, 1991
[bibtex] [paper] [doi]

abstract Hierarchical graph models are a powerful tool for describing VLSI circuits. They combine the representation of a hierarchical decomposition of a circuit with a graph description of its topological structure in terms of components and connections. Structured Graphs are an example of such models. In this paper we consider the graph-theoretic problems of spanning trees and Steiner trees in structured graphs. These have connections with the global routing problems in VLSI circuits.

Using structured steiner trees for hierarchical global routing
Massimo Ancona, Elisabetta Bruzzone, Leila De Floriani
International Journal of Computer Mathematics, vol. 39(3-4), pages 169--192, 1991
[bibtex] [doi]

abstract The Steiner problem in a hierarchical graph model, the structured graph, is defined. The problem finds applications to hierarchical global routing. Properties of minimum-cost Steiner trees in structured graphs are investigated. A “top-down” approximate solution to the Steiner problem in structured graphs, called a top-down Steiner tree, is defined, and an algorithm is given to compute such solution. The top-down Steiner tree provides also an approximate solution to the Steiner problem in graphs admitting a structured representation. The properties of such solution are discussed and some experimental results on the quality of the approximation are presented. A reduction in time complexity is demonstrated with respect to both exact and heuristic algorithms applied to such graphs.

HIDEL: A Language for Hierarchical VLSI Design
M. Ancona, A. Clematis, L. De Floriani, E. Puppo
The Computer Journal, vol. 34(5), pages 195--206, 1991
[bibtex] [paper]

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

Representation of solid objects by a modular boundary model
Leila De Floriani, Amitava Maulik, George Nagy
Computer-Aided Mechanical Assembly Planning, pages 41--80, 1991
[bibtex] [doi]

abstract The geometric representation of man-made objects has always been considered essential for their design and construction. It is inconceivable that cathedrals, catapults, caravels and clockworks could have reached their level of perfection without the concurrent development of graphic tools as the lingua franca between designers, clients (“end-users”), and artisans. Drafting conventions were gradually refined and formalized according to the requirements of different disciplines (sheet metal, piping, trusses, part and assembly drawings, renderings). Till recently, “mechanical drawing” formed an important component of engineering and architectural education.

Extracting adjacency relationships from a modular boundary model
E. Bruzzone, L. De Floriani
Computer-Aided Design, vol. 23(5), pages 344--355, 1991
[bibtex] [paper] [doi]

abstract Modular boundary models are a class of object representations that describe a solid object as a collection of face-abutting components. The face-to-face relationships between components are described in the form of a graph, called the connection graph. The paper addresses the problem of extracting adjacency information from a description of a solid object in terms of a modular boundary model, the FFC model. The encoding structure of the connection graph in such a model is described, and a set of structure-accessing algorithms for retrieving the adjacency relationships from the resulting data structure is defined. Finally, an extension to the connection graph to support instances is briefly presented, and the problems related to the development of adjacency-finding algorithms for such a structure are discussed.

On sorting triangles in a delaunay tessellation
Leila De Floriani, Bianca Falcidieno, George Nagy, Caterina Pienovi
Algorithmica, vol. 6(1-6), pages 522--532, 1991
[bibtex] [paper] [doi]

abstract In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.

Two data structures for building tetrahedralizations
Elisabetta Bruzzone, Leila De Floriani
The Visual Computer, vol. 6(5), pages 266--283, 1990
[bibtex] [paper] [doi]

abstract A polyhedral decomposition can be unambiguously described as the collection of four primitive elements (i.e., polyhedra, facets, edges, and vertices) plus their mutual adjacency relations. We consider here the problem of representing a specific kind of polyhedral decomposition, i.e., a tetrahedralization. We describe two different representations for a tetrahedralization. The first one can only model polyhedral decompositions with tetrahedral cells, while the second one is suitable for describing any partition of a volume into polyhedral cells with triangular facets. We present two sets of primitive Euler operators, which build and manipulate such representations while maintaining their topological integrity. The use of such operators is demonstrated in connection with two algorithms for building a Delaunay tetrahedralization, which show the different hedralization, which show the different uses of the two representations.

Reconstructing three-dimensional shapes through Euler operators
E. Bruzzone, L. De Floriani, E. Puppo
Progress in Image Analysis and Processing, 1990
[bibtex]

Visibility characteristics of grey-scale images
L. De Floriani, G. Nagy, P. Jeanne
Progress in Image Analysis and Processing, 1990
[bibtex]

Structured Spanning Trees
M. Ancona, L. De Floriani, J. S. Deogun
The Computer Journal, vol. 33(4), pages 344--355, 1990
[bibtex] [paper] [doi]

abstract The spanning tree problem in the framework of a hierarchical graph structure, called a structured graph, is considered. A structured graph is a hierarchy of graphs which provides a relational description of an entity at different levels of abstraction. The concept of structured graph is briefly reviewed and some of its properties are presented. The concept of structured spanning tree is defined and its relationship with ‘canonical’ spanning trees is investigated. An algorithm is presented for computing a structured spanning tree of a graph from its canonical spanning tree. An algorithm for finding a minimum-cost canonical spanning tree of a graph by operating on its structured graph representation is developed. The study of structured spanning trees is motivated by their application to hierarchical design and processing of VLSI circuits and communication networks.

An Efficient Data Structure for Three-Dimensional Triangulations
Elisabetta Bruzzone, Leila De Floriani
CG International 90, pages 425--442, 1990
[bibtex] [doi]

abstract A three-dimensional tesselation can be described by four basic topological elements (vertices, edges, faces, and polyhedral cells) plus their mutual pairwise relations. We present a specific data structure for encoding a three-dimensional tesselation composed of a collection of quasi-disjoint tetrahedra, i.e., a three-dimensional triangulation, and discuss those structure accessing algorithms which retrieve the relations not explicitly stored in the structure. A set of primitive operators for building and manipulating a 3D triangulation are presented. Their use is demonstrated in connection with an algorithm for computing a 3D Delaunay triangulation.

A graph model for face-to-face assembly
L. De Floriani, G. Nagy
Proceedings, 1989 IEEE International Conference on Robotics and Automation, pages 75--78, 1989
[bibtex] [paper] [doi]

abstract 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

Feature extraction from boundary models of three-dimensional objects
Leila De Floriani
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 11(8), pages 785--798, 1989
[bibtex] [paper] [doi]

abstract 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

Decomposing a solid object into elementary features
Leila De Floriani, Elisabetta Bruzzone
Recent Issues in Pattern Analysis and Recognition, pages 226--237, 1989
[bibtex] [paper] [doi]

abstract We describe an algorithm for extracting form features, like protrusions or depressions on a face, through-holes or handles, from a relational boundary model of a solid object, called the Symmetric Boundary Graph (SBG). The method is based on loop identification and connected component labeling on the SBG and produces a decomposition of the object boundary into volumetric components describing features. Such a decomposition is represented as a directed labeled multigraph, called the Object Decomposition Graph.

A Survey of Constrained Delaunay Triangulation Algorithms for Surface Representation
L. De Floriani, E. Puppo
Issues on Machine Vision, pages 95--104, 1989
[bibtex] [doi]

abstract The Constrained Delaunay Triangulation (CDT) is the basis for building surface models in a variety of applications. The paper introduces the notion of constrained Delaunay triangulation and presents its fundamental properties. The basic algorithms proposed in the literature for building a CDT are classified and briefly described.

Hierarchical global routing through structured Steiner trees
E. Bruzzone, L. De Floriani
IEEE International Symposium on Circuits and Systems, pages 61--65, 1989
[bibtex] [paper] [doi]

abstract The Steiner problem in a hierarchical graph model, called a structured graph, is defined for a specific application to the hierarchical global routing problem. Properties of minimum-cost Steiner trees in structured graphs are investigated. A top-down solution to the Steiner problem in structured graphs is defined, and an algorithm is given in order to compute such a solution (or an approximation) on the basis of existing exact or heuristic algorithms for solving the Steiner problem on graphs

Manipulating a modular boundary model with a face-based graph structure
L. De Floriani, A. Maulik, G. Nagy
Geometric Modeling for Product Engineering, Wozny, M. et al, editors. IFIP
[bibtex]

Manipulating three-dimensional triangulations
Elisabetta Bruzzone, Leila De Floriani, Enrico Puppo
Foundations of Data Organization and Algorithms, pages 339--353, 1989
[bibtex] [paper] [doi]

abstract The three-dimensional symmetric data structure is a topological model of a three-dimensional triangulation. It is a generalization of the symmetric structure proposed by Woo [Woo85] for describing the boundary of a solid object. In the paper, we present the basic topological elements of a 3D triangulation and their mutual relations. We describe the 3D symmetric structure and present structure accessing algorithms for retrieving those relations which are not explicitly encoded in the structure. Finally, a minimal set of primitive operators for building and manipulating a 3D triangulation are discussed. Such operators are independent of the underlying data structure.

Structured graph representation of a hierarchical triangulation
L. De Floriani, B. Falcidieno, C. Pienovi
Computer Vision, Graphics, and Image Processing, vol. 45(2), pages 215--226, 1989
[bibtex] [doi]

abstract The problem of representing a 212-dimensional surface at variable degrees of accuracy is considered. A hierarchical model, called a hierarchical triangulation, is described which approximates a surface by a network of triangular, planar facets whose projections in the plane are nested. In the paper, a dual representation of such a triangulation in the form of a structured graph is defined and the fundamental properties of this representation are discussed. An algorithm for converting a hierarchical triangulation into its dual form is given. As an example of application, an algorithm is described for the conversion of the dual graph into the standard triangle-oriented structure used for encoding triangulated irregular networks.

A pyramidal data structure for triangle-based surface description
Leila De Floriani
IEEE Computer Graphics and Applications, vol. 9(2), pages 67--78, 1989
[bibtex] [paper] [doi]

abstract A hierarchical model for approximating 2-1/2-dimensional surfaces is described. This model, called a Delaunay pyramid, is a method for compression of spatial data and representation of a surface at successively finer levels of detail. A Delaunay pyramid is based on a sequence of Delaunay triangulations of suitably defined subsets of the set of data points. A triangle-oriented encoding structure for a Delaunay pyramid is presented, and its storage complexity is evaluated. An algorithm for constructing a Delaunay pyramid is described, and a method for solving the point location and evaluation on such a model is discussed

Building a feature-based object description from a boundary model
L. De Floriani, E. Bruzzone
Computer-Aided Design, vol 21(10), pages 602--610, 1989
[bibtex] [doi]

abstract Form features, like protrusions or depressions on a face, through-holes or handles, can be extracted from a relational boundary model of a solid object, called the ‘symmetric boundary graph’ by loop identification and connected component labelling. The result is a decomposition of the object boundary into volumetric components describing features, which is represented as a directed labelled multigraph, called the ‘object decomposition graph’. Based on such a model, issues such as representation uniqueness and matching of object descriptions are discussed.

A hierarchical boundary model for solid object representation
L. De Floriani, B. Falcidieno
ACM Transactions on Graphics (TOG), vol. 7(1), pages 42--60, 1988
[bibtex] [paper] [doi]

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

Surface representations based on triangular grids
Leila De Floriani
The Visual Computer, vol. 3(1), pages 27--50, 1987
[bibtex] [paper] [doi]

abstract The problem of representing 2 1/2 dimensional surfaces defined at a set of randomly located points by means of triangular grids is considered. Such representations approximate a surface as a network of planar, triangular faces with vertices at the data points. In the paper we describe different models and data structures for encoding triangular grids. Since Delaunay triangulation provides a common basis for many models of 2 1/2 D surfaces, we review its basic properties and we describe the most important approaches to its construction. Hierarchical surface models are also presented, which are based on nested triangulations of the surface domain and provide variable resolution surface representations. An algorithm is described for building a hierarchical description of a nested triangulation at different levels of abstraction. Finally, the 3D surface reconstruction problem is briefly discussed.

A graph based approach to object feature recognition
Leila De Floriani
Proceedings of the third annual symposium on Computational geometry, pages 100--109, 1987
[bibtex] [paper] [doi]

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

Path Problems in Structured Graphs
M. Ancona, L. De Floriani, J. S. Deogun
The Computer Journal, vol. 29(6), pages 553--563, 1986
[bibtex] [paper] [doi]

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

Geometric modeling of solid objects by using a face adjacency graph representation
S. Ansaldi, L. De Floriani, B. Falcidieno
Proceedings of the 12th annual conference on Computer graphics and interactive techniques, vol. 19(3), pages 131--139, 1985
[bibtex] [paper] [doi]

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

Delaunay-based representation of surfaces defined over arbitrarily shaped domains
L. De Floriani, B. Falcidieno, C. Pienovi
Computer Vision, Graphics, and Image Processing, vol. 32(1), pages 127--140, 1985
[bibtex] [doi]

abstract A method for constructing surface models from a discrete set of arbitrarily distributed data is described. The surface is represented as a network of planar, triangular faces with vertices at the data points, which is built up on a Delaunay triangulation of the data point projections on thex−y plane. In the paper, the problem of triangulating arbitrarily shaped domains is considered. A new definition of Delaunay triangulation of a set of points constrained by a polygonal boundary is introduced, and some of its basic properties are briefly discussed. A new incremental algorithm for constructing a Delaunay triangulation of an arbitrarily shaped domain is described. This method is also demonstrated to be well suited to generate surface approximations at predefined levels of accuracy, which are based on significant subsets of selected data points.

An Edge-Face Relational Scheme for Boundary Representations
S. Ansaldi, L. De Floriani, B. Falcidieno
Computer Graphics Forum, vol. 4(4), pages 319--332, 1985
[bibtex] [doi]

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.

An Interpolant with Tension Defined over Triangles
Leila De Floriani, Giuliana Dettori
Computer Graphics Forum, vol. 4(4), pages 359--362, 1985
[bibtex] [doi]

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.

Integrating library modules into Pascal programs
M. Ancona, L. De Floriani, G. Dodero, S. Mancosu
Software: Practice and Experience, vol. 14(5), pages 401--412, 1984
[bibtex] [doi]

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.

A hierarchical structure for surface approximation
Leila De Floriani, Bianca Falcidieno, George Nagy, Caterina Pienovi
Computers and Graphics, vol. 8(2), pages 183--193, 1984
[bibtex] [doi]

abstract Hierarchical triangulation is a method for point selection and surface representation where the surface is approximated at successively finer levels of detail by triangular patches whose projections in the horizontal plane are nested. A tree data structure for this representation can be constructed in O(n2) worst case and O(n log n) average case time, where n is the number of data points considered. Efficient algorithms for approximation of the elevation of an arbitrary point, contour extraction, and conversion of the hierarchical structure into an ordinary triangulated irregular network, are demonstrated. The convergence and the optimality of the approximation and the relationship of the hierarchical triangulation to a structured graph representation are examined.