Lightweight preprocessing and fast query of geodesic distance via proximity graph
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 prepr...
Saved in:
Main Authors: | , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2019
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/85378 http://hdl.handle.net/10220/49218 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | 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. |
---|