CGAL 4.7 - Polygon Mesh Processing: Polygon Mesh Processing Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Polygon Mesh Processing

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Files | Classes | Functions
Polygon Mesh Processing Reference

##

Sébastien Loriot, Jane Tournois, Ilker O. Yaz
This package provides a collection of methods and classes for polygon mesh processing, ranging from basic operations on simplices, to complex geometry processing algorithms.

Introduced in: CGAL 4.7
Depends on: documented for each function; Sparse square solver such as those from Eigen
BibTeX: cgal:lty-pmp-15b
License: GPL
Windows Demo: Operations on Polyhedra
Common Demo Dlls: dlls

## Classified Reference Pages

## Parameters

Optional parameters of the functions of this package are implemented as BGL named parameters. The page Named Parameters describes their usage and provides a list of the parameters that are used in this package.

## Meshing Functions

- `CGAL::Polygon_mesh_processing::fair()`
- `CGAL::Polygon_mesh_processing::refine()`
- `CGAL::Polygon_mesh_processing::triangulate_faces()`

## Hole Filling Functions

- `CGAL::Polygon_mesh_processing::triangulate_hole()`
- `CGAL::Polygon_mesh_processing::triangulate_and_refine_hole()`
- `CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole()`
- `CGAL::Polygon_mesh_processing::triangulate_hole_polyline()`

## Predicate Functions and Classes

- `CGAL::Polygon_mesh_processing::does_self_intersect()`
- `CGAL::Polygon_mesh_processing::self_intersections()`
- `CGAL::Side_of_triangle_mesh`

## Orientation Functions

- `CGAL::Polygon_mesh_processing::is_outward_oriented()`
- `CGAL::Polygon_mesh_processing::reverse_face_orientations()`

## Combinatorial Repairing Functions

- `CGAL::Polygon_mesh_processing::stitch_borders()`
- `CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh()`
- `CGAL::Polygon_mesh_processing::orient_polygon_soup()`

## Normal Computation Functions

- `CGAL::Polygon_mesh_processing::compute_face_normal()`
- `CGAL::Polygon_mesh_processing::compute_face_normals()`
- `CGAL::Polygon_mesh_processing::compute_vertex_normal()`
- `CGAL::Polygon_mesh_processing::compute_vertex_normals()`
- `CGAL::Polygon_mesh_processing::compute_normals()`

## Connected Components

- `CGAL::Polygon_mesh_processing::connected_component()`
- `CGAL::Polygon_mesh_processing::connected_components()`
- `CGAL::Polygon_mesh_processing::keep_largest_connected_components()`
- `CGAL::Polygon_mesh_processing::keep_connected_components()`
- `CGAL::Polygon_mesh_processing::remove_connected_components()`

## Miscellaneous

- `CGAL::Polygon_mesh_slicer`

## Modules

| Named Parameters
| How to use BGL Optional Named Parameters
| Concepts
| CGAL::Polygon_mesh_processing::stitch_borders()
| CGAL::reverse_face_orientations()
| CGAL::keep_connected_components()
| CGAL::remove_connected_components()

## Files

file | polygon_mesh_processing.h
| Convenience header file including the headers for all the free functions of this package.

## Classes

class | CGAL::Polygon_mesh_slicer< TriangleMesh, Traits, VertexPointMap, AABBTree, UseParallelPlaneOptimization >
| Function object that computes the intersection of a plane with a triangulated surface mesh. More...
class | CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >
| This class provides an efficient point location functionality with respect to a domain bounded by one or several disjoint closed triangle meshes. More...

## Functions

