Article

Discrete laplace operators: no free lunch

Authors:

Saurabh Mathur,

Felix Kälberer,

Eitan GrinspunAuthors Info & Claims

SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing

Pages 33 - 37

Published: 04 July 2007 Publication History

Abstract

Discrete Laplace operators are ubiquitous in applications spanning geometric modeling to simulation. For robustness and efficiency, many applications require discrete operators that retain key structural properties inherent to the continuous setting. Building on the smooth setting, we present a set of natural properties for discrete Laplace operators for triangular surface meshes. We prove an important theoretical limitation: discrete Laplacians cannot satisfy all natural properties; retroactively, this explains the diversity of existing discrete Laplace operators. Finally, we present a family of operators that includes and extends well-known and widely-used operators.

References

[1]

{Aur87} Aurenhammer F.: A criterion for the affine equivalence of cell complexes and convex polyhedra. Discrete Comp. Geom. 2 (1987), 49--64.

Digital Library

[2]

{BS05} Bobenko A. I., Springborn B. A.: A discrete Laplace-Beltrami operator for simplicial surfaces. arXiv:math.DG/0503219.

Digital Library

[3]

{Cre90} Cremona L.: Graphical statics (Transl. of Le figure reciproche nelle statica graphica, Milano, 1872). Oxford University Press, 1890.

[4]

{DHLM05} Desbrun M., Hirani A., Leok M., Marsden J. E.: Discrete exterior calculus. arXiv:math.DG/0508341.

[5]

{DMSB99} Desbrun M., Meyer M., Schröder P., Barr A. H.: Implicit fairing of irregular meshes using diffusion and curvature flow. SIGGRAPH (1999), 317--324.

Digital Library

[6]

{Ede01} Edelsbrunner H.: Geometry and topology for mesh generation. Cambridge University Press, 2001.

Digital Library

[7]

{FH05} Floater M. S., Hormann K.: Surface Parameterization: A Tutorial and Survey. In Advances in Multiresolution for Geometric Modeling. 2005, pp. 157--186.

[8]

{FHK06} Floater M. S., Hormann K., Kós G.: A general construction of barycentric coordinates over convex polygons. Adv. Comp. Math. 24, 1--4 (2006), 311--331.

[9]

{FSBS} Fisher M., Springborn B., Bobenko A. I., Schröder P.: An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. Computing. To appear.

Digital Library

[10]

{GGT06} Gortler S. J., Gotsman C., Thurtson D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. Computer Aided Geometric Design 23, 2 (2006), 83--112.

Digital Library

[11]

{Gli05} Glickenstein D.: Geometric triangulations and discrete Laplacians on manifolds. arxiv:math.MG/0508188.

[12]

{HPW07} Hildebrandt K., Polthier K., Wardetzky M.: On the convergence of metric and geometric properties of polyhedral surfaces. Geometricae Dedicata (2007). In press.

[13]

{LBS06} Langer T., Belyaev A., Seidel H.-P.: Spherical barycentric coordinates. In Siggraph/Eurographics Sympos. Geom. Processing (2006), pp. 81--88.

Digital Library

[14]

{Max64} Maxwell J. C.: On reciprocal figures and diagrams of forces. Phil. Mag. 27 (1864), 250--261.

[15]

{PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experim. Math. 2 (1993), 15--36.

[16]

{Ros97} Rosenberg S.: The Laplacian on a Riemannian manifold. No. 31 in Student Texts. London Math. Soc., 1997.

[17]

{Sor05} Sorkine O.: Laplacian mesh processing. Eurographics STAR -- State of The Art Report (2005), 53--70.

[18]

{Tau00} Taubin G.: Geometric signal processing on polygonal meshes. Eurographics STAR -- State of The Art Report (2000).

[19]

{Tut63} Tutte W. T.: How to draw a graph. Proc. London Math. Soc. 13, 3 (1963), 743--767.

[20]

{WBH*07} Wardetzky M., Bergou M., Harmon D., Zorin D., Grinspun E.: Discrete quadratic bending energies. Computer Aided Geometric Design (2007). To appear.

Digital Library

[21]

{Xu04} Xu G.: Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design 21, 8 (2004), 767--784.

Digital Library

[22]

{Zha04} Zhang H.: Discrete combinatorial Laplacian operators for digital geometry processing. In Proc. SIAM Conf. Geom. Design and Comp. (2004), pp. 575--592.

Cited By

Ou CBuschek DMayer SButz A(2022)The Human in the Infinite Loop: A Case Study on Revealing and Explaining Human-AI Interaction Loop FailuresProceedings of Mensch und Computer 202210.1145/3543758.3543761(158-168)Online publication date: 4-Sep-2022
https://dl.acm.org/doi/10.1145/3543758.3543761
Alexa M(2019)Harmonic triangulationsACM Transactions on Graphics10.1145/3306346.332298638:4(1-14)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322986
Rabinovich MHoffmann TSorkine-Hornung O(2018)The shape space of discrete orthogonal geodesic netsACM Transactions on Graphics10.1145/3272127.327508837:6(1-17)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275088
Show More Cited By

Index Terms

Discrete laplace operators: no free lunch

Index terms have been assigned to the content through auto-classification.

Recommendations

Discrete Laplace--Beltrami operators and their convergence

The convergence property of the discrete Laplace-Beltrami operators is the foundation of convergence analysis of the numerical simulation process of some geometric partial differential equations which involve the operator. In this paper we propose ...
Convergent Discrete Laplace-Beltrami Operators over Triangular Surfaces
GMP '04: Proceedings of the Geometric Modeling and Processing 2004

The convergence property of the discrete Laplace-Beltrami operators is the foundation of convergence analysis of the numerical simulation process of somegeometric partial differential equations which involvethe operator. In this paper we propose several ...
SUOWA operators

SUOWA operators are a new family of aggregation functions that simultaneously generalize weighted means and OWA operators. Semi-uninorms, which are an extension of uninorms by dispensing with the symmetry and associativity properties, play a fundamental ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing

July 2007

273 pages

ISBN:9783905673463

Conference Chairs:
Alexander Belyaev
MPI Informatik
,
Michael Garland
NVIDIA Corporation

Sponsors

EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 04 July 2007

Check for updates

Qualifiers

Article

Conference

SGP '07

Sponsor:

EUROGRAPHICS

SGP '07: Geometry processing

July 4 - 6, 2007

Barcelona, Spain

Acceptance Rates

SGP '07 Paper Acceptance Rate 21 of 74 submissions, 28%;

Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ou CBuschek DMayer SButz A(2022)The Human in the Infinite Loop: A Case Study on Revealing and Explaining Human-AI Interaction Loop FailuresProceedings of Mensch und Computer 202210.1145/3543758.3543761(158-168)Online publication date: 4-Sep-2022
https://dl.acm.org/doi/10.1145/3543758.3543761
Alexa M(2019)Harmonic triangulationsACM Transactions on Graphics10.1145/3306346.332298638:4(1-14)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322986
Rabinovich MHoffmann TSorkine-Hornung O(2018)The shape space of discrete orthogonal geodesic netsACM Transactions on Graphics10.1145/3272127.327508837:6(1-17)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275088
Brandt CScandolo LEisemann EHildebrandt K(2017)Spectral Processing of Tangential Vector FieldsComputer Graphics Forum10.1111/cgf.1294236:6(338-353)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1111/cgf.12942
Masoumi MBen Hamza A(2017)Spectral shape classificationJournal of Visual Communication and Image Representation10.1016/j.jvcir.2017.01.00143:C(198-211)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.jvcir.2017.01.001
Masoumi MHamza A(2017)Shape classification using spectral graph waveletsApplied Intelligence10.1007/s10489-017-0955-747:4(1256-1269)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10489-017-0955-7
Zhou YKalogerakis EWang RGrosse I(2016)Direct shape optimization for strengthening 3D printable objectsComputer Graphics Forum10.5555/3151666.315170035:7(333-342)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.5555/3151666.3151700
Patané GMadeira JPatow G(2016)STARProceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports10.5555/3059330.3059334(599-624)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059330.3059334
Barrielle VStoiber NCagniart CGomes APurgathofer WJorge JLin M(2016)BlendForcesProceedings of the 37th Annual Conference of the European Association for Computer Graphics10.5555/3058909.3058955(341-352)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3058909.3058955
Patané G(2016)STAR - Laplacian Spectral Kernels and Distances for Geometry Processing and Shape AnalysisComputer Graphics Forum10.5555/3028584.302863735:2(599-624)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.5555/3028584.3028637
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten