Geometric Repair

Functions to repair polygon soups and polygon meshes.

Functions
template<class PolygonMesh >
std::size_t	CGAL::Polygon_mesh_processing::remove_isolated_vertices (PolygonMesh &pmesh)
	removes the isolated vertices from any polygon mesh.
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
std::size_t	CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size (TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
	removes connected components whose area or volume is under a certain threshold value.
template<typename FaceRange , typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
bool	CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces (const FaceRange &face_range, TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
	removes almost degenerate faces in a range of faces from a triangulated surface mesh.
template<typename TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
bool	CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces (TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
	removes all almost degenerate faces from a triangulated surface mesh.

Function Documentation

remove_almost_degenerate_faces() [1/2]

template<typename FaceRange , typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces	(	const FaceRange &	face_range,
		TriangleMesh &	tmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/repair_degeneracies.h>

removes almost degenerate faces in a range of faces from a triangulated surface mesh.

Almost degenerated triangle faces are classified as caps or needles: a triangle is said to be a needle if its longest edge is much longer than its shortest edge. A triangle is said to be a cap if one of its angles is close to 180 degrees. Needles are removed by collapsing their shortest edges, while caps are removed by flipping the edge opposite to the largest angle (with the exception of caps on the boundary that are simply removed from the mesh).

Precondition

CGAL::is_triangle_mesh(tmesh)

Template Parameters

TriangleMesh	a model of FaceListGraph and MutableFaceGraph
FaceRange	a model of ConstRange with boost::graph_traits<TriangleMesh>::face_descriptor as value type
NamedParameters	a sequence of Named Parameters

Parameters

face_range	the initial range of faces to be considered to look for badly shaped triangles. Note that modifications of tmesh are not limited to faces in face_range and neighbor faces might also be impacted.
tmesh	the triangulated surface mesh to be modified
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

cap_threshold the cosine of a minimum angle such that if a face 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. Type: double Default: the cosinus corresponding to an angle of 160 degrees
needle_threshold a bound on the ratio of the lengths of the longest edge and the shortest edge, such that a face having a ratio larger than the threshold is a needle. Type: double Default: 4
collapse_length_threshold if different from 0, an edge collapsed will be prevented if the edge is longer than the threshold given. Type: double Default: 0
flip_triangle_height_threshold if different from 0, an edge flip will be prevented if the height of the triangle (whose base is the edge to be flipped) is longer than the threshold given. Type: double Default: 0
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 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_is_constrained_map a property map containing the constrained-or-not status of each edge of tmesh. Type: a class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::edge_descriptor as key type and bool as value type. Default: a default property map where no edge is constrained. Extra: A constrained edge can not be collapsed nor flipped.
vertex_is_constrained_map a property map containing the constrained-or-not status of each vertex of tmesh. Type: a class model of ReadablePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and bool as value type. Default: a default property map where no vertex is constrained. Extra: A constrained vertex is guaranteed to be present in tmesh after the function call.
filter A function object providing bool operator()(geom_traits::Point_3,geom_traits::Point_3,geom_traits::Point_3). Type: The function object is queried each time a new triangle is about to be created by a flip or a collapse operation. If false is returned, the operation is canceled. Default: a functor always returning true.

Returns

true if no almost degenerate face could not be removed (due to topological constraints), and false otherwise.

See also

is_needle_triangle_face()

is_cap_triangle_face()

Todo:

check what to use as priority queue with removable elements, set might not be optimal

remove_almost_degenerate_faces() [2/2]

template<typename TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces	(	TriangleMesh &	tmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/repair_degeneracies.h>

removes all almost degenerate faces from a triangulated surface mesh.

Equivalent to remove_almost_degenerate_faces(faces(tmesh), tmesh, np)

remove_connected_components_of_negligible_size()

template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>

std::size_t CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size	(	TriangleMesh &	tmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#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

TriangleMesh	a model of FaceListGraph and MutableFaceGraph
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	the triangulated 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 tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and 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 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. Extra: Exact constructions kernels are not supported by this function.
face_index_map a property map associating to each face of tmesh a unique index between 0 and num_faces(tmesh) - 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
area_threshold a fixed value such that only connected components whose area is larger than this value are kept Type: geom_traits::FT Default: 1% of the length of the diagonal of the axis-aligned bounding box of the mesh, squared
volume_threshold a fixed value such that only connected components whose volume is larger than this value are kept (only applies to closed connected components) Type: geom_traits::FT Default: 1% of the length of the diagonal of the axis-aligned bounding box of the mesh, cubed Extra: The mesh must be closed.
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of tmesh Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::edge_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no edge is constrained Extra: A constrained edge can be split or collapsed, but not flipped, nor its endpoints moved by smoothing.
dry_run If true, the mesh will not be altered, but the number of components that would be removed is returned. Type: Boolean Default: false
output_iterator An output iterator to collect the faces that would be removed by the algorithm, when using the "dry run" mode (see parameter dry_run) Type: a model of OutputIterator with value type face_descriptor Default: unused

Returns

the number of connected components removed (ignoring isolated vertices).

See also

keep_connected_components()

remove_connected_components()

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 a simplex of higher dimension.

Template Parameters

PolygonMesh

a model of FaceListGraph and MutableFaceGraph

Parameters

pmesh

the polygon mesh to be repaired

Returns

the number of removed isolated vertices