Discrete Geodesics | Ying He

Discrete Geodesics and Intrinsic Geometry Processing

← Back to Home

Computing geodesic distances and paths on polygonal surfaces is a central problem in geometric modeling and discrete differential geometry, underpinning applications in shape analysis, parameterization, correspondence, simulation, and intrinsic surface editing. Since 2011, my team has developed a sustained and comprehensive research program that advances the discrete geodesic problem in terms of efficiency, accuracy, robustness, and scalability. Our work tackles long-standing computational bottlenecks and structural limitations of classical methods, reframing geodesic computation from a costly source-dependent procedure into reusable and scalable geometric infrastructure.

This research has progressed along four complementary methodological directions: (i) graph-based precomputation methods; (ii) wavefront propagation algorithms; (iii) variational and PDE-based formulations; and (iv) geodesic embeddings. Beyond distance computation itself, these frameworks enable a broad spectrum of intrinsic geometry processing tasks, providing efficient and reliable solutions to problems that fundamentally depend on surface-intrinsic structure.

Graph-based Pre-computation Methods

To accelerate repeated geodesic distance and path queries on triangle meshes, we developed compact intrinsic graph structures, including Saddle Vertex Graphs and later Discrete Geodesic Graphs, which helped change the way people think about shortest-path computation on surfaces. These works uncovered a structural property of the discrete geodesic problem that fundamentally distinguishes it from its smooth counterpart. On polyhedral surfaces, shortest paths exhibit a strong saddle-structured locality: a global geodesic can be decomposed into a sequence of direct (vertex-free) geodesic segments whose endpoints lie at saddle vertices.

This observation challenges the prevailing assumption that each geodesic query must be answered via source-dependent wavefront propagation. Instead, it reframes global geodesic computation as a precomputable geometric data structure: the heavy geometric processing is performed once during preprocessing, and subsequent online queries reduce to efficient shortest-path searches on a sparse intrinsic graph. In this way, geodesics move from a per-query computational procedure to reusable geometric infrastructure.

A key practical advantage of SVG and DGG is that they are not penalized by fine geometric detail in the way many PDE- or optimization-based approximations are. Such approximations often behave like low-order discretizations and may require very fine resolution to faithfully track sharp features and small-scale structures. In contrast, SVG and DGG explicitly exploit geometric detail: richer geometry typically introduces more saddle vertices, which shortens direct geodesic segments and makes the problem increasingly local. This enhanced locality improves both construction efficiency and approximation quality. As a result, SVG/DGG can become faster to build and more accurate on detailed meshes rather than slower or less stable. This precomputation paradigm subsequently inspired later developments in geodesic embeddings and learning-based intrinsic representations (TVCG 2022; NeurIPS 2023; AAAI 2026), extending the idea of intrinsic structure as reusable infrastructure into modern geometric learning pipelines.

Wavefront Propagation Algorithms

Wavefront propagation is a classical computational geometry technique for solving the discrete geodesic problem. By partitioning mesh edges into smaller intervals (called windows), the method propagates these windows from source vertices in a Dijkstra-style manner across the surface. To improve efficiency and scalability, we developed a series of high-performance techniques, including efficient window clipping and scheduling strategies (FWP, TVCG 2015), parallel propagation algorithms (PCH, TOG 2014; AWP, CAD 2019), and accuracy-controlled propagation schemes (approximate VTP, CAD 2021; DGG-VTP, CAD 2022). These works address the classical combinatorial explosion inherent in window propagation and enable scalable exact geodesic computation on large meshes. Beyond distance computation, we further extended this framework to support related geometric structures, including geodesic offsets (CAD 2011), geodesic loops (TVCG 2012), and geodesic ridge curves (CAGD 2025).

Variational and PDE-Based Methods

Beyond triangle meshes, we developed variational and PDE-based frameworks for computing geodesics on broader geometric domains, including point clouds, implicit surfaces, and parametric surfaces. By formulating geodesic computation as g optimization problems or partial differential equations, these methods extend intrinsic geometry processing beyond piecewise-linear meshes and enable a wider range of applications.

Geodesic Embeddings

Following the same “precompute once, query fast” philosophy, we also explored intrinsic embeddings that map a surface into a higher-dimensional Euclidean space, where simple Euclidean distances approximate intrinsic geodesic distances. GeodesicEmbedding (TVCG 2022) constructs such a high-dimensional embedding for fast distance queries and is conceptually rooted in the saddle-vertex decomposition underlying SVG/DGG: rather than performing source-dependent wavefront propagation, the intrinsic structure of the surface is encoded once into a reusable global representation. Building on this idea, we extended intrinsic embeddings to scalable and differentiable learning-based formulations. NeuroGF (NeurIPS 2023) learns a compact neural representation that enables efficient geodesic distance and path queries across collections of shapes, making intrinsic computation compatible with modern 3D deep learning pipelines. LiteGE (AAAI 2026) further advances this direction with a lightweight embedding architecture that supports efficient geodesic computation and non-isometric shape correspondence, combining speed, compactness, and cross-shape generalization.

Intrinsic Geometry Processing and Applications

Discrete geodesics serve as a fundamental building block for constructing intrinsic spatial data structures, including Voronoi diagrams, Delaunay triangulations, and centroidal Voronoi tessellations. Leveraging our efficient geodesic solvers, we developed a series of intrinsic geometry processing algorithms for both 3D meshes and 2D images. In this context, images can be interpreted as 2-manifolds embedded in a higher-dimensional Euclidean space (e.g., uv + rgb), allowing intrinsic geometric formulations to naturally extend to image segmentation and superpixel computation.

Copyright Notice: These materials are provided for academic dissemination only. Copyright remains with the authors or respective copyright holders. Reproduction or redistribution may require prior permission.