GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries

Qianwei Xia, Juyong Zhang, Zheng Fang, Jin Li, Mingyue Zhang, Bailin Deng, Ying He

TL;DR

GeodesicEmbedding (GE) is a novel framework that enables near-constant time ($O(1)$) geodesic distance queries on 3D meshes by embedding vertices into a high-dimensional space. By focusing specifically on "saddle vertices" and employing a unique cascaded non-Euclidean optimization, the method achieves significantly higher accuracy and lower storage costs than previous state-of-the-art embedding techniques.

What Problem Does This Paper Address?

Calculating the geodesic distance—the shortest path between two points on a curved surface—is a fundamental task in 3D shape analysis, used in everything from symmetry detection to texture mapping. While we have efficient algorithms for "single-source-all-destinations" (finding the distance from one point to every other point), "geodesic distance queries" (GDQ)—finding the distance between two arbitrary points on the fly—remain a challenge.

The naive solution is to precompute and store all pairwise distances, but for a mesh with $N$ vertices, this requires $O(N^2)$ space, which is impossible for high-resolution models. Existing alternatives either suffer from high approximation errors (like Euclidean Embedding) or are too slow for real-time applications (like graph-based searches). The authors seek a "best of both worlds" solution: a method that is as fast as a simple lookup but as accurate as a complex geometric calculation.

Methods

The authors introduce two key innovations to make high-dimensional embedding practical for 3D meshes:

  1. Saddle Vertex Embedding: Instead of trying to embed every single vertex (which involves too many variables and high nonlinearity), the authors only embed saddle vertices (vertices with negative Gaussian curvature). Geodesic paths on discrete surfaces only "bend" or branch at these saddle points. By treating saddle vertices as the "backbone" of the surface, they reduce the problem size significantly. Non-saddle vertices are then handled via a local embedding that links them to their nearest saddle neighbors.
  2. Cascaded Non-Euclidean Embedding: Standard Multidimensional Scaling (MDS) tries to fit geodesic distances into a purely Euclidean space. However, geodesic distances are intrinsically non-Euclidean, leading to an "error floor" that more dimensions can't fix. The authors propose a cascaded approach that adds extra dimensions governed by a non-Euclidean distance function: $$f(P_i, P_j) = \sqrt{\|q_i - q_j\|^2 - \|s_i - s_j\|^2 + \|t_i - t_j\|^2}$$ This allows the model to iteratively "correct" the residuals left behind by the initial Euclidean fit, drastically improving accuracy.

Datasets

The researchers evaluated their method on a wide variety of standard 3D mesh models, including:

  • Classic benchmarks: The Stanford Bunny, Armadillo, Dragon, and Lucy.
  • Diverse geometries: Humanoid figures (Sumotori, Kangaroo), organic shapes (Elephant, Aligator), and complex topological objects (TwoHeadedBunny).
  • Ground Truth: Exact geodesic distances for evaluation were computed using the VTP (Virtual Tripod) method, a state-of-the-art exact geodesic algorithm.

Key Insights and Ideas

  • The Sparsity of Curvature: Most vertices on a typical mesh are "spherical" or flat; only a fraction are saddles. Leveraging this geometric property allows for a massive reduction in computational complexity without losing the "skeleton" of the distance field.
  • Beyond Euclidean Space: The "aha moment" here is realizing that the approximation error in previous embedding methods wasn't just due to low dimensionality, but due to the nature of the space. By introducing non-Euclidean terms in a cascaded fashion, they can squeeze out errors that standard MDS simply cannot reach.
  • Hybrid Architecture: The method effectively combines the topological strengths of the Saddle Vertex Graph (SVG) with the speed of High-Dimensional Embedding, creating a hybrid that outperforms either method used in isolation.

Key Results

  • Speed: Once precomputed, the query time for any two points is roughly 0.02ms, which is essentially near-constant time. This is approximately 100x faster than the previous SVG-based methods.
  • Accuracy: The mean relative error is consistently below 1% (e.g., 0.73% for the Bunny model). In contrast, previous embedding methods like EMM typically hover around 5% error.
  • Storage: The method is highly memory-efficient, requiring only $O(N)$ storage for the embedding coordinates, making it feasible for large-scale models where $N^2$ storage would fail.
  • Visual Fidelity: The "iso-contours" (lines of equal distance) produced by this method closely match the exact ground truth, maintaining the expected geometric shape of the distance field better than spectral or earth-mover distance alternatives.

Limitations and Future Work

  • Smoothness: While accurate, the resulting distance function is not perfectly smooth, and its level sets can appear slightly "noisy" compared to exact methods.
  • Metric Properties: The current formulation does not strictly guarantee that the resulting distance function satisfies all properties of a mathematical metric (such as the triangle inequality).
  • Preprocessing Cost: The initial optimization to find the embedding is still computationally heavy for very large meshes, though this is a one-time cost.
  • Saddle Dependency: The performance is tied to the distribution of saddle vertices. Meshes with extremely few saddle vertices might require a different strategy or a denser sampling of "relay" points.

Summary updated

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.
BibTeX
@article{xia2022geodesicembedding,
  author = {Qianwei Xia and Juyong Zhang and Zheng Fang and Jin Li and Mingyue Zhang and Bailin Deng and Ying He},
  title = {{GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2022},
  doi = {10.1109/tvcg.2021.3109975},
}

Loading related content...

Figure