template<typename PolygonMesh , typename NamedParameters >
Vector_3 | CGAL::Polygon_mesh_processing::compute_face_normal (typename boost::graph_traits< PolygonMesh >::face_descriptor f, const PolygonMesh &pmesh, const NamedParameters &np)
| computes the outward unit vector normal to face `f`. More...
template<typename PolygonMesh , typename FaceNormalMap , typename NamedParameters >
void | CGAL::Polygon_mesh_processing::compute_face_normals (const PolygonMesh &pmesh, FaceNormalMap fnm, const NamedParameters &np)
| computes the outward unit vector normal for all faces of the polygon mesh. More...
template<typename PolygonMesh , typename NamedParameters >
Vector_3 | CGAL::Polygon_mesh_processing::compute_vertex_normal (typename boost::graph_traits< PolygonMesh >::vertex_descriptor v, const PolygonMesh &pmesh, const NamedParameters &np)
| computes the unit normal at vertex `v` as the average of the normals of incident faces. More...
template<typename PolygonMesh , typename VertexNormalMap , typename NamedParameters >
void | CGAL::Polygon_mesh_processing::compute_vertex_normals (const PolygonMesh &pmesh, VertexNormalMap vnm, const NamedParameters &np)
| computes the outward unit vector normal for all vertices of the polygon mesh. More...
template<typename PolygonMesh , typename VertexNormalMap , typename FaceNormalMap , typename NamedParameters >
void | CGAL::Polygon_mesh_processing::compute_normals (const PolygonMesh &pmesh, VertexNormalMap vnm, FaceNormalMap fnm, const NamedParameters &np)
| computes the outward unit vector normal for all vertices and faces of the polygon mesh. More...
template<typename PolygonMesh , typename FaceOutputIterator , typename NamedParameters >
FaceOutputIterator | CGAL::Polygon_mesh_processing::connected_component (typename boost::graph_traits< PolygonMesh >::face_descriptor seed_face, const PolygonMesh &pmesh, FaceOutputIterator out, const NamedParameters &np)
| discovers all the faces in the same connected component as `seed_face` and records them in `out`. More...
template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters >
boost::property_traits < FaceComponentMap > ::value_type | CGAL::Polygon_mesh_processing::connected_components (const PolygonMesh &pmesh, const FaceComponentMap &fcm, const NamedParameters &np)
| computes for each face the index of the corresponding connected component. More...
template<typename PolygonMesh , typename NamedParameters >
std::size_t | CGAL::Polygon_mesh_processing::keep_largest_connected_components (PolygonMesh &pmesh, std::size_t nb_components_to_keep, const NamedParameters &np)
| removes the small connected components and all the isolated vertices. More...
template<typename PolygonMesh , typename VertexRange , typename NamedParameters >
bool | CGAL::Polygon_mesh_processing::fair (PolygonMesh &pmesh, const VertexRange &vertices, const NamedParameters &np)
| fairs a region on a polygon mesh. More...
template<class Point , class Polygon >
bool | CGAL::Polygon_mesh_processing::orient_polygon_soup (std::vector< Point > &points, std::vector< Polygon > &polygons)
| tries to consistently orient a soup of polygons in 3D space. More...
template<typename PolygonMesh , typename NamedParameters >
bool | CGAL::Polygon_mesh_processing::is_outward_oriented (const PolygonMesh &pmesh, const NamedParameters &np)
| tests whether a closed polygon mesh has a positive orientation. More...
template<class PolygonMesh , class Point , class Polygon >
void | CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh (const std::vector< Point > &points, const std::vector< Polygon > &polygons, PolygonMesh &out)
| builds a polygon mesh from a soup of polygons. More...
template<typename PolygonMesh , typename FaceRange , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >
std::pair< FaceOutputIterator, VertexOutputIterator > | CGAL::Polygon_mesh_processing::refine (PolygonMesh &pmesh, const FaceRange &faces, FaceOutputIterator faces_out, VertexOutputIterator vertices_out, const NamedParameters &np)
| refines a region of a polygon mesh More...
template<class TriangleMesh , class OutputIterator , class NamedParameters >
OutputIterator | CGAL::Polygon_mesh_processing::self_intersections (const TriangleMesh &tmesh, OutputIterator out, const NamedParameters &np)
| detects and records self-intersections of a triangulated surface mesh. More...
template<class TriangleMesh , class FaceRange , class OutputIterator , class NamedParameters >
OutputIterator | CGAL::Polygon_mesh_processing::self_intersections (const FaceRange &face_range, const TriangleMesh &tmesh, OutputIterator out, const NamedParameters &np)
| Same as above but the self-intersections reported are only limited to the faces in `face_range`. More...
template<class TriangleMesh , class NamedParameters >
bool | CGAL::Polygon_mesh_processing::does_self_intersect (const TriangleMesh &tmesh, const NamedParameters &np)
| tests if a triangulated surface mesh self-intersects. More...
template<typename PolygonMesh , typename NamedParameters >
void | CGAL::Polygon_mesh_processing::triangulate_faces (PolygonMesh &pmesh, const NamedParameters &np)
| triangulates faces of a polygon mesh. More...
template<typename PolygonMesh , typename OutputIterator , typename NamedParameters >
OutputIterator | CGAL::Polygon_mesh_processing::triangulate_hole (PolygonMesh &pmesh, typename boost::graph_traits< PolygonMesh >::halfedge_descriptor border_halfedge, OutputIterator out, const NamedParameters &np)
| triangulates a hole in a polygon mesh. More...
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >
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)
| triangulates and refines a hole in a polygon mesh. More...
template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >
CGAL::cpp11::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)
| triangulates, refines and fairs a hole in a polygon mesh. More...
template<typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator | CGAL::Polygon_mesh_processing::triangulate_hole_polyline (const PointRange &points, const PointRange &third_points, OutputIterator out, const NamedParameters &np)
| creates triangles to fill the hole defined by points in the range `points`. More...
template<typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator | CGAL::Polygon_mesh_processing::triangulate_hole_polyline (const PointRange &points, OutputIterator out, const NamedParameters &np)
| same as above but the range of third points is omitted. More...

## Function Documentation

template<typename PolygonMesh , typename NamedParameters >

Vector_3 CGAL::Polygon_mesh_processing::compute_face_normal | ( | typename boost::graph_traits< PolygonMesh >::face_descriptor | f,
|  | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np
| ) |  |

computes the outward unit vector normal to face `f`.

Template Parameters

  PolygonMesh | a model of `FaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  NamedParameters | a sequence of Named Parameters

Parameters

  f | the face on which the normal is computed
  pmesh | the polygon mesh containing `f`
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

Returns
  the computed normal. The return type is a 3D vector type. It is either deduced from the `geom_traits` Named Parameters if provided, or from the geometric traits class deduced from the point property map of `pmesh`.

`#include <CGAL/Polygon_mesh_processing/compute_normal.h>`

template<typename PolygonMesh , typename FaceNormalMap , typename NamedParameters >

void CGAL::Polygon_mesh_processing::compute_face_normals | ( | const PolygonMesh & | pmesh,
|  | FaceNormalMap | fnm,
|  | const NamedParameters & | np
| ) |  |

computes the outward unit vector normal for all faces of the polygon mesh.

Template Parameters

  PolygonMesh | a model of `FaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  FaceNormalMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `Kernel::Vector_3` as value type.

Parameters

  pmesh | the polygon mesh
  fnm | the property map in which the normals are written
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

`#include <CGAL/Polygon_mesh_processing/compute_normal.h>`

template<typename PolygonMesh , typename VertexNormalMap , typename FaceNormalMap , typename NamedParameters >

void CGAL::Polygon_mesh_processing::compute_normals | ( | const PolygonMesh & | pmesh,
|  | VertexNormalMap | vnm,
|  | FaceNormalMap | fnm,
|  | const NamedParameters & | np
| ) |  |

computes the outward unit vector normal for all vertices and faces of the polygon mesh.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` that has an internal property map for `CGAL::vertex_point_t`
  VertexNormalMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `Kernel::Vector_3` as value type.
  FaceNormalMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `Kernel::Vector_3` as value type.

Parameters

  pmesh | the polygon mesh
  vnm | the property map in which the vertex normals are written
  fnm | the property map in which the face normals are written
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

`#include <CGAL/Polygon_mesh_processing/compute_normal.h>`

Examples:
  Polygon_mesh_processing/compute_normals_example.cpp.

template<typename PolygonMesh , typename NamedParameters >

Vector_3 CGAL::Polygon_mesh_processing::compute_vertex_normal | ( | typename boost::graph_traits< PolygonMesh >::vertex_descriptor | v,
|  | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np
| ) |  |

computes the unit normal at vertex `v` as the average of the normals of incident faces.

Template Parameters

  PolygonMesh | a model of `FaceGraph` that has an internal property map for `CGAL::vertex_point_t`

Parameters

  v | the vertex at which the normal is computed
  pmesh | the polygon mesh containing `v`
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

Returns
  the computed normal. The return type is a 3D vector type. It is either deduced from the `geom_traits` Named Parameters if provided, or the geometric traits class deduced from the point property map of `pmesh`.

`#include <CGAL/Polygon_mesh_processing/compute_normal.h>`

template<typename PolygonMesh , typename VertexNormalMap , typename NamedParameters >

void CGAL::Polygon_mesh_processing::compute_vertex_normals | ( | const PolygonMesh & | pmesh,
|  | VertexNormalMap | vnm,
|  | const NamedParameters & | np
| ) |  |

