Lightweight preprocessing and fast query of geodesic distance via proximity graph. (September 2018)

• Record Type: Journal Article
• Authors: Xin, Shiqing; Wang, Wenping; He, Ying; Zhou, Yuanfeng; Chen, Shuangmin; Tu, Changhe; Shu, Zhenyu
• Is Part Of: Computer aided design. Volume 102(2018)
• Page Start: 128
• Page End: 138
• Publication Date: 2018-09
• Subjects: Proximity graph -- Geodesic distance -- Real-time interaction -- Exponential map -- Spline curves; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2018.04.021
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Computing geodesic distance on a mesh surface S 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 G 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 s and t, we augment the proximity graph G by adding s and t on-the-fly, and then use the shortest path between s and t on the augmented proximity graph to approximate the exact geodesic path between s and t . 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. Graphical abstract: Highlights: A method is proposed to query about geodesic distances accurately and efficiently. A proximity graph is built to encode the exact geodesic distance. Applicable for discrete exponential map and interactive design of spline curves.