Chapter 36
3D Triangulations

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

The basic 3D-triangulation class of CGAL is primarily designed to represent the triangulations of a set of points $$A in $$ ³. It can be viewed as a partition of the convex hull of $$A into tetrahedra whose vertices are the points of $$A. Together with the unbounded cell having the convex hull boundary as its frontier, the triangulation forms a partition of $$ ³.

In order to deal only with tetrahedra, which is convenient for many applications, the unbounded cell can be subdivided into tetrahedra by considering that each convex hull facet is incident to an infinite cell having as fourth vertex an auxiliary vertex called the infinite vertex. In that way, each facet is incident to exactly two cells and special cases at the boundary of the convex hull are simple to deal with.

A triangulation is a collection of vertices and cells that are linked together through incidence and adjacency relations. Each cell gives access to its four incident vertices and to its four adjacent cells. Each vertex gives access to one of its incident cells.

The four vertices of a cell are indexed with 0, 1, 2 and 3 in positive orientation, the positive orientation being defined by the orientation of the underlying Euclidean space $$ ³. 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 .

Concepts

TriangulationTraits_3
DelaunayTriangulationTraits_3
RegularTriangulationTraits_3

TriangulationCellBase_3
TriangulationVertexBase_3
TriangulationHierarchyVertexBase_3

TriangulationDataStructure_3
WeightedPoint

Classes

Main classes

CGAL::Triangulation_3<TriangulationTraits_3,TriangulationDataStructure_3>
CGAL::Delaunay_triangulation_3<DelaunayTriangulationTraits_3,TriangulationDataStructure_3>
CGAL::Triangulation_hierarchy_3<Tr>
CGAL::Regular_triangulation_3<RegularTriangulationTraits_3,TriangulationDataStructure_3>

CGAL::Triangulation_cell_base_3<TriangulationTraits_3, TriangulationDSCellBase_3>
CGAL::Triangulation_cell_base_with_info_3<Info, TriangulationTraits_3, TriangulationCellBase_3>
CGAL::Triangulation_vertex_base_3<TriangulationTraits_3, TriangulationDSVertexBase_3>
CGAL::Triangulation_vertex_base_with_info_3<Info, TriangulationTraits_3, TriangulationVertexBase_3>
CGAL::Triangulation_hierarchy_vertex_base_3<TriangulationVertexBase_3>

Traits classes

CGAL::Regular_triangulation_euclidean_traits_3<R,Weight> CGAL::Regular_triangulation_filtered_traits_3<FK>

Enums

CGAL::Triangulation_3::Locate_type

Links to the Reference Sections

• Triangulation_3<TriangulationTraits_3,TriangulationDataStructure_3>

• Delaunay_triangulation_3<DelaunayTriangulationTraits_3,TriangulationDataStructure_3>

• Triangulation_hierarchy_3<Tr>

• Regular_triangulation_3<RegularTriangulationTraits_3,TriangulationDataStructure_3>

• TriangulationTraits_3

• DelaunayTriangulationTraits_3

• RegularTriangulationTraits_3

• Regular_triangulation_euclidean_traits_3<R,Weight>

• Regular_triangulation_filtered_traits_3<FK>

• TriangulationCellBase_3

• TriangulationVertexBase_3

• TriangulationHierarchyVertexBase_3

• Triangulation_cell_base_3<TriangulationTraits_3, TriangulationDSCellBase_3>

• Triangulation_cell_base_with_info_3<Info, TriangulationTraits_3, TriangulationCellBase_3>

• Triangulation_vertex_base_3<TriangulationTraits_3, TriangulationDSVertexBase_3>

• Triangulation_vertex_base_with_info_3<Info, TriangulationTraits_3, TriangulationVertexBase_3>

• Triangulation_hierarchy_vertex_base_3<TriangulationVertexBase_3>

• Triangulation_3::Locate_type

• WeightedPoint