The Mangrove TDS Library
2.0
A C++ tool for the Fast Prototyping of Topological Data Structures

Simplicial and cell complexes are widely used to discretize digital shapes in several applications, including computer graphics, solid modeling, finite element analysis and simulation, scientic visualization, and geographic data processing. Many geometric modeling tools handle manifold shapes, i.e., subsets of the Euclidean space such that each neighborhood of every point is homeomorphic to an open ball. Objects, which do not satisfy this property, are nonmanifold, and may contain parts of different dimensions. Nonmanifold shapes, not necessarily embedded in any Euclidean space, arise in several applications, for instance in the finite element analysis simulation [44], and in the topological analysis of data in high dimensions [3],[4],[29].
In any case, it is necessary to visualize, managing, and manipulating these shapes efficiently, including nonmanifolds.
In the literature, a large variety of topological data structures have been developed for modeling cell and simplicial complexes [19]. They are formalized by topological relations, which capture connectivity information among cells and simplices [24].
Following [19], topological data structures can be classified on the basis of their domain (i.e., manifold or nonmanifold), and of the dimension for the complex. In particular, there are representations, designed for complexes of a specific dimension, and with a specific embedding space. Finally, there are incidencebased data structures, which encode all cells of the complex, and a subset of their incidence relations, and adjacencybased data structures, which encode only vertices and top cells, namely cells which are not on the boundary of other cells.
Many representations are specific for a particular class of shapes, e.g., those in [30][31] are specific for manifold triangulations, others are specific for shape optimization [7], others for geometry processing [5],[32],[34], and others for computational topology [3],[4]. An interested reader can refer [6],[24],[28] for more details.
As a consequence, there is the need for a framework capable of supporting a wide number of representations for simplicial and cell complexes under a common interface. In particular, it should be focused to their fast prototyping, in the same spirit of the prototyping techniques in the manifacturing [46]. Recall that rapid prototyping provides a fast and inexpensive way to verify and evaluate design tradeoffs for a product. In particular, the main idea of rapid prototyping is to develop learning experiences in a continual designevaluation cycle that continues throughout the life of the project. This cycle, known as the layered approach, is considered to be iterative, meaning that products are continually improved as they cycle continues (see figure). Similarly, in the context of topological representations, the key idea consists of creating a prototype of a topological data structure, which can be customized in order to satisfy any modeling need. In particular, it should be possible to customize this prototype without introducing any overhead when simulating a specific data structure, and thus without harding generality for efficiency. In particular, this prototype provides a generic description of connectivity information among topological entities, namely simplices and cells, in any complex. As suggested in [24], a topological data structure encodes partially only a subset of connectivity information, and the remaining information is retrieved by topological queries. Hence, any topological data structure is a particular instance of this prototype. In this way, this framework can be easily extended by adding new data structures. In particular, each topological data structure can be seen as a plugin to be loaded dynamically in the system without messing with its architecture. Note that this does not imply to write a wrapper, since this operation is not efficient. As a consequence, the internal representation of a complex can be dynamically replaced in order to choose the most efficient one for any specific task. 
A tool with these properties may be useful for many reasons, in particular when programming topological data structures:
it should provide a common basis for performing quantitative comparisons, regarding performances of topological data structures. Note that these latter are often implemented in heterogenous libraries, written in different languages, and/or with different techniques of the same language. Thus, their efficiency depends not only on their intrinsic properties, but also on the programmers' technical ability and on design choices. This property does not allow performing coherent and fair comparisons. Having a common platform for implementing topological data structures imposes the same design for all implementations, emphasizing their intrinsic properties and differences.
It improves the knowledge, regarding topological data structures and their design, which can be defined in a controlled and unique way, regardless their content, the domain, and topological entities they encode. In particular, it is not necessary to exploit different encodings for each class of topological entities (vertices, edges, faces, volumes, hypervolumes, ...), but only one basic description, unique for all topological entities.
It simplifies the programmer's work. In particular, a topological data structure must not be reimplemented from scratch, but it is necessary to provide only a plugin, thus to implement a limited number of primitives. This can be done easily, e.g., thanks to the concept of traits, typical in the templated metaprogramming techniques [32] (see Technical Properties Section). These latter are supported by any recent compiler. Thus, any program, based on this tool, must be written only once, then it can be customized through different plugins. Recall that any topological data structures (we guess ...) can be defined within our framework.
A framework with the above properties may be very interesting both the theoretical and the implementative point of view. Unfortunately, as stated in [42], a framework with these properties is currently lacking in the literature.
Specifically, existing tools, like those in [15],[16],[39],[40],[45], are based on a single representation, which cannot be replaced dynamically at runtime, and some of them are restricted to specific applications. Actually, some tools can be modified dynamically [26],[33],[35],[41],[43] but only in a predefined way and without messing with their internal representation, which remains almost unchanged.
Another interesting properties of a mesh database is given by the efficient representations of nonmanifolds and the recognition of nonmanifold singularities, when possible. In fact, this operation is not decidable for combinatorial complexes, with [38]. As shown in [14] only some topological data structures, like those in [23],[13], allow to answer this query efficiently, and without recomputing the neighborhood of a topological entity from scratch.
The following schema, already presented in [12], summarizes properties of some mesh databases in the current literature.
The VCG Library [45]  The OpenMesh Library [39]  The OpenVolumeMesh Library [40]  The CGoGN Library [16]  The CGAL Library [15]  
Type of Complexes  Simplicial  Cell  Cell  Cell  Any 
Dimension of Complexes  Up to 3  Up to 2  Up to 3  Any  Any 
Internal Representation  Adjacencybased  OM [5]  OVM [34]  Combinatorial Maps [33]  Many 
Extensibility  No (limited)  No (limited)  No (limited)  No (limited)  Modules 
The Visualization and Computer Graphics (VCG) Library [45] is a open source portable C++ templated library for manipulation, processing and displaying with OpenGL of triangle and tetrahedral meshes. The library is fairly large and offers many state of the art functionalities for geometry processing. It exploits an adjacencybased representation, which can be customized by the user, and it is able to represent nonmanifold singularities and support their efficient recognition.
The OpenMesh (OM) Library [39] is another C++ templated library, which is mainly devoted to the geometry processing. In particular, it is based on the OM data structure [5], an edgebased representation for cell 2complexes such that nonmanifold singularities occur only at vertices.
The OpenVolumeMesh Library [40] can be considered as the counterpart of the OM Library for the representation of cell 3complexes. It is based on the OVM data structure [34], which is basically equivalent to the Incidence Graph [27] (see The IG data structure Section), as shown in [14].
The CGoGN Library [16] is a dimensionindependent extension of the Combinatorial Maps [33], and exploits several metaprogramming templated techniques, largely inspired by those described in [32],[42]. As shown in [14], combinatorial maps can represent only quasimanifolds, and are about twice more expensive than the Incidence Graph.
Finally, the Computational Geometry Algorithms Library (CGAL) [15] is an excellent library for geometry processing and computational geometry, which offers several representations of cell and any other complexes. For instance, we can mention the Triangulation data structure [32], and the LinearCellComplex [17]. However, the CGAL can be seen as a unorganized collection of modules, such that each module is optimized for a specific task. In particular, modules are not designed under a common and extensible API. Independent experimental tests in [14],[33],[17] show that these representations are more expensive than the IG data structure.