CGAL 5.5.5 - Polygon Mesh Processing

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 OutputIterator , typename NamedParameters = 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. More...
 
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = 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. More...
 
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = 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. More...
 
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. More...
 
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. More...
 

Function Documentation

◆ triangulate_and_refine_hole()

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = 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.

Template Parameters
PolygonMeshmust be model of MutableFaceGraph
FacetOutputIteratormodel of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces.
VertexOutputIteratormodel of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices.
NamedParametersa sequence of Named Parameters
Parameters
pmeshpolygon mesh which has the hole
border_halfedgea border halfedge incident to the hole
face_outoutput iterator over patch faces
vertex_outoutput iterator over patch vertices without including the boundary
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • 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.

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

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

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

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

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

  • factor to control density of the ouput mesh, where larger values cause denser refinements, as in refine()
  • Type: double
  • Default: \( \sqrt{2}\)

Returns
pair of face_out and vertex_out
See also
CGAL::Polygon_mesh_processing::triangulate_hole()
CGAL::Polygon_mesh_processing::refine()

◆ triangulate_hole()

template<typename PolygonMesh , typename OutputIterator , typename NamedParameters = 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.

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

Template Parameters
PolygonMesha model of MutableFaceGraph
OutputIteratora model of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces.
NamedParametersa sequence of Named Parameters
Parameters
pmeshpolygon mesh containing the hole
border_halfedgea border halfedge incident to the hole
outiterator over patch faces
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • 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.

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

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

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

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

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

Returns
out

◆ triangulate_hole_polyline() [1/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
PointRangerange of points, model of Range. Its iterator type is InputIterator.
OutputIteratormodel 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.
NamedParametersa sequence of Named Parameters
Parameters
pointsthe range of input points
third_pointsthe range of third points
outiterator over output patch triangles, described by indices of points in points
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • 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.

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

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

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

Examples:
Polygon_mesh_processing/triangulate_polyline_example.cpp.

◆ triangulate_hole_polyline() [2/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_refine_and_fair_hole()

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = 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.

Template Parameters
PolygonMesha model of MutableFaceGraph
FaceOutputIteratormodel of OutputIterator holding boost::graph_traits<PolygonMesh>::face_descriptor for patch faces
VertexOutputIteratormodel of OutputIterator holding boost::graph_traits<PolygonMesh>::vertex_descriptor for patch vertices
NamedParametersa sequence of Named Parameters
Parameters
pmeshpolygon mesh which has the hole
border_halfedgea border halfedge incident to the hole
face_outoutput iterator over patch faces
vertex_outoutput iterator over patch vertices without including the boundary
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • 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.

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

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

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

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

  • factor to control density of the ouput mesh, where larger values cause denser refinements, as in refine()
  • Type: double
  • Default: \( \sqrt{2}\)

  • A value controling the tangential continuity of the output surface patch. The possible values are 0, 1 and 2, refering to the C0, C1 and C2 continuity.
  • Type: unsigned int
  • Default: 1
  • Extra: The larger fairing_continuity gets, the more fixed vertices are required.

Returns
tuple of
  • bool: true if fairing is successful
  • face_out
  • vertex_out
See also
CGAL::Polygon_mesh_processing::triangulate_hole()
CGAL::Polygon_mesh_processing::refine()
CGAL::Polygon_mesh_processing::fair()
Examples:
Polygon_mesh_processing/hole_filling_example.cpp, Polygon_mesh_processing/hole_filling_example_SM.cpp, and Polygon_mesh_processing/hole_filling_visitor_example.cpp.