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.
Introduction
Calculating the geodesic distance—the shortest path between two points on a curved surface—is a fundamental task in 3D shape analysis, essential for applications ranging from symmetry detection to texture mapping. While efficient algorithms exist for "single-source-all-destinations" scenarios, performing "geodesic distance queries" (GDQ) between two arbitrary points in real-time remains a significant challenge.
The naive approach of precomputing all pairwise distances requires $O(N^2)$ space, which is prohibitive for high-resolution models. Existing alternatives often compromise either on accuracy (e.g., standard Euclidean Embedding) or speed (e.g., graph-based searches). GeodesicEmbedding (GE) addresses this by enabling near-constant time ($O(1)$) queries with high accuracy and low storage costs.
Methodology: Saddle Vertices and Cascaded Embedding
The GE framework introduces two primary innovations to make high-dimensional embedding practical for complex 3D meshes.
1. Saddle Vertex Embedding
Rather than embedding every vertex, which is computationally expensive and highly non-linear, the method focuses on saddle vertices (vertices with negative Gaussian curvature). Geodesic paths on discrete surfaces typically "bend" or branch at these points. By treating saddle vertices ($V_S$) as the "backbone" of the surface, the problem complexity is drastically reduced. Non-saddle vertices ($V_N$) are then handled via a local embedding (LE) that links them to their nearest saddle neighbors.
2. Cascaded Non-Euclidean Optimization
Standard Multidimensional Scaling (MDS) attempts to fit geodesic distances into a purely Euclidean space. However, geodesic distances are intrinsically non-Euclidean, leading to an "error floor" that cannot be overcome simply by adding dimensions. GE employs a cascaded approach that iteratively introduces additional dimensions governed by a non-Euclidean distance function. This allows the model to "correct" the residuals left by the initial Euclidean fit, significantly improving accuracy.
Key Results and Performance
The researchers evaluated GE on a diverse set of standard 3D models, including the Stanford Bunny, Armadillo, and various humanoid and organic shapes. Ground truth distances were established using the state-of-the-art VTP (Virtual Tripod) method.
Accuracy and Scalability
The cascaded refinement strategy proves highly effective. As shown in the performance metrics, while standard Euclidean embedding hits a plateau in accuracy, the cascaded approach continues to reduce the mean relative error as more dimensions are added, typically reaching below 1%.
Efficiency
- Query Speed: Once precomputed, the query time for any two points is approximately 0.02ms, roughly 100x faster than previous graph-based methods.
- Storage: The method is memory-efficient, requiring only $O(N)$ storage for embedding coordinates, making it suitable for large-scale models.
- Visual Fidelity: The resulting distance fields maintain high geometric integrity, with iso-contours closely matching ground truth calculations.
Conclusion
GeodesicEmbedding (GE) represents a significant step forward in geodesic distance estimation. By leveraging the geometric sparsity of saddle vertices and introducing a non-Euclidean cascaded optimization, it achieves a "best of both worlds" scenario: the speed of a simple lookup with the accuracy required for high-fidelity 3D analysis. While future work may focus on improving the smoothness of the distance function and ensuring strict metric properties, GE currently offers a highly desirable solution for real-time 3D applications.
Summary updated