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

Home People Research Publications

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 this paper we strike a balance by computing topologically correct loops that are also geometrically relevant. Our algorithm 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. T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner. Computing Geometry-aware Handle and Tunnel Loops in 3D Models. SIGGRAPH 2008, to appear. HanTun software is available. 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 On Computing Handle and Tunnel Loops, (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) Our 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: Refinement 1: For a negative volume triangle, the pairing algorithm actually expands a loop till it reaches an unpaired edge. In refinement 1, we choose the loop when it lies completely on the surface for the first time. In this way, we get geometrically better loops. Handles (refinement 1) Tunnels (refinement 1) Refinement 2: Our refinement 2 is based on that a handle or tunnel loop is generated each time a cross section of the surface gets filled. In order to get loops of small size, we want the small cross sections getting filled first. To this end, we compute the geodesic size for all the volume triangles, and add them in increasing order of their geodesic size. Geodesic paths for blue triangles (delaunay mesh) Geodesic path for a blue triangle (iso-surface) Handles (refinement 1&2) Tunnels (refinement 1&2) Please find more examples in the video. The HanTun software based on this result is available.