Parallel algorithms for approximation of distance maps on parametric surfaces
- 1 October 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 27 (4) , 1-16
- https://doi.org/10.1145/1409625.1409626
Abstract
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.Keywords
Funding Information
- Ministry of Science (Mar-14)
- United States-Israel Binational Science Foundation (2004274)
This publication has 28 references indexed in Scilit:
- Fast Sweeping Methods for Eikonal Equations on Triangular MeshesSIAM Journal on Numerical Analysis, 2007
- The phase flow methodJournal of Computational Physics, 2006
- A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud DataFoundations of Computational Mathematics, 2005
- A fast sweeping method for Eikonal equationsMathematics of Computation, 2004
- Hierarchical mesh decomposition using fuzzy clustering and cutsACM Transactions on Graphics, 2003
- Texture mapping using surface flattening via multidimensional scalingIEEE Transactions on Visualization and Computer Graphics, 2002
- Fast Computation of Weighted Distance Functions and Geodesics on Implicit Hyper-SurfacesJournal of Computational Physics, 2001
- An Optimal Algorithm for Euclidean Shortest Paths in the PlaneSIAM Journal on Computing, 1999
- Efficient algorithms for globally optimal trajectoriesIEEE Transactions on Automatic Control, 1995
- Euclidean distance mappingComputer Graphics and Image Processing, 1980