Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAdikusuma, Yohanes Yudhien_US
dc.contributor.authorDu, Jieen_US
dc.contributor.authorFang, Zhengen_US
dc.contributor.authorHe, Yingen_US
dc.identifier.citationAdikusuma, 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-.
dc.description.abstractThis 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
dc.description.sponsorshipMinistry of Education (MOE)en_US
dc.relation.ispartofComputer-Aided Designen_US
dc.rights© 2022 Elsevier Ltd. All rights reserved.en_US
dc.subjectEngineering::Computer science and engineeringen_US
dc.titleAn accuracy controllable and memory efficient method for computing high-quality geodesic distances on triangle meshesen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.subject.keywordsDiscrete Geodesicsen_US
dc.subject.keywordsTriangle Meshesen_US
dc.description.acknowledgementWe thank the anonymous reviewers for their constructive comments. This project was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG20/20) and Tier 2 (MOE-T2EP20220-0005).en_US
item.fulltextNo 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.