Tao Jiong, Zhang Juyong, Deng Bailin, Fang Zheng, Peng Yue, He Ying
IEEE Trans Pattern Anal Mach Intell. 2021 Feb;43(2):579-594. doi: 10.1109/TPAMI.2019.2933209. Epub 2021 Jan 8.
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 [1] 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 percent. 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 128 GB RAM, outperforming the original heat method and other state-of-the-art geodesic distance solvers.
在本文中，我们提出了一种用于在三角形网格上计算测地距离的并行且可扩展的方法。我们的关键观察结果是，使用热方法[1]恢复测地距离可以重新表述为在满足可积性条件下对其梯度进行优化，这可以通过一种高效的一阶方法来解决，该方法无需求解线性系统且收敛速度快。之后，通过以广度优先顺序对优化后的梯度进行并行积分，可以高效地恢复测地距离。此外，我们采用类似的广度优先策略来推导用于热方法中扩散步骤的并行高斯 - 赛德尔求解器。为了进一步降低面梯度优化带来的内存消耗，我们还提出了一种在边上优化投影梯度的公式，这将内存占用减少了约50%。我们的方法很容易并行化，内存占用低，并且随模型大小线性增长。这使得它特别适合处理大型模型。实验结果表明，在具有128GB内存的台式PC上，它可以高效地计算具有超过2亿个顶点的网格上的测地距离，优于原始的热方法和其他现有的测地距离求解器。
