CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ > Class Template Reference

#include <CGAL/Mean_curvature_flow_skeletonization.h>

Definition

template<class TriangleMesh, class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>
class CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >

Function object that enables to extract the mean curvature flow skeleton of a triangulated surface mesh.

The algorithm used takes as input a triangulated surface mesh and iteratively contracts the surface mesh following the mean curvature flow [1]. The intermediate contracted surface mesh is called the meso-skeleton. After each iteration, the meso-skeleton is locally remeshed using angle split and edge contraction. The process ends when the modification of the meso-skeleton between two iterations is small.

Template Parameters

TriangleMesh	a model of FaceListGraph
Traits	a model of MeanCurvatureSkeletonizationTraits Default: CGAL::Kernel_traits< boost::property_traits< boost::property_map<TriangleMesh, CGAL::vertex_point_t>::type >::value_type >::Kernel
VertexPointMap	a model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key and Traits::Point_3 as value type. Default: boost::property_map<TriangleMesh, CGAL::vertex_point_t>::const_type.
SolverTraits_	a model of NormalEquationSparseLinearAlgebraTraits_d. Default: If Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then an overload of Eigen_solver_traits is provided as default parameter: CGAL::Eigen_solver_traits< Eigen::SimplicialLDLT< Eigen::SparseMatrix<double> > >

Examples

Surface_mesh_skeletonization/MCF_Skeleton_example.cpp, Surface_mesh_skeletonization/MCF_Skeleton_om_example.cpp, Surface_mesh_skeletonization/MCF_Skeleton_sm_example.cpp, Surface_mesh_skeletonization/segmentation_example.cpp, Surface_mesh_skeletonization/simple_mcfskel_example.cpp, and Surface_mesh_skeletonization/simple_mcfskel_sm_example.cpp.

Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, Vmap >	Skeleton
	The graph type representing the skeleton. The vertex property Vmap is a struct with a member point of type Traits::Point_3 and a member vertices of type std::vector<boost::graph_traits<TriangleMesh>::vertex_descriptor>. See the boost documentation page for more details.

Access to the Meso-Skeleton
typedef unspecified_type	Meso_skeleton
	When using the low level API it is possible to access the intermediate results of the skeletonization process, called meso-skeleton. It is a triangulated surface mesh which is model of FaceListGraph and HalfedgeListGraph.
const Meso_skeleton &	meso_skeleton () const
	Reference to the collapsed triangulated surface mesh.

Constructor
	Mean_curvature_flow_skeletonization (const TriangleMesh &tmesh, VertexPointMap vertex_point_map=get(CGAL::vertex_point, tmesh), Traits traits=Traits())
	The constructor of a skeletonization object.

Local Remeshing Parameters
double	max_triangle_angle () const
	During the local remeshing step, a triangle will be split if it has an angle larger than max_triangle_angle().
double	min_edge_length () const
	During the local remeshing step, an edge will be collapse if it is length is less than min_edge_length().
void	set_max_triangle_angle (double value)
	set function for max_triangle_angle()
void	set_min_edge_length (double value)
	set function for min_edge_length()

Algorithm Termination Parameters
std::size_t	max_iterations () const
	Maximum number of iterations performed by contract_until_convergence().
double	area_variation_factor () const
	The convergence is considered to be reached if the variation of the area of the meso-skeleton after one iteration is smaller than area_variation_factor()*original_area where original_area is the area of the input triangle mesh.
void	set_max_iterations (std::size_t value)
	set function for max_iterations()
void	set_area_variation_factor (double value)
	set function for area_variation_factor()

Vertex Motion Parameters
double	quality_speed_tradeoff () const
	This is an advanced function.
bool	is_medially_centered () const
	If true, the meso-skeleton placement will be attracted by an approximation of the medial axis of the mesh during the contraction steps, so will be the result skeleton.
double	medially_centered_speed_tradeoff () const
	This is an advanced function.
void	set_quality_speed_tradeoff (double value)
	set function for quality_speed_tradeoff()
void	set_is_medially_centered (bool value)
	set function for is_medially_centered()
void	set_medially_centered_speed_tradeoff (double value)
	set function for medially_centered_speed_tradeoff()
template<class InputIterator >
void	set_fixed_vertices (InputIterator begin, InputIterator end)
	This is an advanced function.

High Level Function
void	operator() (Skeleton &skeleton)
	Creates the curve skeleton: the input surface mesh is iteratively contracted until convergence, and then turned into a curve skeleton.

