Triangulated Surface Mesh Simplification Reference

Fernando Cacciola, Mael Rouxel-Labbé, Baskın Şenbaşlar, and Julian Komaromy

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-24a
License: GPL
Windows Demo: CGAL Lab

Classified Reference Pages

Concepts

• StopPredicate
• GetCost
• GetPlacement
• PlacementFilter
• EdgeCollapseSimplificationVisitor

Functions

• CGAL::Surface_mesh_simplification::edge_collapse()

Policies

• CGAL::Surface_mesh_simplification::Count_stop_predicate<TriangleMesh> (deprecated)
• CGAL::Surface_mesh_simplification::Count_ratio_stop_predicate<TriangleMesh> (deprecated)
• CGAL::Surface_mesh_simplification::Edge_count_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Face_count_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Edge_count_ratio_stop_predicate<TriangleMesh>
• CGAL::Surface_mesh_simplification::Face_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_plane_policies<TriangleMesh, GeomTraits>
• CGAL::Surface_mesh_simplification::GarlandHeckbert_probabilistic_plane_policies<TriangleMesh, GeomTraits>
• CGAL::Surface_mesh_simplification::GarlandHeckbert_triangle_policies<TriangleMesh, GeomTraits>
• CGAL::Surface_mesh_simplification::GarlandHeckbert_probabilistic_triangle_policies<TriangleMesh, GeomTraits>
• CGAL::Surface_mesh_simplification::GarlandHeckbert_policies<TriangleMesh, GeomTraits> (deprecated)

Policy Enhancements

• CGAL::Surface_mesh_simplification::Constrained_placement<Placement, TriangleMesh>
• 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>

Classes

• CGAL::Surface_mesh_simplification::Edge_profile<TriangleMesh, VertexPointMap, GeomTraits>
• CGAL::Surface_mesh_simplification::Edge_collapse_visitor_base<TriangleMesh>

Modules
	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 >
class	CGAL::Surface_mesh_simplification::Count_stop_predicate< TriangleMesh >
class	CGAL::Surface_mesh_simplification::Edge_count_ratio_stop_predicate< TriangleMesh >
class	CGAL::Surface_mesh_simplification::Edge_count_stop_predicate< TriangleMesh >
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::Face_count_ratio_stop_predicate< TriangleMesh >
class	CGAL::Surface_mesh_simplification::Face_count_stop_predicate< TriangleMesh >
class	CGAL::Surface_mesh_simplification::GarlandHeckbert_plane_policies< TriangleMesh, GeomTraits >
	The class GarlandHeckbert_plane_policies regroups the cost and placement policies based on the Garland-Heckbert "Classic Plane" strategy (Section Garland-Heckbert Cost and Placement Strategy). More...
class	CGAL::Surface_mesh_simplification::GarlandHeckbert_policies< TriangleMesh, GeomTraits >
class	CGAL::Surface_mesh_simplification::GarlandHeckbert_probabilistic_plane_policies< TriangleMesh, GeomTraits >
	The class GarlandHeckbert_probabilistic_plane_policies regroups the cost and placement policies based on the "Probabilistic Plane" strategy of Trettner and Kobbelt [7]. More...
class	CGAL::Surface_mesh_simplification::GarlandHeckbert_probabilistic_triangle_policies< TriangleMesh, GeomTraits >
	The class GarlandHeckbert_probabilistic_triangle_policies regroups the cost and placement policies based on the "Probabilistic Triangle" strategy of Trettner and Kobbelt [7]. More...
class	CGAL::Surface_mesh_simplification::GarlandHeckbert_triangle_policies< TriangleMesh, GeomTraits >
	The class GarlandHeckbert_triangle_policies regroups the cost and placement policies using the triangle-based Garland-Heckbert strategy (Section Garland-Heckbert Cost and Placement Strategy). 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 = parameters::Default_named_parameters>
int	CGAL::Surface_mesh_simplification::edge_collapse (TriangleMesh &tmesh, const StopPolicy &should_stop, const NamedParameters &np=parameters::default_values())
	Simplifies tmesh in-place by collapsing edges, and returns the number of edges effectively removed.

Function Documentation

edge_collapse()

template<class TriangleMesh , class StopPolicy , class NamedParameters = parameters::Default_named_parameters>

int CGAL::Surface_mesh_simplification::edge_collapse	(	TriangleMesh &	tmesh,
		const StopPolicy &	should_stop,
		const NamedParameters &	np = parameters::default_values()
	)

#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

vertex_point_map a property map associating points to the vertices of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::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.
geom_traits 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.
halfedge_index_map 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<TriangleMesh>::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.
get_cost a policy which returns the collapse cost for an edge Type: a model of the concept GetCost Default: CGAL::Surface_mesh_simplification::LindstromTurk_cost<TriangleMesh>
get_placement a policy which returns the placement (position of the replacement vertex) for an edge Type: a model of the concept GetPlacement Default: CGAL::Surface_mesh_simplification::LindstromTurk_placement<TriangleMesh>
filter a policy which returns the filter for a placement Type: a model of the concept Filter Default: no placement gets filtered
edge_is_constrained_map a property map containing the constrained-or-not status of each edge of tmesh Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::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.
visitor 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
vertex_index_map 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<TriangleMesh>::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.
use_relaxed_order a Boolean tag indicating if the ordering of elements to be collapsed in the priority queue can be relaxed Type: Either CGAL::Tag_true or CGAL::Tag_false Default: CGAL::Tag_false() Extra: Using a relaxed order will allow the algorithm to use a faster priority queue. However, the ordering of the priority queue is no longer strict and there is a possibility that some elements that ought to have been collapsed are not actually collapsed.

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.