Hole Filling

Functions to fill holes given as a range of halfedges or as range of points.

Classes
struct	CGAL::Polygon_mesh_processing::Hole_filling::Default_visitor
	Default hole filling visitor model of PMPHolefillingVisitor. More...

Functions
template<typename PolygonMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
auto	CGAL::Polygon_mesh_processing::triangulate_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, const NamedParameters &np=parameters::default_values())
	triangulates a hole in a polygon mesh.
template<typename PolygonMesh , typename OutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>
OutputIterator	CGAL::Polygon_mesh_processing::triangulate_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, OutputIterator out, const NamedParameters &np=parameters::default_values())
	triangulates a hole in a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
auto	CGAL::Polygon_mesh_processing::triangulate_and_refine_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, const NamedParameters &np=parameters::default_values())
	triangulates and refines a hole in a polygon mesh.
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>
std::pair< FaceOutputIterator, VertexOutputIterator >	CGAL::Polygon_mesh_processing::triangulate_and_refine_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, FaceOutputIterator face_out, VertexOutputIterator vertex_out, const NamedParameters &np=parameters::default_values())
	triangulates and refines a hole in a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
auto	CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, const NamedParameters &np=parameters::default_values())
	triangulates, refines and fairs a hole in a polygon mesh.
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>
std::tuple< bool, FaceOutputIterator, VertexOutputIterator >	CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, FaceOutputIterator face_out, VertexOutputIterator vertex_out, const NamedParameters &np=parameters::default_values())
	triangulates, refines, and fairs a hole in a polygon mesh.
template<typename PointRange1 , typename PointRange2 , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>
OutputIterator	CGAL::Polygon_mesh_processing::triangulate_hole_polyline (const PointRange1 &points, const PointRange2 &third_points, OutputIterator out, const NamedParameters &np=parameters::default_values())
	creates triangles to fill the hole defined by points in the range points.
template<typename PointRange , typename OutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>
OutputIterator	CGAL::Polygon_mesh_processing::triangulate_hole_polyline (const PointRange &points, OutputIterator out, const NamedParameters &np=parameters::default_values())
	Same as above but the range of third points is omitted.

Function Documentation

triangulate_and_refine_hole() [1/2]

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

auto CGAL::Polygon_mesh_processing::triangulate_and_refine_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates and refines a hole in a polygon mesh.

Template Parameters

PolygonMesh	must be model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	polygon mesh which has the hole
border_halfedge	a border halfedge incident to the hole
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

face_output_iterator iterator over patch faces Type: a model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces Default: Emptyset_iterator
vertex_output_iterator iterator over patch vertices Type: a model of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices Default: Emptyset_iterator
vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
use_delaunay_triangulation If true, use the Delaunay triangulation facet search space. Type: Boolean Default: true Extra: If no valid triangulation can be found in this search space, the algorithm falls back to the non-Delaunay triangulations search space to find a solution.
use_2d_constrained_delaunay_triangulation If true, the points of the boundary of the hole are used to estimate a fitting plane and a 2D constrained Delaunay triangulation is then used to fill the hole projected in the fitting plane. Type: Boolean Default: true Extra: If the boundary of the hole is not planar (according to the parameter threshold_distance) or if no valid 2D triangulation can be found, the algorithm falls back to the method using the 3D Delaunay triangulation. This parameter is a good choice for near planar holes.
threshold_distance The maximum distance between the vertices of the hole boundary and the least squares plane fitted to this boundary. Type: double Default: one quarter of the height of the bounding box of the hole Extra: This parameter is used only in conjunction with the parameter use_2d_constrained_delaunay_triangulation.
do_not_use_cubic_algorithm Set this parameter to true if you only want to use the Delaunay based versions of the algorithm, skipping the cubic search space one in case of failure. Type: Boolean Default: false Extra: If true, use_2d_constrained_delaunay_triangulation or use_delaunay_triangulation must be set to true otherwise nothing will be done.
density_control_factor factor to control density of the output mesh, where larger values cause denser refinements, as in refine() Type: double Default: \( \sqrt{2}\)
visitor a visitor used to track when entering a given phase of the algorithm Type: A model of PMPHolefillingVisitor Type: Hole_filling::Default_visitor

Returns

pair of face and vertex output iterator

See also

CGAL::Polygon_mesh_processing::triangulate_hole()

CGAL::Polygon_mesh_processing::refine()

Todo:

handle islands

triangulate_and_refine_hole() [2/2]

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>

std::pair< FaceOutputIterator, VertexOutputIterator > CGAL::Polygon_mesh_processing::triangulate_and_refine_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		FaceOutputIterator	face_out,
		VertexOutputIterator	vertex_out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates and refines a hole in a polygon mesh.

Deprecated:

