|
Geodesic distance computation
Geodesics on a curved surface. Left-to-right: distance map level lines, geodesic curves, Voronoi tessellation, offset curves.
Approximation of geodesic distances on curved surfaces is an important computational geometric problem, appearing
in many applications ranging from computer graphics, medical imaging, geophysics, to robot motion planning and navigation.
We developed an parallel algorithm for geodesic distance computation suitable for SIMD processors and graphics hardware. Our Cuda implementation on a 2008 NVIDIA GPU achieved the performance of 250,000,000 distances per second on a 10,000,000 vertex surface, which is a four orders of magnitude improvement in execution time compared to the state-of-the-art algorithms.
Papers
O. Weber, Y. Devir, A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Parallel algorithms for approximation of distance maps on parametric surfaces", ACM Transactions on Graphics, Vol. 27/4, October 2008.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Weighted distance maps computation on parametric three-dimensional manifolds", Journal of Computational Physics, Vol. 255/1, pp. 771-784, July 2007.
Patents
A. Bronstein, M. Bronstein, Y. Devir, R. Kimmel, O. Weber, "Parallel approximation of distance maps", PCT application No. WO2008099400, August 2008.
Software
SSE code
Cuda code
See also
SIGGRAPH trailer
Non-rigid shape similarity and correspondence
|