template<class MeshType>
class vcg::tri::HandleTunnelLoops< MeshType >
Handle and tunnel loops of an orientable surface.
A closed surface of genus g bounds an inside I and an outside O. A handle loop bounds a surface in I but not in O: it circles a handle, like the meridian of a torus, which goes around the tube. A tunnel loop bounds in O but not in I: it circles a tunnel, like the longitude of a torus, which goes around the hole. The handle loops span a g-dimensional half of the homology of the surface and the tunnel loops the other half. Compute() finds g short handle loops and g short tunnel loops spanning them, as closed vertex-edge paths on the mesh. They are what to cut to remove a handle or to fill a tunnel, e.g. to repair the topology of a scanned or reconstructed surface.
- Usage
for (
const auto &loop : ht.
handles)
for (int vi : loop) { ... m.vert[vi] ... }
MyEdgeMesh em;
Handle and tunnel loops of an orientable surface.
Definition: handle_tunnel_loops.h:142
std::vector< Loop > handles
the handle loops, around the handles
Definition: handle_tunnel_loops.h:162
static void LoopsToEdgeMesh(const MeshType &m, const std::vector< Loop > &loops, EdgeMeshType &em)
Append loops to the edge mesh em, one closed polyline each.
Definition: handle_tunnel_loops.h:224
void Compute(MeshType &m, const Param &par=Param())
Compute genus, handles and tunnels of m.
Definition: handle_tunnel_loops.h:175
See also the sample trimesh_handle_tunnel.cpp.
- Requirements
- Components: vertex coordinates and face vertex references only. The algorithm works on an internal copy with its own adjacency, so no adjacency has to be up to date and the mesh is not modified.
- The surface must be connected, orientable and edge-manifold. Small holes are allowed: each is closed with a fan around its centroid, and the loops are routed along the hole boundary instead of across it. Larger or knotted holes make the handle/tunnel classification depend on how they would be closed.
- A violated requirement throws vcg::MissingPreconditionException.
- Output
- genus, and the loops in handles and tunnels, as indices of mesh vertices. A sphere gives no loops.
- Algorithm
- It follows T. K. Dey, F. Fan and Y. Wang, "An efficient computation of handle and tunnel
loops via Reeb graphs", ACM TOG 32(4), 2013, without any volume mesh:
- the Reeb graph (tri::ReebGraph) of a random height function gives g loops on the surface, each with a dual loop in the level set just above its lowest point;
- the local shape at that lowest point tells whether each loop is non-trivial inside or outside; pushing each loop off the surface on that side gives bases of the homology of I and of O;
- inverting the matrix of linking numbers between the loops on the surface and the pushed ones turns the 2g loops into a handle basis and a tunnel basis;
- both bases are then tightened: among the loops made of an edge and two shortest paths to a few base points, the shortest independent ones of each family are kept, and the base points are moved onto them, until the total length stops decreasing for Param::patience rounds.
Tightening is a heuristic: the loops are short, not the shortest. It dominates the running time, which grows with the size and the genus of the mesh: about 20 s for genus 4 and 640K triangles, 10 s for genus 27 and 92K triangles, 5 minutes for genus 100 and 287K triangles.
Before tightening (Param::maxIter = 0) a basis element is a sum of several of the 2g loops and often has more than one component: each becomes its own Loop, so there can be more than g of them. Tightened elements are single loops.
- Local minima
- A basis keeps one loop per independent direction, the shortest found. Where to cut a complex object is better answered by every place where a loop is locally short: the several necks of one long handle, which are all the same class and of which a basis keeps one, and the loops around a few handles at once. With Param::localMinima, Compute() starts from Param::samples root vertices spread over the surface (farthest point sampling); from each, the shortest loop of each handle and tunnel class through it is a candidate. Candidates of one class sharing more than Param::overlap of their vertices (of the smaller) are one, the shorter kept; each is then tightened on its own, re-rooted at its vertices while that finds a shorter loop of its class, and the duplicates merged again. Of these, the local minima of length are kept: those that no nearby loop of their class undercuts, and that are separated from any shorter one by loops at least Param::persistence longer, so that a tube of constant section gives one loop and two necks give two. handles and tunnels are then these loops, shortest first, as many as Param::maxLoops allows.
