CGAL 6.1.1 - Polygon Mesh Processing

Loading...
Searching...
No Matches
Modules | Files | Classes | Functions
Reference Manual

##

David Coeurjolly, Jaques-Olivier Lachaud, Konstantinos Katrioplas, Sébastien Loriot, Ivan Pađen, Mael Rouxel-Labbé, Hossam Saeed, Jane Tournois, Sébastien Valette, and 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 such as Boolean operations, remeshing, repairing, collision and intersection detection, and more.
Introduced in: CGAL 4.7
Depends on: documented for each function; CGAL and Solvers
BibTeX: cgal:lty-pmp-26a
License: GPL
Windows Demo: CGAL Lab

## Classified Reference Pages

## Parameters

Optional parameters of the functions of this package are implemented as Named Parameters. The page Named Parameters describes their usage.

## Corefinement and Boolean Operation Functions

- `CGAL::Polygon_mesh_processing::corefine_and_compute_union()`
- `CGAL::Polygon_mesh_processing::corefine_and_compute_difference()`
- `CGAL::Polygon_mesh_processing::corefine_and_compute_intersection()`
- `CGAL::Polygon_mesh_processing::corefine_and_compute_boolean_operations()`
- `CGAL::Polygon_mesh_processing::corefine()`
- `CGAL::Polygon_mesh_processing::surface_intersection()`
- `CGAL::Polygon_mesh_processing::clip()`
- `CGAL::Polygon_mesh_processing::split()`
- `CGAL::Polygon_mesh_processing::autorefine_triangle_soup()`
- `CGAL::Polygon_mesh_processing::autorefine()`

## Meshing Functions

- `CGAL::Polygon_mesh_processing::remesh_planar_patches()`
- `CGAL::Polygon_mesh_processing::remesh_almost_planar_patches()`
- `CGAL::Polygon_mesh_processing::refine()`
- `CGAL::Polygon_mesh_processing::fair()`
- `CGAL::Polygon_mesh_processing::triangulate_face()`
- `CGAL::Polygon_mesh_processing::triangulate_faces()`
- `CGAL::Polygon_mesh_processing::triangulate_polygons()`
- `CGAL::Polygon_mesh_processing::isotropic_remeshing()`
- `CGAL::Polygon_mesh_processing::surface_Delaunay_remeshing()`
- `CGAL::Polygon_mesh_processing::split_long_edges()`
- `CGAL::Polygon_mesh_processing::approximated_centroidal_Voronoi_diagram_remeshing()`
- `CGAL::Polygon_mesh_processing::extrude_mesh()`
- `CGAL::Polygon_mesh_processing::smooth_mesh()` (deprecated)
- `CGAL::Polygon_mesh_processing::angle_and_area_smoothing()`
- `CGAL::Polygon_mesh_processing::tangential_relaxation()`
- `CGAL::Polygon_mesh_processing::smooth_shape()`
- `CGAL::Polygon_mesh_processing::random_perturbation()`

## Sizing Fields

- `CGAL::Polygon_mesh_processing::Uniform_sizing_field`
- `CGAL::Polygon_mesh_processing::Adaptive_sizing_field`

## Orientation Functions

- `CGAL::Polygon_mesh_processing::orient_polygon_soup()`
- `CGAL::Polygon_mesh_processing::orient()`
- `CGAL::Polygon_mesh_processing::does_bound_a_volume()`
- `CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()`
- `CGAL::Polygon_mesh_processing::volume_connected_components()`
- `CGAL::Polygon_mesh_processing::is_outward_oriented()`
- `CGAL::Polygon_mesh_processing::reverse_face_orientations()`
- `CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup()`
- `CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh()`
- `CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_soup()`
- `CGAL::Polygon_mesh_processing::merge_reversible_connected_components()`
- `CGAL::Polygon_mesh_processing::compatible_orientations()`

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

## Intersection Functions

- `CGAL::Polygon_mesh_processing::does_self_intersect()`
- `CGAL::Polygon_mesh_processing::self_intersections()`
- `CGAL::Polygon_mesh_processing::does_triangle_soup_self_intersect()`
- `CGAL::Polygon_mesh_processing::triangle_soup_self_intersections()`
- `CGAL::Polygon_mesh_processing::do_intersect()`
- `CGAL::Polygon_mesh_processing::intersecting_meshes()`

## Collision Detection

