CGAL 5.1 - Polygon Mesh Processing
Combinatorial Repairing

Functions to repair polygon soups and polygon meshes.

Functions

template<typename PolygonMesh >
bool CGAL::Polygon_mesh_processing::is_non_manifold_vertex (typename boost::graph_traits< PolygonMesh >::vertex_descriptor v, const PolygonMesh &pm)
 checks whether a vertex of a polygon mesh is non-manifold. More...
 
template<typename PolygonMesh , typename OutputIterator >
OutputIterator CGAL::Polygon_mesh_processing::non_manifold_vertices (const PolygonMesh &pm, OutputIterator out)
 collects the non-manifold vertices (if any) present in the mesh. More...
 
template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices (PolygonMesh &pm, const NamedParameters &np)
 duplicates all the non-manifold vertices of the input mesh. More...
 
template<class PolygonMesh , class NamedParameter >
void CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle (typename boost::graph_traits< PolygonMesh >::halfedge_descriptor h, PolygonMesh &pm, const NamedParameter &np)
 merges identical vertices around a cycle of boundary edges. More...
 
template<class PolygonMesh , class NamedParameter >
void CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles (PolygonMesh &pm, const NamedParameter &np)
 extracts boundary cycles and merges the duplicated vertices of each cycle. More...
 
template<typename PolygonMesh , typename PointRange , typename PolygonRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup (const PolygonMesh &mesh, PointRange &points, PolygonRange &polygons, const NamedParameters &np)
 Adds the vertices and faces of a mesh into a (possibly non-empty) polygon soup. More...
 
template<typename PolygonRange >
bool CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh (const PolygonRange &polygons)
 returns true if the soup of polygons defines a valid polygon mesh that can be handled by CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh(). More...
 
template<typename PolygonMesh , typename PointRange , typename PolygonRange , typename NamedParameters_PS , typename NamedParameters_PM >
void CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh (const PointRange &points, const PolygonRange &polygons, PolygonMesh &out, const NamedParameters_PS &np_ps, const NamedParameters_PM &np_pm)
 builds a polygon mesh from a soup of polygons. More...
 
template<class PolygonMesh >
std::size_t CGAL::Polygon_mesh_processing::remove_isolated_vertices (PolygonMesh &pmesh)
 removes the isolated vertices from any polygon mesh. More...
 
template<typename TriangleMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size (TriangleMesh &tmesh, const NamedParameters &np)
 removes connected components whose area or volume is under a certain threshold value. More...
 
template<typename PointRange , typename PolygonRange >
std::size_t CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup (PointRange &points, PolygonRange &polygons)
 Removes the isolated points from a polygon soup. More...
 
template<typename PointRange , typename PolygonRange , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup (PointRange &points, PolygonRange &polygons, const NamedParameters &np)
 Merges the duplicate points in a polygon soup. More...
 
template<typename PointRange , typename PolygonRange , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup (const PointRange &points, PolygonRange &polygons, const NamedParameters &np)
 Merges the duplicate polygons in a polygon soup. More...
 
template<typename PointRange , typename PolygonRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::repair_polygon_soup (PointRange &points, PolygonRange &polygons, const NamedParameters &np)
 Cleans a given polygon soup through various repairing operations. More...
 
template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::is_degenerate_edge (typename boost::graph_traits< PolygonMesh >::edge_descriptor e, const PolygonMesh &pm, const NamedParameters &np)
 checks whether an edge is degenerate. More...
 
template<typename EdgeRange , typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_edges (const EdgeRange &edges, const TriangleMesh &tm, OutputIterator out, const NamedParameters &np)
 collects the degenerate edges within a given range of edges. More...
 
template<typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_edges (const TriangleMesh &tm, OutputIterator out, const NamedParameters &np)
 calls the function degenerate_edges() with the range: edges(tm). More...
 
template<typename TriangleMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::is_degenerate_triangle_face (typename boost::graph_traits< TriangleMesh >::face_descriptor f, const TriangleMesh &tm, const NamedParameters &np)
 checks whether a triangle face is degenerate. More...
 
template<typename FaceRange , typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_faces (const FaceRange &faces, const TriangleMesh &tm, OutputIterator out, const NamedParameters &np)
 collects the degenerate faces within a given range of faces. More...
 
