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 |
id |
sg-ntu-dr.10356-85378 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-853782020-03-07T11:48:55Z Lightweight preprocessing and fast query of geodesic distance via proximity graph Xin, Shiqing Wang, Wenping He, Ying Zhou, Yuanfeng Chen, Shuangmin Tu, Changhe Shu, Zhenyu School of Computer Science and Engineering Proximity Graph Geodesic Distance Engineering::Computer science and engineering 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. 2019-07-09T08:22:38Z 2019-12-06T16:02:44Z 2019-07-09T08:22:38Z 2019-12-06T16:02:44Z 2018 Journal Article 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 0010-4485 https://hdl.handle.net/10356/85378 http://hdl.handle.net/10220/49218 10.1016/j.cad.2018.04.021 en Computer-Aided Design © 2018 Elsevier Ltd. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Proximity Graph Geodesic Distance Engineering::Computer science and engineering |
spellingShingle |
Proximity Graph Geodesic Distance Engineering::Computer science and engineering Xin, Shiqing Wang, Wenping He, Ying Zhou, Yuanfeng Chen, Shuangmin Tu, Changhe Shu, Zhenyu Lightweight preprocessing and fast query of geodesic distance via proximity graph |
description |
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. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Xin, Shiqing Wang, Wenping He, Ying Zhou, Yuanfeng Chen, Shuangmin Tu, Changhe Shu, Zhenyu |
format |
Article |
author |
Xin, Shiqing Wang, Wenping He, Ying Zhou, Yuanfeng Chen, Shuangmin Tu, Changhe Shu, Zhenyu |
author_sort |
Xin, Shiqing |
title |
Lightweight preprocessing and fast query of geodesic distance via proximity graph |
title_short |
Lightweight preprocessing and fast query of geodesic distance via proximity graph |
title_full |
Lightweight preprocessing and fast query of geodesic distance via proximity graph |
title_fullStr |
Lightweight preprocessing and fast query of geodesic distance via proximity graph |
title_full_unstemmed |
Lightweight preprocessing and fast query of geodesic distance via proximity graph |
title_sort |
lightweight preprocessing and fast query of geodesic distance via proximity graph |
publishDate |
2019 |
url |
https://hdl.handle.net/10356/85378 http://hdl.handle.net/10220/49218 |
_version_ |
1681036313528107008 |