Bruno Lévy
ABSTRACT
Spectral mesh processing is an idea that was proposed at the beginning of the 90's, to port the "signal processing toolbox" to the setting of 3D mesh models. Recent advances in both computer horsepower and numerical software make it possible to fully implement this vision. In the more classical context of sound and image processing, Fourier analysis was a corner stone in the development of a wide spectrum of techniques, such as filtering, compression, and recognition. In this course, attendees will learn how to transfer the underlying concepts to the setting of a mesh model, how to implement the "spectral mesh processing" toolbox and use it for real applications, including filtering, shape matching, remeshing, segmentation, and parameterization.
Supplemental Material
Available for Download
- {AFW06} D. N. Arnold, R. S. Falk, and R. Winther. Finite element exterior calculus, homological techniques, and applications. Acta Numerica 15, 2006.Google Scholar
- {Arv95} James Arvo. The Role of Functional Analysis in Global Illumination. In P. M. Hanrahan and W. Purgathofer, editors, Rendering Techniques '95 (Proceedings of the Sixth Eurographics Workshop on Rendering), pages 115--126, New York, NY, 1995. Springer-Verlag.Google Scholar
- {BN03} M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Neural Computations, 15(6):1373--1396, 2003. Google ScholarDigital Library
- {Bra99} Ronald N. Bracewell. The Fourier Transform And Its Applications. McGraw-Hill, 1999.Google Scholar
- {Cip93} Barri Cipra. You can't always hear the shape of a drum. What's Happening in the Mathematical Sciences, 1, 1993.Google Scholar
- {DBG+05} S. Dong, P.-T. Bremer, M. Garland, V. Pascucci, and J. C. Hart. Quadrangulating a mesh using laplacian eigenvectors. Technical report, June 2005.Google Scholar
- {DBG+06a} S. Dong, P.-T. Bremer, M. Garland, V. Pascucci, and J. C. Hart. Spectral mesh quadrangulation. ACM Transactions on Graphics (SIGGRAPH 2006 special issue), 2006.Google Scholar
- {DBG+06b} Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, and John C. Hart. Spectral surface quadrangulation. In SIGGRAPH '06: ACM SIGGRAPH 2006 Papers, pages 1057--1066, New York, NY, USA, 2006. ACM Press. Google ScholarDigital Library
- {dGGV08} Fernando de Goes, Siome Goldenstein, and Luiz Velho. A hierarchical segmentation of articulated bodies. Computer Graphics Forum (Symposium on Geometry Processing), 27(5):1349--1356, 2008. Google ScholarDigital Library
- {DKT05} Mathieu Desbrun, Eva Kanzo, and Yiying Tong. Discrete differential forms for computational modeling. Siggraph '05 course notes on Discrete Differential Geometry, Chapter 7, 2005. Google ScholarDigital Library
- {DMA02} Mathieu Desbrun, Mark Meyer, and Pierre Alliez. Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics, pages 209--218, 2002.Google ScholarCross Ref
- {dV90} Y. Colin de Verdiere. Sur un nouvel invariant des graphes et un critere de planarite. J. of Combinatorial Theory, 50, 1990.Google Scholar
- {Dye06} Ramsey Dyer. Mass weights and the cot operator (personal communication). Technical report, Simon Fraser University, CA, 2006.Google Scholar
- {EK03} A. Elad and R. Kimmel. On bending invariant signatures for surfaces. IEEE Trans. Pattern Anal. Mach. Intell., 25(10):1285--1295, 2003. Google ScholarDigital Library
- {Fei96} J. Feidman. Computing betti numbers via combinatorial laplacians. In Proc. 28th Sympos. Theory Comput., pages 386--391. ACM, 1996. Google ScholarDigital Library
- {FH04} M. S. Floater and K. Hormann. Surface parameterization: a tutorial and survey. Springer, 2004.Google Scholar
- {Fie73} Miroslav Fiedler. Algebraic connectivity of graphs. Czech. Math. Journal, 23:298--305, 1973.Google Scholar
- {Fie75} Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. Journal, 25:619--633, 1975.Google Scholar
- {GBAL} Katarzyna Gebal, Andreas Baerentzen, Henrik Aanaes, and Rasmus Larsen. Shape analysis using the auto diffusion function. Computer Graphics Forum (Proc. of Symp. on Geom. Proc.). Google ScholarDigital Library
- {GGS03a} C. Gotsman, X. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3d meshes. ACM Trans. Graph., 22(3):358--363, 2003. Google ScholarDigital Library
- {GGS03b} C. Gotsman, X. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3d meshes, 2003. Google ScholarDigital Library
- {Got03} Craig Gotsman. On graph partitioning, spectral analysis, and digital mesh processing. In Shape Modeling International, pages 165--174, 2003. Google ScholarDigital Library
- {GY02} X. Gu and S.-T. Yau. Computing conformal structures of surfaces. Communications in Information and Systems, 2(2):121--146, 2002.Google ScholarCross Ref
- {Hir03} Anil Hirani. Discrete exterior calculus. PhD thesis, 2003.Google Scholar
- {HPW06} Klaus Hildebrandt, Konrad Polthier, and Max Wardetzky. On the convergence of metric and geometric properties of polyhedral surfaces. Geom Dedicata, 2006.Google ScholarCross Ref
- {HS97} D. D. Hoffman and M. Singh. Salience of visual parts. Cognition, 63:29--78, 1997.Google ScholarCross Ref
- {HWAG09} Qixing Huang, Martin Wicke, Bart Adams, and Leonidas J. Guibas. Shape decomposition using modal analysis. 28(2):to appear, 2009.Google Scholar
- {HZM+08} Jin Huang, Muyang Zhang, Jin Ma, Xinguo Liu, Leif Kobbelt, and Hujun Bao. Spectral quadrangulation with orientation and alignment control. ACM Transactions on Graphics (SIGGRAPH Asia conf. proc., 2008. Google ScholarDigital Library
- {IL05} Martin Isenburg and Peter Lindstrom. Streaming meshes. In IEEE Visualization, page 30, 2005.Google Scholar
- {Jai89} A. K. Jain. Fundamentals of Digital Image Processing. Prentice Hall, 1989. Google ScholarDigital Library
- {JNT} Dmitry Jakobson, Nikolai Nadirashvili, and John Toth. Geometric properties of eigenfunctions.Google Scholar
- {JZ07} Varun Jain and Hao Zhang. A spectral approach to shape-based retrieval of articulated 3D models. Computer Aided Design, 39:398--407, 2007. Google ScholarDigital Library
- {JZvK07} Varun Jain, Hao Zhang, and Oliver van Kaick. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling, 2007. to appear.Google ScholarCross Ref
- {Kac66} Mark Kac. Can you hear the shape of a drum? Amer. Math. Monthly, 73, 1966.Google Scholar
- {KG00a} Z. Karni and C. Gotsman. Spectral compression of mesh geometry. In Proc. of ACM SIGGRAPH, pages 279--286, 2000. Google ScholarDigital Library
- {KG00b} Zachi Karni and Craig Gotsman. Spectral compression of mesh geometry. In SIGGRAPH, pages 279--286, 2000. Google ScholarDigital Library
- {KG00c} Zachi Karni and Craig Gotsman. Spectral compression of mesh geometry. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 279--286, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co. Google ScholarDigital Library
- {KLS03} A. Khodakovsky, N. Litke, and P. Schröder. Globally smooth parameterizations with low distortion. ACM TOG (SIGGRAPH), 2003. Google ScholarDigital Library
- {Kor02} Y. Koren. On spectral graph drawing, 2002.Google Scholar
- {Kor03} Y. Koren. On spectral graph drawing. In Proc. of the International Computing and Combinatorics Conference, pages 496--508, 2003. Google ScholarDigital Library
- {KSO04} Ravikrishna Kolluri, Jonathan Richard Shewchuk, and James F. O'Brien. Spectral surface reconstruction from noisy point clouds. In Proc. of Eurographics Symposium on Geometry Processing, pages 11--21, 2004. Google ScholarDigital Library
- {KVV00} R. Kannan, S. Vempala, and A. Vetta. On clustering - good, bad, and spectral. In FOCS, pages 367--377, 2000. Google ScholarDigital Library
- {Lev06} Bruno Levy. Laplace-beltrami eigenfunctions: Towards an algorithm that understands geometry. In IEEE International Conference on Shape Modeling and Applications, 2006. Google ScholarDigital Library
- {LH05} Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In International Conference of Computer Vision (ICCV), volume 2, pages 1482--1489, October 2005. Google ScholarDigital Library
- {LPM02} Bruno Levy, Sylvain Petitjean, and Nicolas Ray Nicolas Jerome Maillot. Least squares conformal maps for automatic texture atlas generation. In ACM, editor, SIGGRAPH conf. proc., 2002. Google ScholarDigital Library
- {LPRM02} B. Lévy, S. Petitjean, N. Ray, and J. Maillot. Least squares conformal maps for automatic texture atlas generation. In Proc. of ACM SIGGRAPH 02, pages 362--371, 2002. Google ScholarDigital Library
- {LZ04} R. Liu and H. Zhang. Segmentation of 3D meshes through spectral clustering. In Pacific Graphics, pages 298--305, 2004. Google ScholarDigital Library
- {LZ07} Rong Liu and Hao Zhang. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum (Special Issue of Eurographics 2007), 26:385--394, 2007.Google Scholar
- {MCBH07} Diana Mateus, Fabio Cuzzolin, Edmond Boyer, and Radu Horaud. Articulated shape matching by robust alignment of embedded representations. In ICCV '07 Workshop on 3D Representation for Recognition (3dRR-07), 2007.Google ScholarCross Ref
- {MDSB03} Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H. Barr. Discrete differential-geometry operators for triangulated 2-manifolds. In Hans-Christian Hege and Konrad Polthier, editors, Visualization and Mathematics III, pages 35--57. Springer-Verlag, Heidelberg, 2003.Google ScholarCross Ref
- {MIT06} Omer Meshar, Dror Irony, and Sivan Toledo. An out-of-core sparse symmetric indefinite factorization method. ACM Transactions on Mathematical Software, 32:445--471, 2006. Google ScholarDigital Library
- {MTAD08} Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. Spectral conformal parameterization. In ACM/EG Symposium of Geometry Processing, 2008. Google ScholarDigital Library
- {NJW02} A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Neural Information Processing Systems, volume 14, pages 849--856, 2002.Google Scholar
- {OMT02} R. Ohbuchi, A. Mukaiyama, and S. Takahashi. A frequency-domain approach to watermarking 3D shapes. Computer Graphics Forum, 21(3):373--382, 2002.Google ScholarCross Ref
- {OSG08} Maks Ovsjanikov, Jian Sun, and Leonidas Guibas. Global intrinsic symmetries of shapes. Computer Graphics Forum (Symposium on Geometry Processing), 27(5):1341--1348, 2008. Google ScholarDigital Library
- {OTMM01} R. Ohbuchi, S. Takahashi, T. Miyazawa, and A. Mukaiyama. Watermarking 3D polygonal meshes in the mesh spectral domain. In Proc. of Graphics Interface, pages 9--18, 2001. Google ScholarDigital Library
- {PP93} Ulrich Pinkall and Konrad Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1), 1993.Google Scholar
- {Pra99} G. Prathap. Towards a science of fea: Patterns, predictability and proof through some case studies. Current Science, 77:1311--1318, 1999.Google Scholar
- {RS00a} S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323--2326, 2000.Google ScholarCross Ref
- {RS00b} Sam Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, Dec 2000.Google ScholarCross Ref
- {Rus07} R. M. Rustamov. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In Proc. of Eurographics Symposium on Geometry Processing, pages 225--233, 2007. Google ScholarDigital Library
- {RWP05a} M. Reuter, F.-E. Wolter, and N. Peinecke. Laplace-beltrami spectra as "shape-dna" of surfaces and solids. CAD Journal, 2005. Google ScholarDigital Library
- {RWP05b} Martin Reuter, Franz-Erich Wolter, and Niklas Peinecke. Laplacespectra as fingerprints for shape matching. In SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling, pages 101--106, New York, NY, USA, 2005. ACM Press. Google ScholarDigital Library
- {SB92} L. S. Shapiro and J. M. Brady. Feature-based correspondence: an eigenvector approach. Image and Vision Computing, 10(5):283--288, 1992. Google ScholarDigital Library
- {SGD05} P. Schröder, E. Grinspun, and M. Desbrun. Discrete differential geometry: an applied introduction. In SIGGRAPH Course Notes, 2005.Google Scholar
- {SM00} Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000. Google ScholarDigital Library
- {SOG} Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum (Proc. of Symp. on Geom. Proc.).Google Scholar
- {Tau95a} G. Taubin. A signal processing approach to fair surface design. In Proc. of ACM SIGGRAPH, pages 351--358, 1995. Google ScholarDigital Library
- {Tau95b} Gabriel Taubin. A signal processing approach to fair surface design. In SIGGRAPH '95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pages 351--358, New York, NY, USA, 1995. ACM Press. Google ScholarDigital Library
- {TB97} Lloyd N. Trefethen and David Bau. Numerical Linear Algebra. SIAM, 1997.Google Scholar
- {TdSL00} J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319--2323, 2000.Google ScholarCross Ref
- {THCM04} M. Tarini, K. Hormann, P. Cignoni, and C. Montani. Polycubemaps. ACM TOG (SIGGRAPH), 2004. Google ScholarDigital Library
- {vL06} Ulrike von Luxburg. A tutorial on spectral clustering. Technical Report TR-149, Max Plank Institute for Biological Cybernetics, August 2006.Google Scholar
- {VM03} D. Verma and M. Meila. A comparison of spectral clustering algorithms. Technical Report UW-CSE-03-05-01, University of Washington, 2003.Google Scholar
- {VS01} D. V. Vranić and D. Saupe. 3D shape descriptor based on 3D Fourier transform. In Proc. EURASIP Conf. on Digital Signal Processing for Multimedia Communications and Services, 2001.Google Scholar
- {WBH+07} Max Wardetzky, Miklos Bergou, David Harmon, Denis Zorin, and Eitan Grinspun. Discrete quadratic curvature energies. Computer Aided Geometric Design (CAGD), 2007. Google ScholarDigital Library
- {Wei99} Y. Weiss. Segmentation using eigenvectors: A unifying view. In Proc. of the International Conference on Computer Vision, pages 975--983, 1999. Google ScholarDigital Library
- {WK05} Jianhua Wu and Leif Kobbelt. Efficient spectral watermarking of large meshes with orthogonal basis functions. In The Visual Computer, 2005.Google ScholarCross Ref
- {WMKG07} Max Wardetzky, Saurabh Mathur, Felix Kalberer, and Eitan Grinspun. Discrete laplace operators: No free lunch. Eurographics Symposium on Geometry Processing, 2007. Google ScholarDigital Library
- {You85} F. W. Young. Multidimensional scaling. Encyclopedia of Statistical Sciences, 5:649--658, 1985.Google Scholar
- {ZKK02} Gil Zigelman, Ron Kimmel, and Nahum Kiryati. Texture mapping using surface flattening via multidimensional scaling. IEEE Transactions on Visualization and Computer Graphics, 8(2), 2002. Google ScholarDigital Library
- {ZL05} H. Zhang and R. Liu. Mesh segmentation via recursive and visually salient spectral cuts. In Proc. of Vision, Modeling, and Visualization, 2005.Google Scholar
- {ZSGS04} Kun Zhou, John Snyder, Baining Guo, and Heung-Yeung Shum. Iso-charts: Stretch-driven mesh parameterization using spectral analysis. In Symposium on Geometry Processing, pages 47--56, 2004. Google ScholarDigital Library
- {ZvKDar} Hao Zhang, Oliver van Kaick, and Ramsay Dyer. Spectral mesh processing. Computer Graphics Forum, 2009, to appear. http://www.cs.sfu.ca/~haoz/pubs/zhang_cgf09_spect_survey.pdf.Google Scholar
- G. Taubin. A signal processing approach to fair surface design. In Proc. of ACM SIGGRAPH, pages 351--358, 1995. Google ScholarDigital Library
- Z. Karni and C. Gotsman. Spectral compression of mesh geometry. In Proc. of ACM SIGGRAPH, pages 279--286, 2000. Google ScholarDigital Library
- A. K. Jain. Fundamentals of Digital Image Processing. Prentice Hall, 1989. Google ScholarDigital Library
- F. R. K. Chung. Spectral Graph Theory. AMS, 1997.Google Scholar
- Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000. Google ScholarDigital Library
- Ulrike von Luxburg. A tutorial on spectral clustering. Technical Report TR-149, Max Plank Institute for Biological Cybernetics, August 2006.Google Scholar
- Varun Jain, Hao Zhang, and Oliver van Kaick. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling, 13(1):101--124, 2007.Google ScholarCross Ref
- H. Qiu and ER Hancock, Clustering and embedding using commute times, IEEE Transactions on Pattern Analysis and Machine Intelligence 29 (2007), no. 11, 1873--1890. Google ScholarDigital Library
- Hao Zhang, Oliver van Kaick, and Ramsay Dyer. Spectral mesh processing. Computer Graphics Forum, 2009, to appear. http://www.cs.sfu.ca/~haoz/pubs/zhang_cgf09_spect_survey.pdf.Google Scholar
- Rong Liu and Hao Zhang. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum (Special Issue of Eurographics 2007), 26:385--394, 2007.Google Scholar
- {EY36} Eckart C., Young G.: The approximation of one matrix by another of lower rank. Psychometrika 1 (1936), 211--218.Google ScholarCross Ref
- {BH03} Brand M., Huang K.: A unifying theorem for spectral embedding and clustering. In Proc. of Int. Conf. on AI and Stat. (Key West, Florida, 2003).Google Scholar
- Max Wardetzky, Saurabh Mathur, Felix Kalberer, and Eitan Grinspun. Discrete laplace operators: No free lunch. Eurographics Symposium on Geometry Processing, 2007. Google ScholarDigital Library
- {VL08} Vallet B., Lévy B.: Spectral geometry processing with manifold harmonics. Computer Graphics Forum (Special Issue of Eurographics) 27, 2 (2008), 251--260.Google Scholar
- Dyer, R., Zhang, H., and Möller, T. 2007. Delaunay mesh construction. In Symp. Geometry Processing, 271--282. Google ScholarDigital Library
- {LZ06} Li J., Zhang H.: Nonobtuse remeshing and decimation. In SGP (2006), pp. 235--238. Google ScholarDigital Library
- R. Liu, H. Zhang, A. Shamir, and D. Cohen-Or, "A Part-Aware Surface Metric for Shape Processing", Eurographics 2009Google Scholar
- A. Shamir, "A Survey on Mesh Segmentation Techniques", Computer Graphics Forum (Eurographics STAR 2006), 2008.Google Scholar
- F. de Goes, Siome Goldenstein, and Luiz Velho, "A hierarchical Segmentation of Articulated Bodies", SGP 2008. Google ScholarDigital Library
- R. Liu and H. Zhang, "Spectral Clustering for Mesh Segmentation", Pacific Graphics 2004.Google Scholar
- R. Liu and H. Zhang, "Mesh Segmentation via Spectral Embedding and Contour Analysis", Eurographics 2007.Google Scholar
- S. Katz and A. Tal, "Hierarchical Mesh Segmentation via Fuzzy Clustering and Cuts", SIGGRAPH 2003. Google ScholarDigital Library
- R. Rustomov, "Laplacian-Beltrami Eigenfunctions for Deformation Invariant Shape Representation", SGP 2007. Google ScholarDigital Library
- V. Jain, H. Zhang, O. van Kaick, "Non-Rigid Spectral Correspondence of Triangle Meshes, IJSM 2007.Google Scholar
- M. Ovsjanikov, J. Sun, and L. Guibas, "Global Intrinsic Symmetries of Shapes", SGP 2008. Google ScholarDigital Library
- V. Jain and H. Zhang, "A Spectral Approach to Shape-Based Retrieval of Articulated 3D Models", CAD 2007. Google ScholarDigital Library
- K. Xu, H. Zhang, A. Tagliasacchi, L. Liu, M. Meng, L. Guo, Y. Xiong, "Partial Intrinsic Reflectional Symmetry of 3D Shapes", SIGGRAPH Asia 2009. Google ScholarDigital Library
Index Terms
- Spectral mesh processing
Recommendations
Spectral compression of mesh geometry
SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniquesWe show how spectral methods may be applied to 3D mesh data to obtain compact representations. This is achieved by projecting the mesh geometry onto an orthonormal basis derived from the mesh topology. To reduce complexity, the mesh is partitioned into ...
Quad-Mesh Generation and Processing: A Survey
Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi-regular ...
Mesh simplification algorithm based on n-edge mesh collapse
ICAT'06: Proceedings of the 16th international conference on Advances in Artificial Reality and Tele-ExistenceThis paper presents a method for dividing the triangle mesh into n-edge mesh and puts forward a new mesh simplification algorithm based on n-edge mesh collapse. An n-edge mesh can be in the form of an edge, a triangle or a quadrangle, it depends on the ...
Comments