Low Level Functions
Advanced The following functions enable the user to run the mean curvature flow skeletonization algorithm step by step.
void	contract_geometry ()
	Runs one contraction step following the mean curvature flow.
std::size_t	collapse_edges ()
	Collapses edges of the meso-skeleton with length less than min_edge_length() and returns the number of edges collapsed.
std::size_t	split_faces ()
	Splits faces of the meso-skeleton having one angle greater than max_triangle_angle() and returns the number of faces split.
std::size_t	detect_degeneracies ()
	Prevents degenerate vertices to move during the following contraction steps and returns the number of newly fixed vertices.
void	contract ()
	Performs subsequent calls to contract_geometry(), collapse_edges(), split_faces() and detect_degeneracies()
void	contract_until_convergence ()
	Iteratively calls contract() until the change of surface area of the meso-skeleton after one iteration is smaller than area_variation_factor()*original_area where original_area is the area of the input triangle mesh, or if the maximum number of iterations has been reached.
void	convert_to_skeleton (Skeleton &skeleton)
	Converts the contracted surface mesh to a skeleton curve.

Constructor & Destructor Documentation

Mean_curvature_flow_skeletonization()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::Mean_curvature_flow_skeletonization	(	const TriangleMesh &	tmesh,
		VertexPointMap	vertex_point_map = get(CGAL::vertex_point, tmesh),
		Traits	traits = Traits()
	)

The constructor of a skeletonization object.

The algorithm parameters are initialized such that:

• max_triangle_angle() == 110
• quality_speed_tradeoff() == 0.1
• medially_centered_speed_tradeoff() == 0.2
• area_variation_factor() == 0.0001
• max_iterations() == 500
• is_medially_centered() == true
• min_edge_length() == 0.002 * the length of the diagonal of the bounding box of tmesh

Precondition

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

Parameters

tmesh	input triangulated surface mesh.
vertex_point_map	property map which associates a point to each vertex of the graph.
traits	an instance of the traits class.

Member Function Documentation

convert_to_skeleton()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

void CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::convert_to_skeleton

(

Skeleton &

skeleton

)

Converts the contracted surface mesh to a skeleton curve.

Template Parameters

Skeleton

an instantiation of boost::adjacency_list as a data structure for the skeleton curve.

Parameters

skeleton

graph that will contain the skeleton of tmesh. It should be empty before passed to the function.

medially_centered_speed_tradeoff()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

double CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::medially_centered_speed_tradeoff

(

)

const

This is an advanced function.

Advanced

Controls the smoothness of the medial approximation: increasing this value results in a (less smooth) skeleton closer to the medial axis, as well as a lower convergence speed. It is only used if is_medially_centered()==true. This parameter corresponds to \( w_M \) in the original publication.

operator()()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

void CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::operator()

(

Skeleton &

skeleton

)

Creates the curve skeleton: the input surface mesh is iteratively contracted until convergence, and then turned into a curve skeleton.

This is equivalent to calling contract_until_convergence() and convert_to_skeleton().

Parameters

skeleton

graph that will contain the skeleton of the input triangulated surface mesh. For each vertex descriptor vd of skeleton, the corresponding point and the set of input vertices that contracted to vd can be retrieved using skeleton[vd].point and skeleton[vd].vertices respectively.

quality_speed_tradeoff()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

double CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::quality_speed_tradeoff

(

)

const

This is an advanced function.

Advanced

Controls the velocity of movement and approximation quality: decreasing this value makes the mean curvature flow based contraction converge faster, but results in a skeleton of lower quality. This parameter corresponds to \( w_H \) in the original publication.

set_fixed_vertices()

template<class TriangleMesh , class Traits_ = Default, class VertexPointMap_ = Default, class SolverTraits_ = Default>

template<class InputIterator >

void CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ >::set_fixed_vertices	(	InputIterator	begin,
		InputIterator	end
	)

This is an advanced function.

Advanced

sets the vertices in the range [begin, end) as fixed. Fixed vertices will not be moved during contraction and this will therefore prevent convergence towards the skeleton if contract_until_convergence() is used. It is useful only if the end goal is to retrieve the meso-skeleton after a number of contract_geometry(), keeping the specified vertices fixed in place.

Template Parameters

InputIterator

a model of InputIterator with boost::graph_traits<TriangleMesh>::vertex_descriptor as value type.