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
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

Classified Reference Pages

Concepts

• EdgeCollapsableSurfaceMesh
• EdgeCollapsableSurfaceMeshWithConstraints
• EdgeProfile
• StopPredicate
• GetCost
• GetPlacement
• EdgeCollapseSimplificationVisitor

Functions

• CGAL::Surface_mesh_simplification::edge_collapse()

Classes

• CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base<ECM>
• CGAL::Surface_mesh_simplification::Edge_profile<ECM>
• CGAL::Surface_mesh_simplification::Count_stop_predicate<ECM>
• CGAL::Surface_mesh_simplification::Count_ratio_stop_predicate<ECM>
• CGAL::Surface_mesh_simplification::Edge_length_stop_predicate<ECM>
• CGAL::Surface_mesh_simplification::Edge_length_cost<ECM>
• CGAL::Surface_mesh_simplification::Midpoint_placement<ECM>
• CGAL::Surface_mesh_simplification::LindstromTurk_cost<ECM>
• CGAL::Surface_mesh_simplification::LindstromTurk_placement<ECM>
• CGAL::Surface_mesh_simplification::Constrained_placement<Placement,ECM>
• 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< ECM >
	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< ECM >
	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< ECM >
	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< ECM >
	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< ECM >
	The class Edge_profile provides a model for the EdgeProfile concept. More...
class	CGAL::Surface_mesh_simplification::LindstromTurk_cost< ECM >
	The class LindstromTurk_cost provides a model for the GetCost concept. More...
class	CGAL::Surface_mesh_simplification::LindstromTurk_placement< ECM >
	The class LindstromTurk_placement provides a model for the GetPlacement concept. More...
class	CGAL::Surface_mesh_simplification::Midpoint_placement< ECM >
	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...

Function Documentation

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 EdgeCollapsableSurfaceMesh
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 Attention If this parameter is provided, surface_mesh must be a model of the EdgeCollapsableSurfaceMeshWithConstraints concept.
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, and Surface_mesh_simplification/edge_collapse_surface_mesh.cpp.