Geodesics in Heat
arXiv:1204.6216 · doi:10.1145/2516971.2516977
Abstract
We introduce the heat method for computing the shortest geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The method represents a significant breakthrough in the practical computation of distance on a wide variety of geometric domains, since the resulting linear systems can be prefactored once and subsequently solved in near-linear time. In practice, distance can be updated via the heat method an order of magnitude faster than with state-of-the-art methods while maintaining a comparable level of accuracy. We provide numerical evidence that the method converges to the exact geodesic distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where more regularity is required.
References in corpus (1)
Cited by in corpus (53)
- Iso-level tool path planning for free-form surfaces
- DNF-Net: a Deep Normal Filtering Network for Mesh Denoising
- Magnetic-field modeling with surface currents: Physical and computational principles of bfieldtools
- DeltaConv: Anisotropic Operators for Geometric Deep Learning on Point Clouds
- A Survey of Algorithms for Geodesic Paths and Distances
- NASA: Neural Articulated Shape Approximation
- Tangential Errors of Tensor Surface Finite Elements
- A minimalistic approach for fast computation of geodesic distances on triangular meshes
- Ground Metric Learning on Graphs
- RigNet: Neural Rigging for Articulated Characters
- The Hierarchical Subspace Iteration Method for Laplace--Beltrami Eigenproblems
- A geometric approach to non-linear correlations with intrinsic scatter
- PrAGMATiC: a Probabilistic and Generative Model of Areas Tiling the Cortex
- Extracting a functional representation from a dictionary for non-rigid shape matching
- A Convex Optimization Framework for Regularized Geodesic Distances
- Learning the Geodesic Embedding with Graph Neural Networks
- Simplicial Complex Representation Learning
- Bayesian Inference of Bijective Non-Rigid Shape Correspondence
- IntrA: 3D Intracranial Aneurysm Dataset for Deep Learning
- Geodesic Distance Field-based Curved Layer Volume Decomposition for Multi-Axis Support-free Printing
- 3D-TalkEmo: Learning to Synthesize 3D Emotional Talking Head
- Learning Geodesic-Aware Local Features from RGB-D Images
- Geodesic Distance Function Learning via Heat Flow on Vector Fields
- Multiscale Mesh Deformation Component Analysis with Attention-based Autoencoders
- Solving variational problems and partial differential equations that map between manifolds via the closest point method
- Entropic Wasserstein Gradient Flows
- Differentiable Geodesic Distance for Intrinsic Minimization on Triangle Meshes
- Extracting Deformation-Aware Local Features by Learning to Deform
- Mesh-based Autoencoders for Localized Deformation Component Analysis
- Characterization of surface motion patterns in highly deformable soft tissue organs from dynamic MRI: An application to assess 4D bladder motion
- Cobiveco: Consistent biventricular coordinates for precise and intuitive description of position in the heart -- with MATLAB implementation
- Intrinsic-Extrinsic Preserved GANs for Unsupervised 3D Pose Transfer
- Path Planning with Divergence-Based Distance Functions
- DecoSurf: Recursive Geodesic Patterns on Triangle Meshes
- Learning Manifold Implicitly via Explicit Heat-Kernel Learning
- A Unified Definition and Computation of Laplacian Spectral Distances
- Parallel and Scalable Heat Methods for Geodesic Distance Computation
- Steklov Spectral Geometry for Extrinsic Shape Analysis
- Faithful Euclidean Distance Field from Log-Gaussian Process Implicit Surfaces
- Hierarchical Neural Implicit Pose Network for Animation and Motion Retargeting
- Geodesics using Waves: Computing Distances using Wave Propagation
- Multi-Axis Support-Free Printing of Freeform Parts with Lattice Infill Structures
- PageRank and The K-Means Clustering Algorithm
- Efficient Inter-Geodesic Distance Computation and Fast Classical Scaling
- Hybrid Function Representation for Heterogeneous Objects
- Efficient, sparse representation of manifold distance matrices for classical scaling
- Varadhan Asymptotics for the Heat Kernel on Finite Graphs
- Deep Eikonal Solvers
- Manifold-valued subdivision schemes based on geodesic inductive averaging
- Computing the Cut Locus of a Riemannian Manifold via Optimal Transport
- GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries
- Towards Fine-grained 3D Face Dense Registration: An Optimal Dividing and Diffusing Method
- Evaluations of The Hierarchical Subspace Iteration Method