This function is deprecated since CGAL 5.6 and the overload with the named parameters face_output_iterator and vertex_output_iterator should be used instead.

Template Parameters

PolygonMesh	must be model of MutableFaceGraph
FaceOutputIterator	model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces.
VertexOutputIterator	model of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices.
NamedParameters	a sequence of Named Parameters

triangulate_hole() [1/2]

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

auto CGAL::Polygon_mesh_processing::triangulate_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates a hole in a polygon mesh.

Depending on the choice of the underlying algorithm different preconditions apply. When using the 2D constrained Delaunay triangulation, the border edges of the hole must not intersect the surface. Otherwise, additionally, the boundary of the hole must not contain any non-manifold vertex. The patch generated does not introduce non-manifold edges nor degenerate triangles. If a hole cannot be triangulated, pmesh is not modified and nothing is recorded in the face output iterator.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	polygon mesh containing the hole
border_halfedge	a border halfedge incident to the hole
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

face_output_iterator iterator over patch faces Type: a model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces Default: Emptyset_iterator
vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
use_delaunay_triangulation If true, use the Delaunay triangulation facet search space. Type: Boolean Default: true Extra: If no valid triangulation can be found in this search space, the algorithm falls back to the non-Delaunay triangulations search space to find a solution.
use_2d_constrained_delaunay_triangulation If true, the points of the boundary of the hole are used to estimate a fitting plane and a 2D constrained Delaunay triangulation is then used to fill the hole projected in the fitting plane. Type: Boolean Default: true Extra: If the boundary of the hole is not planar (according to the parameter threshold_distance) or if no valid 2D triangulation can be found, the algorithm falls back to the method using the 3D Delaunay triangulation. This parameter is a good choice for near planar holes.
threshold_distance The maximum distance between the vertices of the hole boundary and the least squares plane fitted to this boundary. Type: double Default: one quarter of the height of the bounding box of the hole Extra: This parameter is used only in conjunction with the parameter use_2d_constrained_delaunay_triangulation.
do_not_use_cubic_algorithm Set this parameter to true if you only want to use the Delaunay based versions of the algorithm, skipping the cubic search space one in case of failure. Type: Boolean Default: false Extra: If true, use_2d_constrained_delaunay_triangulation or use_delaunay_triangulation must be set to true otherwise nothing will be done.
visitor a visitor used to track when entering a given phase of the algorithm Type: A model of PMPHolefillingVisitor Type: Hole_filling::Default_visitor

Returns

the face output iterator

Todo:

handle islands

Replace border_halfedge by a range of border halfedges. The first one would describe the hole, the other ones would describe the islands.

Then, insert the holes vertices in the set of possibilities for connecting vertices together

handle the case where an island is reduced to a point

triangulate_hole() [2/2]

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

OutputIterator CGAL::Polygon_mesh_processing::triangulate_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		OutputIterator	out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates a hole in a polygon mesh.

Deprecated:

This function is deprecated since CGAL 5.6 and the overload with the named parameter face_output_iterator should be used instead.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
OutputIterator	a model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces.
NamedParameters	a sequence of Named Parameters

triangulate_hole_polyline() [1/2]

template<typename PointRange , typename OutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>

