More Web Proxy on the site http://driver.im/

article

Discrete heat kernel determines discrete Riemannian metric

Authors:

Xianfeng GuAuthors Info & Claims

Graphical Models, Volume 74, Issue 4

Pages 121 - 129

https://doi.org/10.1016/j.gmod.2012.03.009

Published: 01 July 2012 Publication History

Abstract

The Laplace-Beltrami operator of a smooth Riemannian manifold is determined by the Riemannian metric. Conversely, the heat kernel constructed from the eigenvalues and eigenfunctions of the Laplace-Beltrami operator determines the Riemannian metric. This work proves the analogy on Euclidean polyhedral surfaces (triangle meshes), that the discrete heat kernel and the discrete Riemannian metric (unique up to a scaling) are mutually determined by each other. Given a Euclidean polyhedral surface, its Riemannian metric is represented as edge lengths, satisfying triangle inequalities on all faces. The Laplace-Beltrami operator is formulated using the cotangent formula, where the edge weight is defined as the sum of the cotangent of angles against the edge. We prove that the edge lengths can be determined by the edge weights unique up to a scaling using the variational approach. The constructive proof leads to a computational algorithm that finds the unique metric on a triangle mesh from a discrete Laplace-Beltrami operator matrix.

References

[1]

M. Belkin, J. Sun, Y. Wang, Discrete Laplace operator on meshed surfaces, in: SoCG '08: Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, 2008, pp. 278-287.

Digital Library

[2]

Ben-chen, M., Gotsman, C. and Bunin, G., Conformal flattening by curvature prescription and metric scaling. Eurographics. v27.

[3]

Bobenko, A.I. and Springborn, B.A., Variational principles for circle patterns and Koebe's theorem. Transactions of the American Mathematical Society. v356. 659-689.

[4]

Bowers, P.L. and Hurdal, M.K., Planar conformal mapping of piecewise flat surfaces. In: Visualization and Mathematics III, Springer, Berlin. pp. 3-34.

[5]

Chow, B. and Luo, F., Combinatorial Ricci flows on surfaces. Journal of Differential Geometry. v63 i1. 97-129.

[6]

de Verdiere Yves, C., Un principe variationnel pour les empilements de cercles. Inventiones Mathematicae. v104 i3. 655-669.

[7]

T.K. Dey, P. Ranjan, Y. Wang, Convergence, stability, and discrete approximation of Laplace spectra, in: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA) 2010, 2010, pp. 650-663.

[8]

Dodziuk, J., Finite-difference approach to the Hodge theory of harmonic forms. American Journal of Mathematics. v98 i1. 79-104.

[9]

Floater, M.S. and Hormann, K., Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, Springer. pp. 157-186.

[10]

Glickenstein, D., A monotonicity property for weighted Delaunay triangulations. Discrete Computational Geometry. v38 i4. 651-664.

[11]

X. Gu, S.-T. Yau, Global conformal parameterization, in: Symposium on Geometry Processing, 2003, pp. 127-137.

Digital Library

[12]

Jin, M., Kim, J., Luo, F. and Gu, X., Discrete surface Ricci flow. IEEE TVCG. v14 i5. 1030-1043.

[13]

M. Jin, F. Luo, X. Gu, Computing surface hyperbolic structure and real projective structure, in: SPM '06: Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling, 2006, pp. 105-116.

Digital Library

[14]

Kharevych, L., Springborn, B. and Schröder, P., Discrete conformal mappings via circle patterns. ACM Transactions on Graphics. v25 i2. 412-438.

[15]

Kraevoy, V. and Sheffer, A., Cross-parameterization and compatible remeshing of 3D models. ACM Transactions on Graphics. v23 i3. 861-869.

[16]

B. Lévy, Laplace-Beltrami eigenfunctions towards an algorithm that "understands" geometry, in: SMI '06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, 2006, pp. 13.

Digital Library

[17]

Luo, F., Combinatorial Yamabe flow on surfaces. Communications in Contemporary Mathematics. v6 i5. 765-780.

[18]

Luo, F., Gu, X.D. and Dai, J., Variational Principles for Discrete Surfaces. 2008. International Press, Somerville, MA.

[19]

Ovsjanikov, M., Sun, J. and Guibas, L.J., Global intrinsic symmetries of shapes. Computer Graphics Forum. v27 i5. 1341-1348.

[20]

Pinkall, U. and Polthier, K., Computing discrete minimal surfaces and their conjugates. Experimental Mathematics. v2 i1. 15-36.

[21]

Reuter, M., Wolter, F.-E. and Peinecke, N., Laplace-Beltrami spectra as 'shape-DNA' of surfaces and solids. Computer Aided Design. v38 i4. 342-366.

[22]

Rivin, I., Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of Mathematics. v139 i3.

[23]