- `CGAL::Rigid_triangle_mesh_collision_detection`

## Predicate Functions

- `CGAL::Polygon_mesh_processing::is_degenerate_edge()`
- `CGAL::Polygon_mesh_processing::degenerate_edges()`
- `CGAL::Polygon_mesh_processing::is_degenerate_triangle_face()`
- `CGAL::Polygon_mesh_processing::degenerate_faces()`
- `CGAL::Polygon_mesh_processing::is_needle_triangle_face()`
- `CGAL::Polygon_mesh_processing::is_cap_triangle_face()`
- `CGAL::Polyhedral_envelope`
- `CGAL::Side_of_triangle_mesh`

## Combinatorial Repair Functions

- `CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup()`
- `CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup()`
- `CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup()`
- `CGAL::Polygon_mesh_processing::repair_polygon_soup()`
- `CGAL::Polygon_mesh_processing::stitch_boundary_cycle()`
- `CGAL::Polygon_mesh_processing::stitch_boundary_cycles()`
- `CGAL::Polygon_mesh_processing::stitch_borders()`
- `CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh()`
- `CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh()`
- `CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup()`
- `CGAL::Polygon_mesh_processing::remove_isolated_vertices()`
- `CGAL::Polygon_mesh_processing::is_non_manifold_vertex()`
- `CGAL::Polygon_mesh_processing::non_manifold_vertices()`
- `CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices()`
- `CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()`
- `CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles()`

## Geometric Repair Functions

- `CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces()`

## Connected Components

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

## Location Functions

- Point Location
- Location Predicates
- Nearest Face Location Queries
- Random Location Generation

## Corrected Curvatures

- `CGAL::Polygon_mesh_processing::interpolated_corrected_curvatures()`
- `CGAL::Polygon_mesh_processing::Principal_curvatures_and_directions`

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

## Distance Functions

- `CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance()`
- `CGAL::Polygon_mesh_processing::bounded_error_symmetric_Hausdorff_distance()`
- `CGAL::Polygon_mesh_processing::is_Hausdorff_distance_larger()`
- `CGAL::Polygon_mesh_processing::approximate_Hausdorff_distance()`
- `CGAL::Polygon_mesh_processing::approximate_symmetric_Hausdorff_distance()`
- `CGAL::Polygon_mesh_processing::approximate_max_distance_to_point_set()`
- `CGAL::Polygon_mesh_processing::max_distance_to_triangle_mesh()`
- `CGAL::Polygon_mesh_processing::sample_triangle_soup()`
- `CGAL::Polygon_mesh_processing::sample_triangle_mesh()`

## Geometric Measure Functions

- `CGAL::Polygon_mesh_processing::angle_sum()`
- `CGAL::Polygon_mesh_processing::discrete_Gaussian_curvatures()`
- `CGAL::Polygon_mesh_processing::discrete_Gaussian_curvature()`
- `CGAL::Polygon_mesh_processing::discrete_mean_curvature()`
- `CGAL::Polygon_mesh_processing::discrete_mean_curvatures()`
- `CGAL::Polygon_mesh_processing::edge_length()`
- `CGAL::Polygon_mesh_processing::squared_edge_length()`
- `CGAL::Polygon_mesh_processing::face_area()`
- `CGAL::Polygon_mesh_processing::squared_face_area()`
- `CGAL::Polygon_mesh_processing::area()`
- `CGAL::Polygon_mesh_processing::volume()`
- `CGAL::Polygon_mesh_processing::face_border_length()`
- `CGAL::Polygon_mesh_processing::longest_border()`
- `CGAL::Polygon_mesh_processing::centroid()`

## Feature Detection Functions

- `CGAL::Polygon_mesh_processing::sharp_edges_segmentation()`
- `CGAL::Polygon_mesh_processing::detect_sharp_edges()`
- `CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()`
- `CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces()`
- `CGAL::Polygon_mesh_processing::detect_corners_of_regions()`

## Miscellaneous