OutputIterator CGAL::Polygon_mesh_processing::triangulate_hole_polyline	(	const PointRange &	points,
		OutputIterator	out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

Same as above but the range of third points is omitted.

They are not taken into account in the cost computation that leads the hole filling.

triangulate_hole_polyline() [2/2]

template<typename PointRange1 , typename PointRange2 , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>

OutputIterator CGAL::Polygon_mesh_processing::triangulate_hole_polyline	(	const PointRange1 &	points,
		const PointRange2 &	third_points,
		OutputIterator	out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

creates triangles to fill the hole defined by points in the range points.

Triangles are recorded into out using the indices of the input points in the range points. Note that no degenerate triangles will be produced. If no triangulation can be found, then nothing is recorded in out.

If faces incident to the polyline outside the hole are known, it is recommended to use this function. The point range third_points indicates for each pair of consecutive points in the range points, the third point of the face this segment is incident to. It influences the choice of the best triangulation while avoiding overfolding.

Note that the ranges points and third_points may or may not contain duplicated first point at the end of sequence.

Precondition

third_points.size() == points.size()

Template Parameters

PointRange	range of points, model of Range. Its iterator type is InputIterator.
OutputIterator	model of OutputIterator, to collect patch faces. A specialization for CGAL::value_type_traits<OutputIterator> must be available, and the corresponding value type type must have a constructor type(int p0, int p1, int p2) available. The indices correspond to the ones of input points in points.
NamedParameters	a sequence of Named Parameters

Parameters

points	the range of input points
third_points	the range of third points
out	iterator over output patch triangles, described by indices of points in points
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
use_delaunay_triangulation If true, use the Delaunay triangulation facet search space. Type: Boolean Default: true Extra: If no valid triangulation can be found in this search space, the algorithm falls back to the non-Delaunay triangulations search space to find a solution.
use_2d_constrained_delaunay_triangulation If true, the points of the boundary of the hole are used to estimate a fitting plane and a 2D constrained Delaunay triangulation is then used to fill the hole projected in the fitting plane. Type: Boolean Default: true Extra: If the boundary of the hole is not planar (according to the parameter threshold_distance) or if no valid 2D triangulation can be found, the algorithm falls back to the method using the 3D Delaunay triangulation. This parameter is a good choice for near planar holes.
threshold_distance The maximum distance between the vertices of the hole boundary and the least squares plane fitted to this boundary. Type: double Default: one quarter of the height of the bounding box of the hole Extra: This parameter is used only in conjunction with the parameter use_2d_constrained_delaunay_triangulation.
visitor a visitor used to track when entering a given phase of the algorithm Type: A model of PMPHolefillingVisitor Type: Hole_filling::Default_visitor

Todo:

handle islands

Examples

Polygon_mesh_processing/triangulate_polyline_example.cpp.

triangulate_refine_and_fair_hole() [1/2]

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

auto CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates, refines and fairs a hole in a polygon mesh.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	polygon mesh which has the hole
border_halfedge	a border halfedge incident to the hole
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

face_output_iterator iterator over patch faces Type: a model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces Default: Emptyset_iterator
vertex_output_iterator iterator over patch vertices Type: a model of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices Default: Emptyset_iterator
vertex_point_map a property map associating points to the vertices of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, pmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
use_delaunay_triangulation If true, use the Delaunay triangulation facet search space. Type: Boolean Default: true Extra: If no valid triangulation can be found in this search space, the algorithm falls back to the non-Delaunay triangulations search space to find a solution.
use_2d_constrained_delaunay_triangulation If true, the points of the boundary of the hole are used to estimate a fitting plane and a 2D constrained Delaunay triangulation is then used to fill the hole projected in the fitting plane. Type: Boolean Default: true Extra: If the boundary of the hole is not planar (according to the parameter threshold_distance) or if no valid 2D triangulation can be found, the algorithm falls back to the method using the 3D Delaunay triangulation. This parameter is a good choice for near planar holes.
threshold_distance The maximum distance between the vertices of the hole boundary and the least squares plane fitted to this boundary. Type: double Default: one quarter of the height of the bounding box of the hole Extra: This parameter is used only in conjunction with the parameter use_2d_constrained_delaunay_triangulation.
density_control_factor factor to control density of the output mesh, where larger values cause denser refinements, as in refine() Type: double Default: \( \sqrt{2}\)
fairing_continuity A value controlling the tangential continuity of the output surface patch. The possible values are 0, 1 and 2, referring to the C0, C1 and C2 continuity. Type: unsigned int Default: 1 Extra: The larger fairing_continuity gets, the more fixed vertices are required.
sparse_linear_solver an instance of the sparse linear solver used for fairing Type: a class model of SparseLinearAlgebraWithFactorTraits_d Default: If Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then the following overload of Eigen_solver_traits is provided as default value: CGAL::Eigen_solver_traits<Eigen::SparseLU<CGAL::Eigen_sparse_matrix<double>::EigenType, Eigen::COLAMDOrdering<int> > >
visitor a visitor used to track when entering a given phase of the algorithm Type: A model of PMPHolefillingVisitor Type: Hole_filling::Default_visitor

Returns

tuple of bool with true if fairing is successful, and the face and vertex output iterator

See also

CGAL::Polygon_mesh_processing::triangulate_hole()

CGAL::Polygon_mesh_processing::refine()

CGAL::Polygon_mesh_processing::fair()

Todo:

handle islands

triangulate_refine_and_fair_hole() [2/2]

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = CGAL::parameters::Default_named_parameters>

std::tuple< bool, FaceOutputIterator, VertexOutputIterator > CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole	(	PolygonMesh &	pmesh,
		typename boost::graph_traits< PolygonMesh >::halfedge_descriptor	border_halfedge,
		FaceOutputIterator	face_out,
		VertexOutputIterator	vertex_out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>

triangulates, refines, and fairs a hole in a polygon mesh.

Deprecated:

This function is deprecated since CGAL 5.6 and the overload with the named parameters face_output_iterator and vertex_output_iterator should be used instead.

Template Parameters

PolygonMesh	a model of MutableFaceGraph
FaceOutputIterator	model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces.
VertexOutputIterator	model of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices.
NamedParameters	a sequence of Named Parameters