Schoen, R.M. and Yau, S.-T., Lectures on differential geometry. In: Conference Proceedings and Lecture Notes in Geometry and Topology, vol. I. International Press, Somerville, MA.

[24]

Sorkine, O., Differential representations for mesh processing. Computer Graphics Forum. v25 i4. 789-807.

[25]

Springborn, B., Schröder, P. and Pinkall, U., Conformal equivalence of triangle meshes. ACM Transactions on Graphics. v27 i3. 1-11.

[26]

Rosenberg, S., The Laplacian on a Riemannian manifold. 1998. Cambridge University Press.

[27]

Sun, J., Ovsjanikov, M. and Guibas, L.J., A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum. v28 i5. 1383-1392.

[28]

Thurston, W.P., Geometry and Topology of Three-Manifolds. 1980. Lecture Notes at Princeton University.

[29]

M. Wardetzky, S. Mathur, F. Kälberer, E. Grinspun, Discrete Laplace operators: no free lunch, in: Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association, 2007, pp. 33-37.

Digital Library

[30]

Xu, G., Discrete Laplace-Beltrami operators and their convergence. Computer Aided Geometric Design. v21 i8. 767-784.

[31]

Zhang, H., van Kaick, O. and Dyer, R., Spectral mesh processing. Computer Graphics Forum. v29 i6. 1865-1894.

Cited By

Yan YZhou MZhang DGeng S(2024)Average increment scale-invariant heat kernel signature for 3D non-rigid shape analysisMultimedia Tools and Applications10.1007/s11042-023-15346-583:3(8077-8115)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11042-023-15346-5
Narayanan SRamanagopal MSheinin MSankaranarayanan ANarasimhan S(2024)Shape from Heat ConductionComputer Vision – ECCV 202410.1007/978-3-031-72920-1_24(426-444)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72920-1_24
Arrigoni VMaggioli FMassini ARodolà E(2021)Efficiently Parallelizable Strassen-Based Multiplication of a Matrix by its TransposeProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473519(1-12)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3473519
Show More Cited By

Discrete heat kernel determines discrete Riemannian metric
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation

Recommendations

Localized discrete Laplace-Beltrami operator over triangular mesh

The Laplace-Beltrami operator is the foundation of describing geometric partial differential equations, and it also plays an important role in the fields of computational geometry, computer graphics and image processing, such as surface parameterization,...
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 ...
Convergence of discrete Laplace-Beltrami operators over surfaces

The convergence property of the discrete Laplace-Beltrami operator is the foundationof convergence analysis of the numerical simulation process of some geometric partial differential equations which involve the operator. The aim of this paper is to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Graphical Models

Graphical Models Volume 74, Issue 4

July, 2012

192 pages

ISSN:1524-0703

Issue’s Table of Contents

Copyright © © 2012.

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 July 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yan YZhou MZhang DGeng S(2024)Average increment scale-invariant heat kernel signature for 3D non-rigid shape analysisMultimedia Tools and Applications10.1007/s11042-023-15346-583:3(8077-8115)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11042-023-15346-5
Narayanan SRamanagopal MSheinin MSankaranarayanan ANarasimhan S(2024)Shape from Heat ConductionComputer Vision – ECCV 202410.1007/978-3-031-72920-1_24(426-444)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72920-1_24
Arrigoni VMaggioli FMassini ARodolà E(2021)Efficiently Parallelizable Strassen-Based Multiplication of a Matrix by its TransposeProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473519(1-12)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3473519
Smirnov DSolomon J(2021)HodgeNetACM Transactions on Graphics10.1145/3450626.345979740:4(1-11)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459797
Patané G(2017)An introduction to laplacian spectral distances and kernelsACM SIGGRAPH 2017 Courses10.1145/3084873.3084919(1-54)Online publication date: 30-Jul-2017
https://dl.acm.org/doi/10.1145/3084873.3084919
Ovsjanikov MCorman EBronstein MRodolà EBen-Chen MGuibas LChazal FBronstein A(2017)Computing and processing correspondences with functional mapsACM SIGGRAPH 2017 Courses10.1145/3084873.3084877(1-62)Online publication date: 30-Jul-2017
https://dl.acm.org/doi/10.1145/3084873.3084877
Corman ESolomon JBen-Chen MGuibas LOvsjanikov M(2017)Functional Characterization of Intrinsic and Extrinsic GeometryACM Transactions on Graphics10.1145/3072959.299953536:4(1)Online publication date: 16-Jul-2017
https://dl.acm.org/doi/10.1145/3072959.2999535
Corman ESolomon JBen-Chen MGuibas LOvsjanikov M(2017)Functional Characterization of Intrinsic and Extrinsic GeometryACM Transactions on Graphics10.1145/299953536:2(1-17)Online publication date: 29-Mar-2017
https://dl.acm.org/doi/10.1145/2999535
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
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

Media

Figures

Other

Tables

View Issue’s Table of Contents