Quadrilateral Remeshing and Efficient Surface Parameterization

Dong, Shen

Permalink

https://hdl.handle.net/2142/11407 Copy

Description

Title

Quadrilateral Remeshing and Efficient Surface Parameterization

Author(s)

Dong, Shen

Issue Date

2007-12

Keyword(s)

computer graphics

Abstract

Surface remeshing is a fundamental problem in computer graphics, and can be found in most digital geometry processing systems. The majority of work in this area has focused on remeshing with triangle elements, yet quadrilateral meshes are best suited for many occasions, such as physical simulation and defining Catmull-Clark subdivision surfaces. In the first part of this work, we propose a quad-dominant remeshing method based on the use of a smooth harmonic scalar function defined over the surface. Given such a field, we compute its gradient field and a second vector field that is everywhere orthogonal to the gradient. The two nets of integral lines of these vector fields are used to form the polygons of the output mesh. Curvature-sensitive spacing of the integral lines provides for anisotropic meshes that adapt to the local shape. Our scalar field construction allows users to exercise extensive control over the structure of the final mesh. The entire process is performed without computing an explicit parameterization of the surface, and is thus applicable to manifolds of any genus without the need for cutting the surface into patches. In the next part, we present a 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 we 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 pure quadrilateral mesh with very few extraordinary vertices. Our method is robust in handling surfaces with arbitrary topology, and generates output with high element quality. In the third part, we deal explicitly with the problem of surface parameterization. We present two complementary methods for automatically improving mesh parameterizations, and demonstrate that they provide a desirable combination of efficiency and quality. First, we describe a new iterative method for constructing quasi-conformal parameterizations with free boundaries. We formulate the problem as fitting the coordinate gradients to two guidance vector fields of equal magnitude that are everywhere orthogonal. In only one linear step, our method efficiently enerates parameterizations with natural boundaries from those with convex boundaries. Next, we introduce a new non-linear optimization framework that can rapidly reduce interior distortion under a variety of metrics. By iteratively solving linear systems, our algorithm converges to a high quality, low distortion arameterization in very few iterations.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11407

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections