Parallel window propagation on mesh surfaces
Abstract
The task of calculating the shortest distance with minimal curvature between two points on a mesh surface is a well-known problem in computational geometry. This paper aims to develop a effective algorithm for computing geodesics on large, complex models with fast processing times to facilitate interactive applications. Our contribution is developing of the parallel window propagation (PWP) algorithm, which divides the sequential MMP algorithm into four phases: front node selection, window list propagation, window list merging, and vertex update. We use two separate buffers for incoming windows on each edge to avoid data dependency and conflicts in each phase, allowing for parallel processing on a CPU. As a result, our PWP algorithm can propagate a large number of windows simultaneously and independently, leading to significant improvements in performance for real-world models.
Moraref