template<typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_faces (const TriangleMesh &tm, OutputIterator out, const NamedParameters &np)
 calls the function degenerate_faces() with the range: faces(tm). More...
 
template<typename TriangleMesh , typename NamedParameters >
boost::graph_traits< TriangleMesh >::halfedge_descriptor CGAL::Polygon_mesh_processing::is_needle_triangle_face (typename boost::graph_traits< TriangleMesh >::face_descriptor f, const TriangleMesh &tm, const double threshold, const NamedParameters &np)
 checks whether a triangle face is needle. More...
 
template<typename TriangleMesh , typename NamedParameters >
boost::graph_traits< TriangleMesh >::halfedge_descriptor CGAL::Polygon_mesh_processing::is_cap_triangle_face (typename boost::graph_traits< TriangleMesh >::face_descriptor f, const TriangleMesh &tm, const double threshold, const NamedParameters &np)
 checks whether a triangle face is a cap. More...
 
template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_boundary_cycle (const typename boost::graph_traits< PolygonMesh >::halfedge_descriptor h, PolygonMesh &pm, const NamedParameters &np)
 Stitches together, whenever possible, two halfedges belonging to the boundary cycle described by the halfedge h. More...
 
template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_boundary_cycles (PolygonMesh &pm, const NamedParameters &np)
 Stitches together, whenever possible, two halfedges belonging to the same boundary cycle. More...
 
template<typename PolygonMesh , typename HalfedgePairsRange >
std::size_t CGAL::Polygon_mesh_processing::stitch_borders (PolygonMesh &pmesh, const HalfedgePairsRange &hedge_pairs_to_stitch)
 Stitches together border halfedges in a polygon mesh. More...
 
template<typename PolygonMesh , class NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_borders (PolygonMesh &pmesh, const NamedParameters &np)
 Same as the other overload but the pairs of halfedges to be stitched are automatically found amongst all border halfedges. More...
 

Function Documentation

◆ degenerate_edges() [1/2]

