Polygon Mesh Processing Reference

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

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

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

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

vertex_principal_curvatures_and_directions_map 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().
gradation_factor 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.
use_postprocessing_qem 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
use_qem_based_energy 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.
vertex_count_ratio 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.
vertex_point_map 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.
geom_traits 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.
random_seed a value to seed the random number generator Type: unsigned int Default: a value generated with std::time()

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

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 the functor Bbox_3 operator()(Point_3) where Point_3 is the value type of the vertex point map.
bbox_scaling 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

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

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

edge_is_constrained_map 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.
maximum_distance 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
maximum_angle 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
cosine_of_maximum_angle 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
vertex_point_map 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.
geom_traits 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

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.

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

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

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

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

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

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

maximum_distance 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
maximum_angle 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
postprocess_regions Apply a post-processing step to the output of the region growing algorithm. Type: bool Default: false
cosine_of_maximum_angle 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
minimum_region_size the minimum number of faces such that a new region can be created from a set of faces Type: std::size_t Default: 1
vertex_point_map 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.
geom_traits 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.
region_primitive_map 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

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.

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

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

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.

See also

edge_bbox()

face_bbox()

bbox()