CGAL 5.3 - Triangulated Surface Mesh Simplification
Triangulated Surface Mesh Simplification Reference
Fernando Cacciola, Mael Rouxel-Labbé, and Baskın Şenbaşlar
This package provides an algorithm to simplify a triangulated surface mesh by edge collapsing. Users can define cost, constraints, and placement strategies to decide when and how should edges be collapsed. A few strategies are offered by default, such as the Turk/Lindstrom and Garland-Heckbert memoryless approaches.
Introduced in: CGAL 3.3
BibTeX: cgal:c-tsms-12-21b
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

## Concepts

• StopPredicate
• GetCost
• GetPlacement
• PlacementFilter
• 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, VertexPointMap, GeomTraits>
• 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<FT>
• 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::GarlandHeckbert_policies<TriangleMesh, GeomTraits>
• CGAL::Surface_mesh_simplification::Bounded_normal_change_placement<Placement>
• CGAL::Surface_mesh_simplification::Bounded_normal_change_filter<Filter>
• CGAL::Surface_mesh_simplification::Polyhedral_envelope_filter<Filter>
• CGAL::Surface_mesh_simplification::Constrained_placement<Placement, TriangleMesh>

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_filter< Filter >
The class Bounded_normal_change_filter is a model for the PlacementFilter concept. More...

class  CGAL::Surface_mesh_simplification::Bounded_normal_change_placement< Get_placement_ >

class  CGAL::Surface_mesh_simplification::Constrained_placement< Get_placement_, Edge_is_constrained_map_ >
The class Constrained_placement is a model for the concept GetPlacement. 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, VertexPointMap, GeomTraits >
The class Edge_profile regroups useful information about an edge, such as its incident vertices and faces. More...

class  CGAL::Surface_mesh_simplification::GarlandHeckbert_policies< TriangleMesh, GeomTraits >
The class GarlandHeckbert_policies regroups the cost and placement policies based on the Garland-Heckbert strategy (Section Garland-Heckbert Cost and Placement Strategy), both oracles must indeed be used together as they internally use and share information associating quadrics to vertices. 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...

class  CGAL::Surface_mesh_simplification::Polyhedral_envelope_filter< GeomTraits, Filter >
The class Polyhedral_envelope_filter is a model for the PlacementFilter concept. More...

## Functions

template<class TriangleMesh , class StopPolicy , class NamedParameters >
int CGAL::Surface_mesh_simplification::edge_collapse (TriangleMesh &tmesh, const StopPolicy &should_stop, const NamedParameters &np)
Simplifies tmesh 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 & tmesh, const StopPolicy & should_stop, const NamedParameters & np )

#include <CGAL/Surface_mesh_simplification/edge_collapse.h>

Simplifies tmesh 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
 tmesh a triangle mesh should_stop the stop-condition policy np an optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
 a property map associating points to the vertices of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits::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 should be available for the vertices of tmesh. 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. a property map associating to each halfedge of tmesh a unique index between 0 and num_halfedges(tmesh) - 1 Type: a class model of ReadWritePropertyMap with boost::graph_traits::halfedge_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access. a policy which returns the collapse cost for an edge Type: a model of the concept GetCost Default: CGAL::Surface_mesh_simplification::LindstromTurk_cost a policy which returns the placement (position of the replacemet vertex) for an edge Type: a model of the concept GetPlacement Default: CGAL::Surface_mesh_simplification::LindstromTurk_placement a policy which returns the filter for a placement Type: a model of the concept Filter Default: no placement gets filtered a property map containing the constrained-or-not status of each edge of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits::edge_descriptor as key type and bool as value type Default: a constant property map returning false for any edge key Extra: A constrained edge cannot be collapsed. a visitor that is called by the edge_collapse function at certain points to allow the user to track the simplification process Type: a class model of the concept EdgeCollapseSimplificationVisitor Default: unused a property map associating to each vertex of tmesh a unique index between 0 and num_vertices(tmesh) - 1 Type: a class model of ReadWritePropertyMap with boost::graph_traits::vertex_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access. Extra: 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 until 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_envelope.cpp, Surface_mesh_simplification/edge_collapse_garland_heckbert.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.