“A multi-resolution approach to heat kernels on discrete surfaces” by Vaxman, Ben-Chen and Gotsman

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.

1. Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel solvers for unstructured surface meshes. SIAM Journal of Scientific Computing 26, 4. Google ScholarDigital Library
2. Arioli, M., Codenotti, B. and Fassino, C. 1996. The Padé method for computing the matrix exponential. Linear Algebra and its Applications 240.Google Scholar
3. Belkin, M., Sun, J., and Wang, Y. 2008. Discrete Laplace operator on meshed surfaces. In Proceedings of SOCG 2008. Google ScholarDigital Library
4. Cignoni, P., Corsini, M., and Ranzuglia, G. 2008. Meshlab: An open-source 3D mesh processing system. ERCIM News 73.Google Scholar
5. Coifman, R. and Maggioni, M. 2006. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21, 1.Google ScholarCross Ref
6. deGoes, F., Goldenstein, S., And Velho, L. 2008. A hierarchical segmentation of articulated bodies. Computer Graphics Forum 27, 5.Google Scholar
7. Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH 1997. Google ScholarDigital Library
8. Graphite. 2009. In http://alice.loria.fr/software/graphite.Google Scholar
9. Hochbruck, M., and Lubich, C. 1997. On Krylov subspace approximations to the matrix exponential operator. SIAM Journal on Numerical Analysis, 34, 5. Google ScholarDigital Library
10. Hoppe, H. 1996. Progressive meshes. In Proc. SIGGRAPH 1996. Google ScholarDigital 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.Google ScholarDigital Library
12. Kobbelt L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proc. SIGGRAPH 1998. Google ScholarDigital Library
13. Lafon, S. 2004. Diffusion maps and geometric harmonics. PhD Thesis, Yale University, 2004.Google Scholar
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.Google ScholarCross Ref
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.Google Scholar
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.Google ScholarDigital Library
17. Pinkall U. and Polthier K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1.Google ScholarCross Ref
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. Google ScholarDigital 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. Google ScholarDigital Library
20. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. In Proc. SIGGRAPH 2006. Google ScholarDigital Library
21. Vallet, B. and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Computer Graphics Forum 27, 2.Google ScholarCross Ref
22. Wesseling P. 2004. An Introduction to Multigrid Methods. R. T. Edwards, Inc.Google Scholar
23. Xu G. 2004. Discrete Laplace-Beltrami operators and their convergence. Computer-Aided Geometric Design 21, 8. Google ScholarDigital Library