| 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
without considering geometry is easy but may not be very useful. In our
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.
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.
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:
Please find more examples in the video.
The HanTun software based on this result is available.
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.
Our algorithm is robust against non-uniform triangulations and noises.
The ReebHanTun software based on this result is available.