Free Functions Template for Creating Conforming Constrained Delaunay Triangulations

The following functions create a 3D conforming constrained Delaunay triangulation from either a polygon soup or a polygon mesh.

Input Data

The input data (polygon mesh or polygon soup) represents the polygonal constraints enforced during the triangulation process.

By default, each face of the input is considered a polygonal constraint for the triangulation. The named parameter plc_face_id can be used to describe larger polygonal constraints, possibly with holes. If used, this parameter must be a property map that associates each face of the input with a PLC face identifier. Faces with the same face identifier are considered part of the same surface patch. Each of these surface patches (defined as the union of the input faces with a given patch identifier) is expected to be a polygon or a polygon with holes, with coplanar vertices (or nearly coplanar up to the precision of the number type used).

The generated triangulation will conform to the faces of the input, or to the surface patches described by the plc_face_id property map if provided.

In the case where the input contains a non-planar PLC face, building the triangulation may fail with an exception of type CGAL::Non_planar_plc_facet_exception.

Precondition: The input data must not be coplanar.; The input data must not have self-intersections.

Template Parameters

For both function templates, the template arguments can be deduced from the function arguments, or defaulted.

The first template argument Triangulation defaults to CGAL::Default, and in that case the triangulation type is deduced from the input type and the named parameters (see below).
The following one or two template arguments are deduced from the input data: either a polygon mesh type, or a polygon soup defined by two types (a sequence of points and a sequence of sequences of indices).
The last template argument is the named parameters class, deduced from the function arguments.

Returned Triangulation Type

For both functions, the template parameter Triangulation defines the type of the triangulation that is created and returned by the function.

If Triangulation is CGAL::Default, the geometric traits class type is deduced from the input data and the named parameters. If the named parameter geom_traits is provided, the traits class is deduced from it. Otherwise, the point type of the input data is used to deduce the traits class. Let's call it Traits. The returned triangulation type is then CGAL::Conforming_constrained_Delaunay_triangulation_3<Traits>.
Otherwise, Triangulation must be a specialization of the CGAL::Conforming_constrained_Delaunay_triangulation_3 class template, with the following requirements:
- its Vertex type must be a model of ConformingConstrainedDelaunayTriangulationVertexBase_3, and
- its Cell type must be a model of ConformingConstrainedDelaunayTriangulationCellBase_3.

In both cases, the traits class Traits must fulfill the following requirements:

It must be a model of the concept ConformingConstrainedDelaunayTriangulationTraits_3.
It must have a Point_3 type that is constructible from the point type of the input data.

Functions
template<typename Triangulation = CGAL::Default, typename PolygonMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
auto	CGAL::make_conforming_constrained_Delaunay_triangulation_3 (const PolygonMesh &mesh, const NamedParameters &np=parameters::default_values())
	creates a 3D constrained Delaunay triangulation conforming to the faces of a polygon mesh.

template<typename Triangulation = CGAL::Default, typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>
auto	CGAL::make_conforming_constrained_Delaunay_triangulation_3 (const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
	creates a 3D constrained Delaunay triangulation conforming to the faces of a polygon soup.

Function Documentation

◆ make_conforming_constrained_Delaunay_triangulation_3() [1/2]

template<typename Triangulation = CGAL::Default, typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>

auto CGAL::make_conforming_constrained_Delaunay_triangulation_3	(	const PointRange &	points,
		const PolygonRange &	polygons,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>

creates a 3D constrained Delaunay triangulation conforming to the faces of a polygon soup.

Template Parameters

PointRange	a model of the concept `RandomAccessContainer` whose value type is the point type of the polygon soup
PolygonRange	a model of the concept `RandomAccessContainer` whose value type is a model of the concept `RandomAccessContainer` whose value type is `std::size_t`
Triangulation	an instance of the `CGAL::Conforming_constrained_Delaunay_triangulation_3` class template, or `CGAL::Default`
NamedParameters	a sequence of Named Parameters

Parameters

points	a range of points representing the vertices of the polygon soup
polygons	a range of ranges of indices representing the faces of the polygon soup
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

a property map associating points to the elements of the range points
Type: a model of ReadablePropertyMap whose key type is the value type of PointRange, and value type is convertible to the point type of the geometric traits class
Default: CGAL::Identity_property_map

a property map associating a patch identifier to each facet of soup. Each identifier corresponds to a planar surface patch. Each surface patch can be composed of several faces of soup, forming a planar polygon.
Type: a class model of ReadablePropertyMap with std::size_t as key type and with any value type that is a regular type (model of Regular)
Extra: If this parameter is omitted, each facet of the polygon soup is considered a separate PLC face.
Extra: Otherwise facets with the same patch identifier are considered part of the same PLC face.

an instance of a geometric traits class
Type: Traits as defined above in the section Returned Triangulation Type
Default: the default constructed traits object Traits{}

Returns: a 3D constrained Delaunay triangulation conforming to the faces of the polygon soup, of a type described in the section Returned Triangulation Type above.

Precondition: The polygon soup must be free of self-intersections. If the polygon soup is a triangle soup, this is equivalent to: CGAL::Polygon_mesh_processing::does_triangle_soup_self_intersect(points, polygons, np) == false .

◆ make_conforming_constrained_Delaunay_triangulation_3() [2/2]

template<typename Triangulation = CGAL::Default, typename PolygonMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>

auto CGAL::make_conforming_constrained_Delaunay_triangulation_3	(	const PolygonMesh &	mesh,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>

creates a 3D constrained Delaunay triangulation conforming to the faces of a polygon mesh.

Template Parameters

PolygonMesh	a model of `FaceListGraph`
Triangulation	an instance of the `CGAL::Conforming_constrained_Delaunay_triangulation_3` class template, or `CGAL::Default`
NamedParameters	a sequence of Named Parameters

Parameters

mesh	the polygon mesh representing the constraints
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

a property map associating points to the vertices of mesh
Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Traits::Point_3 as value type
Default: boost::get(CGAL::vertex_point, mesh)
Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.

a property map associating a patch identifier to each facet of mesh. Each identifier corresponds to a planar surface patch. Each surface patch can be composed of several facets of mesh, forming a planar polygon.
Type: a class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::face_descriptor as key type and with any value type that is a regular type (model of Regular)
Extra: If this parameter is omitted, each facet of mesh is considered a separate PLC face. Faces of mesh with the same patch identifier are considered part of the same PLC face.

an instance of a geometric traits class
Type: Traits as defined above in the section Returned Triangulation Type
Default: the default constructed traits object Traits{}

Returns: a 3D constrained Delaunay triangulation conforming to the faces of the polygon mesh, of a type described in the section Returned Triangulation Type above.

Precondition: mesh must not have self-intersections. For triangulated surfaces, it can be checked using the function CGAL::Polygon_mesh_processing::does_self_intersect(mesh, np) == false

Examples: Constrained_triangulation_3/ccdt_3_after_autorefinement.cpp, Constrained_triangulation_3/ccdt_3_check_preconditions.cpp, Constrained_triangulation_3/ccdt_3_fimap_region_growing.cpp, Constrained_triangulation_3/ccdt_3_from_soup.cpp, Constrained_triangulation_3/ccdt_3_from_soup_fimap.cpp, Constrained_triangulation_3/ccdt_3_preprocessing.cpp, Constrained_triangulation_3/conforming_constrained_Delaunay_triangulation_3.cpp, and Constrained_triangulation_3/conforming_constrained_Delaunay_triangulation_3_fimap.cpp.