computes the outward unit vector normal for all vertices of the polygon mesh.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` that has an internal property map for `CGAL::vertex_point_t`
  VertexNormalMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and the return type of `compute_vertex_normal()` as value type.

Parameters

  pmesh | the polygon mesh
  vnm | the property map in which the normals are written
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

`#include <CGAL/Polygon_mesh_processing/compute_normal.h>`

template<typename PolygonMesh , typename FaceOutputIterator , typename NamedParameters >

FaceOutputIterator CGAL::Polygon_mesh_processing::connected_component | ( | typename boost::graph_traits< PolygonMesh >::face_descriptor | seed_face,
|  | const PolygonMesh & | pmesh,
|  | FaceOutputIterator | out,
|  | const NamedParameters & | np
| ) |  |

discovers all the faces in the same connected component as `seed_face` and records them in `out`.

`seed_face` will also be added in `out`. Two faces are recorded in the same connected component if they share an edge that is not marked as constrained.

Template Parameters

  PolygonMesh | a model of `FaceGraph`
  FaceOutputIterator | a model of `OutputIterator` that accepts faces of type `boost::graph_traits<PolygonMesh>::face_descriptor`.
  NamedParameters | a sequence of Named Parameters

Parameters

  seed_face | a face of `pmesh` from which exploration starts to detect the connected component that contains it
  pmesh | the polygon mesh
  out | the output iterator that collects faces from the same connected component as `seed_face`
  np | optional Named Parameters described below

Named Parameters

  edge_is_constrained_map | a property map containing the constrained-or-not status of each edge of `pmesh`

Returns
  the output iterator.

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

Examples:
  Polygon_mesh_processing/connected_components_example.cpp.

template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters >

boost::property_traits<FaceComponentMap>::value_type CGAL::Polygon_mesh_processing::connected_components | ( | const PolygonMesh & | pmesh,
|  | const FaceComponentMap & | fcm,
|  | const NamedParameters & | np
| ) |  |

computes for each face the index of the corresponding connected component.

Two faces are recorded in the same connected component if they share an edge that is not marked as constrained.

A property map for `CGAL::face_index_t` should be either available as an internal property map to `pmesh` or provided as one of the Named Parameters.

Template Parameters

  PolygonMesh | a model of `FaceListGraph`
  FaceComponentMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `boost::face_index` as value type.
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  fcm | the property map with indices of components associated to faces in `pmesh`
  np | optional Named Parameters described below

Named Parameters

  edge_is_constrained_map | a property map containing the constrained-or-not status of each edge of `pmesh`
  face_index_map | a property map containing the index of each face of `pmesh`

Returns
  the number of connected components.

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

Examples:
  Polygon_mesh_processing/connected_components_example.cpp.

template<class TriangleMesh , class NamedParameters >

bool CGAL::Polygon_mesh_processing::does_self_intersect | ( | const TriangleMesh & | tmesh,
|  | const NamedParameters & | np
| ) |  |

tests if a triangulated surface mesh self-intersects.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  TriangleMesh | a model of `FaceListGraph` that has an internal property map for `CGAL::vertex_point_t`
  NamedParameters | a sequence of Named Parameters

Parameters

  tmesh | the triangulated surface mesh to be tested
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `tmesh`
  geom_traits | an instance of a geometric traits class, model of `SelfIntersectionTraits`

Returns
  true if `tmesh` self-intersects

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

Examples:
  Polygon_mesh_processing/self_intersections_example.cpp.

template<typename PolygonMesh , typename VertexRange , typename NamedParameters >

bool CGAL::Polygon_mesh_processing::fair | ( | PolygonMesh & | pmesh,
|  | const VertexRange & | vertices,
|  | const NamedParameters & | np
| ) |  |

fairs a region on a polygon mesh.

The points of the selected vertices are relocated to yield an as-smooth-as-possible surface patch, based on solving a linear bi-Laplacian system with boundary constraints, described in [2]. The optional parameter `fairing_continuity` gives the ability to control the tangential continuity Cn of the output mesh.

The region described by `vertices` might contain multiple disconnected components. Note that the mesh connectivity is not altered in any way, only vertex locations get updated.

Fairing might fail if fixed vertices, which are used as boundary conditions, do not suffice to solve constructed linear system.

Note that if the vertex range to which fairing is applied contains all the vertices of the polygon mesh, fairing does not fail, but the mesh gets shrinked to `CGAL::ORIGIN`.

Template Parameters

  PolygonMesh | a model of `FaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  VertexRange | a range of vertex descriptors of `PolygonMesh`, model of `Range`. Its iterator type is `InputIterator`.
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh with patches to be faired
  vertices | the vertices of the patches to be faired (the positions of only those vertices will be changed)
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  fairing_continuity | tangential continuity of the output surface patch. The larger `fairing_continuity` gets, the more fixed vertices are required
  sparse_linear_solver | an instance of the sparse linear solver used for fairing

Returns
  `true` if fairing is successful, otherwise no vertices are relocated

`#include <CGAL/Polygon_mesh_processing/fair.h>`

Examples:
  Polygon_mesh_processing/refine_fair_example.cpp.

template<typename PolygonMesh , typename NamedParameters >

bool CGAL::Polygon_mesh_processing::is_outward_oriented | ( | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np
| ) |  |

tests whether a closed polygon mesh has a positive orientation.

A closed polygon mesh is considered to have a positive orientation if the normal vectors to all its faces point outside the domain bounded by the polygon mesh. The normal vector to each face is chosen pointing on the side of the face where its sequence of vertices is seen counterclockwise.

Precondition
  `CGAL::is_closed(pmesh)`
  If `pmesh` contains several connected components, they are oriented consistently. In other words, the answer to this predicate would be the same for each isolated connected component.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` that has an internal property map for `boost::vertex_point_t`
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the closed polygon mesh to be tested
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

See Also
  `CGAL::Polygon_mesh_processing::reverse_face_orientations()`

`#include <CGAL/Polygon_mesh_processing/orientation.h>`

Examples:
  Polygon_mesh_processing/polygon_soup_example.cpp.

template<typename PolygonMesh , typename NamedParameters >

std::size_t CGAL::Polygon_mesh_processing::keep_largest_connected_components | ( | PolygonMesh & | pmesh,
|  | std::size_t | nb_components_to_keep,
|  | const NamedParameters & | np
| ) |  |

removes the small connected components and all the isolated vertices.

Keep `nb_components_to_keep` largest connected components. Two faces are considered in the same connected component if they share an edge that is not marked as constrained.

Property maps for `CGAL::face_index_t` and `CGAL::vertex_index_t` should be either available as internal property maps to `pmesh` or provided as Named Parameters.

Template Parameters

  PolygonMesh | a model of `FaceListGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  nb_components_to_keep | the number of components to be kept
  np | optional Named Parameters described below

Named Parameters

  edge_is_constrained_map | a property map containing the constrained-or-not status of each edge of `pmesh`
  face_index_map | a property map containing the index of each face of `pmesh`
  vertex_index_map | a property map containing the index of each vertex of `pmesh`

Returns
  the number of connected components removed (ignoring isolated vertices).

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

Examples:
  Polygon_mesh_processing/connected_components_example.cpp.

template<class Point , class Polygon >

bool CGAL::Polygon_mesh_processing::orient_polygon_soup | ( | std::vector< Point > & | points,
|  | std::vector< Polygon > & | polygons
| ) |  |

tries to consistently orient a soup of polygons in 3D space.

When it is not possible to produce a combinatorial manifold surface, some points are duplicated. Because a polygon soup does not have any connectivity (each point has as many occurences as the number of polygons it belongs to), duplicating one point (or a pair of points) amounts to duplicate the polygon to which it belongs.

These points are either an endpoint of an edge incident to more than two polygons, an endpoint of an edge between two polygons with incompatible orientations (during the re-orientation process), or more generally a point p at which the intersection of an infinitesimally small ball centered at p with the polygons incident to it is not a topological disk.

The algorithm is described in [1].

Template Parameters

  Point | the point type
  Polygon | a `std::vector<std::size_t>` containing the indices of the points of the face

Parameters

  points | points of the soup of polygons. Some points might be pushed back to resolve non-manifold or non-orientability issues.
  polygons | each element in the vector describes a polygon using the index of the points in `points`. If needed the order of the indices of a polygon might be reversed.

Returns
  `true` if the orientation operation succeded.
  `false` if some points were duplicated, thus producing a self-intersecting polyhedron.

`#include <CGAL/Polygon_mesh_processing/orient_polygon_soup.h>`

Examples:
  Polygon_mesh_processing/polygon_soup_example.cpp.

template<class PolygonMesh , class Point , class Polygon >

void CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh | ( | const std::vector< Point > & | points,
|  | const std::vector< Polygon > & | polygons,
|  | PolygonMesh & | out
| ) |  |

builds a polygon mesh from a soup of polygons.

Precondition
  the input polygon soup describes consistently oriented polygon mesh.

Template Parameters

  PolygonMesh | a model of `MutableFaceGraph`
  Point | a point type that has an operator `[]` to access coordinates
  Polygon | a `std::vector<std::size_t>` containing the indices of the points of the face

Parameters

  points | points of the soup of polygons
  polygons | each element in the vector describes a polygon using the index of the points in `points`
  out | the polygon mesh to be built

See Also
  `CGAL::Polygon_mesh_processing::orient_polygon_soup()`

`#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>`

Examples:
  Polygon_mesh_processing/polygon_soup_example.cpp.

template<typename PolygonMesh , typename FaceRange , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >

std::pair<FaceOutputIterator, VertexOutputIterator> CGAL::Polygon_mesh_processing::refine | ( | PolygonMesh & | pmesh,
|  | const FaceRange & | faces,
|  | FaceOutputIterator | faces_out,
|  | VertexOutputIterator | vertices_out,
|  | const NamedParameters & | np
| ) |  |

refines a region of a polygon mesh

Template Parameters

  PolygonMesh | model of `MutableFaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  FaceRange | range of face descriptors, model of `Range`. Its iterator type is `InputIterator`.
  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

Parameters

  pmesh | polygon mesh with patches to be refined
  faces | the range of faces defining the patches to refine
  faces_out | output iterator into which descriptors of new faces are recorded
  vertices_out | output iterator into which descriptors of new vertices are recorded
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh` Instance of a class model of `ReadWritePropertyMap`
  density_control_factor | factor to control density of the ouput mesh, where larger values lead to denser refinements. The density of vertices of `faces_out` is this factor times higher than the vertices of `faces.`

Returns
  pair of `faces_out` and `vertices_out`

`#include <CGAL/Polygon_mesh_processing/refine.h>`

Examples:
  Polygon_mesh_processing/refine_fair_example.cpp.

template<class TriangleMesh , class OutputIterator , class NamedParameters >

OutputIterator CGAL::Polygon_mesh_processing::self_intersections | ( | const TriangleMesh & | tmesh,
|  | OutputIterator | out,
|  | const NamedParameters & | np
| ) |  |

detects and records self-intersections of a triangulated surface mesh.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  TriangleMesh | a model of `FaceListGraph` that has an internal property map for `CGAL::vertex_point_t`
  OutputIterator | a model of `OutputIterator` holding objects of type `std::pair<boost::graph_traits<TriangleMesh>::face_descriptor, boost::graph_traits<TriangleMesh>::face_descriptor>`
  NamedParameters | a sequence of Named Parameters

Parameters

  tmesh | the triangulated surface mesh to be checked
  out | output iterator to be filled with all pairs of non-adjacent faces that intersect
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | an instance of a geometric traits class, model of `SelfIntersectionTraits`

Returns
  `out`

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

Examples:
  Polygon_mesh_processing/self_intersections_example.cpp.

template<class TriangleMesh , class FaceRange , class OutputIterator , class NamedParameters >

OutputIterator CGAL::Polygon_mesh_processing::self_intersections | ( | const FaceRange & | face_range,
|  | const TriangleMesh & | tmesh,
|  | OutputIterator | out,
|  | const NamedParameters & | np
| ) |  |

Same as above but the self-intersections reported are only limited to the faces in `face_range`.

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  FaceRange | range of `boost::graph_traits<PolygonMesh>::face_descriptor`, model of `Range`. Its iterator type is `RandomAccessIterator`.
  TriangleMesh | a model of `FaceListGraph` that has an internal property map for `CGAL::vertex_point_t`
  OutputIterator | a model of `OutputIterator` holding objects of type `std::pair<boost::graph_traits<TriangleMesh>::face_descriptor, boost::graph_traits<TriangleMesh>::face_descriptor>`
  NamedParameters | a sequence of Named Parameters

Parameters

  face_range | the range of faces to check for self-intersection.
  tmesh | the triangulated surface mesh to be checked
  out | output iterator to be filled with all pairs of non-adjacent faces that intersect
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | an instance of a geometric traits class, model of `SelfIntersectionTraits`

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >

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
| ) |  |

triangulates and refines a hole in a polygon mesh.

Template Parameters

  PolygonMesh | must be model of `MutableFaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  FacetOutputIterator | 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

Parameters

  pmesh | polygon mesh which has the hole
  border_halfedge | a border halfedge incident to the hole
  face_out | output iterator over patch faces
  vertex_out | output iterator over patch vertices without including the boundary
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  density_control_factor | factor to control density of the ouput mesh, where larger values cause denser refinements, as in `refine()`
  use_delaunay_triangulation | if `true`, use the Delaunay triangulation facet search space
  geom_traits | a geometric traits class instance

Returns
  pair of `face_out` and `vertex_out`

See Also
  CGAL::Polygon_mesh_processing::triangulate_hole()
  CGAL::Polygon_mesh_processing::refine()

`#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>`

template<typename PolygonMesh , typename NamedParameters >

void CGAL::Polygon_mesh_processing::triangulate_faces | ( | PolygonMesh & | pmesh,
|  | const NamedParameters & | np
| ) |  |

triangulates faces of a polygon mesh.

This function depends on the package 2D Triangulation

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph` that has an internal property map for `boost::vertex_point_t`
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh to be triangulated
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  geom_traits | a geometric traits class instance

`#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>`

Examples:
  Polygon_mesh_processing/triangulate_faces_example.cpp.

template<typename PolygonMesh , typename OutputIterator , typename NamedParameters >

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

triangulates a hole in a polygon mesh.

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

  PolygonMesh | a model of `MutableFaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  OutputIterator | a model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::face_descriptor` for patch faces.
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | polygon mesh containing the hole
  border_halfedge | a border halfedge incident to the hole
  out | iterator over patch faces
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  use_delaunay_triangulation | if `true`, use the Delaunay triangulation facet search space
  geom_traits | a geometric traits class instance

Returns
  `out`

`#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>`

template<typename PointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::Polygon_mesh_processing::triangulate_hole_polyline | ( | const PointRange & | points,
|  | const PointRange & | third_points,
|  | OutputIterator | out,
|  | const NamedParameters & | np
| ) |  |

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

The point range `third_points` indicates for each pair of consecutive points in the range `points`, the third point of the facet this segment is incident to.

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

Template Parameters

  OutputIteratorValueType | value type of `OutputIterator` having a constructor `OutputIteratorValueType(int p0, int p1, int p2)` available. It defaults to `value_type_traits<OutputIterator>::type`, and can be omitted when the default is fine.
  PointRange | range of points, model of `Range`. Its iterator type is `InputIterator`.
  OutputIterator | model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::face_descriptor` for patch faces
  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
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  use_delaunay_triangulation | if `true`, use the Delaunay triangulation facet search space
  geom_traits | a geometric traits class instance

`#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>`

Examples:
  Polygon_mesh_processing/triangulate_polyline_example.cpp.

template<typename PointRange , typename OutputIterator , typename NamedParameters >

OutputIterator CGAL::Polygon_mesh_processing::triangulate_hole_polyline | ( | const PointRange & | points,
|  | OutputIterator | out,
|  | const NamedParameters & | np
| ) |  |

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.

`#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>`

template<typename PolygonMesh , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters >

CGAL::cpp11::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
| ) |  |

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

Template Parameters

  PolygonMesh | a model of `MutableFaceGraph` that has an internal property map for `CGAL::vertex_point_t`
  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

Parameters

  pmesh | polygon mesh which has the hole
  border_halfedge | a border halfedge incident to the hole
  face_out | output iterator over patch faces
  vertex_out | output iterator over patch vertices without including the boundary
  np | optional sequence of Named Parameters among the ones listed below

Named Parameters

  vertex_point_map | the property map with the points associated to the vertices of `pmesh`
  use_delaunay_triangulation | if `true`, use the Delaunay triangulation facet search space
  density_control_factor | factor to control density of the ouput mesh, where larger values cause denser refinements, as in `refine()`
  fairing_continuity | tangential continuity of the output surface patch
  sparse_linear_solver | an instance of the sparse linear solver used for fairing
  geom_traits | a geometric traits class instance

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()

`#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>`

Examples:
  Polygon_mesh_processing/hole_filling_example.cpp.