Parallel algorithms for approximation of distance maps on parametric surfaces

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.

REFERENCES

• 1: Bornemann, F. and Rasch, C. 2006. Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle. Comput. Visualiz. Sci. 9, 2, 57--69.
• 2: Bronstein, A. M., Bronstein, A. M., and Kimmel, R. 2006a. Calculus of non-rigid surfaces for geometry and texture manipulation. IEEE Trans. Visualiz. Comput. Graph. To appear.
• 3: Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006b. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc. National Academy Sciences 103, 5, 1168--1172.
• 4: Nathan A. Carr , Jared Hoberock , Keenan Crane , John C. Hart, Rectangular multi-chart geometry images, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 5: Chang, K., Bowyer, K., and Flynn, P. 2003. Face recognition using 2D and 3D facial data. ACM Workshop on Multimodal User Authentication, 25--32.
• 6: Danielsson, P.-E. 1980. Euclidean distance mapping. Comput. Graph. Image Processing 14, 227--248.
• 7: Paul Dupuis , John Oliensis, Shape from Shading: Provably Convergent Algorithms and Uniqueness Results, Proceedings of the Third European Conference-Volume II on Computer Vision, p.259-268, May 02-06, 1994
• 8: Elad, A. and Kimmel, R. 2001. Bending invariant representations for surfaces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 168--174.
• 9: Fischer, I. and Gotsman, C. 2005. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Tech. rep. CS TR-07-05, Harvard University.
• 10: Thomas Funkhouser , Michael Kazhdan , Philip Shilane , Patrick Min , William Kiefer , Ayellet Tal , Szymon Rusinkiewicz , David Dobkin, Modeling by example, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 11: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 13: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 14: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 15: Jeong, W.-K. and Whitaker, R. 2007. A fast eikonal equation solver for parallel systems. In Proc. SIAM Conference on Computational Science and Engineering.
• 16: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: Kimmel, R. and Sethian, J. A. 1998. Computing geodesic paths on manifolds. Proc. National Academy Sciences 95, 15, 8431--8435.
• 18: Facundo Mémoli , Guillermo Sapiro, Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces: 730, Journal of Computational Physics, v.173 n.2, p.764, November 1, 2001
• 19: Facundo Mémoli , Guillermo Sapiro, A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud Data, Foundations of Computational Mathematics, v.5 n.3, p.313-347, July 2005 [doi>10.1007/s10208-004-0145-y]
• 20: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 21: Novotni, M. and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proceedings of the International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG'02).
• 22: Peyré, G. and Cohen, L. 2003. Geodesic re-meshing and parameterization using front propagation. In Proceedings of the International Conference on Visual Learning of Science and Mathematics (VLSM'03).
• 23: Emil Praun , Hugues Hoppe , Adam Finkelstein, Robust mesh watermarking, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.49-56, July 1999 [doi>10.1145/311535.311540]
• 24: Jianliang Qian , Yong-Tao Zhang , Hong-Kai Zhao, Fast Sweeping Methods for Eikonal Equations on Triangular Meshes, SIAM Journal on Numerical Analysis, v.45 n.1, p.83-107, January 2007 [doi>10.1137/050627083]
• 25: Sethian, J. and Popovici, A. 2006. 3-d traveltime computation using the fast marching method. Geophysics 64, 2, 516--523.
• 26: Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. Proc. National Academy Sciences 93, 4, 1591--1595.
• 27: Sethian, J. A. and Vladimirsky, A. 2000. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proc. National Academy Sciences 11, 5699--5703.
• 28: Christian Sigg , Ronald Peikert , Markus Gross, Signed Distance Transform Using Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.12, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250358]
• 29: Peter-Pike J. Sloan , Charles F. Rose, III , Michael F. Cohen, Shape by example, Proceedings of the 2001 symposium on Interactive 3D graphics, p.135-143, March 2001 [doi>10.1145/364338.364382]
• 30: Spira, A. and Kimmel, R. 2004. An efficient solution to the eikonal equation on parametric manifolds. Interfaces Free Boundaries 6, 4, 315--327.
• 31: Avneesh Sud , Naga Govindaraju , Russell Gayle , Dinesh Manocha, Interactive 3D distance field computation using linear factorization, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111432]
• 32: Vitaly Surazhsky , Tatiana Surazhsky , Danil Kirsanov , Steven J. Gortler , Hugues Hoppe, Fast exact and approximate geodesics on meshes, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 33: Tsitsiklis, J. N. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 40, 9, 1528--1538.
• 34: Lexing Ying , Emmanuel J. Candès, The phase flow method, Journal of Computational Physics, v.220 n.1, p.184-215, December, 2006 [doi>10.1016/j.jcp.2006.05.008]
• 35: Zhao, H. 2004. A fast sweeping method for eikonal equations. Mathe. Computat. 74, 250, 603--627.
• 36: Kun Zhou , John Synder , Baining Guo , Heung-Yeung Shum, Iso-charts: stretch-driven mesh parameterization using spectral analysis, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057439]
• 37: G. Zigelman , R. Kimmel , N. Kiryati, Texture Mapping Using Surface Flattening via Multidimensional Scaling, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.198-207, April 2002 [doi>10.1109/2945.998671]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General

Keywords:
Eikonal equation, GPU, SIMD, fast marching, geodesic distances, geometry image, multiple charts, parallel algorithms