Polygon Mesh Processing Reference

Sébastien Loriot, Mael Rouxel-Labbé, 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; CGAL and Solvers
BibTeX: cgal:lty-pmp-21b
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.

Meshing Functions

• CGAL::Polygon_mesh_processing::fair()
• CGAL::Polygon_mesh_processing::refine()
• CGAL::Polygon_mesh_processing::smooth_mesh()
• CGAL::Polygon_mesh_processing::smooth_shape()
• CGAL::Polygon_mesh_processing::triangulate_face()
• CGAL::Polygon_mesh_processing::triangulate_faces()
• CGAL::Polygon_mesh_processing::isotropic_remeshing()
• CGAL::Polygon_mesh_processing::split_long_edges()
• CGAL::Polygon_mesh_processing::minimal_angle_remeshing()
• CGAL::Polygon_mesh_processing::random_perturbation()
• CGAL::Polygon_mesh_processing::extrude_mesh()

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

• CGAL::Polygon_mesh_processing::does_self_intersect()
• CGAL::Polygon_mesh_processing::self_intersections()
• CGAL::Polygon_mesh_processing::do_intersect()
• CGAL::Polygon_mesh_processing::intersecting_meshes()
• 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

Location Functions

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

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

Combinatorial Repairing 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::duplicate_non_manifold_vertices()
• CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()
• CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles()
• CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size()

Normal Computation Functions

• CGAL::Polygon_mesh_processing::compute_face_normal()
• CGAL::Polygon_mesh_processing::compute_face_normals()
• CGAL::Polygon_mesh_processing::compute_vertex_normal()
• CGAL::Polygon_mesh_processing::compute_vertex_normals()
• CGAL::Polygon_mesh_processing::compute_normals()

Connected Components

• CGAL::Polygon_mesh_processing::connected_component()
• CGAL::Polygon_mesh_processing::connected_components()
• CGAL::Polygon_mesh_processing::keep_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()

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

Geometric Measure Functions

• CGAL::Polygon_mesh_processing::face_area()
• CGAL::Polygon_mesh_processing::area()
• CGAL::Polygon_mesh_processing::volume()
• CGAL::Polygon_mesh_processing::edge_length()
• CGAL::Polygon_mesh_processing::face_border_length()
• CGAL::Polygon_mesh_processing::centroid()
• CGAL::Polygon_mesh_processing::match_faces()

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_mesh()
• CGAL::Polygon_mesh_processing::sample_triangle_soup()

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

Collision Detection

• CGAL::Rigid_triangle_mesh_collision_detection

Miscellaneous

• CGAL::Polygon_mesh_slicer
• CGAL::Side_of_triangle_mesh
• 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()

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 Repairing
	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.
	Intersection Detection Functions
	Functions to detect intersections.
	I/O 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::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 >
CGAL::Bbox_3	CGAL::Polygon_mesh_processing::bbox (const PolygonMesh &pmesh, const NamedParameters &np)
	computes a bounding box of a polygon mesh. More...
template<typename PolygonMesh , typename NamedParameters >
CGAL::Bbox_3	CGAL::Polygon_mesh_processing::vertex_bbox (typename boost::graph_traits< PolygonMesh >::vertex_descriptor vd, const PolygonMesh &pmesh, const NamedParameters &np)
	computes a bounding box of a vertex of a polygon mesh. More...
template<typename PolygonMesh , typename NamedParameters >
CGAL::Bbox_3	CGAL::Polygon_mesh_processing::edge_bbox (typename boost::graph_traits< PolygonMesh >::edge_descriptor ed, const PolygonMesh &pmesh, const NamedParameters &np)
	computes a bounding box of an edge of a polygon mesh. More...
template<typename PolygonMesh , typename NamedParameters >
CGAL::Bbox_3	CGAL::Polygon_mesh_processing::face_bbox (typename boost::graph_traits< PolygonMesh >::face_descriptor fd, const PolygonMesh &pmesh, const NamedParameters &np)
	computes a bounding box of a face of a polygon mesh. More...
template<typename PolygonMesh , typename NamedParameters >
CGAL::Bbox_3	CGAL::Polygon_mesh_processing::bbox_3 (const PolygonMesh &pmesh, const NamedParameters &np)
template<typename PolygonMesh , typename FaceRange , typename HalfedgeOutputIterator , typename NamedParameters >
HalfedgeOutputIterator	CGAL::Polygon_mesh_processing::border_halfedges (const FaceRange &face_range, const PolygonMesh &pmesh, HalfedgeOutputIterator out, const NamedParameters &np)
	collects the border halfedges of a surface patch defined as a face range. More...
template<typename PolygonMesh , typename OutputIterator >
OutputIterator	CGAL::Polygon_mesh_processing::extract_boundary_cycles (PolygonMesh &pm, OutputIterator out)
	extracts boundary cycles as a list of halfedges, with one halfedge per border. More...
template<class Transformation , class PolygonMesh , class NamedParameters >
void	CGAL::Polygon_mesh_processing::transform (const Transformation &transformation, PolygonMesh &mesh, const NamedParameters &np)
	applies a transformation to every vertex of a PolygonMesh. More...

Function Documentation

bbox()

template<typename PolygonMesh , typename NamedParameters >

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::bbox	(	const PolygonMesh &	pmesh,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/bbox.h>

computes a bounding box of a polygon mesh.

Template Parameters

PolygonMesh	a model of HalfedgeListGraph
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

vertex_point_map 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.
geom_traits 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.

Returns

a bounding box of pmesh

bbox_3()

template<typename PolygonMesh , typename NamedParameters >

CGAL::Bbox_3 CGAL::Polygon_mesh_processing::bbox_3	(	const PolygonMesh &	pmesh,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/bbox.h>

Deprecated:

This function is deprecated since CGAL 4.10, CGAL::Polygon_mesh_processing::bbox() should be used instead.

border_halfedges()

template<typename PolygonMesh , typename FaceRange , typename HalfedgeOutputIterator , typename NamedParameters >

HalfedgeOutputIterator CGAL::Polygon_mesh_processing::border_halfedges	(	const FaceRange &	face_range,
		const PolygonMesh &	pmesh,
		HalfedgeOutputIterator	out,
		const NamedParameters &	np
	)

#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

face_index_map 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

Examples:

Polygon_mesh_processing/isotropic_remeshing_example.cpp.

edge_bbox()

template<typename PolygonMesh , typename NamedParameters >

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

#include <CGAL/Polygon_mesh_processing/bbox.h>

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

Template Parameters

PolygonMesh	a model of HalfedgeGraph
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

vertex_point_map 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.
geom_traits 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.

Returns

a bounding box of pmesh

extract_boundary_cycles()

template<typename PolygonMesh , typename OutputIterator >

OutputIterator CGAL::Polygon_mesh_processing::extract_boundary_cycles	(	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

Todo:

It could make sense to also return the length of each cycle.

It should probably go into BGL package (like the rest of this file).

Examples:

Polygon_mesh_processing/hole_filling_example_SM.cpp.

face_bbox()

template<typename PolygonMesh , typename NamedParameters >

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

#include <CGAL/Polygon_mesh_processing/bbox.h>

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

Template Parameters

PolygonMesh	a model of HalfedgeGraph
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

vertex_point_map 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.
geom_traits 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

Returns

a bounding box of pmesh

transform()

template<class Transformation , class PolygonMesh , class NamedParameters >

void CGAL::Polygon_mesh_processing::transform	(	const Transformation &	transformation,
		PolygonMesh &	mesh,
		const NamedParameters &	np
	)

#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

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

Examples:

Polygon_mesh_processing/hausdorff_bounded_error_distance_example.cpp.

vertex_bbox()

template<typename PolygonMesh , typename NamedParameters >

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

#include <CGAL/Polygon_mesh_processing/bbox.h>

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

Template Parameters

PolygonMesh	a model of HalfedgeGraph
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

vertex_point_map 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.
geom_traits 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.

Returns

a bounding box of pmesh