3D Triangulations Reference

Clément Jamin, Sylvain Pion and Monique Teillaud

This package allows to build and handle triangulations for point sets in three dimensions. Any CGAL triangulation covers the convex hull of its vertices. Triangulations are build incrementally and can be modified by insertion, displacements or removal of vertices. They offer point location facilities. The package provides plain triangulation (whose faces depends on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams. Optionally, the main Delaunay and regular triangulation algorithms (insert, remove) support multi-core shared-memory architectures to take advantage of available parallelism.

Introduced in: CGAL 2.1
Depends on: 3D Triangulation Data Structure
BibTeX: cgal:pt-t3-22b
License: GPL
Windows Demo: 3D Triangulations
Common Demo Dlls: dlls

A three-dimensional triangulation is a three-dimensional simplicial complex, pure connected and without singularities [4]. 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 \( \mathbb{R}^3 \). 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 \( \mathbb{R}^3 \).

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 \( \mathbb{R}^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 45.1.

Classified Reference Pages

Concepts

• TriangulationTraits_3
• DelaunayTriangulationTraits_3
• RegularTriangulationTraits_3
• TriangulationVertexBase_3
• TriangulationVertexBaseWithInfo_3
• TriangulationCellBase_3
• TriangulationCellBaseWithInfo_3
• DelaunayTriangulationCellBase_3
• RegularTriangulationVertexBase_3
• RegularTriangulationCellBase_3
• RegularTriangulationCellBaseWithWeightedCircumcenter_3
• TriangulationDataStructure_3
• WeightedPoint

Classes

Main Classes

• CGAL::Triangulation_3<TriangulationTraits_3,TriangulationDataStructure_3,SurjectiveLockDataStructure>
• CGAL::Delaunay_triangulation_3<DelaunayTriangulationTraits_3,TriangulationDataStructure_3,LocationPolicy,SurjectiveLockDataStructure>
• CGAL::Regular_triangulation_3<RegularTriangulationTraits_3,TriangulationDataStructure_3,SurjectiveLockDataStructure>
• CGAL::Triangulation_vertex_base_3<TriangulationTraits_3, TriangulationDSVertexBase_3>
• CGAL::Triangulation_vertex_base_with_info_3<Info, TriangulationTraits_3, TriangulationVertexBase_3>
• CGAL::Triangulation_cell_base_3<TriangulationTraits_3, TriangulationDSCellBase_3>
• CGAL::Triangulation_cell_base_with_info_3<Info, TriangulationTraits_3, TriangulationCellBase_3>
• CGAL::Delaunay_triangulation_cell_base_3<DelaunayTriangulationTraits_3,Cb>
• CGAL::Delaunay_triangulation_cell_base_with_circumcenter_3<DelaunayTriangulationTraits_3,Cb>
• CGAL::Regular_triangulation_vertex_base_3<RegularTriangulationTraits_3,Vb>
• CGAL::Regular_triangulation_cell_base_3<RegularTriangulationTraits_3,Cb>
• CGAL::Regular_triangulation_cell_base_with_weighted_circumcenter_3<RegularTriangulationTraits_3,Cb>
• CGAL::Triangulation_simplex_3<Triangulation_3>

Traits Classes

• CGAL::Regular_triangulation_euclidean_traits_3<K,Weight>
• CGAL::Robust_weighted_circumcenter_filtered_traits_3<K>

Enums

• CGAL::Triangulation_3::Locate_type

Draw a Triangulation 3

• CGAL::draw<T3>()

I/O

• CGAL::Triangulation_3::file_input<Tr_src, ConvertVertex, ConvertCell>()
• CGAL::file_input<Tr_src, Tr_tgt, ConvertVertex, ConvertCell>()

Modules
	Concepts
	Triangulation Classes
	Traits Classes
	Vertex and Cell Classes
	Draw a Triangulation 3
	I/O for a Triangulation 3

Functions
template<class Triangulation , class TriangleMesh >
boost::graph_trait< FG >::vertex_descriptor	CGAL::link_to_face_graph (const Triangulation &t, typename Triangulation::Vertex_handle vh, TriangleMesh &tm, bool no_infinite_faces=true)
	fills the face graph tm with the link of triangulation vertex vh. More...

Function Documentation

link_to_face_graph()

template<class Triangulation , class TriangleMesh >

boost::graph_trait<FG>::vertex_descriptor CGAL::link_to_face_graph	(	const Triangulation &	t,
		typename Triangulation::Vertex_handle	vh,
		TriangleMesh &	tm,
		bool	no_infinite_faces = true
	)

#include <CGAL/link_to_face_graph.h>

fills the face graph tm with the link of triangulation vertex vh.

Precondition

T.dimension()==3.

Template Parameters

Triangulation	must be a CGAL 3D triangulation.
TriangleMesh	must be a model of the concept MutableFaceGraph.

Parameters

t	the 3D triangulation
vh	the vertex handle of the vertex
tm	the triangle mesh
no_infinite_faces	If vh is on the convex hull of the triangulation, no_infinite_faces == true generates a triangle mesh with a border. Otherwise, this parameter is ignored.

Returns

the vertex descriptor of the triangle mesh tm corresponding to the infinite vertex of t, if vh is on the convex hull of the triangulation, and if no_infinite_faces == false. Otherwise, an arbitrary vertex descriptor of the triangle mesh tm.

See also

convex_hull_3_to_face_graph()