Concept

EdgeCollapsableMesh

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.

template<class EdgeCollapsableMesh>
typename 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.
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 [DEGN99], which guarantees that the surface is also 2-manifold after the edge collapse.


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

For e { 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 function returns vertex vkept (which can be either v0 or v1).

Simplification illustration
Figure 53.1:  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.

Simplification illustration
Figure 53.2:  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.

Simplification illustration
Figure 53.3:  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.

Simplification illustration
Figure 53.4:  When the collapsing edge is itself a border, only 1 triangle is removed. Thus, even if (ep',epo') exists, it's not removed.

Simplification illustration
Figure 53.5:  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 [SLL02] 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> >


Footnotes

 1  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 53.5.