- `CGAL::Polygon_mesh_slicer`
- `CGAL::Polygon_mesh_processing::bbox()`
- `CGAL::Polygon_mesh_processing::vertex_bbox()`
- `CGAL::Polygon_mesh_processing::edge_bbox()`
- `CGAL::Polygon_mesh_processing::face_bbox()`
- `CGAL::Polygon_mesh_processing::border_halfedges()`
- `CGAL::Polygon_mesh_processing::extract_boundary_cycles()`
- `CGAL::Polygon_mesh_processing::transform()`
- `CGAL::Polygon_mesh_processing::triangle()`
- `CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces()`
- `CGAL::Polygon_mesh_processing::detect_corners_of_regions()`
- `CGAL::Polygon_mesh_processing::refine_mesh_at_isolevel()`
- `CGAL::Polygon_mesh_processing::refine_with_plane()`

## I/O Functions

- `CGAL::Polygon_mesh_processing::IO::read_polygon_mesh()`

## Modules
| Concepts
| Connected Components
| Two faces are in the same connected component if there is a path of adjacent faces such that all edges between two consecutive faces of the path are not marked as constrained.
| Hole Filling
| Functions to fill holes given as a range of halfedges or as range of points.
| Meshing
| Functions to triangulate faces, and to refine and fair regions of a polygon mesh.
| Corrected Curvature Computation
| Functions to compute the corrected curvatures of a polygon mesh.
| Normal Computation
| Functions to compute unit normals for individual/all vertices or faces.
| Geometric Measure Functions
| Functions to compute discrete curvatures, lengths of edges and borders, areas of faces and patches, volumes of closed meshes.
| Orientation Functions
| Functions to compute or change the orientation of faces and surfaces.
| Intersection Functions
| Functions to test if there are self intersections, and to report faces that do intersect.
| Combinatorial Repair
| Functions to repair polygon soups and polygon meshes.
| Geometric Repair
| Functions to repair polygon soups and polygon meshes.
| Distance Functions
| Functions to compute the distance between meshes, between a mesh and a point set and between a point set and a mesh.
| Corefinement and Boolean Operations
| Functions to corefine triangulated surface meshes and compute triangulated surface meshes of the union, difference and intersection of the bounded volumes.
| Feature Detection Functions
| Functions to detect sharp edges and surface patches of polygon meshes.
| Location Functions
| Functions to locate points on a mesh, and manipulate such locations.
| Predicates
| Classes and functions that answer queries about a polygon mesh or its elements.
| I/O Functions
| Deprecated Functions

## 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...
struct | CGAL::Polyhedral_envelope< GeomTraits >
| This class can be used to check if a query point, segment, or triangle is inside or outside a polyhedral envelope of a set of triangles, constructed for a given \( \epsilon \) distance tolerance. More...
class | CGAL::Rigid_triangle_mesh_collision_detection< TriangleMesh, VertexPointMap, Kernel, AABBTree, Has_rotation >
| This class provides methods to perform some intersection tests between triangle meshes that undergo affine transformations (rotation, translation, and scaling). More...

## Functions
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::approximated_centroidal_Voronoi_diagram_remeshing (TriangleMesh &tmesh, std::size_t nb_vertices, const NamedParameters &np=parameters::default_values())
| performs Approximated Centroidal Voronoi Diagram (ACVD) remeshing on a triangle mesh.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
CGAL::Bbox_3 | CGAL::Polygon_mesh_processing::bbox (const PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
| computes a bounding box of a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
CGAL::Bbox_3 | CGAL::Polygon_mesh_processing::vertex_bbox (typename boost::graph_traits< PolygonMesh >::vertex_descriptor vd, const PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
| computes a bounding box of the vertex of a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
CGAL::Bbox_3 | CGAL::Polygon_mesh_processing::edge_bbox (typename boost::graph_traits< PolygonMesh >::edge_descriptor ed, const PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
| computes a bounding box of an edge of a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
CGAL::Bbox_3 | CGAL::Polygon_mesh_processing::face_bbox (typename boost::graph_traits< PolygonMesh >::face_descriptor fd, const PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
| computes a bounding box of a face of a polygon mesh.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::add_bbox (PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
| adds an axis-aligned bounding box to a polygon mesh.
template<typename PolygonMesh , typename FaceRange , typename HalfedgeOutputIterator , typename NamedParameters = parameters::Default_named_parameters>
HalfedgeOutputIterator | CGAL::Polygon_mesh_processing::border_halfedges (const FaceRange &face_range, const PolygonMesh &pmesh, HalfedgeOutputIterator out, const NamedParameters &np=parameters::default_values())
| collects the border halfedges of a surface patch defined as a face range.
template<typename PolygonMesh , typename OutputIterator >
OutputIterator | CGAL::Polygon_mesh_processing::extract_boundary_cycles (const PolygonMesh &pm, OutputIterator out)
| extracts boundary cycles as a list of halfedges, with one halfedge per border.
template<class PolygonMesh , class ValueMap , class NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::refine_mesh_at_isolevel (PolygonMesh &pm, ValueMap value_map, typename boost::property_traits< ValueMap >::value_type isovalue, const NamedParameters &np=parameters::default_values())
| refines `pm` by adding new vertices on edges having their incident vertices associated with values respectively larger and smaller than `isovalue` in `value_map`.
template<class Transformation , class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::transform (const Transformation &transformation, PolygonMesh &mesh, const NamedParameters &np=parameters::default_values())
| applies a transformation to every vertex of a `PolygonMesh`.
template<typename TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
Triangle_3 | CGAL::Polygon_mesh_processing::triangle (typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
| computes a triangle for a face descriptor of a triangle mesh.
template<typename PolygonMesh , typename RegionMap , typename NamedParameters = parameters::Default_named_parameters>
std::size_t | CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces (const PolygonMesh &mesh, RegionMap region_map, const NamedParameters &np=parameters::default_values())
| applies a region growing algorithm to fit planes on faces of a mesh.
template<typename PolygonMesh , typename RegionMap , typename CornerIdMap , typename NamedParameters = parameters::Default_named_parameters>
std::size_t | CGAL::Polygon_mesh_processing::detect_corners_of_regions (const PolygonMesh &mesh, RegionMap region_map, std::size_t nb_regions, CornerIdMap corner_id_map, const NamedParameters &np=parameters::default_values())
| detects the corners on the boundary of almost planar regions by applying the region growing algorithm fitting lines on segment edges of a partition of a mesh.

## Function Documentation

## ◆ add_bbox()

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

void CGAL::Polygon_mesh_processing::add_bbox | ( | PolygonMesh & | pmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

adds an axis-aligned bounding box to a polygon mesh.

Template Parameters

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

Parameters

  pmesh | a polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a double used to scale the bounding box. The default value is 1 and the bounding box is the smallest possible axis-aligned bounding box. Default: 1. Precondition: `bbox_scaling > 0` |
  a Boolean used to specify whether the bounding box's faces should be triangulated or not. The default value is `true`, and faces are not triangulated. Default: true |
  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 model of `Kernel`. |

See also
  `bbox()`

## ◆ approximated_centroidal_Voronoi_diagram_remeshing()

template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::approximated_centroidal_Voronoi_diagram_remeshing | ( | TriangleMesh & | tmesh,
|  | std::size_t | nb_vertices,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

performs Approximated Centroidal Voronoi Diagram (ACVD) remeshing on a triangle mesh.

The remeshing is either uniform or adaptative. Note that there is no guarantee that the output mesh will have the same topology as the input. See Approximated Discrete Centroidal Voronoi Diagram (ACVD) Remeshing for more details on the algorithm. This function requires the Eigen library.

Template Parameters

  TriangleMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  NamedParameters | a sequence of Named Parameters.

Parameters

  tmesh | triangle mesh to be remeshed
  nb_vertices | lower bound on the target number of vertices in the output mesh. The requested number of vertices in the output will be respected except if the input mesh is not closed (extra vertices will be used on the boundary), or if the number of points is too low and no manifold mesh can be produced with that budget of points (extra points are added to get a manifold output).
  np | optional sequence of Named Parameters among the ones listed below. `GT` stands for the type of the traits object provided to the named parameter `geom_traits()`.

Optional Named Parameters

  a property map associating principal curvatures and directions to the vertices of `tmesh`, used for adaptive clustering. Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Principal_curvatures_and_directions<GT>` as value type. Default: If this parameter is omitted, but `gradation_factor` is provided, an internal property map will be created and curvature values will be computed using the function `interpolated_corrected_curvatures()`. |
  a factor used to gradate the weights of the vertices based on their curvature values. The larger the value is, the more the curvature will impact the distribution of output vertices on the surface. The original paper recommends the value `1.5`. Type: `GT::FT` Default: 0 Extra: If this parameter is omitted, no adaptive clustering will be performed. |
  indicates if a projection step using quadric error metric should be applied to cluster centers at the end of the minimization, in order for example to recover sharp features. This is a fast method but can result in badly shaped triangles and even self-intersections. Type: Boolean Default: false |
  indicates if quadric error metric should be applied during the minimization algorithm in order for example to recover sharp features. This is slower than using `use_postprocessing_qem(true)`, but it is more accurate. Type: Boolean Default: false Extra: If this parameter is `true` then `use_postprocessing_qem` will be automatically set to `false`. |
  a ratio used to control the subdivision of the input mesh in case it does not have enough vertices compared to `nb_vertices`. More precisely, the number of vertices of the input mesh should at least be the ratio times `nb_vertices`. If not, the mesh will first be subdivided until the aforementioned criterium is met. Type: `GT::FT` Default: 0.1 Extra: A value between 0.1 and 0.01 is recommended, the smaller the better the approximation will be, but it will increase the runtime. |
  a property map associating points to the vertices of `tmesh`. Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `GT::Point_3` as value type. Default: `boost::get(CGAL::vertex_point, tmesh)`. Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available in `TriangleMesh`. |
  an instance of a geometric traits class. Type: a class model of `Kernel`, with `GT::FT` being either `float` or `double`. Default: a CGAL Kernel deduced from the vertex point type, using `CGAL::Kernel_traits`. Extra: The geometric traits class must be compatible with the vertex point type. |
  a value to seed the random number generator Type: unsigned int Default: a value generated with `std::time()` |

Precondition
  `tmesh` is a triangulated surface mesh and has exactly one connected component.

Returns
  `true` if `nb_vertices` was sufficiently large for remeshing the input, and `false` if more points were used

## ◆ bbox()

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

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::bbox | ( | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

computes a bounding box of a polygon mesh.

Template Parameters

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

Parameters

  pmesh | a polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `pmesh` Type: a class model of `ReadablePropertyMap` 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 providing the functor `Construct_bbox_3` and the function `Construct_bbox_3 construct_bbox_3_object()`. `Construct_bbox_3` must provide the functor `Bbox_3 operator()(Point_3)` where `Point_3` is the value type of the vertex point map. |
  a double used to scale the bounding box. The default value is 1 and the bounding box is the smallest possible axis-aligned bounding box. Default: 1. Precondition: `bbox_scaling > 0` |

See also
  `vertex_bbox()`
  `edge_bbox()`
  `face_bbox()`

## ◆ border_halfedges()

template<typename PolygonMesh , typename FaceRange , typename HalfedgeOutputIterator , typename NamedParameters = parameters::Default_named_parameters>

HalfedgeOutputIterator CGAL::Polygon_mesh_processing::border_halfedges | ( | const FaceRange & | face_range,
|  | const PolygonMesh & | pmesh,
|  | HalfedgeOutputIterator | out,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

collects the border halfedges of a surface patch defined as a face range.

For each returned halfedge `h`, `opposite(h, pmesh)` belongs to a face of the patch, but `face(h, pmesh)` does not belong to the patch.

Template Parameters

  PolygonMesh | model of `HalfedgeGraph`
  FaceRange | a model of `Range` with value type `boost::graph_traits<PolygonMesh>::face_descriptor`.
  HalfedgeOutputIterator | model of `OutputIterator` holding `boost::graph_traits<PolygonMesh>::halfedge_descriptor` for patch border
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh to which the faces in `face_range` belong
  face_range | the range of faces defining the patch whose border halfedges are collected
  out | the output iterator that collects the border halfedges of the patch, seen from outside.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

Returns
  `out`

See also
  `extract_boundary_cycles()`

## ◆ detect_corners_of_regions()

template<typename PolygonMesh , typename RegionMap , typename CornerIdMap , typename NamedParameters = parameters::Default_named_parameters>

std::size_t CGAL::Polygon_mesh_processing::detect_corners_of_regions | ( | const PolygonMesh & | mesh,
|  | RegionMap | region_map,
|  | std::size_t | nb_regions,
|  | CornerIdMap | corner_id_map,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

detects the corners on the boundary of almost planar regions by applying the region growing algorithm fitting lines on segment edges of a partition of a mesh.

More precisely, a corner on the boundary of a region is a vertex that is either shared by at least three regions (two if it is also a vertex on the boundary of the mesh), or that is incident to two segments edges assigned to different lines. See Section Region Growing for more details on the method.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `EdgeListGraph`
  RegionMap | a model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type.
  CornerIdMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type.
  NamedParameters | a sequence of Named Parameters

Parameters

  mesh | polygon mesh for region growing.
  region_map | property map providing the region index of each face, values must be in `[0, nb_regions-1]`.
  corner_id_map | property map storing the corner index of each vertex. Values start at `0` up to the value returned minus 1. `std::size_t(-1)` is put for vertices that are not corners.
  nb_regions | the number of patches in the partition of `mesh` defined by `region_map`
  np | an optional sequence of Named Parameters among the ones listed below

Returns
  the number of corners detected

Optional Named Parameters

  a property map filled by this function such that an edge is marked as constrained if it is at the interface of two different regions or on the boundary of the mesh Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: Unused if not provided Extra: The value for each edge must be initialized to `false`. |
  the maximum distance from a segment to a line such that it is considered part of the region of the line Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: 1 |
  the maximum angle in degrees between two adjacent segments such that they are considered part of the same region Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: 25 degrees Extra: this parameter and `cosine_of_maximum_angle` are exclusive |
  The maximum angle, given as a cosine, for the smallest angle between the supporting line of a segment and an adjacent segment such that they are considered part of the same region Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: `cos(25 * PI / 180)` Extra: this parameter and `maximum_angle` are exclusive |
  a property map associating points to the vertices of `mesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, mesh)` 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. |

## ◆ edge_bbox()

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

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::edge_bbox | ( | typename boost::graph_traits< PolygonMesh >::edge_descriptor | ed,
|  | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

computes a bounding box of an edge of a polygon mesh.

Template Parameters

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

Parameters

  ed | a descriptor of an edge in `pmesh`
  pmesh | a polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `pmesh` Type: a class model of `ReadablePropertyMap` 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 providing the functor `Construct_bbox_3` and the function `Construct_bbox_3 construct_bbox_3_object()`. `Construct_bbox_3` must provide `Bbox_3 operator()(Point_3)` where `Point_3` is the value type of the vertex point map. |

See also
  `vertex_bbox()`
  `face_bbox()`
  `bbox()`

## ◆ extract_boundary_cycles()

template<typename PolygonMesh , typename OutputIterator >

OutputIterator CGAL::Polygon_mesh_processing::extract_boundary_cycles | ( | const PolygonMesh & | pm,
|  | OutputIterator | out
| ) |  |

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

extracts boundary cycles as a list of halfedges, with one halfedge per border.

Template Parameters

  PolygonMesh | a model of `HalfedgeListGraph`
  OutputIterator | a model of `OutputIterator` holding objects of type `boost::graph_traits<PolygonMesh>::halfedge_descriptor`

Parameters

  pm | a polygon mesh
  out | an output iterator where the border halfedges will be put

See also
  `border_halfedges()`

## ◆ face_bbox()

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

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::face_bbox | ( | typename boost::graph_traits< PolygonMesh >::face_descriptor | fd,
|  | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

computes a bounding box of a face of a polygon mesh.

Template Parameters

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

Parameters

  fd | a descriptor of a face in `pmesh`
  pmesh | a polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `pmesh` Type: a class model of `ReadablePropertyMap` 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 providing the functor `Construct_bbox_3` and the function `Construct_bbox_3 construct_bbox_3_object()`. `Construct_bbox_3` must provide `Bbox_3 operator()(Point_3)` where `Point_3` is the value type of the vertex point map. Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` |

See also
  `vertex_bbox()`
  `edge_bbox()`
  `bbox()`

## ◆ refine_mesh_at_isolevel()

template<class PolygonMesh , class ValueMap , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::refine_mesh_at_isolevel | ( | PolygonMesh & | pm,
|  | ValueMap | value_map,
|  | typename boost::property_traits< ValueMap >::value_type | isovalue,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

refines `pm` by adding new vertices on edges having their incident vertices associated with values respectively larger and smaller than `isovalue` in `value_map`.

The placement of new vertices on edges will be done by linear interpolation using the aforementioned values. New vertices will be associated `isovalue` in `value_map` when created. Additionally, new edges will be added by connecting new vertices created sharing a common incident face. Note that in case more than two new vertices are added on a face boundary, no edges will be created in that face.

Template Parameters

  PolygonMesh | a model of the concepts `EdgeListGraph` and `FaceListGraph`
  ValueMap | a model of the concept `ReadWritePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and with its value type being the type of the coordinates of points associated with vertices in the vertex map provided to the `vertex_point_map()` named parameter.
  NamedParameters | a sequence of Named Parameters for `pm`

Parameters

  pm | the polygon mesh to be refined.
  value_map | the property map containing a value at each vertex for a given function defined over the mesh.
  isovalue | the value used to refine
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  an output property map associating `true` to all edges connecting vertices on the isolevel, and `false` for all other edges. Type: a class model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: No marks on edges will be put |
  a property map associating points to the vertices of `pm` 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, pm)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available in `PolygonMesh`. |

## ◆ region_growing_of_planes_on_faces()

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

std::size_t CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces | ( | const PolygonMesh & | mesh,
|  | RegionMap | region_map,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

applies a region growing algorithm to fit planes on faces of a mesh.

See Section Region Growing for more details on the method.

Template Parameters

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

Parameters

  mesh | the polygon mesh whose faces are used for region growing
  region_map | a property map storing the region index of each face. Values start at `0` up to the value returned minus `1`. `std::size_t(-1)` is put for faces with no region assigned (it can happen if `minimum_region_size > 1` or for a non-triangular face having a fitting plane not satisfying the maximum distance criterium).
  np | an optional sequence of Named Parameters among the ones listed below

Returns
  the number of regions detected

Optional Named Parameters

  the maximum distance from a face to a plane such that it is considered part of the region of the plane Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: 1 |
  the maximum angle (in degrees) between the normals of the supporting planes of two adjacent faces such that they are considered part of the same region Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: 25 degrees Extra: this parameter and `cosine_of_maximum_angle` are exclusive |
  Apply a postprocessing step to the output of the region growing algorithm. Type: `bool` Default: false |
  The maximum angle, given as a cosine, between the normals of the supporting planes of adjacent faces such that they are considered part of the same region Type: `GeomTraits::FT` with `GeomTraits` being the type of the parameter `geom_traits` Default: `cos(25 * PI / 180)` Extra: this parameter and `maximum_angle` are exclusive |
  the minimum number of faces such that a new region can be created from a set of faces Type: `std::size_t` Default: 1 |
  a property map associating points to the vertices of `mesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, mesh)` 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. |
  a property map filled by this function and that will contain for each region the plane (or only its orthognonal vector) estimated that approximates it. Type: a class model of `WritablePropertyMap` with the value type of `RegionMap` as key and `GeomTraits::Plane_3` or `GeomTraits::Vector_3` as value type, `GeomTraits` being the type of the parameter `geom_traits` Default: None |

## ◆ transform()

template<class Transformation , class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::transform | ( | const Transformation & | transformation,
|  | PolygonMesh & | mesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

applies a transformation to every vertex of a `PolygonMesh`.

Template Parameters

  Transformation | a functor that has an `operator()(Point_3)`, with `Point_3` the `value_type` of `vertex_point_map` (see below). Such a functor can be `CGAL::Aff_transformation_3` for example.
  PolygonMesh | a model of `VertexListGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  transformation | the transformation functor to apply to the points of `mesh`.
  mesh | the `PolygonMesh` to transform.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `mesh` 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, mesh)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` must be available in `PolygonMesh`. |

## ◆ triangle()

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

Triangle_3 CGAL::Polygon_mesh_processing::triangle | ( | typename boost::graph_traits< TriangleMesh >::face_descriptor | fd,
|  | const TriangleMesh & | tmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

computes a triangle for a face descriptor of a triangle mesh.

Template Parameters

  TriangleMesh | a model of `FaceGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  tmesh | the triangulated surface mesh
  fd | the descriptor of the face to construct the triangle from
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tmesh)` |
  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. |

## ◆ vertex_bbox()

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

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::vertex_bbox | ( | typename boost::graph_traits< PolygonMesh >::vertex_descriptor | vd,
|  | const PolygonMesh & | pmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

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

computes a bounding box of the vertex of a polygon mesh.

Template Parameters

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

Parameters

  vd | a descriptor of a vertex in `pmesh`
  pmesh | a polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `pmesh` Type: a class model of `ReadablePropertyMap` 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 providing the functor `Construct_bbox_3` and the function `Construct_bbox_3 construct_bbox_3_object()`. `Construct_bbox_3` must provide `Bbox_3 operator()(Point_3)` where `Point_3` is the value type of the vertex point map. |

See also
  `edge_bbox()`
  `face_bbox()`
  `bbox()`