TriangulationDataStructure_3

Definition

3D-triangulation data structures are meant to maintain the combinatorial information for 3D-geometric triangulations.

In Cgal, a triangulation data structure is a container of cells (3-faces) and vertices (0-faces). Following the standard vocabulary of simplicial complexes, an i-face f_i and a j-face f_j (0 ≤ j < i ≤ 3) are said to be incident in the triangulation if f_j is a (sub)face of f_i, and two i-faces (0 ≤ i ≤ 3) are said to be adjacent if they share a common incident (sub)face.

Each cell gives access to its four incident vertices and to its four adjacent cells. Each vertex gives direct access to one of its incident cells, which is sufficient to retrieve all the incident cells when needed.

The four vertices of a cell are indexed with 0, 1, 2 and 3. The neighbors of a cell are also indexed with 0, 1, 2, 3 in such a way that the neighbor indexed by i is opposite to the vertex with the same index (see Figure 40.1).

Edges (1-faces) and facets (2-faces) are not explicitly represented: a facet is given by a cell and an index (the facet i of a cell c is the facet of c that is opposite to the vertex of index i) and an edge is given by a cell and two indices (the edge (i,j) of a cell c is the edge whose endpoints are the vertices of indices i and j of c).

As Cgal explicitly deals with all degenerate cases, a 3D-triangulation data structure in Cgal can handle the cases when the dimension of the triangulation is lower than 3 (see Section 40.1).

Thus, a 3D-triangulation data structure can store a triangulation of a topological sphere S^d of ℝ^d+1, for any d ∈ {-1,0,1,2,3}.

The second template parameter of the basic triangulation class (see Chapter 39 ) Triangulation_3 is a triangulation data structure class. (See Chapter 40.)

To ensure all the flexibility of the class Triangulation_3, a model of a triangulation data structure must be templated by the base vertex and the base cell classes (see 40.1): TriangulationDataStructure_3<TriangulationVertexBase_3,TriangulationCellBase_3>. The optional functionalities related to geometry are compulsory for this use as a template parameter of Triangulation_3.

A class that satisfies the requirements for a triangulation data structure class must provide the following types and operations.

Types

Vertices and cells are usually manipulated via handles, which support the two dereference operators operator* and operator->.

Requirements for Vertex and Cell are described in TriangulationDataStructure_3::Vertex and TriangulationDataStructure_3::Cell .

The following iterators allow one to visit all the vertices, edges, facets and cells of the triangulation data structure. They are all bidirectional, non-mutable iterators.

The following circulators allow us to visit all the cells and facets incident to a given edge. They are bidirectional and non-mutable.

Iterators and circulators are convertible to the corresponding handles, thus the user can pass them directly as arguments to the functions.

Creation

Operations

Access Functions

Non constant-time access functions

Queries

There is a method has_vertex in the cell class. The analogous methods for facets are defined here.

The following three methods test whether two facets have the same vertices.

Flips

Two kinds of flips exist for a three-dimensional triangulation. They are reciprocal. To be flipped, an edge must be incident to three tetrahedra. During the flip, these three tetrahedra disappear and two tetrahedra appear. Figure 40.7(left) shows the edge that is flipped as bold dashed, and one of its three incident facets is shaded. On the right, the facet shared by the two new tetrahedra is shaded.

Figure 40.7:  Flips.

The following methods guarantee the validity of the resulting 3D combinatorial triangulation. Moreover the flip operations do not invalidate the vertex handles, and only invalidate the cell handles of the affected cells.

Flips for a 2d triangulation are not implemented yet

Insertions

The following modifier member functions guarantee the combinatorial validity of the resulting triangulation.

Figure 40.8:  insert_increase_dimension (1-dimensional case).

Removal

Dimension Manipulation

The following operation, decrease_dimension, is necessary when the displacement of a vertex decreases the dimension of the triangulation.

Figure 40.9:  From an S^d data structure to an S^d-1 data structure (top: d==2, bottom: d==3).

Traversing the triangulation

Cell and facet circulators

The following circulators on facets are defined only in dimension 3, though facets are defined also in dimension 2: there are only two facets sharing an edge in dimension 2.

Traversal of the incident cells, facets and edges, and the adjacent vertices of a given vertex

Traversal between adjacent cells

I/O

The information stored in the iostream is: the dimension, the number of vertices, the number of cells, the indices of the vertices of each cell, then the indices of the neighbors of each cell, where the index corresponds to the preceding list of cells. When dimension < 3, the same information is stored for faces of maximal dimension instead of cells.

Has Models

CGAL::Triangulation_data_structure_3

See Also

TriangulationDataStructure_3::Vertex
TriangulationDataStructure_3::Cell