CGAL 6.1.1 - Triangulated Surface Mesh Simplification

Loading...
Searching...
No Matches
Modules | Classes | Functions
Reference Manual

##

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-26a
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

  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 collapse cost for an edge Type: a model of the concept `GetCost` Default: `CGAL::Surface_mesh_simplification::LindstromTurk_cost<TriangleMesh>` |
  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>` |
  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.