dc.contributor.authorXin, Shi-Qing
dc.contributor.authorHe, Ying
dc.contributor.authorFu, Chi-Wing
dc.date.accessioned2013-10-14T08:25:22Z
dc.date.available2013-10-14T08:25:22Z
dc.date.copyright2012en_US
dc.date.issued2012
dc.identifier.citationXin, 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.
dc.identifier.issn1077-2626en_US
dc.identifier.urihttp://hdl.handle.net/10220/16491
dc.description.abstractClosed 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.en_US
dc.language.isoenen_US
dc.relation.ispartofseriesIEEE Transactions on Visualization and Computer Graphicsen_US
dc.rights© 2012 IEEEen_US
dc.subjectDRNTU::Engineering::Computer science and engineering::Computing methodologies::Symbolic and algebraic manipulation
dc.titleEfficiently computing exact geodesic loops within finite stepsen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Computer Engineeringen_US
dc.identifier.doihttp://dx.doi.org/10.1109/TVCG.2011.119


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record