Please use this identifier to cite or link to this item:
Title: An accuracy controllable and memory efficient method for computing high-quality geodesic distances on triangle meshes
Authors: Adikusuma, Yohanes Yudhi
Du, Jie
Fang, Zheng
He, Ying
Keywords: Engineering::Computer science and engineering
Issue Date: 2022
Source: Adikusuma, Y. Y., Du, J., Fang, Z. & He, Y. (2022). An accuracy controllable and memory efficient method for computing high-quality geodesic distances on triangle meshes. Computer-Aided Design, 150, 103333-.
Project: RG20/20
Journal: Computer-Aided Design
Abstract: This paper presents a new method for computing approximate geodesic distances and paths on triangle meshes. Our method combines two state-of-the-art discrete geodesic methods, which are discrete geodesic graphs (DGG) and vertex-oriented triangle propagation (VTP), so that it allows the user to specify the desired accuracy using a single parameter ɛ. The method, called DGG-VTP, extends the conventional window propagation framework by monitoring the accuracy of the computed distances so that propagation can terminate immediately when the desired accuracy is reached. It is worth noting that for robustness consideration, tiny windows with length less than a threshold (usually, between 10−7 and 10−6) are discarded in the implementation of the existing exact algorithms, such as the Mitchel–Mount–Papadimitriou (MMP) algorithm, the Chen–Han (CH) algorithm and their many variants. By setting the accuracy parameter ɛ∈[10−7,10−6], our method can produce results with comparable accuracy to VTP, while being 3–40 times faster and consuming much less memory. Furthermore, the performance of our method is less sensitive to mesh tessellation than what VTP does. Our method empirically produces [Formula presented] windows and scales well to deal with large-scale models. Though the parameter ɛ in DGG-VTP is not a guaranteed error bound, it acts as an intuitive guide for the user to set the desired accuracy. Extensive evaluations demonstrate the effectiveness of our accuracy control: given a parameter ɛ∈[10−7,10−4], 99% of the computed distances have error less than the accuracy parameter. The features of predicable accuracy and computational efficiency distinguish DGG-VTP from the existing approximation methods, and make it an alternative to exact methods in computing accurate geodesic distances on large-scale mesh models. We also develop a parallel version of DGG-VTP on multi-core CPUs, which runs up to 60× faster than the existing parallel VTP algorithm with comparable accuracy under single floating point precision setting. The source code is available at
ISSN: 0010-4485
DOI: 10.1016/j.cad.2022.103333
Schools: School of Computer Science and Engineering 
Rights: © 2022 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Nov 28, 2023

Page view(s)

Updated on Dec 2, 2023

Google ScholarTM




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