GeodesicEmbedding (GE): a high-dimensional embedding approach for fast geodesic distance queries

Xia, Qianwei, Zhang, Juyong, Fang, Zheng, Li, Jin, Zhang, Mingyue, Deng, Bailin ORCID: https://orcid.org/0000-0002-0158-7670 and He, Ying 2022. GeodesicEmbedding (GE): a high-dimensional embedding approach for fast geodesic distance queries. IEEE Transactions on Visualization and Computer Graphics 28 (12) , pp. 4930-4939. 10.1109/TVCG.2021.3109975

PDF - Accepted Post-Print Version Download (7MB)

Abstract

In this paper, we develop a novel method for fast geodesic distance queries. The key idea is to embed the mesh into a high-dimensional space, such that the Euclidean distance in the high-dimensional space can induce the geodesic distance in the original manifold surface. However, directly solving the high-dimensional embedding problem is not feasible due to the large number of variables and the fact that the embedding problem is highly nonlinear. We overcome the challenges with two novel ideas. First, instead of taking all vertices as variables, we embed only the saddle vertices, which greatly reduces the problem complexity. We then compute a local embedding for each non-saddle vertex. Second, to reduce the large approximation error resulting from the purely Euclidean embedding, we propose a cascaded optimization approach that repeatedly introduces additional embedding coordinates with a non-Euclidean function to reduce the approximation residual. Using the precomputation data, our approach can determine the geodesic distance between any two vertices in near-constant time. Computational testing results show that our method is more desirable than previous geodesic distance queries methods.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
Publisher:	Institute of Electrical and Electronics Engineers
ISSN:	1077-2626
Date of First Compliant Deposit:	31 August 2021
Date of Acceptance:	30 August 2021
Last Modified:	29 Nov 2024 18:12
URI:	https://orca.cardiff.ac.uk/id/eprint/143769

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item