Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/96690
Title: Constant-time all-pairs geodesic distance query on triangle meshes
Authors: Xin, Shi-Qing
Ying, Xiang
He, Ying
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2012
Source: Xin, S. Q., Ying, X.,& He, Y. (2012). Constant-time all-pairs geodesic distance query on triangle meshes. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games - I3D '12.
Abstract: Computing discrete geodesics on polyhedral surfaces plays an important role in computer graphics. In contrast to the well-studied "single-source, all-destination" discrete geodesic problem, little progress has been reported to the all-pairs geodesic, i.e., computing the geodesic distance between arbitrary two points on the surface. To our knowledge, the existing all-pairs geodesic algorithms have very high computational cost, thus, can not be applied to real-world models, which usually contain thousands of vertices. In this paper, we propose an efficient algorithm to approximate the all-pairs geodesic on triangular meshes. The pre-processing step takes O(mn2 log n) time for the input mesh with n vertices and m samples, where m (<< n) is specified by the user, usually between a few hundred and several thousand. In the query step, our algorithm can compute the approximate geodesic distance between arbitrary pair of points (not necessarily mesh vertices) in O(1) time. Furthermore, the geodesic path and the geodesic distance field can be approximated in linear time. Both theoretical analysis and experimental results on real-world models demonstrate that our algorithm is efficient and accurate. We demonstrate the efficacy of our algorithm on the interactive texture mapping by using discrete exponential map.
URI: https://hdl.handle.net/10356/96690
http://hdl.handle.net/10220/12996
DOI: http://dx.doi.org/10.1145/2159616.2159622
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Conference Papers

Google ScholarTM

Check

Altmetric

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