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

research-article

Spectral mesh processing

Authors:

Hao (Richard) ZhangAuthors Info & Claims

SIGGRAPH ASIA '09: ACM SIGGRAPH ASIA 2009 Courses

Article No.: 17, Pages 1 - 47

https://doi.org/10.1145/1665817.1665834

Published: 16 December 2009 Publication History

Abstract

Spectral mesh processing is an idea that was proposed at the beginning of the 1990s to port the "signal processing toolbox" to the setting of 3D mesh models. Recent advances in both computing power and numerical software make it possible to fully implement this vision. In the classical context of sound and image processing, Fourier analysis was a cornerstone in development of a wide spectrum of techniques, such as filtering and recognition, to name but a few. In this course, attendees learn how to transfer the underlying concepts to setting a mesh model, how to implement the "spectral mesh processing" toolbox, and how to use it for real applications, including filtering, shape matching, remeshing, segmentation, and parameterization, among others.

References

[1]

{AFW06} D. N. Arnold, R. S. Falk, and R. Winther. Finite element exterior calculus, homological techniques, and applications. Acta Numerica 15, 2006.

[2]

{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.

[3]

{BN03} M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Neural Computations, 15(6):1373--1396, 2003.

Digital Library

[4]

{Bra99} Ronald N. Bracewell. The Fourier Transform And Its Applications. McGraw-Hill, 1999.

[5]

{Cip93} Barri Cipra. You can't always hear the shape of a drum. What's Happening in the Mathematical Sciences, 1, 1993.

[6]

{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.

[7]

{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.

[8]

{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.

Digital Library

[9]

{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.

Digital Library

[10]

{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.

Digital Library

[11]

{DMA02} Mathieu Desbrun, Mark Meyer, and Pierre Alliez. Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics, pages 209--218, 2002.

[12]

{dV90} Y. Colin de Verdiere. Sur un nouvel invariant des graphes et un critere de planarite. J. of Combinatorial Theory, 50, 1990.

[13]

{Dye06} Ramsey Dyer. Mass weights and the cot operator (personal communication). Technical report, Simon Fraser University, CA, 2006.

[14]

{EK03} A. Elad and R. Kimmel. On bending invariant signatures for surfaces. IEEE Trans. Pattern Anal. Mach. Intell., 25(10):1285--1295, 2003.

Digital Library

[15]

{Fei96} J. Feidman. Computing betti numbers via combinatorial laplacians. In Proc. 28th Sympos. Theory Comput., pages 386--391. ACM, 1996.

Digital Library

[16]

{FH04} M. S. Floater and K. Hormann. Surface parameterization: a tutorial and survey. Springer, 2004.

[17]

{Fie73} Miroslav Fiedler. Algebraic connectivity of graphs. Czech. Math. Journal, 23:298--305, 1973.

[18]

{Fie75} Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. Journal, 25:619--633, 1975.

[19]

{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.).

Digital Library

[20]

{GGS03a} C. Gotsman, X. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3d meshes. ACM Trans. Graph., 22(3):358--363, 2003.

Digital Library

[21]

{GGS03b} C. Gotsman, X. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3d meshes, 2003.

Digital Library

[22]

{Got03} Craig Gotsman. On graph partitioning, spectral analysis, and digital mesh processing. In Shape Modeling International, pages 165--174, 2003.

Digital Library

[23]

{GY02} X. Gu and S.-T. Yau. Computing conformal structures of surfaces. Communications in Information and Systems, 2(2):121--146, 2002.

[24]

{Hir03} Anil Hirani. Discrete exterior calculus. PhD thesis, 2003.

Digital Library

[25]

{HPW06} Klaus Hildebrandt, Konrad Polthier, and Max Wardetzky. On the convergence of metric and geometric properties of polyhedral surfaces. Geom Dedicata, 2006.

[26]

{HS97} D. D. Hoffman and M. Singh. Salience of visual parts. Cognition, 63:29--78, 1997.

[27]

{HWAG09} Qixing Huang, Martin Wicke, Bart Adams, and Leonidas J. Guibas. Shape decomposition using modal analysis. 28(2):to appear, 2009.

[28]

{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.

Digital Library

[29]

{IL05} Martin Isenburg and Peter Lindstrom. Streaming meshes. In IEEE Visualization, page 30, 2005.

[30]

{Jai89} A. K. Jain. Fundamentals of Digital Image Processing. Prentice Hall, 1989.

Digital Library

[31]

{JNT} Dmitry Jakobson, Nikolai Nadirashvili, and John Toth. Geometric properties of eigenfunctions.

[32]

{JZ07} Varun Jain and Hao Zhang. A spectral approach to shape-based retrieval of articulated 3D models. Computer Aided Design, 39:398--407, 2007.

Digital Library

[33]

{JZvK07} Varun Jain, Hao Zhang, and Oliver van Kaick. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling, 2007. to appear.

[34]

{Kac66} Mark Kac. Can you hear the shape of a drum? Amer. Math. Monthly, 73, 1966.

[35]

{KG00a} Z. Karni and C. Gotsman. Spectral compression of mesh geometry. In Proc. of ACM SIGGRAPH, pages 279--286, 2000.

Digital Library

[36]

{KG00b} Zachi Karni and Craig Gotsman. Spectral compression of mesh geometry. In SIGGRAPH, pages 279--286, 2000.

Digital Library

[37]

{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.

Digital Library

[38]

{KLS03} A. Khodakovsky, N. Litke, and P. Schröder. Globally smooth parameterizations with low distortion. ACM TOG (SIGGRAPH), 2003.

Digital Library

[39]

{Kor02} Y. Koren. On spectral graph drawing, 2002.

[40]

{Kor03} Y. Koren. On spectral graph drawing. In Proc. of the International Computing and Combinatorics Conference, pages 496--508, 2003.

Digital Library

[41]

{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.

Digital Library

[42]

{KVV00} R. Kannan, S. Vempala, and A. Vetta. On clustering - good, bad, and spectral. In FOCS, pages 367--377, 2000.

Digital Library

[43]

{Lev06} Bruno Levy. Laplace-beltrami eigenfunctions: Towards an algorithm that understands geometry. In IEEE International Conference on Shape Modeling and Applications, 2006.

Digital Library

[44]

{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.

Digital Library

[45]

{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.

Digital Library

[46]

{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.

Digital Library

[47]

{LZ04} R. Liu and H. Zhang. Segmentation of 3D meshes through spectral clustering. In Pacific Graphics, pages 298--305, 2004.

Digital Library

[48]

{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.

[49]

{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.

[50]

{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.

[51]

{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.

Digital Library

[52]

{MTAD08} Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. Spectral conformal parameterization. In ACM/EG Symposium of Geometry Processing, 2008.

Digital Library

[53]

{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.

[54]

{OMT02} R. Ohbuchi, A. Mukaiyama, and S. Takahashi. A frequency-domain approach to watermarking 3D shapes. Computer Graphics Forum, 21(3):373--382, 2002.

[55]

{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.

Digital Library

[56]

{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.

Digital Library

[57]

{PP93} Ulrich Pinkall and Konrad Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1), 1993.

[58]

{Pra99} G. Prathap. Towards a science of fea: Patterns, predictability and proof through some case studies. Current Science, 77:1311--1318, 1999.

[59]

{RS00a} S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323--2326, 2000.

[60]

{RS00b} Sam Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, Dec 2000.

[61]

{Rus07} R. M. Rustamov. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In Proc. of Eurographics Symposium on Geometry Processing, pages 225--233, 2007.

Digital Library

[62]

{RWP05a} M. Reuter, F.-E. Wolter, and N. Peinecke. Laplace-beltrami spectra as "shape-dna" of surfaces and solids. CAD Journal, 2005.

Digital Library

[63]

{RWP05b} Martin Reuter, Franz-Erich Wolter, and Niklas Peinecke. Laplace-spectra 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.

Digital Library

[64]

{SB92} L. S. Shapiro and J. M. Brady. Feature-based correspondence: an eigenvector approach. Image and Vision Computing, 10(5):283--288, 1992.

Digital Library

[65]

{SGD05} P. Schröder, E. Grinspun, and M. Desbrun. Discrete differential geometry: an applied introduction. In SIGGRAPH Course Notes, 2005.

[66]

{SM00} Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000.

Digital Library

[67]

{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.).

[68]

{Tau95a} G. Taubin. A signal processing approach to fair surface design. In Proc. of ACM SIGGRAPH, pages 351--358, 1995.

Digital Library

[69]

{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.

Digital Library

[70]

{TB97} Lloyd N. Trefethen and David Bau. Numerical Linear Algebra. SIAM, 1997.

[71]

{TdSL00} J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319--2323, 2000.

[72]

{THCM04} M. Tarini, K. Hormann, P. Cignoni, and C. Montani. Polycubemaps. ACM TOG (SIGGRAPH), 2004.

Digital Library

[73]

{vL06} Ulrike von Luxburg. A tutorial on spectral clustering. Technical Report TR-149, Max Plank Institute for Biological Cybernetics, August 2006.

[74]

{VM03} D. Verma and M. Meila. A comparison of spectral clustering algorithms. Technical Report UW-CSE-03-05-01, University of Washington, 2003.

[75]

{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.

[76]

{WBH⁺07} Max Wardetzky, Miklos Bergou, David Harmon, Denis Zorin, and Eitan Grinspun. Discrete quadratic curvature energies. Computer Aided Geometric Design (CAGD), 2007.

Digital Library

[77]

{Wei99} Y. Weiss. Segmentation using eigenvectors: A unifying view. In Proc. of the International Conference on Computer Vision, pages 975--983, 1999.

Digital Library

[78]

{WK05} Jianhua Wu and Leif Kobbelt. Efficient spectral watermarking of large meshes with orthogonal basis functions. In The Visual Computer, 2005.

[79]

{WMKG07} Max Wardetzky, Saurabh Mathur, Felix Kalberer, and Eitan Grinspun. Discrete laplace operators: No free lunch. Eurographics Symposium on Geometry Processing, 2007.

Digital Library

[80]

{You85} F. W. Young. Multidimensional scaling. Encyclopedia of Statistical Sciences, 5:649--658, 1985.

[81]

{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.

Digital Library

[82]

{ZL05} H. Zhang and R. Liu. Mesh segmentation via recursive and visually salient spectral cuts. In Proc. of Vision, Modeling, and Visualization, 2005.

[83]

{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.

Digital Library

[84]

{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.

Cited By

Geng ZCao CTulyakov S(2020)Towards Photo-Realistic Facial Expression ManipulationInternational Journal of Computer Vision10.1007/s11263-020-01361-8128:10-11(2744-2761)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11263-020-01361-8
Caissard TCoeurjolly DLachaud JRoussillon T(2019)Laplace–Beltrami Operator on Digital SurfacesJournal of Mathematical Imaging and Vision10.1007/s10851-018-0839-461:3(359-379)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10851-018-0839-4
Brandt CScandolo LEisemann EHildebrandt K(2018)Modeling n-Symmetry Vector Fields using Higher-Order EnergiesACM Transactions on Graphics10.1145/317775037:2(1-18)Online publication date: 13-Mar-2018
https://dl.acm.org/doi/10.1145/3177750
Show More Cited By

Index Terms

Spectral mesh processing
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision tasks
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computation of transforms

Recommendations

Spectral mesh processing
SIGGRAPH '10: ACM SIGGRAPH 2010 Courses

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 ...
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 saliency via spectral processing

We propose a novel method for detecting mesh saliency, a perceptually-based measure of the importance of a local region on a 3D surface mesh. Our method incorporates global considerations by making use of spectral attributes of the mesh, unlike most ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH ASIA '09: ACM SIGGRAPH ASIA 2009 Courses

December 2009

2555 pages

ISBN:9781450379311

DOI:10.1145/1665817

Copyright © 2009 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: 16 December 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

SA09

Sponsor:

SIGGRAPH

SA09: SIGGRAPH ASIA 2009

December 16 - 19, 2009

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
616
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Geng ZCao CTulyakov S(2020)Towards Photo-Realistic Facial Expression ManipulationInternational Journal of Computer Vision10.1007/s11263-020-01361-8128:10-11(2744-2761)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11263-020-01361-8
Caissard TCoeurjolly DLachaud JRoussillon T(2019)Laplace–Beltrami Operator on Digital SurfacesJournal of Mathematical Imaging and Vision10.1007/s10851-018-0839-461:3(359-379)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10851-018-0839-4
Brandt CScandolo LEisemann EHildebrandt K(2018)Modeling n-Symmetry Vector Fields using Higher-Order EnergiesACM Transactions on Graphics10.1145/317775037:2(1-18)Online publication date: 13-Mar-2018
https://dl.acm.org/doi/10.1145/3177750
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
Caissard TCoeurjolly DLachaud JRoussillon T(2017)Heat Kernel Laplace-Beltrami Operator on Digital SurfacesDiscrete Geometry for Computer Imagery10.1007/978-3-319-66272-5_20(241-253)Online publication date: 22-Aug-2017
https://doi.org/10.1007/978-3-319-66272-5_20
Li JZhang YXu PLan SLi S(2016)3D Personalized Face Modeling Based on KINECT22016 9th International Symposium on Computational Intelligence and Design (ISCID)10.1109/ISCID.2016.1052(197-201)Online publication date: Dec-2016
https://doi.org/10.1109/ISCID.2016.1052
Fernández Abrevaya VManandhar SHétroy-Wheeler FWuhrer S(2016)A 3D+t Laplace operator for temporal mesh sequencesComputers and Graphics10.1016/j.cag.2016.05.01858:C(12-22)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.05.018
Wang HSimari PSu ZZhang HKry PBunt A(2014)Spectral global intrinsic symmetry invariant functionsProceedings of Graphics Interface 201410.5555/2619648.2619683(209-215)Online publication date: 7-May-2014
https://dl.acm.org/doi/10.5555/2619648.2619683
Levi ZGotsman C(2014)Smooth Rotation Enhanced As-Rigid-As-Possible Mesh AnimationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2014.235946321:2(264-277)Online publication date: 30-Dec-2014
https://dl.acm.org/doi/10.1109/TVCG.2014.2359463
Kovnatsky ABronstein MBronstein AGlashoff KKimmel R(2013)Coupled quasi‐harmonic basesComputer Graphics Forum10.1111/cgf.1206432:2pt4(439-448)Online publication date: 6-May-2013
https://doi.org/10.1111/cgf.12064
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents