Discrete laplace operator on meshed surfaces

ABSTRACT

In recent years a considerable amount of work in graphics and geometric optimization used tools based on the Laplace-Beltrami operator on a surface. The applications of the Laplacian include mesh editing, surface smoothing, and shape interpolations among others. However, it has been shown [13, 24, 26] that the popular cotangent approximation schemes do not provide convergent point-wise (or even L2) estimates, while many applications rely on point-wise estimation. Existence of such schemes has been an open question [13].

In this paper we propose the first algorithm for approximating the Laplace operator of a surface from a mesh with point-wise convergence guarantees applicable to arbitrary meshed surfaces. We show that for a sufficiently fine mesh over an arbitrary surface, our mesh Laplacian is close to the Laplace-Beltrami operator on the surface at every point of the surface.

Moreover, the proposed algorithm is simple and easily implementable. Experimental evidence shows that our algorithm exhibits convergence empirically and compares favorably with cotangentbased methods in providing accurate approximation of the Laplace operator for various meshes.

REFERENCES

• 1: Discrete differential geometry: An applied introduction. SIGGRAPH 2005/2006 course notes.
• 2: Convergence of Laplacian Eigenmaps. Preprint, 2008.
• 3: Pierre Alliez , Mark Meyer , Mathieu Desbrun, Interactive geometry remeshing, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 4: N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. Discr. Comput. Geom., 22:481--504, 1999.
• 5: N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. & Applications, 12:125--141, 2002.
• 6: N. Amenta and T. K. Dey. Normal variation with adaptive feature size. http://www.cse.ohio-state.edu/~tamaldey/papers.html, 2007.
• 7: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 8: M. Belkin and P. Niyogi. Towards a theoretical foundation for laplacian-based manifold methods. In COLT, pages 486--500, 2005.
• 9: L. Demanet. Painless, highly accurate discretizations of the laplacian on a smooth manifold. Technical report, Stanford University, 2006.
• 10: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 11: Tamal K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 12: Shen Dong , Peer-Timo Bremer , Michael Garland , Valerio Pascucci , John C. Hart, Spectral surface quadrangulation, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 13: K. Hildebrandt, K. Polthier, and M. Wardetzky. On the convergence of metric and geometric properties of polyhedral surfaces. Geometriae Dedicata, 123(1):89--112, December 2006.
• 14: U. F. Mayer. Numerical solutions for the surface diffusion flow in three space dimensions. comput. Appl. Math, 20(3):361--379, 2001.
• 15: M. Meyer, M. Desbrun, P. Schröder, and A. H. Barr. Discrete differential geometry operators for triangulated 2-manifolds. In Proc. VisMath'02, Berlin, Germany, 2002.
• 16: J.-M. Morvan and B. Thibert. Approximation of the normal vector field and the area of a smooth surface. Discrete & Computational Geometry, 32(3):383--400, 2004.
• 17: Partha Niyogi , Stephen Smale , Shmuel Weinberger, Finding the Homology of Submanifolds with High Confidence from Random Samples, Discrete & Computational Geometry, v.39 n.1, p.419-441, March 2008 [doi>10.1007/s00454-008-9053-2]
• 18: B. O'Neil. Elementary Differential Geometry. Academic Press, New York, NY, USA, 1966.
• 19: U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1):15--36, 1993.
• 20: S. Rosenberg. The Laplacian on a Riemannian Manifold: An Introduction to Analysis on Manifolds. Cambridge University Press, 1997.
• 21: O. Sorkine. Differential representations for mesh processing. Computer Graphics Forum, 25(4):789--807, 2006.
• 22: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 23: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 24: M. Wardetzky. Convergence of the cotangent formula: An overview. In A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. Ziegler, editors, Discrete Differential Geometry, pages 89--112. BirkhÃd'user, to appear.
• 25: Guoliang Xu, Discrete Laplace-Beltrami operators and their convergence, Computer Aided Geometric Design, v.21 n.8, p.767-784, October 2004 [doi>10.1016/j.cagd.2004.07.007]
• 26: Guoliang Xu, Convergence analysis of a discretization scheme for Gaussian curvature over triangular surfaces, Computer Aided Geometric Design, v.23 n.2, p.193-207, February 2006 [doi>10.1016/j.cagd.2005.07.002]
• 27: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Experimentation, Theory

Keywords:
approximation algorithm, laplace-beltrami operator, surfacemesh