Computing Geometry-aware Handle and Tunnel Loops in 3D Models

Many applications such as topology repair, model editing, surface parameterization, and feature recognition benefit from computing loops on surfaces that wrap around their `handles' and `tunnels'. Computing such loops while optimizing their geometric lengths is difficult. On the other hand, computing such loops without considering geometry is easy but may not be very useful. In our research, we strike a balance by computing topologically correct loops that are also geometrically relevant. We have developed several algorithms along this direction which are published in the following papers.

[DLS07] T. K. Dey, K. Li, and J. Sun. On computing handle and tunnel loops. IEEE Proc. Internat. Conf. Cyberworlds (NASAGEM workshop) 2007.
[DLSC08] T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner. Computing Geometry-aware Handle and Tunnel Loops in 3D Models. SIGGRAPH 2008.
[DFW13] T. K. Dey, F. Fan, and Y. Wang. An efficient computation of handle and tunnel loops via Reeb graphs. SIGGRAPH 2013.

HanTun software based on the [DLSC08] and ReebHanTun software based on [DFW13] will be available soon.

This line of work has been supported by NSF grants CCF-0915996, CCF-1064416

Computing Handle and Tunnel Loops via Persistence ([DLSC08])

Our algorithm in this paper is a novel application of the concepts from topological persistence introduced recently in computational topology. The usability of the computed loops is demonstrated with some examples in feature identification and topology simplification. Our algorithm computes a set of non-trivial loops called Handle and Tunnel loops in 3D models and iso-surfaces in volume data. The concept of handle and tunnel loops was introduced in an earlier paper [DLS07] (also see Web-page). The input to our algorithm are a closed surface mesh and associated volume mesh. For a surface mesh, we use DelPSC software built in our group to get the volume mesh. While for the case of iso-surfaces, the volume mesh is obtained almost freely.


Handles and tunnels on Botijo and Atom	Input surfaces Botijo and Atom


Volumes of Botijo (obtained from DelPSC)	Volumes of Atom (iso-surface)

This method is based on the Topological Persistence ([Edelsbrunner, Letscher, Zomorodian 2002]) which pairs simplices in a filtration of the complex. A positive 1-simplex simplex which create a cycle is paired with a negative 2-simplex which kills a cycle. In our topological algorithm, we first add all the vertices on the surface, then the edges. Pairing algorithm will finds all the positive edges and negative ones. All surface surface triangles are then added to pair with the positive edges. Some positive edges are left unpaired. These unpaired edges will be paired with the volume triangles later to get handle and tunnel loops.

Next, we add triangles from the volume mesh. For handle loops, we add triangles from inside. A handle loop is generated when a negative triangle from inside is paired with an unpaired edge on the surface. Similarly, for tunnel loops, we add triangles from outside. A tunnel loop is generated each time a negative triangle from outside is paired with an unpaired positive edge on the surface.

Unpaired positive edges on surface Topological handles Topological tunnels

This topological algorithm produces topologically correct handle and tunnel loops but may not be geometrically meaningful. We then propose two refinements to get geometrically relevant handle and tunnel loops:


Handles after refinement 1(lower figure) & refinement 2 (upper figure)	Tunnels after refinement 1(lower figure) & refinement 2 (upper figure)

Please find more examples in the video.

The HanTun software based on this result is available.

Computing Handle and Tunnel Loops via Reeb Graphs ([DFW13])

We developed another efficient algorithm for computing handle and tunnel loops for 3D models in this paper. This algorithm no longer requires the tessellations of the interior and exterior bounded the closed surface. Instead, it uses the concepts of Reeb graph and linking number. As a result, this algorithm is significantly faster than previous methods ( [DLS07] and [DLSC08]).

Our algorithm is illustrated below.


(1)The input model and a random height function;		(2) Compute the Reeb Graph with respect to the height function;		(3) Map loops in the Reeb Graph back to the mesh and compute the dual levelset loop (see the loop in the highlighted plane) for each loop mapped back to the mesh;		(4) Obtain initial handle and tunnel loops as linear combinations of loops on the mesh and their dual levelset loops by linking number computation;		(5) Shorten the initial handle and tunnel loops using the concept of homology annotation ([BCCDW12]);

Our algorithm is robust against non-uniform triangulations and noises.


Non-uniform mesh	Mesh without noises	Mesh with noises

The ReebHanTun software based on this result is available.