To Appear in SIGGRAPH 2006Spectral Surface QuadrangulationShen Dong∗Peer-Timo Bremer∗Michael Garland∗Valerio Pascucci†John C. Hart∗∗University of Illinois at Urbana-Champaign†Lawrence Livermore National Laboratory(a) Laplacian eigenfunction (b) Morse-Smale complex (c) Optimized complex (d) Semi-regular remeshingFigure 1: We quadrangulate a given triangle mesh by extracting the Morse-Smale complex of a selected eigenvector of the mesh Laplacianmatrix. After optimizing the geometry of the base complex, we remesh the surface with a semi-regular grid of quadrilaterals.AbstractResampling raw surface meshes is one of the most fundamentaloperations 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 prob-lems, especially fluid dynamics, and are best suited for definingCatmull-Clark subdivision surfaces. We describe a fundamentallynew approach to the quadrangulation of manifold polygon meshesusing Laplacian eigenfunctions, the natural harmonics of the sur-face. These surface functions distribute their extrema evenly acrossa mesh, which connect via gradient flow into a quadrangular basemesh. An iterative relaxation algorithm simultaneously refines thisinitial complex to produce a globally smooth parameterization ofthe surface. From this, we can construct a well-shaped quadrilat-eral mesh with very few extraordinary vertices. The quality of thismesh relies on the initial choice of eigenfunction, for which we de-scribe algorithms and hueristics to efficiently and effectively selectthe harmonic most appropriate for the intended application.Keywords: quadrangular remeshing, spectral mesh decomposi-tion, Laplacian eigenvectors, Morse theory, Morse-Smale complex1 IntroductionMeshes generated from laser scanning, isosurface extraction andother methods often suffer from irregular element and sampling ar-∗{shendong,ptbremer,garland,jch}@uiuc.edu†[email protected] of the process. Because these problems arise so easily andcan hinder the accuracy and efficiency of subsequent operations, theability to remesh surfaces with well-shaped well-spaced elements isan important tool for mesh processing.Much of the remeshing work in the graphics literature focuses ontriangle meshes, though many graphics and scientific applicationsbenefit from good quadrilateral meshes. Such meshes should haveas few extraordinary vertices as possible and their elements shouldhave internal angles near 90◦. Quadrilaterals are the preferred prim-itive in several simulation domains, including computational fluiddynamics, where extraordinary points can lead to numerical in-stability [Stam 2003]. Catmull-Clark subdivision of a poor meshcan yield wrinkles [Halstead et al. 1993], and the tensor-productNURBS patches still used in CAD/CAM production software workbest on a mesh composed exclusively of quadrilaterals. Further-more, decomposing a surface into well-shaped quadrangles simpli-fies the construction of a texture atlas.We have developed a new approach for building a quadrangularbase complex over a triangulated manifold of arbitrary genus. Thisapproach is based on the Morse theorem that for almost all realfunctions, the Morse-Smale complex (reviewed in §4), consistingof the ridge lines that extend from its saddles to its extrema, formsquadrangular regions. To space these regions evenly over the sur-face, we choose as our real function a shape harmonic of the appro-priate frequency, computed in §3 as an eigenvector of the Laplacianmatrix of the input mesh. A new iterative relaxation algorithm de-scribed in §5 simultaneously improves this base mesh layout whilecomputing a globally smooth parameterization used to generate thefinal semi-regular grid of well-shaped quadrilaterals.The complete spectrum of the mesh defines two families of com-plexes: the primal Morse-Smale and their quasi-dual complexes, aconstruction we propose in §4.3. The quality of the final mesh is in-timately tied to the choice of complex, a choice we make based onparametric distortion. Section 3 provides a detailed analysis of theLaplacian spectrum, using spectral shifts to efficiently limit com-putation only to the eigenvectors around a desired frequency.The resulting method produces fully conforming semi-regular1To Appear in SIGGRAPH 2006quad-only meshes that §6 shows contain fewer extraordinary points,have better element quality and competitive geometric fidelity whencompared to meshes produced by existing quadrangulation meth-ods. Though this method is designed for uniform surface sampling,§3.2 explores its adaptation to follow large-scale sharp features us-ing a selective feature-based shifting of the Laplacian matrix.2 Related WorkMeshed surface patching and retessellation touch on a number ofclosely interrelated and extensively studied areas. We review onlythe most relevant results here, leaving the details to survey articleson parameterization [Floater and Hormann 2004], remeshing [Al-liez et al. 2005], surface simplification [Garland 1999], and meshgeneration [Bern and Eppstein 1995].Semi-Regular Triangle Remeshing. Semi-regular schemes mapthe input surface onto a triangulated base domain and then regu-larly sample each triangular patch by recursive subdivision. Eck etal. [1995] formed a triangular base mesh from the dual of a q uasi-Voronoi surface decomposition whereas the MAPS system [Leeet al. 1998] used simplification. Normal meshes [Guskov et al.2000; Friedel et al. 2004] improve the encoding efficiency using amultiresolution hierarchy, globally smooth parameterization [Kho-dakovsky et al. 2003] increases parametric smoothness across tri-angular base-domain boundaries, and non-linear parameterizationmethods [Schreiner et al. 2004] can further reduce distortion.Meshing with Quadrilaterals. Geometry images [Gu et al. 2002]produce a fully regular quadrangulation by cutting the mesh into asingle component mapped onto a square domain, whereas multi-chart geometry images [Sander et al. 2003] cut the mesh into regu-larly sampled patches, improving distortion at the expense of patchcontinuity. Hormann and Greiner [2000] present a most-isometricparameterization of individual patches. Boier-Martin et al. [2004]produce a fully conforming quadrilateral mesh by quadrangulatingand grid sampling a general patch decomposition.Eck and Hoppe [1996] build a quadrangular base complex by con-structing a
View Full Document
Unlocking...