Data Structures in the Simplicial Mesh Package.

Simplicial Mesh Data Structures.

The position of the nodes (vertices) defines the geometry of a mesh. The connection of the nodes to form elements, faces and edges defines the topology of a mesh.

Let N be the space dimension and M be the simplex dimension. For a tetrahedral mesh in 3-D, N = 3 and M = 3. The boundary of this tetrahdral mesh is a triangle mesh with N = 3 and M = 2. There are three mesh data structures:

• geom::IndSimpSet, Indexed Simplex Set.
• geom::IndSimpSetIncAdj, Indexed Simplex Set with Incidence and Adjacency information.
• geom::SimpMeshRed, Simplicial Mesh, Reduced representation.

These data structures have the space dimension and the simplex dimension as template parameters.

geom::IndSimpSet implements an indexed simplex set. This is a economical representation of a mesh. It is composed of an array of vertices and an array of indexed simplices. A vertex is an N-tuple of numbers (a Cartesian point). An indexed simplex is represented by an (M+1)-tuple of vertex indices. From these, one can make a simplex: an (M+1)-tuple of vertices. The indexed simplex set is well suited for implementing algorithms in which the topology of the mesh does not change. The ``cookie cutter'' mesh generation and file I/O are implemented using the geom::IndSimpSet data structure.

Note that the only topological information stored in geom::IndSimpSet is the simplex-vertex incidencies. One needs more information to perform geometric optimization of vertices. There are auxillary data structures for storing vertex-simplex incidencies (geom::VertexSimplexInc) and simplex-simplex adjacencies (geom::SimplexAdj) The geom::IndSimpSetIncAdj class inherits from geom::IndSimpSet and has geom::VertexSimplexInc and geom::SimplexAdj as data members. Geometric mesh optimization capabilities are implemented using this augmented data structure.

geom::SimpMeshRed is a reduced mesh representation. A full mesh representation stores all of the topological entities. For a tetrahedral mesh, there are tetrahedral cells, triangle faces, edges, and vertices. geom::SimpMeshRed (short for Simplicial Mesh Reduced) stores only the top and bottom level entities. The intermediate entities (edges for triangle meshes, faces and edges for tetrahedral meshes) are represented implictly. This approach has the advantage that the data structure can be general in the space dimension and simplex dimension. It also reduces the storage requirements.

geom::SimpMeshRed supports algorithms in which the topology of the mesh changes. The data structure is composed of a container of nodes and container of cells. The node type is a template parameter for the mesh. A node stores at least a vertex and an iterator to itself. In addition, it may store an integer identifier and iterators to one or all of the incident cells. The cell type is also a template parameter for the mesh. A cell stores at least a simplex of its nodes (technically a simplex of node iterators) and an iterator to itself. In addition, it may store an integer identifier and iterators to the adjacent cells. The container type is also a template parameter of the mesh. It is required that inserting and removing elements does not invalidate iterators. By default, the container type is std::list.

Manifold with Features Data Structures.

To represent the boundary of a model, one uses a "manifold with features" data structure. The boundary of a triangle mesh in 2-D is a line segment mesh. In this case, one can represent the boundary with PointsOnManifoldN11T. The boundary of a tetrahedral mesh in 3-D is a triangle mesh in 3-D. Here one can represent the boundary with PointsOnManifold321T. One can also use PointsOnManifold321T to represent the geometry of your model when working with 3-2 meshes (triangle meshes in 3-D).