research-article

A multi-resolution approach to heat kernels on discrete surfaces

Authors:

Mirela Ben-Chen,

Craig GotsmanAuthors Info & Claims

SIGGRAPH '10: ACM SIGGRAPH 2010 papers

Article No.: 121, Pages 1 - 10

https://doi.org/10.1145/1833349.1778858

Published: 26 July 2010 Publication History

Abstract

Studying the behavior of the heat diffusion process on a manifold is emerging as an important tool for analyzing the geometry of the manifold. Unfortunately, the high complexity of the computation of the heat kernel -- the key to the diffusion process - limits this type of analysis to 3D models of modest resolution. We show how to use the unique properties of the heat kernel of a discrete two dimensional manifold to overcome these limitations. Combining a multi-resolution approach with a novel approximation method for the heat kernel at short times results in an efficient and robust algorithm for computing the heat kernels of detailed models. We show experimentally that our method can achieve good approximations in a fraction of the time required by traditional algorithms. Finally, we demonstrate how these heat kernels can be used to improve a diffusion-based feature extraction algorithm.

Supplementary Material

MP4 File (tp107-10.mp4)

Download
41.20 MB

References

[1]

Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel solvers for unstructured surface meshes. SIAM Journal of Scientific Computing 26, 4.

Digital Library

[2]

Arioli, M., Codenotti, B. and Fassino, C. 1996. The Padé method for computing the matrix exponential. Linear Algebra and its Applications 240.

[3]

Belkin, M., Sun, J., and Wang, Y. 2008. Discrete Laplace operator on meshed surfaces. In Proceedings of SOCG 2008.

Digital Library

[4]

Cignoni, P., Corsini, M., and Ranzuglia, G. 2008. Meshlab: An open-source 3D mesh processing system. ERCIM News 73.

[5]

Coifman, R. and Maggioni, M. 2006. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21, 1.

[6]

deGoes, F., Goldenstein, S., And Velho, L. 2008. A hierarchical segmentation of articulated bodies. Computer Graphics Forum 27, 5.

[7]

Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH 1997.

Digital Library

[8]

Graphite. 2009. In http://alice.loria.fr/software/graphite.

[9]

Hochbruck, M., and Lubich, C. 1997. On Krylov subspace approximations to the matrix exponential operator. SIAM Journal on Numerical Analysis, 34, 5.

Digital Library

[10]

Hoppe, H. 1996. Progressive meshes. In Proc. SIGGRAPH 1996.

Digital Library

[11]

Sun, J., Ovsjanikov, M., and Guibas, L. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum 28, 5.

Digital Library

[12]

Kobbelt L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proc. SIGGRAPH 1998.

Digital Library

[13]

Lafon, S. 2004. Diffusion maps and geometric harmonics. PhD Thesis, Yale University, 2004.

[14]

Mémoli, F. 2009. Spectral Gromov-Wasserstein distances for shape matching. In Proc. of Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment.

[15]

Meyer, M., Desbrun, M., Schröder, P. and Barr, A. H. 2002. Discrete differential geometry operators for triangulated 2-manifolds. In Proc. VisMath'02.

[16]

Moler, C. and Loan, C. V. 2003. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review, 45, 1.

Digital Library

[17]

Pinkall U. and Polthier K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1.

[18]

Reuter, M., Wolter, F.-E., and Peinecke, N. 2006. Laplace-Beltrami spectra as 'Shape-DNA' of surfaces and solids. Computer-Aided Design 38, 4.

Digital Library

[19]

Sheffer, A, Lévy, B., Mogilnitsky, M. and Bogomjakov, A. 2005. ABF++: fast and robust angle based flattening. ACM Trans. Graph. 24, 2.

Digital Library

[20]

Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. In Proc. SIGGRAPH 2006.

Digital Library

[21]

Vallet, B. and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Computer Graphics Forum 27, 2.

[22]

Wesseling P. 2004. An Introduction to Multigrid Methods. R. T. Edwards, Inc.

[23]

Xu G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer-Aided Geometric Design 21, 8.

Digital Library

Cited By

