Discretizing Laplace–Beltrami Operator from Differential Quantities

Abstract

The Laplace–Beltrami operator (LBO) is the fundamental geometric object associated with manifold surfaces and has been widely used in various tasks in geometric processing.

By understanding that the LBO can be computed by differential quantities, we propose an approach for discretizing the LBO on manifolds by estimating differential quantities. For a point on the manifold, we first fit a quadratic surface to this point and its neighborhood by minimizing the least-square energy function. Then we compute the first- and second-order differential quantities by the approximated quadratic surface. Finally the discrete LBO at this point is computed from the estimated differential quantities and thus the Laplacian matrix over the discrete manifold is constructed.

Our approach has several advantages: it is simple and efficient and insensitive to noise and boundaries. Experimental results have shown that our approach performs better than most of the current approaches.

We also propose a feature-aware scheme for modifying the Laplacian matrix. The modified Laplacian matrix can be used in other feature preserving geometric processing applications.

Keywords

Laplace–Beltrami operator / Discretization / Differential quantities

References

[1] Arnold D., Falk R., Winther R. Finite element exterior calculus, homological techniques, and applications. Acta Numer.. 2006, 15 1 1-156

[2] Arya S., Mount D.M., Netanyahu N.S., Silverman R., Wu A.Y. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM. 1998, 45 6 891-923

[3] Belkin M., Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems. 2001 585-591

[4] Belkin M., Sun J., Wang Y. Discrete Laplace operator on meshed surfaces. Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry. 2008 New York: ACM. 278-287

[5] Belkin M., Sun J., Wang Y. Constructing Laplace operator from point clouds in R ^d. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2009 1031-1040

[6] Desbrun M., Meyer M., Alliez P. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum. 2002, 21 3 209-218

[7] Desbrun M., Meyer M., Schröder P., Barr A. Implicit fairing of irregular meshes using diffusion and curvature flow. Proc. SIGGRAPH. 1999 317-324

[8] Do Carmo M. Differential Geometry of Curves and Surfaces. 1976 Englewood Cliffs: Prentice-Hall

[9] Dong S., Bremer P., Garland M., Pascucci V., Hart J. Spectral surface quadrangulation. ACM Trans. Graph.. 2006, 25 3 1057-1066

[10] Hildebrandt K., Polthier K. Anisotropic filtering of non-linear surface features. Comput. Graph. Forum. 2004, 23 3 391-400

[11] Jolliffe I.T. Principal Component Analysis. 1986 New York: Springer

[12] Karni Z., Gotsman C. Spectral compression of mesh geometry. Proc. SIGGRAPH. 2000 279-286

[13] Lévy B., Petitjean S., Ray N., Maillot J. . Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph.. 2002, 21 3 362-371

[14] Lévy B., Zhang H. Spectral mesh processing. ACM SIGGRAPH 2010 Courses. 2010 New York: ACM. 8

[15] Liang J., Lai R., Wong T.W., Zhao H. Geometric understanding of point clouds using Laplace–Beltrami operator. 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2012 New York: IEEE. 214-221

[16] Liang J., Zhao H. Solving partial differential equations on point clouds. SIAM J. Sci. Comput.. 2013, 35 3 A1461-A1486

[17] Liu R., Zhang H. Mesh segmentation via spectral embedding and contour analysis. Comput. Graph. Forum. 2007, 26 3 385-394

[18] Liu Y., Prabhakaran B., Guo X. Point-based manifold harmonics. IEEE Trans. Vis. Comput. Graph.. 2011, 18 10 1693-1703

[19] Meyer M., Desbrun M., Schröder P., Barr A. Discrete differential-geometry operators for triangulated 2-manifolds. Vis. Math.. 2002, 3 7 34-57

[20] Nealen A., Igarashi T., Sorkine O., Alexa M. Laplacian mesh optimization. Proceedings of ACM GRAPHITE. 2006 381-389

[21] Ovsjanikov M., Ben-Chen M., Solomon J., Butscher A., Guibas L. Functional maps: a flexible representation of maps between shapes. ACM Trans. Graph.. 2012, 31 4 30

[22] Pinkall U., Polthier K. Computing discrete minimal surfaces and their conjugates. Exp. Math.. 1993, 2 1 15-36

[23] Reuter M., Biasotti S., Giorgi D., Patanè G., Spagnuolo M. Discrete Laplace–Beltrami operators for shape analysis and segmentation. Comput. Graph.. 2009, 33 3 381-390

[24] Sorkine O. Differential representations for mesh processing. Comput. Graph. Forum. 2006, 25 4 789-807

[25] Sorkine O., Cohen-Or D. Least-squares meshes. Proceedings of Shape Modeling International. 2004 191-199

[26] Taubin G. A signal processing approach to fair surface design. Proc. SIGGRAPH. 1995 New York: ACM. 351-358

[27] Vallet B., Lévy B. Spectral geometry processing with manifold harmonics. Comput. Graph. Forum. 2008, 27 2 251-260

[28] Vollmer J., Mencl R., Mueller H. Improved Laplacian smoothing of noisy surface meshes. Comput. Graph. Forum. 1999, 18 3 131-138

[29] Von Luxburg U. A tutorial on spectral clustering. Stat. Comput.. 2007, 17 4 395-416

[30] Wardetzky M., Bergou M., Harmon D., Zorin D., Grinspun E. Discrete quadratic curvature energies. Comput. Aided Geom. Des.. 2007, 24 8–9 499-518

[31] Wardetzky M., Mathur S., Kälberer F., Grinspun E. Discrete Laplace operators: no free lunch. Proc. SGP. 2007 New York: ACM. 33-37

[32] Xu G. Discrete Laplace–Beltrami operators and their convergence. Comput. Aided Geom. Des.. 2004, 21 8 767-784

[33] Xu, G.: Consistent approximations of several geometric differential operators and their convergence. Appl. Numer. Math. (2013)

[34] Xu Z., Xu G., Sun J.G. Convergence analysis of discrete differential geometry operators over surfaces. Mathematics of Surfaces XI. 2005 Berlin: Springer. 448-457

[35] Zhang H. Discrete combinatorial Laplacian operators for digital geometry processing. Proc. SIAM Conference on Geometric Design and Computing. 2004 575-592

[36] Zhang H., Van Kaick O., Dyer R. Spectral methods for mesh processing and analysis. Proceedings of Eurographics State-of-the-Art Report. 2007 1-22