'The Maze' - Parallel algorithms for approximation of distance maps on parametric surfaces

Parallel Algorithms for Approximation of Distance Maps on Parametric Surfaces

OFIR WEBER, YOHAI S. DEVIR, ALEXANDER M. BRONSTEIN, MICHAEL M. BRONSTEIN, and RON KIMMEL

Technion Israel Institute of Technology

We present an efficient O(n) numerical algorithm for first-order approximation of geodesic distances on geometry images, where n is the number of points on the surface. The structure of our algorithm allows efficient implementation on parallel architectures. Two implementations on a SIMD processor and on a GPU are discussed. Numerical results demonstrate up to four orders of magnitude improvement in execution time compared to the state-of-the-art algorithms.