\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Triangulated Surface Mesh Simplification
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Triangulated Surface Mesh Simplification Reference

detail.png
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
Depends on: CGAL and the Boost Graph Library
Depends on: 3D Polyhedral Surface
BibTeX: cgal:c-tsms-12-14b
License: GPL
Windows Demo: Operations on Polyhedra
Common Demo Dlls: dlls

Classified Reference Pages

Concepts

Functions

Classes

Modules

 Concepts
 

Classes

class  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::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_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 EdgeCollapsableSurfaceMesh , class StopPredicate , class P , class T , class R >
int CGAL::Surface_mesh_simplification::edge_collapse (EdgeCollapsableSurfaceMesh &surface_mesh, StopPredicate const &should_stop, sms_named_params< P, T, R > const &named_parameters)
 Simplifies surface_mesh in-place by collapsing edges, and returns the number of edges effectively removed. More...
 

Function Documentation

template<class EdgeCollapsableSurfaceMesh , class StopPredicate , class P , class T , class R >
int CGAL::Surface_mesh_simplification::edge_collapse ( EdgeCollapsableSurfaceMesh surface_mesh,
StopPredicate const &  should_stop,
sms_named_params< P, T, R > const &  named_parameters 
)

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

The function Surface_mesh_simplification::edge_collapse simplifies in-place a triangulated surface mesh by iteratively collapsing edges.

Non-Named Parameters

surface_mesh is the surface mesh to simplify. It must be a model of the EdgeCollapsableSurfaceMesh concept.

should_stop is the stop-condition policy. It must be a model of the StopPredicate concept.

Named Parameters

named_parameters holds the list of all the additional parameters used by the edge_collapse function (including default parameters).

The named parameters list is a composition of function calls separated by a dot ( \( .\)) where the name of each function matches the name of an argument and wraps the actual parameter.

This is an example with 2 arguments:

vertex_index_map(the_actual_vertex_index_map).halfedge_index_map(the_actual_halfedge_index_map)

the_actual_vertex_index_map and the_actual_halfedge_index_map are the actual parameters, while vertex_index_map() and halfedge_index_map() are wrapper functions used to designate each formal argument.

All named parameters have default values so you only need to compose those for which the default is inappropriate. Furthermore, since each actual parameter is wrapped in a function whose name designates the formal argument, the order of named parameters in the list is totally irrelevant.

In the following subsections, each named parameter is documented as a helper function. The argument to each helper function is the actual parameter to edge_collapse(), while the name of the helper function designates which formal argument it is.

vertex_index_map(VertexIndexMap vpm)

Maps each vertex in the surface mesh into an unsigned integer number in the range [0,num_vertices(surface_mesh)).

VertexIndexMap must be a model of ReadablePropertyMap with key type boost::graph_traits<EdgeCollapsableSurfaceMesh const>::vertex_descriptor and with value type boost::graph_traits<EdgeCollapsableSurfaceMesh>::size_type,

Default: the property map obtained by calling get(CGAL::vertex_index,surface_mesh), which requires the surface mesh vertices to have an id() member properly initialized to the required value.

If the vertices don't have such an id(), you must pass some property map explicitly. An external property map can be easily obtained by calling get(CGAL::vertex_external_index,surface_mesh). This constructs on the fly, and returns, a property map which non-intrusively associates a proper id with each vertex.

vertex_point_map(VertexPointMap vpm)

Maps each vertex in the surface mesh into a 3D CGAL point.

VertexPointMap must be a model of ReadWritePropertyMap with key type boost::graph_traits<EdgeCollapsableSurfaceMesh const>::vertex_descriptor and with any model of Kernel::Point_3 as value type.

Default: the property map obtained by calling get(CGAL::vertex_point,surface_mesh),

halfedge_index_map(HalfedgeIndexMap eim)

Maps each halfedge in the surface mesh into an unsigned integer number in the range [0,num_halfedges(surface_mesh)).

HalfedgeIndexMap must be a model of ReadablePropertyMap with key type boost::graph_traits<EdgeCollapsableSurfaceMesh const>::halfedge_descriptor and with value type boost::graph_traits<EdgeCollapsableSurfaceMesh>::size_type

Default: the property map obtained by calling get(CGAL::halfedge_index,surface_mesh), which requires the surface mesh edges to have an id() member properly initialized to the require value.

If the edges don't have such an id(), you must pass some property map explicitly. An external property map can be easily obtained by calling get(CGAL::halfedge_external_index,surface_mesh). This constructs on the fly, and returns, a property map which non-intrusively associates a proper id with each edge.

edge_is_constrained_map(EdgeIsConstrainedMap ecm)

Maps each edge in the surface mesh into a Boolean value which indicates if the edge is constrained. EdgeIsConstrainedMap must be a model ReadablePropertyMap with key type boost::graph_traits<EdgeCollapsableSurfaceMesh const>::edge_descriptor and with value type bool.

Attention
If this parameter is provided, surface_mesh must be a model of the EdgeCollapsableSurfaceMeshWithConstraints concept.

Default: A property map always returning false, that is no edge is constrained.

get_cost(GetCost gc)

The policy which returns the collapse cost for an edge.

The type of gc must be a model of the GetCost concept.

Default: CGAL::Surface_mesh_simplification::LindstromTurk_cost<EdgeCollapsableSurfaceMesh>.

get_placement(GetPlacement gp)

The policy which returns the placement (position of the replacemet vertex) for an edge.

The type of gp must be a model of the GetPlacement concept.

Default: CGAL::Surface_mesh_simplification::LindstromTurk_placement<EdgeCollapsableSurfaceMesh>

visitor(EdgeCollapseSimplificationVisitor v)

The visitor that is called by the edge_collapse function in certain points to allow the user to track the simplification process.

The type of v must be a model of the EdgeCollapseSimplificationVisitor concept.

Default: an implementation-defined dummy visitor.

If you wish to provide your own visitor, you can derive from: CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base<EdgeCollapsableSurfaceMesh> and override only the callbacks you are interested in.

All these functions naming parameters are defined in namespace CGAL. Being non-member functions, they could clash with equally named functions in some other namespace. If that happens, simply qualify the first The second and subsequent named parameters shall not be qualified as they are member functions named parameter with CGAL::, as shown in the examples in the user manual.

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.

#include <CGAL/Surface_mesh_simplification/edge_collapse.h>

Examples:
Surface_mesh_simplification/edge_collapse_constrain_sharp_edges.cpp, Surface_mesh_simplification/edge_collapse_constrained_border_polyhedron.cpp, Surface_mesh_simplification/edge_collapse_enriched_polyhedron.cpp, Surface_mesh_simplification/edge_collapse_OpenMesh.cpp, and Surface_mesh_simplification/edge_collapse_polyhedron.cpp.