CGAL 6.1 - Triangulated Surface Mesh Skeletonization

Loading...
Searching...
No Matches
List of all members
CGAL::Mean_curvature_flow_skeletonization< TriangleMesh, Traits_, VertexPointMap_, SolverTraits_ > Class Template Reference
Reference Manual

`#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 Kernel CGAL::Kernel_traits
  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> > > CGAL::Eigen_solver_traits

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.