Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Parallel and scalable heat methods for geodesic distance computation

Tao, Jiong, Zhang, Juyong, Deng, Bailin ORCID:, Fang, Zheng, Peng, Yue and He, Ying 2021. Parallel and scalable heat methods for geodesic distance computation. IEEE Transactions on Pattern Analysis and Machine Intelligence 43 (2) , pp. 579-594. 10.1109/TPAMI.2019.2933209

[thumbnail of paper-arxiv.pdf]
PDF - Accepted Post-Print Version
Download (7MB) | Preview


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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
ISSN: 0162-8828
Date of First Compliant Deposit: 5 August 2019
Date of Acceptance: 31 July 2019
Last Modified: 07 Nov 2023 01:51

Citation Data

Cited 9 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics