Sébastien Loriot, Mael Rouxel-Labbé, Jane Tournois, 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-23a
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

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

Meshing Functions

Orientation Functions

Hole Filling Functions

Intersection Functions

Collision Detection

CGAL::Rigid_triangle_mesh_collision_detection

Predicate Functions

Combinatorial Repair Functions

Geometric Repair Functions

CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces()

Connected Components

Location Functions

Normal Computation Functions

Distance Functions

Geometric Measure Functions

Feature Detection Functions

Miscellaneous

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.

	Normal Computation
	Functions to compute unit normals for individual/all vertices or faces.

	Geometric Measure Functions
	Functions to compute lengths of edges and borders, areas of faces and patches, as well as 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 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 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 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

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

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

◆ 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 (can only happen if `minimum_region_size > 1`).
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 post-processing 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()

Classified Reference Pages

Parameters

Corefinement and Boolean Operation Functions

Meshing Functions

Orientation Functions

Hole Filling Functions

Intersection Functions

Collision Detection

Predicate Functions

Combinatorial Repair Functions

Geometric Repair Functions

Connected Components

Location Functions

Normal Computation Functions

Distance Functions

Geometric Measure Functions

Feature Detection Functions

Miscellaneous

I/O Functions

Modules

Files

Classes

Functions

Function Documentation

◆ bbox()

◆ border_halfedges()

◆ detect_corners_of_regions()

◆ edge_bbox()

◆ extract_boundary_cycles()

◆ face_bbox()

◆ region_growing_of_planes_on_faces()

◆ transform()

◆ triangle()

◆ vertex_bbox()