“Discrete Laplacians on general polygonal meshes” by Alexa and Wardetzky

While the theory and applications of discrete Laplacians on triangulated surfaces are well developed, far less is known about the general polygonal case. We present here a principled approach for constructing geometric discrete Laplacians on surfaces with arbitrary polygonal faces, encompassing non-planar and non-convex polygons. Our construction is guided by closely mimicking structural properties of the smooth Laplace–Beltrami operator. Among other features, our construction leads to an extension of the widely employed cotan formula from triangles to polygons. Besides carefully laying out theoretical aspects, we demonstrate the versatility of our approach for a variety of geometry processing applications, embarking on situations that would have been more difficult to achieve based on geometric Laplacians for simplicial meshes or purely combinatorial Laplacians for general meshes.

1. Belkin, M., Sun, J., and Wang, Y. 2008. Discrete Laplace operator on meshed surfaces. In Proc. of the 24th annual Symposium on Computational Geometry, 278–287. Google Scholar
2. Bobenko, A. I., and Springborn, B. A. 2007. A discrete Laplace–Beltrami operator for simplicial surfaces. Discrete and Computational Geometry 38, 4, 740–756. Google ScholarDigital Library
3. Brezzi, F., Lipnikov, K., and Shashkov, M. 2005. Convergence of mimetic finite difference methods for diffusion problems on polyhedral meshes. SIAM J. Num. Anal. 43, 1872–1896. Google ScholarDigital Library
4. Brezzi, F., Lipnikov, K., and Simoncini, V. 2005. A family of mimetic finite difference methods on polygonal and polyhedral meshes. Math. Models Methods Appl. Sci. 15, 1533–1553.Google ScholarCross Ref
5. Chen, R., Xua, Y., Gotsman, C., and Liu, L. 2010. A spectral characterization of the Delaunay triangulation. Computer Aided Geometric Design 27, 4, 295–300. Google ScholarDigital Library
6. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of ACM SIGGRAPH, 317–324. Google Scholar
7. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of triangle meshes. Computer Graphics Forum (Proc. of Eurographics), 209–218.Google Scholar
8. Desbrun, M., Hirani, A., Leok, M., and Marsden, J. E. 2005. Discrete exterior calculus. arXiv:math.DG/0508341.Google Scholar
9. Dey, T., Ranjan, P., and Wang, Y. 2010. Convergence, stability, and discrete approximation of Laplace spectra. In Proceedings of SODA, 650–663. Google ScholarDigital Library
10. Duffin, R. 1959. Distributed and Lumped Networks. Journal of Mathematics and Mechanics 8, 793–825.Google Scholar
11. Dyer, R., and Schaefer, S., 2009. Circumcentric dual cells with negative area. Technical Report CMPT2009-6.Google Scholar
12. Dziuk, G. 1988. Finite elements for the Beltrami operator on arbitrary surfaces. In Partial Differential Equations and Calculus of Variations, vol. 1357 of Lec. Notes Math. Springer, 142–155.Google Scholar
13. Glickenstein, D. 2007. A monotonicity property for weighted Delaunay triangulations. Discrete and Computational Geometry 38, 651–664. Google ScholarDigital Library
14. Grinspun, E., Gingold, Y., Reisman, J., and Zorin, D. 2006. Computing discrete shape operators on general meshes. Eurographics (Computer Graphics Forum) 25, 547–556.Google ScholarCross Ref
15. Gu, X., and Yau, S.-T. 2003. Global conformal surface parameterization. In Sympos. Geom. Processing, 127–137. Google Scholar
16. Gu, X. D., Guo, R., Luo, F., and Zeng, W. 2010. Discrete Laplace–Beltrami operator determines discrete Riemannian metric. arXiv:1010.4070.Google Scholar
17. Hildebrandt, K., Polthier, K., and Wardetzky, M. 2006. On the convergence of metric and geometric properties of polyhedral surfaces. Geometricae Dedicata 123, 89–112.Google ScholarCross Ref
18. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 21, 3, 362–371. Google ScholarDigital Library
19. Liu, D., Xu, G., and Zhang, Q. 2008. A discrete scheme of Laplace–Beltrami operator and its convergence over quadrilateral meshes. Computers and Mathematics with Applications 55, 1081–1093. Google ScholarDigital Library
20. Mercat, C. 2001. Discrete Riemann surfaces and the Ising model. Communications in Mathematical Physics 218, 1, 177–216.Google ScholarCross Ref
21. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, H.-C. Hege and K. Polthier, Eds. Springer, 35–57.Google Scholar
22. Mullen, P., Tong, Y., Alliez, P., and Desbrun, M. 2008. Spectral conformal parameterization. Computer Graphics Forum (Proc. of SGP) 27, 5, 1487–1494. Google ScholarDigital Library
23. Perot, J., and Subramanian, V. 2007. Discrete calculus methods for diffusion. Journal of Comp. Physics 224, 1, 59–81. Google ScholarDigital Library
24. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2, 15–36.Google ScholarCross Ref
25. Rippa, S. 1990. Minimal roughness property of the Delaunay triangulation. Computer Aided Geometric Design 7, 489–497. Google ScholarDigital Library
26. Rosenberg, S. 1997. The Laplacian on a Riemannian manifold. No. 31 in Student Texts. London Math. Soc.Google Scholar
27. Shafiqul-Islam, M., and Rathod, H. 2006. Alternative approach of numerical integration for rational functions related to linear convex quadrilateral finite elements. Journal of App. Sciences Research 2, 9, 533–540.Google Scholar
28. Sullivan, J. 2008. Curvatures of smooth and discrete surfaces. In Discrete Differential Geometry, A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. Ziegler, Eds. Birkhäuser Basel, 175–188.Google Scholar
29. Wardetzky, M., Bergou, M., Harmon, D., Zorin, D., and Grinspun, E. 2007. Discrete Quadratic Curvature Energies. Computer Aided Geometric Design 24, 499–518. Google ScholarDigital Library
30. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete Laplace operators: No free lunch. In Siggraph/Eurographics Sympos. Geom. Processing, 33–37. Google Scholar
31. Xiong, Y., Li, G., and Han, G. 2011. Mean Laplace–Beltrami operator for quadrilateral meshes. In Transactions on Edutainment V, Springer, 189–201. Google Scholar
32. Xu, G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design 21, 8, 767–784. Google ScholarDigital Library