Parallel Chen-Han (PCH) algorithm for discrete geodesics

DOI10.1145/2534161MaRDI QIDQ5419165zbMATH OpenOpenAlexFDO

Authors Xiang Ying, Shiqing Xin, Ying He

Publication date 5 June 2014

Published in ACM Transactions on Graphics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1293

zbMATH Keywords

discrete geodesicGPUparallel computationwindow propagation

Mathematics Subject Classification ID

Geodesics in global differential geometry (53C22) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10) Approximation algorithms (68W25)

Abstract: In many graphics applications, the computation of exact geodesic distance is very important. However, the high computational cost of the existing geodesic algorithms means that they are not practical for large-scale models or time-critical applications. To tackle this challenge, we propose the parallel Chen-Han (or PCH) algorithm, which extends the classic Chen-Han (CH) discrete geodesic algorithm to the parallel setting. The original CH algorithm and its variant both lack a parallel solution because the windows (a key data structure that carries the shortest distance in the wavefront propagation) are maintained in a strict order or a tightly coupled manner, which means that only one window is processed at a time. We propose dividing the CH's sequential algorithm into four phases, window selection, window propagation, data organization, and events processing so that there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in parallel. The proposed PCH algorithm is able to propagate a large number of windows simultaneously and independently. We also adopt a simple yet effective strategy to control the total number of windows. We implement the PCH algorithm on modern GPUs (such as Nvidia GTX 580) and analyze the performance in detail. The performance improvement (compared to the sequential algorithms) is highly consistent with GPU double-precision performance (GFLOPS). Extensive experiments on real-world models demonstrate an order of magnitude improvement in execution time compared to the state-of-the-art.

Recommendations

• Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
• Discrete Geometry for Computer Imagery
• Geodesics on point clouds
• The Discrete Geodesic Problem
• A general algorithm for computing distance transforms in linear time

Cites work

• A fast marching level set method for monotonically advancing fronts.
• Computing geodesic paths on manifolds
• Convergence of geodesics on triangulations
• Distance Functions and Geodesics on Submanifolds of \R^d and Point Clouds
• Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces
• scientific article; zbMATH DE number 5506188 (Why is no real title available?)
• scientific article; zbMATH DE number 1305036 (Why is no real title available?)
• On Shortest Paths in Polyhedral Spaces
• The Discrete Geodesic Problem

Cited in

(3)

• Craniofacial reconstruction evaluation by geodesic network
• Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
• On different topological classes of spherical geodesic paths and circles in \(\mathbb{Z}^3\)

Describes a project that uses

Uses Software

• Thrust
• CUDA

This page was built for publication: Parallel Chen-Han (PCH) algorithm for discrete geodesics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419165)