vcg::tri::ReebGraph< MeshType > Class Template Reference

Reeb graph of the vertex quality of a triangle mesh. More...

#include <reeb_graph.h>

Public Types
typedef MeshType::FaceType	FaceType

Public Member Functions
bool	Below (int v, int w) const
	True if mesh vertex v comes before w in the order by quality.
template<class EdgeMeshType >
void	Compute (MeshType &m, EdgeMeshType &graph)
	Compute the Reeb graph of the vertex quality of m into graph.

Public Attributes
std::vector< int >	nodeVert
	mesh vertex of each node
std::vector< int >	vertNode
	node of each mesh vertex, -1 for vertices inside an arc
std::vector< int >	vertArc
	arc of each mesh vertex inside an arc, -1 for nodes
std::vector< int >	rank
	position of each mesh vertex in the order by quality
std::vector< int >	faceEdge
	edge number of side z of face fi, at 3*fi+z
std::vector< std::pair< int, int > >	edgeVert
	lower and upper mesh vertex of each edge
std::vector< std::vector< int > >	edgePath
	arcs crossed by each mesh edge, going up

Detailed Description

template<class MeshType>
class vcg::tri::ReebGraph< MeshType >

Reeb graph of the vertex quality of a triangle mesh.

The Reeb graph of a function on a surface collapses every connected component of every level set to a point. Its nodes are the critical points: minima, maxima, and saddles where a contour splits or two contours merge. Its arcs are the families of contours swept between them. Whatever the function, the Reeb graph of a closed orientable surface of genus g has exactly g independent cycles. It is a compact description of the shape along the function, used for shape matching, skeletons and topology repair (see tri::HandleTunnelLoops).

Usage

tri::UpdateTopology<MyMesh>::FaceFace(m);
tri::UpdateQuality<MyMesh>::VertexFromPlane(m, Plane3f(0, dir));  // a height function
MyEdgeMesh graph;
tri::ReebGraph<MyMesh> rg;
rg.Compute(m, graph);
// graph.vert[n] is node n, at mesh vertex rg.nodeVert[n];
// graph.edge[a] is arc a, from its lower node V(0) to its upper node V(1).

See also the sample trimesh_handle_tunnel.cpp.

Requirements

• The function is the vertex quality, and must be finite. Ties are broken by vertex index, so it need not be Morse.
• The mesh needs per-vertex quality and up-to-date FF adjacency, and must be edge-manifold. Boundaries are allowed, but then the cycles of the graph no longer count the genus.
• The edge mesh needs vertex coordinates and edge vertex references. Its VE adjacency is filled when it has one.

Output

Compute() replaces the content of the edge mesh with the graph: a vertex per node, placed at its mesh vertex, and an edge per arc, going up. This object keeps the map from the mesh to the graph, as indices of the edge mesh's vertices and edges: the node (vertNode) or arc (vertArc) of every vertex, the mesh vertex of every node (nodeVert), and the arcs crossed by every mesh edge (edgePath), with the edge numbering it uses (faceEdge, edgeVert).

Algorithm

The on-line algorithm of V. Pascucci, G. Scorzelli, P.-T. Bremer and A. Mascarenhas, "Robust on-line computation of Reeb graphs: simplicity and speed", ACM TOG 26(3), 2007: every edge starts as an arc, every triangle glues the paths of its edges by a merge sort along the function, and a vertex is dropped from the graph as soon as all its triangles are in and it has one arc below and one above. It takes about 1.2 s for 640K triangles.

Member Function Documentation

Compute()

template<class MeshType >

template<class EdgeMeshType >

void vcg::tri::ReebGraph< MeshType >::Compute ( MeshType &  m, EdgeMeshType &  graph  )

inline

Compute the Reeb graph of the vertex quality of m into graph.

Parameters

m	the mesh; only read
graph	the edge mesh that receives the graph; its previous content is cleared

Exceptions

vcg::MissingComponentException	if m has no per-vertex quality or no FF adjacency.
vcg::MissingPreconditionException	if the FF adjacency is not computed, if m has non-manifold edges, or if a quality is NaN or infinite.

---

The documentation for this class was generated from the following file:

• vcg/complex/algorithms/reeb_graph.h