\( \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.3 - Triangulated Surface Mesh Simplification
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Related Functions
EdgeCollapsableMesh Concept Reference
Concepts

Definition

The concept EdgeCollapsableMesh describes the requirements for the type of triangulated surface mesh that can be passed to the simplification algorithm.

The surface must be structurally equivalent to a polyhedral surface having only triangular faces. It can have any number of connected components, boundaries (borders and holes) and handles (arbitrary genus).

Refines:
HalfedgeGraph

Valid Expressions

The mesh simplification algorithm requires the free function collapse_triangulation_edge().

Let v0 be the source and v1 be the target vertices of v0v1.

For e \( \in \{\) v0v1,v1v0 \( \}\), let en and ep be the next and previous edges, that is en = next_edge(e, mesh), ep = prev_edge(e,mesh), and let eno and epo be their opposite edges, that is eno = opposite_edge(en, mesh) and epo = opposite_edge(ep,mesh).

Then, after the collapse of (v0v1,v1v0) the following holds:

  • The edge e is no longer in mesh.
  • One of \( \{\)v0,v1 \( \}\) is no longer in mesh while the other remains. Even though it would appear that v0 can always be the vertex being removed, there is a case when removing the edge e requires v1 to be removed as well. See figure CollapseFigure5. Let vgone be the removed vertex and vkept be the remaining vertex.
  • If e was a border edge, that is get(is_border, e, mesh) == true, then next_edge(ep) == en, and prev_edge(en) == ep.
  • If e was not a border edge, that is get(is_border, e, mesh) == false, then ep and epo are no longer in mesh while en and eno are kept in mesh.
  • For all edges ie in in_edges(vgone,mesh), target(ie,mesh) == vkept and source(opposite_edge(ie),mesh) == vkept.
  • No other incidence information has changed in mesh.

The function returns vertex vkept (which can be either v0 or v1).

general_collapse.png
General case. The following mesh elements are removed: triangles ( \( v0,v1,vL\)) and ( \( v1,v0,vR\)), edges \( (e,e')\), \( (ep,epo)\) and \( (ep',epo')\), and vertex \( v0\).
border_collapse3.png
When the collapsing edge is not itself a border, but is incident upon a border edge that is removed, the operation is the same as in the general case.
border_collapse2.png
When the collapsing edge is not itself a border, but is incident upon a border edge that is not removed, the operation is still the same as in the general case.
border_collapse1.png
When the collapsing edge is itself a border, only 1 triangle is removed. Thus, even if \( (ep',epo')\) exists, it's not removed.

border_collapse4.png
This figure illustrates the single exceptional case when removing \( (v0,v1)\) neccesarily implies removing \( (v1)\), thus \( (v0)\) remains.
Has Models:
CGAL::Polyhedron_3<Traits> (If it has only triangular faces, and via External Adaptation, which is described in

[6] and this Bgl web page: http://www.boost.org/libs/graph/doc/leda_conversion.html).

See Also
boost::graph_traits< CGAL::Polyhedron_3<Traits> >
CGAL::halfedge_graph_traits< CGAL::Polyhedron_3<Traits> >

Related Functions

(Note that these are not member functions.)

template<class EdgeCollapsableMesh >
boost::graph_traits
< EdgeCollapsableMesh >
::vertex_descriptor 		halfedge_collapse (typename boost::graph_traits< EdgeCollapsableMesh >::edge_descriptor const &ue, EdgeCollapsableMesh &mesh)
 Collapses the undirected edge (v0v1,v1v0) replacing it with v0 or v1, as described in the following paragraph. More...
 

Friends And Related Function Documentation

template<class EdgeCollapsableMesh >
boost::graph_traits< EdgeCollapsableMesh >::vertex_descriptor halfedge_collapse ( typename boost::graph_traits< EdgeCollapsableMesh >::edge_descriptor const &  ue,
EdgeCollapsableMesh &  mesh 
)
related

Collapses the undirected edge (v0v1,v1v0) replacing it with v0 or v1, as described in the following paragraph.

Precondition
This function requires mesh to be an oriented 2-manifold with or without boundaries. Furthermore, the undirected edge (v0v1,v1v0) must satisfy the link condition [1], which guarantees that the surface is also 2-manifold after the edge collapse.