Marc Alexa
Max Wardetzky
Abstract
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.
Supplemental Material
- 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
- 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
- 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
- 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
- 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
- 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
- Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of triangle meshes. Computer Graphics Forum (Proc. of Eurographics), 209--218.Google Scholar
- Desbrun, M., Hirani, A., Leok, M., and Marsden, J. E. 2005. Discrete exterior calculus. arXiv:math.DG/0508341.Google Scholar
- 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
- Duffin, R. 1959. Distributed and Lumped Networks. Journal of Mathematics and Mechanics 8, 793--825.Google Scholar
- Dyer, R., and Schaefer, S., 2009. Circumcentric dual cells with negative area. Technical Report CMPT2009-6.Google Scholar
- 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
- Glickenstein, D. 2007. A monotonicity property for weighted Delaunay triangulations. Discrete and Computational Geometry 38, 651--664. Google ScholarDigital Library
- 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
- Gu, X., and Yau, S.-T. 2003. Global conformal surface parameterization. In Sympos. Geom. Processing, 127--137. Google Scholar
- Gu, X. D., Guo, R., Luo, F., and Zeng, W. 2010. Discrete Laplace--Beltrami operator determines discrete Riemannian metric. arXiv:1010.4070.Google Scholar
- 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
- 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
- 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
- Mercat, C. 2001. Discrete Riemann surfaces and the Ising model. Communications in Mathematical Physics 218, 1, 177--216.Google ScholarCross Ref
- 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
- 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
- Perot, J., and Subramanian, V. 2007. Discrete calculus methods for diffusion. Journal of Comp. Physics 224, 1, 59--81. Google ScholarDigital Library
- Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2, 15--36.Google ScholarCross Ref
- Rippa, S. 1990. Minimal roughness property of the Delaunay triangulation. Computer Aided Geometric Design 7, 489--497. Google ScholarDigital Library
- Rosenberg, S. 1997. The Laplacian on a Riemannian manifold. No. 31 in Student Texts. London Math. Soc.Google Scholar
- 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
- 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
- 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
- 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
- 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
- Xu, G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design 21, 8, 767--784. Google ScholarDigital Library
Index Terms
- Discrete Laplacians on general polygonal meshes
Recommendations
Discrete differential operators on polygonal meshes
Geometry processing of surface meshes relies heavily on the discretization of differential operators such as gradient, Laplacian, and covariant derivative. While a variety of discrete operators over triangulated meshes have been developed and used for ...
Discrete Laplacians on general polygonal meshes
SIGGRAPH '11: ACM SIGGRAPH 2011 papersWhile 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 ...
A simple and complete discrete exterior calculus on general polygonal meshes
Graphical abstractHighlights- Discrete operators acting directly on meshes made of arbitrary polygons are proposed.
AbstractDiscrete exterior calculus (DEC) offers a coordinate–free discretization of exterior calculus especially suited for computations on curved spaces. In this work, we present an extended version of DEC on surface meshes formed by general ...
Comments