Please use this identifier to cite or link to this item:
Title: Lightweight preprocessing and fast query of geodesic distance via proximity graph
Authors: Xin, Shiqing
Wang, Wenping
He, Ying
Zhou, Yuanfeng
Chen, Shuangmin
Tu, Changhe
Shu, Zhenyu
Keywords: Proximity Graph
Geodesic Distance
Engineering::Computer science and engineering
Issue Date: 2018
Source: Xin, S., Wang, W., He, Y., Zhou, Y., Chen, S., Tu, C., & Shu, Z. (2018). Lightweight preprocessing and fast query of geodesic distance via proximity graph. Computer-Aided Design, 102, 128-138. doi:10.1016/j.cad.2018.04.021
Series/Report no.: Computer-Aided Design
Abstract: Computing geodesic distance on a mesh surface efficiently and accurately is a central task in numerous computer graphics applications. In order to deal with high-resolution mesh surfaces, a lightweight preprocessing is a proper choice to make a balance between query accuracy and speed. In the preprocessing stage, we build a proximity graph with regard to a set of sample points and keep the exact geodesic distance between any pair of nearby sample points. In the query stage, given two query points and , we augment the proximity graph by adding and on-the-fly, and then use the shortest path between and on the augmented proximity graph to approximate the exact geodesic path between and . We establish an empirical relationship between the number of samples and expected accuracy (measured in relative error), which facilitates fast and accurate query of geodesic distance with a lightweight processing cost. We exhibit the uses of the new approach in two applications—real-time computation of discrete exponential map for texture mapping and interactive design of spline curves on surfaces.
ISSN: 0010-4485
DOI: 10.1016/j.cad.2018.04.021
Rights: © 2018 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Jan 25, 2023

Web of ScienceTM
Citations 50

Updated on Jan 31, 2023

Page view(s)

Updated on Jan 31, 2023

Google ScholarTM




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