Parallel and Scalable Heat Methods for Geodesic Distance Computation | JoVE Visualize

Area of Science:

Computer Graphics
Computational Geometry
Scientific Computing

Background:

Geodesic distance computation is crucial for various applications in computer graphics and geometry processing.
Existing methods, like the heat method, can be computationally expensive and memory-intensive, especially for large-scale meshes.
The need for efficient and scalable algorithms for geodesic distance calculation remains a significant challenge.

Purpose of the Study:

To propose a novel parallel and scalable approach for computing geodesic distances on triangle meshes.
To reformulate the heat method for efficient gradient optimization and parallel integration.
To reduce memory consumption and improve performance for large mesh processing.

Main Methods:

Reformulated geodesic distance recovery as gradient optimization with integrability constraints.
Employed an efficient first-order method for gradient optimization, avoiding linear system solving.
Developed a parallel integration strategy using a breadth-first order for optimized gradients.
Introduced a parallel Gauss-Seidel solver for the diffusion step of the heat method.
Proposed an edge-based gradient optimization to reduce memory footprint by approximately 50%.

Main Results:

The proposed method is trivially parallelizable and exhibits a low, linearly growing memory footprint with model size.
Demonstrated efficient computation of geodesic distances on meshes exceeding 200 million vertices on standard hardware.
Achieved superior performance compared to the original heat method and other state-of-the-art geodesic distance solvers.
The edge-based formulation significantly reduces memory requirements.

Conclusions:

The developed parallel approach offers a highly efficient and scalable solution for geodesic distance computation on large triangle meshes.
The method's low memory overhead and parallel nature make it suitable for handling complex and massive datasets.
This work advances the state-of-the-art in geometric computation, enabling faster and more memory-efficient analysis of 3D models.