“Spectral surface quadrangulation” by Dong, Bremer, Garland, Pascucci and Hart

  • ©Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, and John C. Hart




    Spectral surface quadrangulation



    Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many surface PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application.


    1. Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. TOG 22, 3, 485–493. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    2. Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces. ftp://ftp-sop.inria.fr/geometrica/alliez/survey_remeshing.pdf.]]Google Scholar
    3. Banchoff, T. F. 1967. Critical points and curvature for embedded polyhedral surfaces. Differential Geometry, 3, 1, 257–268.]]Google Scholar
    4. Bern, M. W., and Eppstein, D. 1995. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, Lecture Notes on Computing #4. World Scientific, 47–123.]]Google Scholar
    5. Boier-Martin, I., Rushmeier, H., and Jin, J. 2004. Parameterization of triangle meshes over quadrilateral domains. In Proc. Eurographics Symposium on Geometry Processing, 197–207.]] Google ScholarDigital Library
    6. Bremer, P.-T., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2004. A topological hierarchy for functions on triangulated surfaces. TVCG 10, 4, 385–396.]]Google ScholarDigital Library
    7. Chung, F. R. K. 1997. Spectral Graph Theory. American Mathematical Society.]]Google Scholar
    8. Courant, R., and Hilbert, D. 1953. Methods of Mathematical Physics, vol. I. Interscience Publishers, New York.]]Google Scholar
    9. Dong, S., Kircher, S., and Garland, M. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. CAGD 22, 5, 392–423.]]Google ScholarCross Ref
    10. Eck, M., and Hoppe, H. 1996. Automatic reconstruction of B-spline surfaces of arbitrary topological type. In Proc. SIGGRAPH, 325–334.]] Google ScholarDigital Library
    11. Eck, M., DeRose, T. D., Duchamp, T., Hoppe, H., Louns-Bery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proc. SIGGRAPH, 173–182.]] Google ScholarDigital Library
    12. Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533.]]Google ScholarDigital Library
    13. Edelsbrunner, H., Harer, J., and Zomorodian, A. 2003. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete Comput. Geom. 30, 87–107.]]Google ScholarCross Ref
    14. Floater, M. S., and Hormann, K. 2004. Surface parameterization: A tutorial and survey. In Multiresolution in Geometric Modelling.]]Google Scholar
    15. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1 (Mar.), 19–27.]] Google ScholarDigital Library
    16. Friedel, I., Schröder, P., and Khodakovsky, A. 2004. Variational normal meshes. TOG 23, 4, 1061–1073.]] Google ScholarDigital Library
    17. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH, 209–216.]] Google ScholarDigital Library
    18. Garland, M. 1999. Multiresolution modeling: Survey & future opportunities. In State of the Art Report, Eurographics, 111–131.]]Google Scholar
    19. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. TOG 21, 3, 355–361. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    20. Guskov, I., Vidimce, K., Sweldens, W., and Schröder, P. 2000. Normal meshes. In Proc. SIGGRAPH, 95–102.]] Google ScholarDigital Library
    21. Halstead, M., Kass, M., and DeRose, T. 1993. Efficient, fair interpolation using Catmull-Clark surfaces. In Proc. SIGGRAPH, 35–44.]] Google ScholarDigital Library
    22. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proc. SIGGRAPH, 203–212.]] Google ScholarDigital Library
    23. Hormann, K., and Greiner, G. 2000. Quadrilateral remeshing. In Proc. Vision Modeling and Visualization, 153–162.]]Google Scholar
    24. Karni, Z., and Gotsman, C. 2000. Spectral compression of mesh geometry. In Proc. SIGGRAPH, 279–286.]] Google ScholarDigital Library
    25. Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally smooth parameterizations with low distortion. TOG 22, 3, 350–357. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    26. Koren, Y., Carmel, L., and Harel, D. 2002. ACE:A fast multiscale eigenvector computation for drawing huge graphs. In Proc. InfoVis ’02, 137–144.]] Google ScholarDigital Library
    27. Lee, A. W. F., Sweldens, W., Schröder, P., Cowsar, L., and Dobkin, D. 1998. MAPS: Multiresolution adaptive parameterization of surfaces. In Proc. SIGGRAPH, 95–104.]] Google ScholarDigital Library
    28. Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quad-dominant remeshing. In Proc. Pacific Graphics.]] Google ScholarDigital Library
    29. Ni, X., Garland, M., and Hart, J. C. 2004. Fair Morse functions for extracting the topological structure of a surface mesh. TOG 23, 3, 613–622. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    30. Owen, S., Staten, M. L., Canann, S. A., and Saigal, S. 1999. Q-Morph: An indirect approach to advancing front quad meshing. Intl. J. Num. Methods in Engineering 9, 1317–1340.]]Google ScholarCross Ref
    31. Pascucci, V., and Cole-McLaughlin, K. 2002. Efficient computation of the topology of level sets. In Proc. Visualization, 187–194.]] Google ScholarDigital Library
    32. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exp. Math. 2, 1, 15–36.]]Google ScholarCross Ref
    33. Ray, N., Li, W. C., Levy, B., Sheffer, A., and Alliez, P. 2005. Periodic global parameterization. TOG. (Accepted, pending revision).]] Google ScholarDigital Library
    34. Sander, P. V., Wood, Z. J., Gortler, S. J., Snyder, J., and Hoppe, H. 2003. Multi-chart geometry images. In Proc. Eurographics Symposium on Geometry Processing, 146–155.]] Google ScholarDigital Library
    35. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. TOG 23, 3, 870–877. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    36. Shimada, K., Liao, J.-H., and Itoh, T. 1998. Quadrilateral meshing with directionality control through the packing of square cells. In Seventh Int’l Meshing Roundtable, 61–75.]]Google Scholar
    37. Stam, J. 2003. Flows on surfaces of arbitrary topology. TOG 22, 3, 724–731. (Proc. SIGGRAPH).]] Google ScholarDigital Library
    38. Stander, B. T., and Hart, J. C. 1997. Guaranteeing the topology of implicit surface polygonization for interactive modeling. In Proc. SIGGRAPH, 279–286.]] Google ScholarDigital Library
    39. Taubin, G. 2000. Geometric signal processing on polygonal meshes. In State of the Art Report, Eurographics, 81–96.]]Google Scholar
    40. van Kreveld, M. J., van Oostrum, R., Bajaj, C. L., Pas-Cucci, V., and Schikore, D. 1997. Contour trees and small seed sets for isosurface traversal. In Sym. Comp. Geo., 212–220.]] Google ScholarDigital Library
    41. Velho, L., and Zorin, D. 2001. 4-8 subdivision. CAGD 18, 5, 397–427. Spec. Issue on Subdiv. Techniques.]]Google ScholarDigital Library
    42. Weber, G., Scheuermann, G., Hagen, H., and Hamann, B. 2002. Exploring scalar fields using critical isovalues. In Proc. Visualization, 171–178.]] Google ScholarDigital Library
    43. Ying, L., and Zorin, D. 2004. A simple manifold-based construction of surfaces of arbitrary smoothness. TOG 23, 3, 271–275. (Proc. SIGGRAPH).]] Google ScholarDigital Library

ACM Digital Library Publication: