CGAL 4.7 - Polygon Mesh Processing
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
Windows Demo: Operations on Polyhedra
Common Demo Dlls: dlls

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

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

## 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::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::vertex_descriptor as key type and Kernel::Vector_3 as value type. FaceNormalMap a model of WritablePropertyMap with boost::graph_traits::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::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::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::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::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
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 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 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
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 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::face_descriptor for patch faces VertexOutputIterator model of OutputIterator holding boost::graph_traits::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::face_descriptor, boost::graph_traits::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::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::face_descriptor, boost::graph_traits::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 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::face_descriptor for patch faces. VertexOutputIterator model of OutputIterator holding boost::graph_traits::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
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::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::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::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 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::face_descriptor for patch faces VertexOutputIterator model of OutputIterator holding boost::graph_traits::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
#include <CGAL/Polygon_mesh_processing/triangulate_hole.h>