Local Remeshing Algorithms

Functions to iteratively remesh a polygon mesh using local operations.

Classes
class	CGAL::Polygon_mesh_processing::Adaptive_sizing_field< class PolygonMesh, class VPMap >
	A sizing field describing variable target mesh edge lengths for CGAL::Polygon_mesh_processing::isotropic_remeshing().
class	CGAL::Polygon_mesh_processing::Uniform_sizing_field< class PolygonMesh, class VPMap >
	A sizing field describing a uniform target edge length for CGAL::Polygon_mesh_processing::isotropic_remeshing().

Functions
template<typename PolygonMesh , typename FaceRange , typename SizingFunction , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::isotropic_remeshing (const FaceRange &faces, SizingFunction &sizing, PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	remeshes a triangulated region of a polygon mesh.
template<typename PolygonMesh , typename EdgeRange , typename SizingFunction , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::split_long_edges (const EdgeRange &edges, SizingFunction &sizing, PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
	splits the edges listed in edges into sub-edges that are not longer than the given threshold max_length.
template<typename VertexRange , typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::random_perturbation (VertexRange vertices, TriangleMesh &tmesh, const double &perturbation_max_size, const NamedParameters &np=parameters::default_values())
	randomly perturbs the locations of non-border vertices of a triangulated surface mesh.
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::random_perturbation (TriangleMesh &tmesh, const double &perturbation_max_size, const NamedParameters &np=parameters::default_values())
	randomly perturbs the locations of all non-border vertices of a triangulated surface mesh.
template<typename TriangleMesh , typename FaceRange , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::angle_and_area_smoothing (const FaceRange &faces, TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
	smooths a region of a triangle mesh.
template<typename TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::angle_and_area_smoothing (TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
	smooths a triangle mesh.
template<typename TriangleMesh , typename FaceRange , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::smooth_shape (const FaceRange &faces, TriangleMesh &tmesh, const double time, const NamedParameters &np=parameters::default_values())
	smooths the overall shape of the mesh by using the mean curvature flow.
template<typename VertexRange , class TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::tangential_relaxation (const VertexRange &vertices, TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
	applies an iterative area-based tangential smoothing to the given range of vertices.
template<class TriangleMesh , typename NamedParameters = CGAL::parameters::Default_named_parameters>
void	CGAL::Polygon_mesh_processing::tangential_relaxation (TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
	applies tangential_relaxation() to all the vertices of tm.
template<typename TriangleMesh , typename FaceRange , typename FaceOutputIterator , typename VertexOutputIterator , typename NamedParameters = parameters::Default_named_parameters>
std::pair< FaceOutputIterator, VertexOutputIterator >	CGAL::Polygon_mesh_processing::refine (TriangleMesh &tmesh, const FaceRange &faces, FaceOutputIterator faces_out, VertexOutputIterator vertices_out, const NamedParameters &np=parameters::default_values())
	refines a region of a triangle mesh.
template<typename TriangleMesh , typename VertexRange , typename NamedParameters = parameters::Default_named_parameters>
bool	CGAL::Polygon_mesh_processing::fair (TriangleMesh &tmesh, const VertexRange &vertices, const NamedParameters &np=parameters::default_values())
	fairs a region on a triangle mesh.
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.

Function Documentation

angle_and_area_smoothing() [1/2]

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

void CGAL::Polygon_mesh_processing::angle_and_area_smoothing	(	const FaceRange &	faces,
		TriangleMesh &	tmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/angle_and_area_smoothing.h>

smooths a region of a triangle mesh.

This function aims to make the triangle angle and area distributions as uniform as possible by moving (non-constrained) vertices.

Angle-based smoothing does not change the combinatorial information of the mesh. Area-based smoothing might change the combinatorial information, unless specified otherwise. It is also possible to make the smoothing algorithm "safer" by rejecting moves that, when applied, would worsen the quality of the mesh, e.g. that would decrease the value of the smallest angle around a vertex or create self-intersections.

Optionally, the points are reprojected after each iteration.

Template Parameters

TriangleMesh	model of MutableFaceGraph.
FaceRange	range of boost::graph_traits<TriangleMesh>::face_descriptor, model of Range. Its iterator type is ForwardIterator.
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	a triangle mesh smoothed.
faces	the range of triangular faces defining one or several surface patches to be smoothed.
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

number_of_iterations the number of iterations for the sequence of the smoothing iterations performed Type: unsigned int Default: 1
use_angle_smoothing value to indicate whether angle-based smoothing should be used Type: Boolean Default: true
use_area_smoothing value to indicate whether area-based smoothing should be used Type: Boolean Default: true
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.
use_safety_constraints If true, vertex moves that would worsen the mesh are ignored. Type: Boolean Default: false
use_Delaunay_flips If true, area-based smoothing will be completed by a phase of Delaunay-based edge-flips to prevent the creation of elongated triangles. Type: Boolean Default: true
do_project If true, points are projected onto the initial surface after each iteration. Type: Boolean Default: true
vertex_is_constrained_map a property map containing the constrained-or-not status of each vertex of tmesh. Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertex is constrained Extra: A constrained vertex cannot be modified at all during smoothing.
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of tmesh. Type: a class model of ReadWritePropertyMap 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 cannot be modified at all during smoothing.

Warning

The third party library Ceres is required to use area-based smoothing.

Precondition

tmesh does not contain any degenerate faces.

Examples

Polygon_mesh_processing/mesh_smoothing_example.cpp.

angle_and_area_smoothing() [2/2]

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

void CGAL::Polygon_mesh_processing::angle_and_area_smoothing	(	TriangleMesh &	tmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/angle_and_area_smoothing.h>

smooths a triangle mesh.

This function aims to make the triangle angle and area distributions as uniform as possible by moving (non-constrained) vertices.

Angle-based smoothing does not change the combinatorial information of the mesh. Area-based smoothing might change the combinatorial information, unless specified otherwise. It is also possible to make the smoothing algorithm "safer" by rejecting moves that, when applied, would worsen the quality of the mesh, e.g. that would decrease the value of the smallest angle around a vertex or create self-intersections.

Optionally, the points are reprojected after each iteration.

See the overload which takes a face range as additional parameter for a comprehensive description of the parameters.

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 </home/runner/work/cgal/cgal/Polygon_mesh_processing/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. This function requires the Eigen library.

Template Parameters

TriangleMesh	a model of VertexListGraph 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()

Precondition

tmesh is a triangulated surface mesh and has exactly one connected component.

Returns

true if nb_vertices was sufficiently large for remeshing the input, and false if more points were used

Examples

Polygon_mesh_processing/acvd_remeshing_example.cpp.

fair()

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

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

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/fair.h>

fairs a region on a triangle mesh.

The points of the selected vertices are relocated to yield an as-smooth-as-possible surface patch, based on solving a linear bi-Laplacian system with boundary constraints, described in [3]. The optional parameter fairing_continuity gives the ability to control the tangential continuity C ⁿ of the output mesh.

The region described by vertices might contain multiple disconnected components. Note that the mesh connectivity is not altered in any way, only vertex locations get updated.

Fairing might fail if fixed vertices, which are used as boundary conditions, do not suffice to solve constructed linear system.

Note that if the vertex range to which fairing is applied contains all the vertices of the triangle mesh, fairing does not fail, but the mesh gets shrunk to CGAL::ORIGIN.

Template Parameters

TriangleMesh	a model of FaceGraph and MutableFaceGraph
VertexRange	a range of vertex descriptors of TriangleMesh, model of Range. Its iterator type is InputIterator.
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	the triangle mesh with patches to be faired
vertices	the vertices of the patches to be faired (the positions of only those vertices will be changed)
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) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available for the vertices of tmesh.
fairing_continuity A value controlling the tangential continuity of the output surface patch. The possible values are 0, 1 and 2, referring to the C0, C1 and C2 continuity. Type: unsigned int Default: 1 Extra: The larger fairing_continuity gets, the more fixed vertices are required.
sparse_linear_solver an instance of the sparse linear solver used for fairing Type: a class model of SparseLinearAlgebraWithFactorTraits_d Default: If Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then the following overload of Eigen_solver_traits is provided as default value: CGAL::Eigen_solver_traits<Eigen::SparseLU<CGAL::Eigen_sparse_matrix<double>::EigenType, Eigen::COLAMDOrdering<int> > >

Returns

true if fairing is successful, otherwise no vertices are relocated.

Precondition

CGAL::is_triangle_mesh(tmesh)

Warning

This function involves linear algebra, that is computed using non-exact, floating-point arithmetic.

Todo:

accuracy of solvers are not good, for example when there is no boundary condition pre_factor should fail, but it does not.

Examples

Polygon_mesh_processing/refine_fair_example.cpp.

isotropic_remeshing()

template<typename PolygonMesh , typename FaceRange , typename SizingFunction , typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::isotropic_remeshing	(	const FaceRange &	faces,
		SizingFunction &	sizing,
		PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh.h>

remeshes a triangulated region of a polygon mesh.

This operation sequentially performs edge splits, edge collapses, edge flips, tangential relaxation and projection to the initial surface to generate a smooth mesh with a prescribed edge length.

Template Parameters

PolygonMesh	model of MutableFaceGraph. The descriptor types boost::graph_traits<PolygonMesh>::face_descriptor and boost::graph_traits<PolygonMesh>::halfedge_descriptor must be models of Hashable.
FaceRange	range of boost::graph_traits<PolygonMesh>::face_descriptor, model of Range. Its iterator type is ForwardIterator.
SizingFunction	model of PMPSizingField
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh with triangulated surface patches to be remeshed
faces	the range of triangular faces defining one or several surface patches to be remeshed
sizing	field that determines a target length for individual edges. If a number convertible to a double is passed, Uniform_sizing_field() will be used, with the number as a target edge length. If 0 is passed then only the edge-flip, tangential relaxation, and projection steps will be done.
np	an optional sequence of Named Parameters among the ones listed below

Precondition

if constraints protection is activated, the constrained edges must not be longer than 4/3*target_edge_length.

Optional Named Parameters

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 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 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
number_of_iterations the number of iterations for the sequence of atomic operations performed (listed in the above description) Type: unsigned int Default: 1
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::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. Extra: Sub-edges generated by splitting are set to be constrained. Extra: Patch boundary edges (i.e. incident to only one face in the range) are always considered as constrained edges.
vertex_is_constrained_map a property map containing the constrained-or-not status of each vertex of pmesh. Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertex is constrained Extra: A constrained vertex cannot be modified during remeshing.
protect_constraints If true, the edges set as constrained in edge_is_constrained_map (or by default the boundary edges) are neither split nor collapsed during remeshing. Type: Boolean Default: false Extra: Note that around constrained edges that have their length higher than twice target_edge_length, remeshing will fail to provide good quality results. It can even fail to terminate because of cascading vertex insertions.
collapse_constraints If true, the edges set as constrained in edge_is_constrained_map (or by default the boundary edges) are collapsed during remeshing. Type: Boolean Default: true Extra: This value is ignored if protect_constraints is true.
face_patch_map a property map with the patch id's associated to the faces of faces Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::face_descriptor as key type and the desired property, model of CopyConstructible and LessThanComparable as value type. Default: a default property map where each face is associated with the ID of the connected component it belongs to. Connected components are computed with respect to the constrained edges listed in the property map edge_is_constrained_map Extra: The map is updated during the remeshing process while new faces are created.
do_split whether edges that are too long with respect to the given sizing are split Type: Boolean Default: true
do_collapse whether edges that are too short with respect to the given sizing are collapsed Type: Boolean Default: true
do_flip whether edge flips are performed to improve shape and valence Type: Boolean Default: true
number_of_relaxation_steps the number of iterations of tangential relaxation that are performed at each iteration of the remeshing process Type: unsigned int Default: 1
relax_constraints If true, the end vertices of the edges set as constrained in edge_is_constrained_map and boundary edges move along the constrained polylines they belong to. Type: Boolean Default: false
allow_move_functor A function object used to determinate if a vertex move should be allowed or not during the relaxation step. Type: Functor that provides bool operator()(vertex_descriptor v, Point_3 src, Point_3 tgt) returning true if the vertex v can be moved from src to tgt; Point_3 being the value type of the vertex point map Default: If not provided, all moves are allowed.
do_project whether vertices should be reprojected on the input surface after creation or displacement Type: Boolean Default: true
projection_functor A function object used to project input vertices (moved by the smoothing) and created vertices Type: Unary functor that provides Point_3 operator()(vertex_descriptor), Point_3 being the value type of the vertex point map. Default: If not provided, vertices are projected on the input surface mesh.

See also

split_long_edges()

Todo:

Deal with exact constructions Kernel. The only thing that makes sense is to guarantee that the output vertices are exactly on the input surface. To do so, we can do every construction in double, and use an exact process for projection. For each vertex, the AABB_tree would be used in an inexact manner to find the triangle on which projection has to be done. Then, use CGAL::intersection(triangle, line) in the exact constructions kernel to get a point which is exactly on the surface.

Examples

Polygon_mesh_processing/isotropic_remeshing_example.cpp, Polygon_mesh_processing/isotropic_remeshing_of_patch_example.cpp, Polygon_mesh_processing/isotropic_remeshing_with_allow_move.cpp, Polygon_mesh_processing/isotropic_remeshing_with_custom_sizing_example.cpp, Polygon_mesh_processing/isotropic_remeshing_with_sizing_example.cpp, and Polygon_mesh_processing/remesh_planar_patches.cpp.

random_perturbation() [1/2]

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

void CGAL::Polygon_mesh_processing::random_perturbation	(	TriangleMesh &	tmesh,
		const double &	perturbation_max_size,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/random_perturbation.h>

randomly perturbs the locations of all non-border vertices of a triangulated surface mesh.

By default, the vertices are re-projected onto the input surface after perturbation. Note that no geometric checks are performed after the perturbation (self-intersections might be introduced).

Template Parameters

TriangleMesh	model of VertexListGraph.
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	the triangulated surface mesh
perturbation_max_size	the maximal length of moves that can be applied to vertices of tmesh.
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)
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_is_constrained_map a property map containing the constrained-or-not status of each vertex of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertex is constrained Extra: A constrained vertex cannot be modified at all during perturbation
do_project indicates whether vertices are reprojected on the input surface after their coordinates random perturbation Type: Boolean Default: true
random_seed a value to seed the random number generator, and make the perturbation deterministic Type: unsigned int Default: unsigned int(-1)

random_perturbation() [2/2]

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

void CGAL::Polygon_mesh_processing::random_perturbation	(	VertexRange	vertices,
		TriangleMesh &	tmesh,
		const double &	perturbation_max_size,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/random_perturbation.h>

randomly perturbs the locations of non-border vertices of a triangulated surface mesh.

By default, the vertices are re-projected onto the input surface after perturbation. Note that no geometric checks are performed after the perturbation (self-intersections might be introduced).

Template Parameters

VertexRange	model of Range, holding vertices of type boost::graph_traits<TriangleMesh>::vertex_descriptor. Its iterator type is ForwardIterator.
TriangleMesh	model of VertexListGraph.
NamedParameters	a sequence of Named Parameters

Parameters

vertices	the range of vertices to be perturbed
tmesh	the triangulated surface mesh
perturbation_max_size	the maximal length of moves that can be applied to vertices of tmesh.
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)
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_is_constrained_map a property map containing the constrained-or-not status of each vertex of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertex is constrained Extra: A constrained vertex cannot be modified at all during perturbation
do_project indicates whether vertices are reprojected on the input surface after their coordinates random perturbation Type: Boolean Default: true
random_seed a value to seed the random number generator, and make the perturbation deterministic Type: unsigned int Default: unsigned int(-1)

Examples

Polygon_mesh_processing/remesh_almost_planar_patches.cpp.

refine()

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

std::pair< FaceOutputIterator, VertexOutputIterator > CGAL::Polygon_mesh_processing::refine	(	TriangleMesh &	tmesh,
		const FaceRange &	faces,
		FaceOutputIterator	faces_out,
		VertexOutputIterator	vertices_out,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/refine.h>

refines a region of a triangle mesh.

Template Parameters

TriangleMesh	model of MutableFaceGraph
FaceRange	range of face descriptors, model of Range. Its iterator type is InputIterator.
FaceOutputIterator	model of OutputIterator holding boost::graph_traits<TriangleMesh>::face_descriptor for patch faces
VertexOutputIterator	model of OutputIterator holding boost::graph_traits<TriangleMesh>::vertex_descriptor for patch vertices
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	triangle mesh with patches to be refined
faces	the range of faces defining the patches to refine
faces_out	output iterator into which descriptors of new faces are recorded
vertices_out	output iterator into which descriptors of new vertices are recorded
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.
density_control_factor a factor to control density of the output mesh, where larger values lead to denser refinements Type: double Default: \( \sqrt{2}\) Extra: The density of vertices of faces_out is this factor times higher than the vertices of faces.

Returns

pair of faces_out and vertices_out

Precondition

CGAL::is_triangle_mesh(tmesh)

Todo:

current algorithm iterates 10 times at most, since (I guess) there is no termination proof.

Examples

Polygon_mesh_processing/refine_fair_example.cpp.

smooth_shape()

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

void CGAL::Polygon_mesh_processing::smooth_shape	(	const FaceRange &	faces,
		TriangleMesh &	tmesh,
		const double	time,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/smooth_shape.h>

smooths the overall shape of the mesh by using the mean curvature flow.

The effect depends on the curvature of each area and on a time step which represents the amount by which vertices are allowed to move. The result conformally maps the initial surface to a sphere.

Template Parameters

TriangleMesh	model of MutableFaceGraph.
FaceRange	range of boost::graph_traits<TriangleMesh>::face_descriptor, model of Range. Its iterator type is ForwardIterator.
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	a polygon mesh with triangulated surface patches to be smoothed.
faces	the range of triangular faces defining one or several surface patches to be smoothed.
time	a time step that corresponds to the speed by which the surface is smoothed. A larger time step results in faster convergence but details may be distorted to a larger extent compared to more iterations with a smaller step. Typical values scale in the interval (1e-6, 1].
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

number_of_iterations the number of iterations for the sequence of the smoothing iterations performed Type: unsigned int Default: 1
vertex_is_constrained_map a property map containing the constrained-or-not status of each vertex of tmesh. Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertex is constrained Extra: A constrained vertex cannot be modified at all during smoothing.
do_scale Whether to apply rescaling after smoothing. This is useful because the mean curvature flow tends to shrink the surface. Type: Boolean Default: true Extra: Scaling can only be applied if the mesh is closed and if there is no more than a single constrained vertex. Extra: If a vertex is constrained, it is the fixed point of the scaling, otherwise the centroid is used.
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.
sparse_linear_solver an instance of the sparse linear solver used for smoothing Type: a class model of SparseLinearAlgebraWithFactorTraits_d Default: if Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then the following overload of Eigen_solver_traits is provided as default value: CGAL::Eigen_solver_traits<Eigen::BiCGSTAB<CGAL::Eigen_sparse_matrix<double>::EigenType, Eigen::IncompleteLUT<double> > >

Warning

This function involves linear algebra, that is computed using non-exact, floating-point arithmetic.

See also

angle_and_area_smoothing()

Examples

Polygon_mesh_processing/shape_smoothing_example.cpp.

split_long_edges()

template<typename PolygonMesh , typename EdgeRange , typename SizingFunction , typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::split_long_edges	(	const EdgeRange &	edges,
		SizingFunction &	sizing,
		PolygonMesh &	pmesh,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh.h>

splits the edges listed in edges into sub-edges that are not longer than the given threshold max_length.

Note this function is useful to split constrained edges before calling isotropic_remeshing() with protection of constraints activated (to match the constrained edge length required by the remeshing algorithm to be guaranteed to terminate)

Template Parameters

PolygonMesh	model of MutableFaceGraph that has an internal property map for CGAL::vertex_point_t.
EdgeRange	range of boost::graph_traits<PolygonMesh>::edge_descriptor, model of Range. Its iterator type is InputIterator.
SizingFunction	model of PMPSizingField
NamedParameters	a sequence of Named Parameters

Parameters

pmesh	a polygon mesh
edges	the range of edges to be split if they are longer than given threshold
sizing	the sizing function that is used to split edges from 'edges' list. If a number convertible to a double is passed, Uniform_sizing_field() will be used, with the number as target edge length.
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 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.
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
face_patch_map a property map with the patch id's associated to the faces of faces Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::face_descriptor as key type and the desired property, model of CopyConstructible and LessThanComparable as value type. Default: a default property map where each face is associated with the ID of the connected component it belongs to. Connected components are computed with respect to the constrained edges listed in the property map edge_is_constrained_map Extra: The map is updated during the remeshing process while new faces are created.
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of pmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::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.

See also

isotropic_remeshing()

Examples

Polygon_mesh_processing/isotropic_remeshing_example.cpp, and Polygon_mesh_processing/isotropic_remeshing_of_patch_example.cpp.

tangential_relaxation()

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

void CGAL::Polygon_mesh_processing::tangential_relaxation	(	const VertexRange &	vertices,
		TriangleMesh &	tm,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/tangential_relaxation.h>

applies an iterative area-based tangential smoothing to the given range of vertices.

Each vertex v is relocated to its gravity-weighted centroid, and the relocation vector is projected back to the tangent plane to the surface at v, iteratively. The connectivity remains unchanged.

Template Parameters

TriangleMesh	model of FaceGraph and VertexListGraph. The descriptor types boost::graph_traits<TriangleMesh>::face_descriptor and boost::graph_traits<TriangleMesh>::halfedge_descriptor must be models of Hashable.
VertexRange	range of boost::graph_traits<TriangleMesh>::vertex_descriptor, model of Range. Its iterator type is ForwardIterator.
NamedParameters	a sequence of Named Parameters

Parameters

vertices	the range of vertices which will be relocated by relaxation
tm	the triangle mesh to which vertices belong
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 tm 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, tm) 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_3 type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex Point_3 type. Extra: Exact constructions kernels are not supported by this function.
number_of_iterations the number of smoothing iterations Type: unsigned int Default: 1
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of tm. The endpoints of a constrained edge cannot be moved by relaxation. Type: a class model of ReadWritePropertyMap 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 edges are constrained Extra: Boundary edges are always considered as constrained edges.
vertex_is_constrained_map a property map containing the constrained-or-not status of each vertex of tm. A constrained vertex cannot be modified during relaxation. Type: a class model of ReadWritePropertyMap with boost::graph_traits<PolygonMesh>::vertex_descriptor as key type and bool as value type. It must be default constructible. Default: a default property map where no vertices are constrained
relax_constraints If true, the end vertices of the edges set as constrained in edge_is_constrained_map and boundary edges move along the constrained polylines they belong to. Type: Boolean Default: false
allow_move_functor A function object used to determinate if a vertex move should be allowed or not Type: Unary functor that provides bool operator()(vertex_descriptor v, Point_3 src, Point_3 tgt) returning true if the vertex v can be moved from src to tgt; Point_3 being the value type of the vertex point map Default: If not provided, all moves are allowed.
sizing_function An object containing sizing field for individual vertices. Used to derive smoothing weights. Type: A model of PMPSizingField. Default: If not provided, smoothing weights are the same for all vertices.

Todo:

check if it should really be a triangle mesh or if a polygon mesh is fine

Examples

Polygon_mesh_processing/tangential_relaxation_example.cpp.