CGAL 6.1 - Polygon Mesh Processing

Loading...
Searching...
No Matches
Classes | Functions
Hole Filling
Reference Manual

##

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

  iterator over patch faces Type: a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::face_descriptor` for patch faces Default: `Emptyset_iterator` |
  iterator over patch vertices Type: a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::vertex_descriptor` for patch vertices Default: `Emptyset_iterator` |
  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 output mesh, where larger values cause denser refinements, as in `refine()` Type: double Default: \( \sqrt{2}\) |
  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()

## ◆ 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

  iterator over patch faces Type: a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::face_descriptor` for patch faces Default: `Emptyset_iterator` |
  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. |
  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

## ◆ 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

  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`. |
  a visitor used to track when entering a given phase of the algorithm Type: A model of PMPHolefillingVisitor Type: Hole_filling::Default_visitor |

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

  iterator over patch faces Type: a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::face_descriptor` for patch faces Default: `Emptyset_iterator` |
  iterator over patch vertices Type: a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::vertex_descriptor` for patch vertices Default: `Emptyset_iterator` |
  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 output mesh, where larger values cause denser refinements, as in `refine()` Type: double Default: \( \sqrt{2}\) |
  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. |
  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> > >` |
  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()

## ◆ 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