Efficiently computing exact geodesic loops within finite steps
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/101681 http://hdl.handle.net/10220/16491 |
| _version_ | 1826116299183357952 |
|---|---|
| author | Xin, Shi-Qing He, Ying Fu, Chi-Wing |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Xin, Shi-Qing He, Ying Fu, Chi-Wing |
| author_sort | Xin, Shi-Qing |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T04:08:44Z |
| format | Journal Article |
| id | ntu-10356/101681 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:08:44Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/1016812020-05-28T07:17:35Z Efficiently computing exact geodesic loops within finite steps Xin, Shi-Qing He, Ying Fu, Chi-Wing School of Computer Engineering DRNTU::Engineering::Computer science and engineering::Computing methodologies::Symbolic and algebraic manipulation 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. 2013-10-14T08:25:22Z 2019-12-06T20:42:42Z 2013-10-14T08:25:22Z 2019-12-06T20:42:42Z 2012 2012 Journal Article 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. 1077-2626 https://hdl.handle.net/10356/101681 http://hdl.handle.net/10220/16491 10.1109/TVCG.2011.119 en IEEE Transactions on Visualization and Computer Graphics © 2012 IEEE |
| spellingShingle | DRNTU::Engineering::Computer science and engineering::Computing methodologies::Symbolic and algebraic manipulation Xin, Shi-Qing He, Ying Fu, Chi-Wing Efficiently computing exact geodesic loops within finite steps |
| title | Efficiently computing exact geodesic loops within finite steps |
| title_full | Efficiently computing exact geodesic loops within finite steps |
| title_fullStr | Efficiently computing exact geodesic loops within finite steps |
| title_full_unstemmed | Efficiently computing exact geodesic loops within finite steps |
| title_short | Efficiently computing exact geodesic loops within finite steps |
| title_sort | efficiently computing exact geodesic loops within finite steps |
| topic | DRNTU::Engineering::Computer science and engineering::Computing methodologies::Symbolic and algebraic manipulation |
| url | https://hdl.handle.net/10356/101681 http://hdl.handle.net/10220/16491 |
| work_keys_str_mv | AT xinshiqing efficientlycomputingexactgeodesicloopswithinfinitesteps AT heying efficientlycomputingexactgeodesicloopswithinfinitesteps AT fuchiwing efficientlycomputingexactgeodesicloopswithinfinitesteps |