template<typename EdgeRange , typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_edges ( const EdgeRange &  edges,
const TriangleMesh &  tm,
OutputIterator  out,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

collects the degenerate edges within a given range of edges.

Template Parameters
EdgeRangea model of Range with value type boost::graph_traits<TriangleMesh>::edge_descriptor
TriangleMesha model of HalfedgeGraph
NamedParametersa sequence of Named Parameters
Parameters
edgesa subset of edges of tm
tma triangle mesh
outan output iterator in which the degenerate edges are written
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested type Point_3, and the nested functor Equal_3 to check whether two points are identical.

◆ degenerate_edges() [2/2]

template<typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_edges ( const TriangleMesh &  tm,
OutputIterator  out,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

calls the function degenerate_edges() with the range: edges(tm).

See above for the comprehensive description of the parameters.

◆ degenerate_faces() [1/2]

template<typename FaceRange , typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_faces ( const FaceRange &  faces,
const TriangleMesh &  tm,
OutputIterator  out,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

collects the degenerate faces within a given range of faces.

Template Parameters
FaceRangea model of Range with value type boost::graph_traits<TriangleMesh>::face_descriptor
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
facesa subset of faces of tm
tma triangle mesh
outan output iterator in which the degenerate faces are put
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested functor Collinear_3 to check whether three points are collinear.

◆ degenerate_faces() [2/2]

template<typename TriangleMesh , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::Polygon_mesh_processing::degenerate_faces ( const TriangleMesh &  tm,
OutputIterator  out,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

calls the function degenerate_faces() with the range: faces(tm).

See above for the comprehensive description of the parameters.

◆ duplicate_non_manifold_vertices()

template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices ( PolygonMesh &  pm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/manifoldness.h>

duplicates all the non-manifold vertices of the input mesh.

Template Parameters
PolygonMesha model of HalfedgeListGraph and MutableHalfedgeGraph
NamedParametersa sequence of Named Parameters
Parameters
pmthe surface mesh to be repaired
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
vertex_is_constrained_mapa writable property map with vertex_descriptor as key and bool as value_type. put(pmap, v, true) will be called for each duplicated vertices, as well as the original non-manifold vertex in the input mesh.
output_iteratora model of OutputIterator with value type std::vector<vertex_descriptor>. The first vertex of each vector is a non-manifold vertex of the input mesh, followed by the new vertices that were created to fix this precise non-manifold configuration.
Returns
the number of vertices created.
Examples:
Polygon_mesh_processing/manifoldness_repair_example.cpp.

◆ is_cap_triangle_face()

template<typename TriangleMesh , typename NamedParameters >
boost::graph_traits<TriangleMesh>::halfedge_descriptor CGAL::Polygon_mesh_processing::is_cap_triangle_face ( typename boost::graph_traits< TriangleMesh >::face_descriptor  f,
const TriangleMesh &  tm,
const double  threshold,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

checks whether a triangle face is a cap.

A triangle is said to be a cap if one of the its angles is close to 180 degrees.

Template Parameters
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
fa triangle face of tm
tmtriangle mesh containing f
thresholdthe cosine of a minimum angle such that if f has an angle greater than this bound, it is a cap. The threshold is in range [-1 0] and corresponds to an angle between 90 and 180 degrees.
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested type Point_3 and the nested functors Compute_squared_distance_3, Construct_vector_3, and Compute_scalar_product_3.
Returns
the halfedge opposite of the largest angle if the face is a cap, and a null halfedge otherwise.

◆ is_degenerate_edge()

template<typename PolygonMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::is_degenerate_edge ( typename boost::graph_traits< PolygonMesh >::edge_descriptor  e,
const PolygonMesh &  pm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

checks whether an edge is degenerate.

An edge is considered degenerate if the geometric positions of its two extremities are identical.

Template Parameters
PolygonMesha model of HalfedgeGraph
NamedParametersa sequence of Named Parameters
Parameters
ean edge of pm
pmpolygon mesh containing e
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested type Point_3, and the nested functor Equal_3 to check whether two points are identical.
See also
degenerate_edges()
Returns
true if the edge e is degenerate, false otherwise.

◆ is_degenerate_triangle_face()

template<typename TriangleMesh , typename NamedParameters >
bool CGAL::Polygon_mesh_processing::is_degenerate_triangle_face ( typename boost::graph_traits< TriangleMesh >::face_descriptor  f,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

checks whether a triangle face is degenerate.

A triangle face is considered degenerate if the geometric positions of its vertices are collinear.

Template Parameters
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
fa triangle face of tm
tma triangle mesh containing f
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested functor Collinear_3 to check whether three points are collinear.
See also
degenerate_faces()
Returns
true if the face f is degenerate, false otherwise.

◆ is_needle_triangle_face()

template<typename TriangleMesh , typename NamedParameters >
boost::graph_traits<TriangleMesh>::halfedge_descriptor CGAL::Polygon_mesh_processing::is_needle_triangle_face ( typename boost::graph_traits< TriangleMesh >::face_descriptor  f,
const TriangleMesh &  tm,
const double  threshold,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/shape_predicates.h>

checks whether a triangle face is needle.

A triangle is said to be a needle if its longest edge is much longer than its shortest edge.

Template Parameters
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
fa triangle face of tm
tmtriangle mesh containing f
thresholda bound on the ratio of the longest edge length and the shortest edge length
npoptional Named Parameters described below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. The type of this map is model of ReadWritePropertyMap. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in TriangleMesh
geom_traitsa geometric traits class instance. The traits class must provide the nested type FT and the nested functor Compute_squared_distance_3.
Returns
the shortest halfedge if the triangle face is a needle, and a null halfedge otherwise. If the face contains degenerate edges, a halfedge corresponding to one of these edges is returned.

◆ is_non_manifold_vertex()

template<typename PolygonMesh >
bool CGAL::Polygon_mesh_processing::is_non_manifold_vertex ( typename boost::graph_traits< PolygonMesh >::vertex_descriptor  v,
const PolygonMesh &  pm 
)

#include <CGAL/Polygon_mesh_processing/manifoldness.h>

checks whether a vertex of a polygon mesh is non-manifold.

Template Parameters
PolygonMesha model of HalfedgeListGraph
Parameters
va vertex of pm
pma triangle mesh containing v
Warning
This function has linear runtime with respect to the size of the mesh.
See also
duplicate_non_manifold_vertices()
Returns
true if the vertex is non-manifold, false otherwise.
Examples:
Polygon_mesh_processing/manifoldness_repair_example.cpp.

◆ is_polygon_soup_a_polygon_mesh()

template<typename PolygonRange >
bool CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh ( const PolygonRange &  polygons)

#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>

returns true if the soup of polygons defines a valid polygon mesh that can be handled by CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh().

It checks that each edge has at most two incident faces and such an edge is visited in opposite direction along the two face boundaries, no polygon has twice the same vertex, and the polygon soup describes a manifold surface. This function does not require a range of points as an argument since the check is purely topological. To each vertex of the mesh is associated an index that is used in the description of the boundaries of the polygons provided in polygons.

Template Parameters
PolygonRangea model of the concept RandomAccessContainer whose value_type is a model of the concept RandomAccessContainer whose value_type is std::size_t.
Parameters
polygonseach element in the range describes a polygon using the indices of the vertices.
See also
orient_polygon_soup()
Examples:
Polygon_mesh_processing/orientation_pipeline_example.cpp.

◆ merge_duplicate_points_in_polygon_soup()

template<typename PointRange , typename PolygonRange , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup ( PointRange &  points,
PolygonRange &  polygons,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>

Merges the duplicate points in a polygon soup.

Note that the index of a point that is merged with another point will thus change in all the polygons that the point appears in.

Template Parameters
PointRangea model of the concepts SequenceContainer and Swappable whose value type is the point type.
PolygonRangea model of the concept RandomAccessContainer whose value_type is itself a model of the concept RandomAccessContainer whose value_type is std::size_t.
NamedParametersa sequence of Named Parameters
Parameters
pointspoints of the soup of polygons.
polygonsa vector of polygons. Each element in the vector describes a polygon using the indices of the points in points.
npoptional Named Parameters described below
Named Parameters
geom_traitsa geometric traits class instance. The traits class must provide the nested functor Less_xyz_3 to compare lexicographically two points a function Less_xyz_3 less_xyz_3_object().
Returns
the number of removed points

◆ merge_duplicate_polygons_in_polygon_soup()

template<typename PointRange , typename PolygonRange , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup ( const PointRange &  points,
PolygonRange &  polygons,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>

Merges the duplicate polygons in a polygon soup.

Two polygons are duplicate if they share the same vertices in the same order. Note that the first vertex of the polygon does not matter, that is the triangle 0,1,2 is a duplicate of the triangle 2,0,1.

Template Parameters
PointRangea model of the concept RandomAccessContainer whose value type is the point type.
PolygonRangea model of the concept SequenceContainer whose value_type is itself a model of the concepts RandomAccessContainer and ReversibleContainer whose value_type is std::size_t.
NamedParametersa sequence of Named Parameters
Parameters
pointspoints of the soup of polygons.
polygonsa vector of polygons. Each element in the vector describes a polygon using the indices of the points in points.
npoptional Named Parameters, amongst those described below
Named Parameters
geom_traitsa geometric traits class instance. The traits class must provide the nested functor Less_xyz_3 to compare lexicographically two points a function Less_xyz_3 less_xyz_3_object().
erase_all_duplicatesParameter to indicate, when multiple polygons are duplicates, whether all the duplicate polygons should be removed or if one (arbitrarily chosen) face should be kept. Default is false.
require_same_orientationParameter to indicate if polygon orientation should be taken into account when determining whether two polygons are duplicates, that is, whether e.g. the triangles 0,1,2 and 0,2,1 are duplicates. Default is false.
Returns
the number of removed polygons

◆ merge_duplicated_vertices_in_boundary_cycle()

template<class PolygonMesh , class NamedParameter >
void CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle ( typename boost::graph_traits< PolygonMesh >::halfedge_descriptor  h,
PolygonMesh &  pm,
const NamedParameter &  np 
)

#include <CGAL/Polygon_mesh_processing/merge_border_vertices.h>

merges identical vertices around a cycle of boundary edges.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph.
NamedParametera sequence of Named Parameters.
Parameters
ha halfedge that belongs to a boundary cycle.
pmthe polygon mesh which contains the boundary cycle.
npoptional parameter of Named Parameters listed below.
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pm. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh

◆ merge_duplicated_vertices_in_boundary_cycles()

template<class PolygonMesh , class NamedParameter >
void CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles ( PolygonMesh &  pm,
const NamedParameter &  np 
)

#include <CGAL/Polygon_mesh_processing/merge_border_vertices.h>

extracts boundary cycles and merges the duplicated vertices of each cycle.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph.
NamedParametera sequence of Named Parameters.
Parameters
pmthe polygon mesh which contains the cycles.
npoptional parameter of Named Parameters listed below.
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pm. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh
See also
merge_duplicated_vertices_in_boundary_cycle()

◆ non_manifold_vertices()

template<typename PolygonMesh , typename OutputIterator >
OutputIterator CGAL::Polygon_mesh_processing::non_manifold_vertices ( const PolygonMesh &  pm,
OutputIterator  out 
)

#include <CGAL/Polygon_mesh_processing/manifoldness.h>

collects the non-manifold vertices (if any) present in the mesh.

A non-manifold vertex v is returned via one incident halfedge h such that target(h, pm) = v for all the umbrellas that v apppears in (an umbrella being the set of faces incident to all the halfedges reachable by walking around v using hnext = prev(opposite(h, pm), pm), starting from h).

Template Parameters
PolygonMesha model of HalfedgeListGraph
OutputIteratora model of OutputIterator holding objects of type boost::graph_traits<PolygonMesh>::halfedge_descriptor
Parameters
pma triangle mesh
outthe output iterator that collects halfedges incident to v
See also
is_non_manifold_vertex()
duplicate_non_manifold_vertices()
Returns
the output iterator.

◆ polygon_mesh_to_polygon_soup()

template<typename PolygonMesh , typename PointRange , typename PolygonRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup ( const PolygonMesh &  mesh,
PointRange &  points,
PolygonRange &  polygons,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/polygon_mesh_to_polygon_soup.h>

Adds the vertices and faces of a mesh into a (possibly non-empty) polygon soup.

Template Parameters
PolygonMesha model of FaceListGraph
PointRangea model of the concepts RandomAccessContainer and BackInsertionSequence whose value type can be constructed from the point type of the polygon mesh
PolygonRangea model of the concepts RandomAccessContainer and BackInsertionSequence whose value type is itself a model of the concepts RandomAccessContainer and BackInsertionSequence whose value type is std::size_t
NamedParametersa sequence of Named Parameters
Parameters
meshthe mesh whose faces are being put in the polygon soup
pointspoints making the polygons of the soup
polygonseach element in the vector describes a polygon using the indices of the points in points
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapa model of ReadablePropertyMap, the property map with the points associated to the vertices of mesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.

Advanced

PolygonRange can also be a model of the concepts RandomAccessContainer and BackInsertionSequence whose value type is an array, but it is the user's responsability to ensure that all faces have the same number of vertices, and that this number is equal to the size of the array.

See also
CGAL::Polygon_mesh_processing::orient_polygon_soup()
CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh()
CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh()

◆ polygon_soup_to_polygon_mesh()

template<typename PolygonMesh , typename PointRange , typename PolygonRange , typename NamedParameters_PS , typename NamedParameters_PM >
void CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh ( const PointRange &  points,
const PolygonRange &  polygons,
PolygonMesh &  out,
const NamedParameters_PS &  np_ps,
const NamedParameters_PM &  np_pm 
)

#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>

builds a polygon mesh from a soup of polygons.

Precondition
the input polygon soup describes a consistently oriented polygon mesh. This can be checked using the function CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons) .
Template Parameters
PolygonMesha model of MutableFaceGraph
PointRangea model of the concept RandomAccessContainer whose value type is the point type
PolygonRangea model of the concept RandomAccessContainer whose value type is a model of the concept RandomAccessContainer whose value type is std::size_t
NamedParameters_PSa sequence of Named Parameters
NamedParameters_PMa sequence of Named Parameters
Parameters
pointspoints of the soup of polygons
polygonseach element in the vector describes a polygon using the indices of the points in points
outthe polygon mesh to be built
np_psoptional sequence of Named Parameters among the ones listed below
Named Parameters
point_mapa model of ReadablePropertyMap whose value type is a point type convertible to the point type of the vertex point map associated to the polygon mesh. If this parameter is omitted, CGAL::Identity_property_map is used.
Parameters
np_pmoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapa model of WritablePropertyMap, the property map with the points associated to the vertices of out. If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
See also
CGAL::Polygon_mesh_processing::orient_polygon_soup()
CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh()
CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup()
Examples:
Polygon_mesh_processing/orient_polygon_soup_example.cpp, Polygon_mesh_processing/orientation_pipeline_example.cpp, and Polygon_mesh_processing/repair_polygon_soup_example.cpp.

◆ remove_connected_components_of_negligible_size()

template<typename TriangleMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size ( TriangleMesh &  tmesh,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/repair.h>

removes connected components whose area or volume is under a certain threshold value.

Thresholds are provided via Named Parameters. (see below). If thresholds are not provided by the user, default values are computed as follows:

  • the area threshold is taken as the square of one percent of the length of the diagonal of the bounding box of the mesh.
  • the volume threshold is taken as the third power of one percent of the length of the diagonal of the bounding box of the mesh.

The area and volume of a connected component will always be positive values (regardless of the orientation of the mesh).

As a consequence of the last sentence, the area or volume criteria can be disabled by passing zero (0) as threshold value.

Template Parameters
TriangleMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
tmeshthe triangulated polygon mesh
npoptional Named Parameters, amongst those described below
Named Parameters
area_thresholda fixed value such that only connected components whose area is larger than this value are kept
volume_thresholda fixed value such that only connected components whose volume is larger than this value are kept (only applies to closed connected components)
edge_is_constrained_mapa property map containing the constrained-or-not status of each edge of pmesh
face_index_mapa property map containing the index of each face of tmesh
vertex_point_mapthe property map with the points associated to the vertices of tmesh.
geom_traitsan instance of a geometric traits class, model of Kernel
dry_runa Boolean parameter. If set to true, the mesh will not be altered, but the number of components that would be removed is returned. The default value is false.
output_iteratora model of OutputIterator with value type face_descriptor. When using the "dry run" mode (see parameter dry_run), faces that would be removed by the algorithm can be collected with this output iterator.
Returns
the number of connected components removed (ignoring isolated vertices).

◆ remove_isolated_points_in_polygon_soup()

template<typename PointRange , typename PolygonRange >
std::size_t CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup ( PointRange &  points,
PolygonRange &  polygons 
)

#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>

Removes the isolated points from a polygon soup.

A point is considered isolated if it does not appear in any polygon of the soup.

Template Parameters
PointRangea model of the concept SequenceContainer whose value type is the point type.
PolygonRangea model of the concept RandomAccessContainer whose value_type is itself a model of the concept RandomAccessContainer whose value_type is std::size_t.
Parameters
pointspoints of the soup of polygons.
polygonsa vector of polygons. Each element in the vector describes a polygon using the indices of the points in points.
Returns
the number of removed isolated points

◆ remove_isolated_vertices()

template<class PolygonMesh >
std::size_t CGAL::Polygon_mesh_processing::remove_isolated_vertices ( PolygonMesh &  pmesh)

#include <CGAL/Polygon_mesh_processing/repair.h>

removes the isolated vertices from any polygon mesh.

A vertex is considered isolated if it is not incident to any simplex of higher dimension.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
Parameters
pmeshthe polygon mesh to be repaired
Returns
number of removed isolated vertices

◆ repair_polygon_soup()

template<typename PointRange , typename PolygonRange , typename NamedParameters >
void CGAL::Polygon_mesh_processing::repair_polygon_soup ( PointRange &  points,
PolygonRange &  polygons,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>

Cleans a given polygon soup through various repairing operations.

More precisely, this function carries out the following tasks, in the same order as they are listed:

Note that the point and polygon containers will be modified by the repairing operations, and thus the indexation of the polygons will also be changed.

Template Parameters
PointRangea model of the concepts SequenceContainer and Swappable and whose value type is the point type.
PolygonRangea model of the concept SequenceContainer. whose value_type is itself a model of the concepts SequenceContainer, Swappable, and ReversibleContainer whose value_type is std::size_t.
NamedParametersa sequence of Named Parameters
Parameters
pointspoints of the soup of polygons.
polygonsa vector of polygons. Each element in the vector describes a polygon using the indices of the points in points.
npoptional Named Parameters, amongst those described below
Named Parameters
geom_traits

a geometric traits class instance. The traits class must provide the nested functors :

  • Less_xyz_3 to compare lexicographically two points
  • Equal_3 to check whether 2 points are identical

and, for each functor Foo, a function Foo foo_object().

erase_all_duplicatesParameter forwarded to the function merge_duplicate_polygons_in_polygon_soup() to indicate, when multiple polygons are duplicates, whether all the duplicate polygons should be removed or if one (arbitrarily chosen) face should be kept. Default is false.
require_same_orientationParameter forwarded to the function merge_duplicate_polygons_in_polygon_soup() to indicate if polygon orientation should be taken into account when determining whether two polygons are duplicates, that is, whether e.g. the triangles 0,1,2 and 0,2,1 are duplicates. Default is false.
Examples:
Polygon_mesh_processing/repair_polygon_soup_example.cpp.

◆ stitch_borders() [1/2]

template<typename PolygonMesh , typename HalfedgePairsRange >
std::size_t CGAL::Polygon_mesh_processing::stitch_borders ( PolygonMesh &  pmesh,
const HalfedgePairsRange &  hedge_pairs_to_stitch 
)

#include <CGAL/Polygon_mesh_processing/stitch_borders.h>

Stitches together border halfedges in a polygon mesh.

The halfedges to be stitched are provided in hedge_pairs_to_stitch. For each pair p in this vector, p.second and its opposite will be removed from pmesh.

Template Parameters
PolygonMesha model of MutableFaceGraph
HalfedgePairsRangea range of std::pair<boost::graph_traits<PolygonMesh>::halfedge_descriptor, boost::graph_traits<PolygonMesh>::halfedge_descriptor>, model of Range. Its iterator type is InputIterator.
Parameters
pmeshthe polygon mesh to be modified by stitching
hedge_pairs_to_stitcha range of std::pair of halfedges to be stitched together
Returns
the number of pairs of halfedges that were stitched.
Examples:
Polygon_mesh_processing/stitch_borders_example.cpp.

◆ stitch_borders() [2/2]

template<typename PolygonMesh , class NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_borders ( PolygonMesh &  pmesh,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/stitch_borders.h>

Same as the other overload but the pairs of halfedges to be stitched are automatically found amongst all border halfedges.

Two border halfedges h1 and h2 are set to be stitched if the points associated to the source and target vertices of h1 are the same as those of the target and source vertices of h2 respectively.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmeshthe polygon mesh to be modified by stitching
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
apply_per_connected_componentspecifies if the borders should only be stitched inside their own connected component. Default value is false.
face_index_mapa property map containing for each face of pmesh a unique index between 0 and num_faces(pmesh)-1
Returns
the number of pairs of halfedges that were stitched.
See also
stitch_boundary_cycle()
stitch_boundary_cycles()

◆ stitch_boundary_cycle()

template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_boundary_cycle ( const typename boost::graph_traits< PolygonMesh >::halfedge_descriptor  h,
PolygonMesh &  pm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/stitch_borders.h>

Stitches together, whenever possible, two halfedges belonging to the boundary cycle described by the halfedge h.

Two border halfedges h1 and h2 can be stitched if the points associated to the source and target vertices of h1 are the same as those of the target and source vertices of h2 respectively.

Template Parameters
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
ha border halfedge of the polygon mesh pm
pmthe polygon mesh to be stitched
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
Returns
the number of pairs of halfedges that were stitched.
See also
stitch_boundary_cycles()
stitch_borders()

◆ stitch_boundary_cycles()

template<typename PolygonMesh , typename NamedParameters >
std::size_t CGAL::Polygon_mesh_processing::stitch_boundary_cycles ( PolygonMesh &  pm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/stitch_borders.h>

Stitches together, whenever possible, two halfedges belonging to the same boundary cycle.

Two border halfedges h1 and h2 can be stitched if the points associated to the source and target vertices of h1 are the same as those of the target and source vertices of h2 respectively.

Template Parameters
PolygonMesha model of MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
pmthe polygon mesh to be stitched
npoptional sequence of Named Parameters among the ones listed below
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of pmesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in PolygonMesh.
Returns
the number of pairs of halfedges that were stitched.
See also
stitch_boundary_cycle()
stitch_borders()