CGAL 5.5.1 - Triangulated Surface Mesh Simplification
Triangulated Surface Mesh Simplification Reference

SMS-detail.png
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-22b
License: GPL
Windows Demo: Polyhedron demo
Common Demo Dlls: dlls

Classified Reference Pages

Concepts

Functions

Policies

Policy Enhancements

Classes

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 >
 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_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. More...
 

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
TriangleMesha model of the MutableFaceGraph and HalfedgeListGraph concepts.
StopPolicya model of StopPredicate
NamedParametersa sequence of Named Parameters
Parameters
tmesha triangle mesh
should_stopthe stop-condition policy
npan 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<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.

  • 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<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.

  • 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<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.

  • 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<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.

  • 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.

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.