| Tunnels are very important topological features of surfaces. In computer graphics, processing tunnels is important for surface parameterization, feature identification, and topological simplification. Tunnels can be represented by loops, circles wrapping around the tunnels. In this dissertation, we will first focus on defining and computing a special set of non-trivial loops called handle and tunnel loops in surfaces embedded in 3D. We show that a closed surface M of genus g always has g handle and g tunnel loops induced by the embedding in 3D. We then propose two algorithms to compute them that are useful in practice: a linking-based algorithm and a persistence-based algorithm.;Our linking-based algorithm works on a class of shapes that retract to graphs. We characterize handle and tunnel loops by a linking condition with these graphs. These characterizations lead to algorithms for detection and generation of these loops. We also provide an implementation with applications in feature detection and topology simplification to show the effectiveness of this method.;Our second algorithm is a novel application of the concepts from persistent homology in computational topology. It computes topologically correct handle and tunnel loops that are also geometrically relevant. Compared with previous algorithms, this method works combinatorially and doesn't require any extra data structures. Moreover, it is time efficient and can be applied on a large class of shapes including Delaunay meshes, iso-surfaces, point clouds, 'knotted' surfaces, surfaces with boundaries and even non-manifolds. We later upgrade this algorithm based on some key observations. These modifications reduce the running time of the algorithm dramatically without sacrificing loop qualities.;Given a surface M, a cut locus with respect to a point p ∈ M is the set of points in M that have more than one equal shortest geodesic path from p. A cut locus contains most of the topological information of a surface. Given a point sample P of M embedded in any high dimensional Euclidean space, we consider using the cut locus to derive the topology of M from P. We propose a novel algorithm to compute a subsample P' of P, where P' approximates a cut locus of M. Since a cut locus of M has dimension lower than M. P' is much smaller in size than P. Thus computing the homology of M from P' becomes more efficient than computing it from P. |
