CGAL 5.5 - Polygon Mesh Processing

Functions to compute or change the orientation of faces and surfaces.

Classes

struct  CGAL::Polygon_mesh_processing::Default_orientation_visitor
 Default visitor model of PMPPolygonSoupOrientationVisitor. More...
 

Enumerations

enum  CGAL::Polygon_mesh_processing::Volume_error_code { CGAL::Polygon_mesh_processing::VALID_VOLUME, CGAL::Polygon_mesh_processing::SURFACE_WITH_SELF_INTERSECTIONS, CGAL::Polygon_mesh_processing::VOLUME_INTERSECTION, CGAL::Polygon_mesh_processing::INCOMPATIBLE_ORIENTATION }
 Enumeration type used to indicate the status of a set of faces classified by the function volume_connected_components(). More...
 

Functions

template<class PointRange , class PolygonRange , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::orient_polygon_soup (PointRange &points, PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
 tries to consistently orient a soup of polygons in 3D space. More...
 
template<class PointRange , class PolygonRange >
bool CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup (PointRange &points, PolygonRange &polygons)
 duplicates each point p at which the intersection of an infinitesimally small ball centered at p with the polygons incident to it is not a topological disk. More...
 
template<class Concurrency_tag = CGAL::Sequential_tag, class ReferencePointRange , class ReferenceFaceRange , class PointRange , class FaceRange , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_soup (const ReferencePointRange &ref_points, const ReferenceFaceRange &ref_faces, const PointRange &points, FaceRange &faces, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
 orients each triangle of a triangle soup using the orientation of its closest non degenerate triangle in a triangle soup. More...
 
template<class Concurrency_tag = Sequential_tag, class PointRange , class TriangleRange , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh (const TriangleMesh &tm_ref, const PointRange &points, TriangleRange &triangles, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
 orients each triangle of a triangle soup using the orientation of its closest non degenerate triangle in tm_ref. More...
 
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::is_outward_oriented (const TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
 tests whether a closed triangle mesh has a positive orientation. More...
 
template<typename PolygonMesh >
void CGAL::Polygon_mesh_processing::reverse_face_orientations (PolygonMesh &pmesh)
 reverses for each face the order of the vertices along the face boundary. More...
 
template<typename PolygonMesh , typename FaceRange >
void CGAL::Polygon_mesh_processing::reverse_face_orientations (const FaceRange &face_range, PolygonMesh &pmesh)
 reverses for each face in face_range the order of the vertices along the face boundary. More...
 
template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient (TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
 makes each closed connected component of a triangulated surface mesh inward or outward oriented. More...
 
template<class TriangleMesh , class VolumeFaceIndexMap , class NamedParameters = parameters::Default_named_parameters>
std::size_t CGAL::Polygon_mesh_processing::volume_connected_components (const TriangleMesh &tm, VolumeFaceIndexMap volume_id_map, const NamedParameters &np=parameters::default_values())
 assigns to each face of tm an id corresponding to the volume connected component it contributes to. More...
 
template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::does_bound_a_volume (const TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
 indicates if tm bounds a volume. More...
 
template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_to_bound_a_volume (TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
 orients the connected components of tm to make it bound a volume. More...
 
template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::merge_reversible_connected_components (PolygonMesh &pm, const NamedParameters &np=parameters::default_values())
 reverses the connected components of tm having compatible boundary cycles that could be merged if their orientation were made compatible, and stitches them. More...
 
template<class PolygonMesh , class FaceBitMap , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::compatible_orientations (const PolygonMesh &pm, FaceBitMap fbm, const NamedParameters &np=parameters::default_values())
 identifies faces whose orientation must be reversed in order to enable stitching of connected components. More...
 

Enumeration Type Documentation

◆ Volume_error_code

#include <CGAL/Polygon_mesh_processing/orientation.h>

Enumeration type used to indicate the status of a set of faces classified by the function volume_connected_components().

The set of faces defines either a volume connected connected component in the case of VALID_VOLUME or a surface connected component otherwise.

Enumerator
VALID_VOLUME 

The set of faces bounds a volume.

SURFACE_WITH_SELF_INTERSECTIONS 

The set of faces is self-intersecting.

VOLUME_INTERSECTION 

The set of faces intersects another surface connected component.

INCOMPATIBLE_ORIENTATION 

The set of faces is included in a volume but has an incompatible orientation.

Function Documentation

◆ compatible_orientations()

template<class PolygonMesh , class FaceBitMap , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::compatible_orientations ( const PolygonMesh &  pm,
FaceBitMap  fbm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

identifies faces whose orientation must be reversed in order to enable stitching of connected components.

Each face is assigned a bit (false or true) such that two faces have compatible orientations iff they are assigned the same bits.

Template Parameters
PolygonMesha model of HalfedgeListGraph, FaceGraph.
FaceBitMapa model of WritablePropertyMap with face_descriptor as key and bool as value_type
NamedParametersa sequence of Named Parameters
Parameters
pma surface mesh
fbmface bit map indicating if a face orientation should be reversed to be stitchable (see CGAL::Polygon_mesh_processing::stitch_borders()) with another face. If false is returned, the map will not be filled.
npan optional sequence of Named Parameters among the ones listed below
Returns
true if pm can be reoriented and false otherwise.
Optional Named Parameters
  • a property map associating points to the vertices of pm
  • 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, pm)
  • Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pm.
See also
reverse_face_orientations()
stitch_borders()
Examples:
Polygon_mesh_processing/cc_compatible_orientations.cpp.

◆ does_bound_a_volume()

template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::does_bound_a_volume ( const TriangleMesh &  tm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

indicates if tm bounds a volume.

See Definitions for details.

Template Parameters
TriangleMesha model of HalfedgeListGraph, FaceListGraph, and MutableFaceGraph.
NamedParametersa sequence of Named Parameters
Parameters
tma closed triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below
Precondition
CGAL::is_closed(tm)
Attention
if tm is self-intersecting the behavior of this function is undefined.
Optional Named Parameters
  • a property map associating points to the vertices of tm
  • 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, tm)

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

  • For each connected component identified using its id ccid, the output of is_outward_oriented() called on the triangle mesh corresponding to this connected component is the value at the position ccid in the container. The size of the container is exactly the number of connected components.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to a container that must be a model of the BackInsertionSequence concept, with value type bool
  • Default: unused
See also
CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()

◆ duplicate_non_manifold_edges_in_polygon_soup()

template<class PointRange , class PolygonRange >
bool CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup ( PointRange &  points,
PolygonRange &  polygons 
)

#include <CGAL/Polygon_mesh_processing/orient_polygon_soup_extension.h>

duplicates each point p at which the intersection of an infinitesimally small ball centered at p with the polygons incident to it is not a topological disk.

Template Parameters
PointRangea model of the concepts RandomAccessContainer and BackInsertionSequence 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, and is also a model of BackInsertionSequence
Parameters
pointspoints of the soup of polygons. Some additional points might be pushed back to resolve non-manifoldness or non-orientability issues.
polygonseach element in the vector describes a polygon using the indices of the points in points. If needed the order of the indices of a polygon might be reversed.
Returns
false if some points were duplicated, thus producing a self-intersecting surface mesh.
true otherwise.
See also
orient_polygon_soup()
duplicate_non_manifold_vertices()
Examples:
Polygon_mesh_processing/orientation_pipeline_example.cpp.

◆ is_outward_oriented()

template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::is_outward_oriented ( const TriangleMesh &  tm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

tests whether a closed triangle mesh has a positive orientation.

A closed triangle mesh is considered to have a positive orientation if the normal vectors to all its faces point outside the domain bounded by the triangle mesh. The normal vector to each face is chosen pointing on the side of the face where its sequence of vertices is seen counterclockwise.

Precondition
CGAL::is_closed(tm)
CGAL::is_triangle_mesh(tm)
If tm contains several connected components, they are oriented consistently. In other words, the answer to this predicate would be the same for each isolated connected component.
Template Parameters
TriangleMesha model of FaceListGraph
NamedParametersa sequence of Named Parameters
Parameters
tmthe closed triangle mesh free from self-intersections to be tested
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the vertices of tm
  • 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, tm)

  • 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.
Note
This function is only doing an orientation test for one connected component of tm. For performance reasons, it is left to the user to call the function does_bound_a_volume() on a triangulated version of tm to ensure the result returned is relevant. For advanced usages, the function volume_connected_components() should be used instead.
See also
CGAL::Polygon_mesh_processing::reverse_face_orientations()

◆ merge_reversible_connected_components()

template<class PolygonMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::merge_reversible_connected_components ( PolygonMesh &  pm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

reverses the connected components of tm having compatible boundary cycles that could be merged if their orientation were made compatible, and stitches them.

Connected components are examined by increasing number of faces.

Template Parameters
PolygonMesha model of HalfedgeListGraph, FaceListGraph, and MutableFaceGraph.
NamedParametersa sequence of Named Parameters
Parameters
pma surface mesh
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the vertices of pm
  • 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, pm)
  • Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of pm.

  • a property map associating to each face of pm a unique index between 0 and num_faces(pm) - 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

  • If not 0, a connected component is considered reversible only if it has no more faces than the value given. Otherwise, it is always considered reversible.
  • Type: std::size_t
  • Default: 0
Examples:
Polygon_mesh_processing/orientation_pipeline_example.cpp.

◆ orient()

template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient ( TriangleMesh &  tm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

makes each closed connected component of a triangulated surface mesh inward or outward oriented.

If a connected component is not closed, the orientation may or may not be changed or not is not guaranteed.

Template Parameters
TriangleMesha model of FaceListGraph and MutableFaceGraph
NamedParametersa sequence of Named Parameters
Parameters
tma closed triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below
Precondition
CGAL::is_closed(tm)
Optional Named Parameters
  • a property map associating points to the vertices of tm
  • 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, tm)

  • an instance of a geometric traits class
  • Type: a class model of Kernel
  • Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits
  • Extra: The geometric traits class must be compatible with the vertex point type.

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

  • If true, each connected component will be outward oriented (and inward oriented if false).
  • Type: Boolean
  • Default: true

◆ orient_polygon_soup()

template<class PointRange , class PolygonRange , class NamedParameters = parameters::Default_named_parameters>
bool CGAL::Polygon_mesh_processing::orient_polygon_soup ( PointRange &  points,
PolygonRange &  polygons,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orient_polygon_soup.h>

tries to consistently orient a soup of polygons in 3D space.

When it is not possible to produce a combinatorial manifold surface, some points are duplicated. Because a polygon soup does not have any connectivity (each point has as many occurrences as the number of polygons it belongs to), duplicating one point (or a pair of points) amounts to duplicate the polygon to which it belongs.

These points are either an endpoint of an edge incident to more than two polygons, an endpoint of an edge between two polygons with incompatible orientations (during the re-orientation process), or more generally a point p at which the intersection of an infinitesimally small ball centered at p with the polygons incident to it is not a topological disk.

The algorithm is described in [1].

Template Parameters
PointRangea model of the concepts RandomAccessContainer and BackInsertionSequence 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.
NamedParametersa sequence of named parameters
Parameters
pointspoints of the soup of polygons. Some additional points might be pushed back to resolve non-manifoldness or non-orientability issues.
polygonseach element in the vector describes a polygon using the index of the points in points. If needed the order of the indices of a polygon might be reversed.
npoptional sequence of named parameters among the ones listed below
Optional Named Parameters
Returns
true if the orientation operation succeded.
false if some points were duplicated, thus producing a self-intersecting polyhedron.
See also
orient_triangle_soup_with_reference_triangle_mesh()
Examples:
Polygon_mesh_processing/orient_polygon_soup_example.cpp, and Polygon_mesh_processing/repair_polygon_soup_example.cpp.

◆ orient_to_bound_a_volume()

template<class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_to_bound_a_volume ( TriangleMesh &  tm,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

orients the connected components of tm to make it bound a volume.

See Definitions for a precise definition.

Template Parameters
TriangleMesha model of HalfedgeListGraph, FaceListGraph, and MutableFaceGraph.
NamedParametersa sequence of Named Parameters
Parameters
tma closed triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below
Precondition
CGAL::is_closed(tm)
Optional Named Parameters
  • If true, each connected component will be outward oriented (and inward oriented if false).
  • Type: Boolean
  • Default: true
  • Extra: If the outer connected components are inward oriented, it means that the infinity will be considered as part of the volume bounded by tm.

  • a property map associating points to the vertices of tm
  • 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, tm)

  • an instance of a geometric traits class
  • Type: a class model of Kernel
  • Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits
  • Extra: The geometric traits class must be compatible with the vertex point type.

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

See also
CGAL::Polygon_mesh_processing::does_bound_a_volume()
Examples:
Polygon_mesh_processing/orient_polygon_soup_example.cpp.

◆ orient_triangle_soup_with_reference_triangle_mesh()

template<class Concurrency_tag = Sequential_tag, class PointRange , class TriangleRange , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh ( const TriangleMesh &  tm_ref,
const PointRange &  points,
TriangleRange &  triangles,
const NamedParameters1 &  np1 = parameters::default_values(),
const NamedParameters2 &  np2 = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orient_polygon_soup_extension.h>

orients each triangle of a triangle soup using the orientation of its closest non degenerate triangle in tm_ref.

Template Parameters
Concurrency_tagenables sequential versus parallel orientation. Possible values are Sequential_tag (the default), Parallel_if_available_tag, and Parallel_tag.
PointRangea model of the concept RandomAccessContainer whose value type is the point type
TriangleRangea model of the concept RandomAccessContainer whose value_type is a model of the concept RandomAccessContainer whose value_type is std::size_tand of size 3
TriangleMesha model of FaceListGraph
Parameters
tm_refthe reference triangle_mesh
pointsthe points of the soup
trianglesthe triangles of the soup
np1an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the vertices of tm_ref
  • 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, tm_ref)

Parameters
np2an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the elements of the point set points
  • Type: a model of ReadablePropertyMap whose key type is the value type of the iterator of PointRange and whose value type is geom_traits::Point_3
  • Default: CGAL::Identity_property_map<geom_traits::Point_3>
Attention
The types of points in PointRange, geom_traits, and vertex_point_map must be the same.
See also
orient_polygon_soup()

◆ orient_triangle_soup_with_reference_triangle_soup()

template<class Concurrency_tag = CGAL::Sequential_tag, class ReferencePointRange , class ReferenceFaceRange , class PointRange , class FaceRange , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
void CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_soup ( const ReferencePointRange &  ref_points,
const ReferenceFaceRange &  ref_faces,
const PointRange &  points,
FaceRange &  faces,
const NamedParameters1 &  np1 = parameters::default_values(),
const NamedParameters2 &  np2 = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orient_polygon_soup_extension.h>

orients each triangle of a triangle soup using the orientation of its closest non degenerate triangle in a triangle soup.

Template Parameters
Concurrency_tagenables sequential versus parallel orientation. Possible values are Sequential_tag (the default), Parallel_if_available_tag, and Parallel_tag.
ReferencePointRangea model of the concept RandomAccessContainer whose value_type is the point type
ReferenceTriangleRangea model of the concept RandomAccessContainer whose value_type is a model of the concept RandomAccessContainer whose value_type is std::size_t and is of size 3
PointRangea model of the concept RandomAccessContainer whose value_type is the point type
TriangleRangea model of the concept RandomAccessContainer whose value_type is a model of the concept RandomAccessContainer whose value_type is std::size_tand is of size 3.
NamedParameters1a sequence of Named Parameters
NamedParameters2a sequence of Named Parameters
Parameters
ref_pointsthe points of the reference soup
ref_facestriples of indices of points in ref_points defining the triangles of the reference soup
pointsthe points of the soup to be oriented
facestriples of indices of points in points defining the triangles of the soup
np1an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the elements of the point set ref_points
  • Type: a model of ReadablePropertyMap whose key type is the value type of the iterator of ReferencePointRange and whose value type is geom_traits::Point_3
  • Default: CGAL::Identity_property_map<geom_traits::Point_3>

Parameters
np2an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating points to the elements of the point set points
  • Type: a model of ReadablePropertyMap whose key type is the value type of the iterator of PointRange and whose value type is geom_traits::Point_3
  • Default: CGAL::Identity_property_map<geom_traits::Point_3>
Attention
The types of points in ReferencePointRange, PointRange, and geom_traits must be the same.

◆ reverse_face_orientations() [1/2]

template<typename PolygonMesh >
void CGAL::Polygon_mesh_processing::reverse_face_orientations ( PolygonMesh &  pmesh)

#include <CGAL/Polygon_mesh_processing/orientation.h>

reverses for each face the order of the vertices along the face boundary.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
See also
is_outward_oriented()
Examples:
Polygon_mesh_processing/cc_compatible_orientations.cpp, and Polygon_mesh_processing/orient_polygon_soup_example.cpp.

◆ reverse_face_orientations() [2/2]

template<typename PolygonMesh , typename FaceRange >
void CGAL::Polygon_mesh_processing::reverse_face_orientations ( const FaceRange &  face_range,
PolygonMesh &  pmesh 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

reverses for each face in face_range the order of the vertices along the face boundary.

The function does not perform any control and if the change of orientation of the faces makes the polygon mesh invalid, the behavior is undefined.

Template Parameters
PolygonMesha model of FaceListGraph and MutableFaceGraph
FaceRangerange of face descriptors, model of Range. Its iterator type is InputIterator.
See also
is_outward_oriented()

◆ volume_connected_components()

template<class TriangleMesh , class VolumeFaceIndexMap , class NamedParameters = parameters::Default_named_parameters>
std::size_t CGAL::Polygon_mesh_processing::volume_connected_components ( const TriangleMesh &  tm,
VolumeFaceIndexMap  volume_id_map,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/Polygon_mesh_processing/orientation.h>

assigns to each face of tm an id corresponding to the volume connected component it contributes to.

Using the adjacency relation of two faces along an edge, a triangle mesh can be split into connected components (surface components in the following). A surface component without boundary separates the 3D space into an infinite and a finite volume. We say that the finite volume is enclosed by this surface component.

The volume connected components (volume components in the following) are defined as follows: Each surface component S that is outside any volume enclosed by another surface component defines the outer boundary of a volume component. Each surface component that is inside the volume enclosed by S defines a hole if it is included in no other volume enclosed by a surface component but S. Ignoring the identified volume component, the same procedure is recursively repeated for all surface components in each hole.

There are some special cases:

  • a non-closed surface component is reported as a volume component ignoring any inclusion test
  • a self-intersecting surface component is reported as a volume component ignoring any inclusion test
  • a surface component intersecting another surface component is reported as a volume component, and so are all the surface components inside its enclosed volume
  • if do_orientation_tests is set to true, if the holes are not all equally oriented (all inward or all outward) or if the holes and the outer boundary are equally oriented, each surface component is reported as a volume component, and so are all the surface components inside the corresponding enclosed volumes
  • If do_orientation_tests is set to true and the surface components that are outside all enclosed volumes are inward oriented, they are then considered as holes of the unbounded volume (that has no outer boundary)

A property map for CGAL::vertex_point_t must be either available as an internal property map of tm or provided as one of the Named Parameters.

Template Parameters
TriangleMesha model of FaceListGraph
VolumeFaceIndexMapa model of WritablePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and boost::graph_traits<TriangleMesh>::faces_size_type as value type.
NamedParametersa sequence of Named Parameters
Parameters
tmthe input triangle mesh
volume_id_mapthe property map filled by this function with indices of volume components associated to the faces of tm
npan optional sequence of Named Parameters among the ones listed below
Precondition
CGAL::is_closed(tm)
Optional Named Parameters
  • a property map associating points to the vertices of tm
  • 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, tm)

  • an instance of a geometric traits class
  • Type: a class model of Kernel
  • Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits
  • Extra: The geometric traits class must be compatible with the vertex point type.

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

  • a property map filled by this function and that will contain for each face the id of its surface component in the range [0, number of surface components - 1]
  • Type: a class model of WritablePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and std::size_t as value type
  • Default: an automatically indexed internal map

  • a container, which contains at position k the ids of all the surface components that are the first intersected by any ray with source on the surface component k and directed outside the volume enclosed by the surface component k. There is only one such id but when some surface components intersect. The size of the container is exactly the number of surface components of tm.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to an object that must be a model of the BackInsertionSequence concept, with a value type being a model of BackInsertionSequence of std::size_t, both types having the functions reserve() and push_back()
  • Default: unused

  • If true, the orientation of the faces of each surface components will be taken into account for the definition of the volume. If false, the face orientation is ignored and the volumes are defined only by the nesting of surface components.
  • Type: Boolean
  • Default: true

  • a container which indicates the status of a volume assigned to a set of faces. The description of the value type is given in the documentation of the enumeration type. The size of the container is exactly the number of volume components.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to a container that must be a model of the BackInsertionSequence concept, with value type Volume_error_code
  • Default: unused

  • If false, it is assumed that tm does not contains any self-intersections. If true, the input might contain some self-intersections and a test is done prior to the volume decomposition.
  • Type: Boolean
  • Default: false

  • For each connected component identified using its id ccid, the id of the volume it contributes to describe is the value at the position ccid in the container. The size of the container is exactly the number of connected components.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to a container that must be a model of the BackInsertionSequence concept, with value type std::size_t
  • Default: unused

  • For each connected component identified using its id ccid, the container contains the number of connected components containing on its bounded side this component. The size of the container is exactly the number of connected components.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to a container that must be a model of the BackInsertionSequence concept, with value type std::size_t
  • Default: unused

  • For each connected component identified using its id ccid, the output of is_outward_oriented() called on the triangle mesh corresponding to this connected component is the value at the position ccid in the container. The size of the container is exactly the number of connected components.
  • Type: a reference_wrapper (either from boost or the standard library) containing a reference to a container that must be a model of the BackInsertionSequence concept, with value type bool
  • Default: unused

  • Output iterator into which pairs of ids (id must be convertible to std::size_t) can be put. Each pair of connected components intersecting will be reported using their ids. If do_self_intersection_tests named parameter is set to false, nothing will be reported.
  • Type: a model of OutputIterator
  • Default: unused
Returns
the number of volume components defined by tm
Examples:
Polygon_mesh_processing/volume_connected_components.cpp.