Please use this identifier to cite or link to this item:
|Title:||Constant-time all-pairs geodesic distance query on triangle meshes||Authors:||Xin, Shi-Qing
|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
|DOI:||10.1145/2159616.2159622||Fulltext Permission:||none||Fulltext Availability:||No Fulltext|
|Appears in Collections:||SCSE Conference Papers|
Updated on Jul 16, 2020
Updated on Jan 17, 2021
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.