Please use this identifier to cite or link to this item:
Title: Efficiently computing exact geodesic loops within finite steps
Authors: Xin, Shi-Qing
He, Ying
Fu, Chi-Wing
Keywords: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Symbolic and algebraic manipulation
Issue Date: 2012
Source: Xin, S., He, Y., & Fu, C. (2012). Efficiently computing exact geodesic loops within finite steps. IEEE transactions on visualization and computer graphics, 18(6), 879-889.
Series/Report no.: IEEE Transactions on Visualization and Computer Graphics
Abstract: Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.
ISSN: 1077-2626
DOI: 10.1109/TVCG.2011.119
Rights: © 2012 IEEE
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.