  In this paper, we propose a parallel and scalable approach for geodesic
distance computation on triangle meshes. Our key observation is that the
recovery of geodesic distance with the heat method from [Crane et al. 2013] can
be reformulated as optimization of its gradients subject to integrability,
which can be solved using an efficient first-order method that requires no
linear system solving and converges quickly. Afterward, the geodesic distance
is efficiently recovered by parallel integration of the optimized gradients in
breadth-first order. Moreover, we employ a similar breadth-first strategy to
derive a parallel Gauss-Seidel solver for the diffusion step in the heat
method. To further lower the memory consumption from gradient optimization on
faces, we also propose a formulation that optimizes the projected gradients on
edges, which reduces the memory footprint by about 50%. Our approach is
trivially parallelizable, with a low memory footprint that grows linearly with
respect to the model size. This makes it particularly suitable for handling
large models. Experimental results show that it can efficiently compute
geodesic distance on meshes with more than 200 million vertices on a desktop PC
with 128GB RAM, outperforming the original heat method and other
state-of-the-art geodesic distance solvers.
