CGAL 4.14 - Triangulated Surface Mesh Simplification
Triangulated Surface Mesh Simplification Reference
Fernando Cacciola
This package provides an algorithm to simplify a triangulated surface mesh by edge collapsing. It is an implementation of the Turk/Lindstrom memoryless surface mesh simplification algorithm.
Introduced in: CGAL 3.3
BibTeX: cgal:c-tsms-12-19a
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

## Concepts

• EdgeProfile
• StopPredicate
• GetCost
• GetPlacement
• EdgeCollapseSimplificationVisitor

## Functions

• CGAL::Surface_mesh_simplification::edge_collapse()

## Classes

• CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base<TriangleMesh>
• CGAL::Surface_mesh_simplification::Edge_profile<TriangleMesh>
• CGAL::Surface_mesh_simplification::Count_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Count_ratio_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Edge_length_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Edge_length_cost<TriangleMesh>
• CGAL::Surface_mesh_simplification::Midpoint_placement<TriangleMesh>
• CGAL::Surface_mesh_simplification::LindstromTurk_cost<TriangleMesh>
• CGAL::Surface_mesh_simplification::LindstromTurk_placement<TriangleMesh>
• CGAL::Surface_mesh_simplification::Constrained_placement<Placement,TriangleMesh>
• CGAL::Surface_mesh_simplification::Bounded_normal_change_placement<Placement>

## Modules

Named Parameters for Surface Mesh Simplification
In this package, some optional parameters are implemented as BGL optional named parameters (see Named Parameters for more information on how to use them).

Concepts

## Classes

struct  CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base< TriangleMesh >
The class Surface_mesh_simplification::Edge_collapse_visitor_base provides a base class for models of the EdgeCollapseSimplificationVisitor concept. More...

class  CGAL::Surface_mesh_simplification::Bounded_normal_change_placement< Placement >
The class Bounded_normal_change_placement is a model for the GetPlacement concept which serves as a filter for another placement. More...

class  CGAL::Surface_mesh_simplification::Constrained_placement< BasePlacement, EdgeIsConstrainedMap >
The class Constrained_placement is a model for the GetPlacement concept provided the template parameter BasePlacement is such a model. More...

class  CGAL::Surface_mesh_simplification::Count_ratio_stop_predicate< TriangleMesh >
The class Count_ratio_stop_predicate is a model for the StopPredicate concept which returns true when the relation between the initial and current number of edges drops below a certain ratio. More...

class  CGAL::Surface_mesh_simplification::Count_stop_predicate< TriangleMesh >
The class Count_stop_predicate is a model for the StopPredicate concept, which returns true when the number of current edges drops below a certain threshold. More...

class  CGAL::Surface_mesh_simplification::Edge_length_cost< TriangleMesh >
The class Edge_length_cost is a model for the GetCost concept, which computes the collapse cost as the squared length of the edge. More...

class  CGAL::Surface_mesh_simplification::Edge_length_stop_predicate< FT >
The class Edge_length_stop_predicate is a model for the StopPredicate concept, which returns true when the top edge in the priority queue is larger than a certain threshold. More...

class  CGAL::Surface_mesh_simplification::Edge_profile< TriangleMesh >
The class Edge_profile provides a model for the EdgeProfile concept. More...

class  CGAL::Surface_mesh_simplification::LindstromTurk_cost< TriangleMesh >
The class LindstromTurk_cost provides a model for the GetCost concept. More...

class  CGAL::Surface_mesh_simplification::LindstromTurk_placement< TriangleMesh >
The class LindstromTurk_placement provides a model for the GetPlacement concept. More...

class  CGAL::Surface_mesh_simplification::Midpoint_placement< TriangleMesh >
The class Midpoint_placement is a model for the GetPlacement concept which computes the placement as the midpoint position along the edge. More...

## Functions

template<class TriangleMesh , class StopPolicy , class NamedParameters >
int CGAL::Surface_mesh_simplification::edge_collapse (TriangleMesh &surface_mesh, const StopPolicy &should_stop, const NamedParameters &np)
Simplifies surface_mesh in-place by collapsing edges, and returns the number of edges effectively removed. More...

## ◆ edge_collapse()

template<class TriangleMesh , class StopPolicy , class NamedParameters >
 int CGAL::Surface_mesh_simplification::edge_collapse ( TriangleMesh & surface_mesh, const StopPolicy & should_stop, const NamedParameters & np )

#include <CGAL/Surface_mesh_simplification/edge_collapse.h>

Simplifies surface_mesh in-place by collapsing edges, and returns the number of edges effectively removed.

Template Parameters
 TriangleMesh a model of the MutableFaceGraph and HalfedgeListGraph concepts. StopPolicy a model of StopPredicate NamedParameters a sequence of Named Parameters
Parameters
 surface_mesh a triangle mesh should_stop the stop-condition policy np optional sequence of Named Parameters among the ones listed below
Named Parameters
 vertex_point_map the property map with the points associated to the vertices of the mesh. If this parameter is omitted, an internal property map for CGAL::vertex_point_t should be available in PolygonMesh halfedge_index_map the property map containing an index for each halfedge, initialized 0 to num_halfedges(graph) get_cost The policy which returns the collapse cost for an edge. get_placement The policy which returns the placement (position of the replacemet vertex) for an edge. edge_is_constrained_map The property map containing the constrained-or-not status of each edge of pmesh visitor The visitor that is called by the edge_collapse function in certain points to allow the user to track the simplification process. vertex_index_map is the property map containing the index of each vertex of the input polygon mesh. Debugging Support This parameter is only used by debug functions and is usually not needed for users. 

Semantics

The simplification process continues until the should_stop policy returns true or the surface mesh cannot be simplified any further due to topological constraints.

get_cost and get_placement are the policies which control the cost-strategy, that is, the order in which edges are collapsed and the remaining vertex is re-positioned.

visitor is used to keep track of the simplification process. It has several member functions which are called at certain points in the simplification code.

Examples:
Surface_mesh_simplification/edge_collapse_all_short_edges.cpp, Surface_mesh_simplification/edge_collapse_bounded_normal_change.cpp, Surface_mesh_simplification/edge_collapse_constrain_sharp_edges.cpp, Surface_mesh_simplification/edge_collapse_constrained_border_polyhedron.cpp, Surface_mesh_simplification/edge_collapse_constrained_border_surface_mesh.cpp, Surface_mesh_simplification/edge_collapse_enriched_polyhedron.cpp, Surface_mesh_simplification/edge_collapse_OpenMesh.cpp, Surface_mesh_simplification/edge_collapse_polyhedron.cpp, Surface_mesh_simplification/edge_collapse_surface_mesh.cpp, and Surface_mesh_simplification/edge_collapse_visitor_surface_mesh.cpp.