3D Triangulation Data Structure

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

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 3D combinatorial triangulation is said to be locally valid iff the following is true:

(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 Triangulation_data_structure_3 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 Triangulation_vb_3 and Triangulation_cb_3.

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 .

Example of incremental construction

// Triangulation_3/example_tds.C
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_3.h>
#include <CGAL/Triangulation_data_structure_3.h>

#include <iostream>
#include <fstream>
#include <cassert>
#include <vector>

// We define a minimal traits class, because the Point_3 type is needed in
// order to instantiate Triangulation_vertex_base_3<>.

class empty_traits {
public:
  class Point_3 {};
};
typedef empty_traits K;

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

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

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

int main()
{
  Tds T;

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

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

  PV[0] = T.insert_increase_dimension(NULL);
  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(NULL, 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(NULL, 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(NULL, c);

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

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

  return 0;
}