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

Representing Digital Shapes

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 non-manifold, and may contain parts of different dimensions. Non-manifold 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].

torus_complex.png
Example of manifold shape, discretized by a 2-complex
gia3d_nmedge.png
Examples of non-manifold shapes, discretized by 2-complexes
bottles1.png
Example of non-manifold shape, discretized by a 3-complex

In any case, it is necessary to visualize, managing, and manipulating these shapes efficiently, including non-manifolds.

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 non-manifold), 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 incidence-based data structures, which encode all cells of the complex, and a subset of their incidence relations, and adjacency-based 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.

The Rapid Prototyping Approach and its Advantages

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

rapid1.png
The layered approach for the rapid prototyping techniques

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, hyper-volumes, ...), 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.

  • It is very easy-to-use and it requires a short learning curve. In fact, it is necessary to be familiar with the unique application program interface (API) in the system, which may be simplified. Thanks to a deep study of the design of this API, it is possible to describe the behavior of a plugin as a black box, and to hide many details regarding the topological data structure we are simulating. In particular, the API include several features, which are currently in the state-of-art of mesh databases (i.e., tools describing simplicial and cell complexes), like iterators, circulators, and collections of topological entities with garbage collector [32],[28],[42],[14] (see the Internal Encoding of Mangroves Section for more details).

What we have in the Current Literature

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 run-time, 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 non-manifolds and the recognition of non-manifold singularities, when possible. In fact, this operation is not decidable for combinatorial $d$-complexes, with $d\ge 6$ [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 ComplexesSimplicialCellCellCellAny
Dimension of ComplexesUp to 3Up to 2Up to 3AnyAny
Internal RepresentationAdjacency-basedOM [5]OVM [34]Combinatorial Maps [33]Many
ExtensibilityNo (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 adjacency-based representation, which can be customized by the user, and it is able to represent non-manifold 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 edge-based representation for cell 2-complexes such that non-manifold singularities occur only at vertices.

The OpenVolumeMesh Library [40] can be considered as the counterpart of the OM Library for the representation of cell 3-complexes. 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 dimension-independent 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 quasi-manifolds, 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.

Attention
Our Mangrove Topological Data Structure (Mangrove TDS) Library can be considered a fair solution to this lacking in the current literature.