Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces

We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and ε>0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show...

Full description

Saved in:
Bibliographic Details
Main Authors: Wang, Xiaoning, Fang, Zheng, Wu, Jiajun, Xin, Shi-Qing, He, Ying
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2018
Subjects:
Online Access:https://hdl.handle.net/10356/87204
http://hdl.handle.net/10220/44328
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-87204
record_format dspace
spelling sg-ntu-dr.10356-872042020-03-07T11:48:55Z Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces Wang, Xiaoning Fang, Zheng Wu, Jiajun Xin, Shi-Qing He, Ying School of Computer Science and Engineering Geodesic Distances Polyhedral Surfaces We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and ε>0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has O(n/sqrt(ε)) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error O(ε). Computational results show that the actual error is less than 0.6ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) – another graph based method for discrete geodesics – in terms of graph size, accuracy control and runtime performance. MOE (Min. of Education, S’pore) Accepted version 2018-01-19T04:30:47Z 2019-12-06T16:37:11Z 2018-01-19T04:30:47Z 2019-12-06T16:37:11Z 2017 Journal Article Wang, X., Fang, Z., Wu, J., Xin, S.-Q., & He, Y. (2017). Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces. Computer Aided Geometric Design, 52-53, 262-284. 0167-8396 https://hdl.handle.net/10356/87204 http://hdl.handle.net/10220/44328 10.1016/j.cagd.2017.03.010 en Computer Aided Geometric Design © 2017 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Computer Aided Geometric Design, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1016/j.cagd.2017.03.010]. 19 p. application/pdf
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Geodesic Distances
Polyhedral Surfaces
spellingShingle Geodesic Distances
Polyhedral Surfaces
Wang, Xiaoning
Fang, Zheng
Wu, Jiajun
Xin, Shi-Qing
He, Ying
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
description We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and ε>0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has O(n/sqrt(ε)) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error O(ε). Computational results show that the actual error is less than 0.6ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) – another graph based method for discrete geodesics – in terms of graph size, accuracy control and runtime performance.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Wang, Xiaoning
Fang, Zheng
Wu, Jiajun
Xin, Shi-Qing
He, Ying
format Article
author Wang, Xiaoning
Fang, Zheng
Wu, Jiajun
Xin, Shi-Qing
He, Ying
author_sort Wang, Xiaoning
title Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
title_short Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
title_full Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
title_fullStr Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
title_full_unstemmed Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
title_sort discrete geodesic graph (dgg) for computing geodesic distances on polyhedral surfaces
publishDate 2018
url https://hdl.handle.net/10356/87204
http://hdl.handle.net/10220/44328
_version_ 1681036459040047104