Maggioli FBaieri DRodolà EMelzi S(2024)ReMatching: Low-Resolution Representations for Scalable Shape CorrespondenceComputer Vision – ECCV 202410.1007/978-3-031-72913-3_11(183-200)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-72913-3_11
Magnet ROvsjanikov M(2023)Scalable and Efficient Functional Map Computations on Dense MeshesComputer Graphics Forum10.1111/cgf.1474642:2(89-101)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14746
Spielberg AZhong FRematas KJatavallabhula KOztireli CLi TNowrouzezahrai D(2023)Differentiable visual computing for inverse problems and machine learningNature Machine Intelligence10.1038/s42256-023-00743-05:11(1189-1199)Online publication date: 17-Nov-2023
https://doi.org/10.1038/s42256-023-00743-0
Show More Cited By

Index Terms

A multi-resolution approach to heat kernels on discrete surfaces
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A multi-resolution approach to heat kernels on discrete surfaces

Studying the behavior of the heat diffusion process on a manifold is emerging as an important tool for analyzing the geometry of the manifold. Unfortunately, the high complexity of the computation of the heat kernel -- the key to the diffusion process - ...
Analysis of Influencing Factors of Heat Transfer Performance of Heat Pipe Heat Exchanger
ICEET '09: Proceedings of the 2009 International Conference on Energy and Environment Technology - Volume 01

Heat transfer performance of heat pipe heat exchanger affected by many factors, such as the opening temperature of the heat pipe , the rate of fluid-filled, the physical nature of liquid refrigerant 、the work temperature of tube , angle, tube spacing, ...
Kinematic Reeb Graph Extraction Based on Heat Diffusion
ICPR '14: Proceedings of the 2014 22nd International Conference on Pattern Recognition

This paper presents a new approach of Reeb graph extraction adapted to 3D dynamic triangular Meshes. Particularly, we propose a new continuous scalar function, used for Reeb graph construction. This function is based on the heat diffusion properties. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '10: ACM SIGGRAPH 2010 papers

July 2010

984 pages

ISBN:9781450302104

DOI:10.1145/1833349

Conference Chair:
Tony DeRose,
Editor:
Hugues Hoppe
ACM Transactions on Graphics

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SIGGRAPH '10

Sponsor:

SIGGRAPH

SIGGRAPH '10: Special Interest Group on Computer Graphics and Interactive Techniques Conference

July 26 - 30, 2010

California, Los Angeles

Acceptance Rates

SIGGRAPH '10 Paper Acceptance Rate 103 of 390 submissions, 26%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1,031
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Maggioli FBaieri DRodolà EMelzi S(2024)ReMatching: Low-Resolution Representations for Scalable Shape CorrespondenceComputer Vision – ECCV 202410.1007/978-3-031-72913-3_11(183-200)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-72913-3_11
Magnet ROvsjanikov M(2023)Scalable and Efficient Functional Map Computations on Dense MeshesComputer Graphics Forum10.1111/cgf.1474642:2(89-101)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14746
Spielberg AZhong FRematas KJatavallabhula KOztireli CLi TNowrouzezahrai D(2023)Differentiable visual computing for inverse problems and machine learningNature Machine Intelligence10.1038/s42256-023-00743-05:11(1189-1199)Online publication date: 17-Nov-2023
https://doi.org/10.1038/s42256-023-00743-0
Nasikun AHildebrandt K(2022)The Hierarchical Subspace Iteration Method for Laplace–Beltrami EigenproblemsACM Transactions on Graphics10.1145/349520841:2(1-14)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3495208
Wang KWu ZXu PZhao JJia TShui WAli SZhou M(2014)Scale-Invariant Heat Kernel MappingProceedings of the 2014 International Conference on Cyberworlds10.1109/CW.2014.24(114-121)Online publication date: 6-Oct-2014
https://dl.acm.org/doi/10.1109/CW.2014.24
Ovsjanikov MMérigot QMémoli FGuibas L(2010)One Point Isometric Matching with the Heat KernelComputer Graphics Forum10.1111/j.1467-8659.2010.01764.x29:5(1555-1564)Online publication date: 21-Sep-2010
https://doi.org/10.1111/j.1467-8659.2010.01764.x

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten