Triangulation Data Structure in 3D

Introduction

A three-dimensional triangulation is a three-dimensional simplicial complex, pure connected and without singularities [BY98]. Its cells ($$3-faces, tetrahedra) are such that two cells either do not intersect or share a common facet ($$2-face), edge ($$1-face) or vertex ($$0-face).

A geometric triangulation has two aspects: the combinatorial structure which gives the incidence and adjacency relations between faces, and the geometric information related to the position of vertices.

CGAL provides 3D geometric triangulations in which these two aspects are clearly separated. As described in Chapter , a geometric triangulation of a set of points in $$ ^d is a partition of the whole space $$ ^d into cells having $$d+1 vertices. Some of them are infinite, they are obtained by linking an additional vertex at infinity to each facet of the convex hull of the points (see Section ). The underlying combinatorial graph of such a triangulation without boundary of $$ ^d can be seen as a triangulation of the topological sphere $$S^d in $$ ^d+1.

This chapter deals with 3D-triangulation data structures, meant to maintain the combinatorial information for 3D-geometric triangulations. The reader interested in geometric triangulations of $$ ³ is advised to read Chapter .

Representation

In CGAL, a triangulation data structure is a container of cells ($$3-faces) and vertices ($$0-faces). 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 ).

Figure:  Representation

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

Degenerate Dimensions

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

Let us give, for each dimension, the example corresponding to the triangulation data structure having a minimal number of vertices, i.e. a simplex. These examples are illustrated by presenting their usual geometric embedding.

• dimension 3. The triangulation data structure consists of the boundary of a 4-dimensional simplex, which has 5 vertices. A geometric embedding consists in choosing one of these vertices to be infinite, thus four of the five 3-cells become infinite: the geometric triangulation has one finite tetrahedron remaining, each of its facets being incident to an infinite cell. See Figure . Figure:  4D simplex and a 3D geometric embedding
  
• dimension 2. We have 4 vertices forming one 3-dimensional simplex, i.e. the boundary of a tetrahedron. The geometric embedding in the plane results from choosing one of these vertices to be infinite, then the geometric triangulation has one finite triangle whose edges are incident to the infinite triangles. See Figure . Figure:  3D simplex and a 2D geometric embedding
  
• dimension 1. A 2-dimensional simplex (a triangle) has 3 vertices. The geometric embedding is and edge whose vertices are linked to an infinite point. See Figure . Figure:  2D simplex and a 1D geometric embedding
  

The last three cases are defined uniquely:

• dimension 0. A 0-dimensional triangulation is combinatorially equivalent to the boundary of a 1-dimensional simplex (an edge), which consists of 2 vertices. One of them becomes infinite in the geometric embedding, and there is only one finite vertex remaining. The two vertices are adjacent.
• dimension -1. This dimension is a convention to represent a 0-dimensional simplex, that is a sole vertex, which will be geometrically embedded as an ``empty'' triangulation, having only one infinite vertex.
• dimension -2. This is also a convention. The triangulation data structure has no vertex. There is no associated geometric triangulation.

Note that the notion of infinite vertex has no meaning for the triangulation data structure. The infinite vertex of the geometric embedding is a vertex that cannot be distinguished from the other vertices in the combinatorial triangulation.

The implicit representation of facets (resp. edges) still holds for degenerate ($$< 3) dimensions : in dimension 2, each cell has only one facet of index 3, and 3 edges $$(0,1), $$(1,2) and $$(2,0); in dimension 1, each cell has one edge $$(0,1).

Validity

(a) When a cell $$c has a neighbor pointer to another cell $$c', then reciprocally this cell $$c' has a neighbor pointer to $$c, and $$c and $$c' have three vertices in common. These cells are called adjacent.

(b) The cells have a coherent orientation: if two cells $$c₁ and $$c₂ are adjacent and share a facet with vertices $$u,v,w, then the vertices of $$c₁ are numbered $$(v₀¹ = u, v₁¹ = v, v₂¹ = w, v₃¹), and the vertices of $$c₂ are numbered $$(v₀² = v, v₁² = u, v₂² = w, v₃²), up to positive permutations of $$(0,1,2,3). In other words, if we embed the triangulation in $$ ³, then the fourth vertices $$v₃¹ and $$v₃² of $$c₁ and $$c₂ see the common facet in opposite orientations. See Figure .

The set $$$$₄ of permutations of $$(0,1,2,3) has cardinality 24, and the set of positive permutations $$A₄ has cardinality 12. Thus, for a given orientation, there are up to 12 different orderings of the four vertices of a cell. Note that circular permutations are negative and so do not preserve the orientation of a cell.

Figure:  Coherent orientations of two cells (3-dimensional case)

The is_valid() method provided by CGAL checks the local validity of a given triangulation data structure.

Software Design

The 3D-triangulation data structure class of CGAL is designed to be used as a combinatorial layer upon which a geometric layer can be built [Ket98]. This upper class can be the 3D-triangulation class of CGAL. Figure  shows the organization of the software design in this case.

Figure:  Layers in the software design

In the bottom layer, the CGAL base classes store elementary geometric information. These classes are parameterized by a geometric traits class providing all the geometric types. A vertex has a pointer to a cell, and a cell has four pointers to vertices. These pointers are of type void*.

The middle layer class stores the triangulation data structure, which is purely combinatorial. A vertex of the triangulation data structure has a pointer to a cell of the triangulation data structure, and a cell has four pointers to vertices. These pointers are usual C++ pointers. The triangulation data structure provides operations such as insertion of a new vertex in a given cell, on a $$1 or $$2-face. It also allows one, if the dimension of the triangulation is smaller than $$3, to insert a vertex so that the dimension of the triangulation is increased by one. The triangulation data structure is responsible for the combinatorial integrity of the triangulation.

It is up to the user to derive his own base classes from the CGAL base classes to add any other information he may need for his given application, or to write his own base classes from scratch. In this case, the base classes must be models for the concepts described in Section .

The upper layer, described in Chapter , is the geometric triangulation class, providing operations such as location of a point in the triangulation, insertion of a point, and is responsible for the geometric validity. A vertex of the triangulation has a pointer to a cell and a cell has four pointers to vertices. These pointers are CGAL handles. The triangulation data structure class is one of the template parameters of the geometric triangulation class. The user may choose to replace the CGAL triangulation data structure class by his own triangulation data structure. In this case, his class has to be a model of the concept described in Section .

Examples

#include <CGAL/basic.h>

#include <iostream>

#include <vector>

#include <CGAL/Cartesian.h>
#include <CGAL/Point_3.h>

#include <CGAL/Triangulation_geom_traits_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_3.h>
#include <CGAL/Triangulation_data_structure_3.h>

// the definition of the geometric traits class is necessary to
// instantiate base vertices and cells but will in fact never be used
// in the program 
typedef CGAL::Cartesian<double>  Rep;
typedef CGAL::Triangulation_geom_traits_3<Rep> Gt;

typedef CGAL::Triangulation_vertex_base_3<Gt> Vb;
typedef CGAL::Triangulation_cell_base_3<Gt> Cb;

typedef CGAL::Triangulation_data_structure_3<Vb,Cb> Tds;

typedef typename Tds::Cell TDSCell;
typedef typename Tds::Vertex TDSVertex;

int main()
{
  Tds T;

  assert( T.number_of_vertices() == 0 );
  assert( T.dimension() == -2 );
  assert( T.is_valid() );

  std::vector<TDSVertex> V(5);
  std::vector<TDSVertex*> PV(7);

  PV[0] = T.insert_increase_dimension(V[0]);
  assert( T.number_of_vertices() == 1 );
  assert( T.dimension() == -1 );
  assert( T.is_valid() );

  int i;
  // each of the following insertions of vertices increases the dimension
  for ( i=1; i<5; i++ ) {
    PV[i] = T.insert_increase_dimension(V[i], PV[0]);
    assert( T.number_of_vertices() == i+1 );
    assert( T.dimension() == i-1 );
    assert( T.is_valid() );
  }
  assert( T.number_of_cells() == 5 );

  // we now have a simplex in dimension 4

  // cell incident to PV[0]
  TDSCell* c = PV[0]->cell();
  int ind;
  assert( c->has_vertex( PV[0], ind ) );
  // PV[0] is the vertex of index ind in c

  // insertion of a new vertex in the facet opposite to PV[0]
  PV[5] = T.insert_in_facet(TDSVertex(), c, ind);
  
  assert( T.number_of_vertices() == 6 );
  assert( T.dimension() == 3 );
  assert( T.is_valid() );

  // insertion of a new vertex in c
  PV[6] = T.insert_in_cell( TDSVertex(), c );

  assert( T.number_of_vertices() == 7 );
  assert( T.dimension() == 3 );
  assert( T.is_valid() );

  std::ofstream oFileT("output_tds",ios::out);
  // writing file output_tds; 
  oFileT << T; 

  return 0;
}

Concepts

This section describes the concepts for a 3D-triangulation data structure, its vertices and cells.

Concepts for a 3D-Triangulation Data Structure

• Class declaration of Tds<Vb,Fb>.

Concept for the Vertex of a 3D-Triangulation Data Structure

• Class declaration of Tds::Vertex.

Concept for the Cell of a 3D-Triangulation Data Structure

• Class declaration of Tds::Cell.

A model of Triangulation Data Structure

• Class declaration of Triangulation_data_structure_3<Vb,Cb>.

Concepts for the Base Vertices and Cells

Concept for the Base Vertex

• Class declaration of Vertex_base.

Concept for the Base Cell

• Class declaration of Cell_base.

Models of Base Vertices and Cells

CGAL provides two base vertex classes. Both are templated by a geometric traits class Traits that provides the geometric types. The user who uses the geometric layer (Section  and Chapter ) is strongly advised to use the same geometric traits class Traits as the one used for Triangulation_3<Traits,Tds>. In this way, the point type defined by the base vertex is the same as the point type defined by the geometric traits class. The default geometric traits class provided by CGAL is presented in Section .

These base classes can be used directly or can serve as a base to derive other base classes with some additionnal attributes (a color for example) tuned for a specific application.

#include <CGAL/Triangulation_vertex_base_3.h>

The same include file proposes the two classes described in Sections  and .

A Base Class for vertices

• Class declaration of Triangulation_vertex_base_3<Traits>.

Another Base Class for vertices

• Class declaration of Triangulation_vertex_base_pointer_3<Traits>.

A Base Class for cells

• Class declaration of Triangulation_cell_base_3<Traits>.