Problem overview

Parameterization definition. A curve (or surface) is parameterized if there's a mapping from a line (or plane) to the curve (or surface). So, for example, you might parameterize a line by:

l(t) = p + tv, p a point, v a vector.

The mapping is a function that takes t to a curve in 2D or 3D. For surfaces, the mapping is a function that takes two parameters (s,t) to a surface in 3D. (Actually parameterization works for any input dimension, and any output dimension, but the most common mappings in graphics are the three listed above.)

Why parameterize? There's a lot of reasons.

The goal of this work is to introduce manifolds as a technique for representing parameterizations. There are many surface representations that do not have a natural parameterization; two common examples are meshes and implicit surfaces. There are several techniques for parameterizing meshes (see below), which range from ad-hoc to fairly well principled. Most of these techniques are complementary to the problem proposed here.

It's fairly well understood how to do parameterization from a plane to a surface. The problem with these parameterizations is that they're limited to shapes that have the topology of a plane - think of a bendy, stretchy piece of rubber. There is no way to do a single, global, smooth parameterization of a spherical object, or objects with multiple handles or holes. The standard thing to do in this case is take individual, planar parameterizations and "glue" them together at the edges geometrically, creating a patchwork effect.

Manifolds are a technique for building arbitrary topology parameterizations that are smooth - they're just not global. Instead of gluing individual parameterizations together at the edges, manifolds glue them by overlapping the parameterizations. Think of a world atlas - each page is a local parameterization of some part of the world. Together, they cover the entire world. The pages overlap at the boundaries - they may not line up perfectly, but it's easy to navigate from one page to another.

Most parameterization techniques work by cutting up arbitrary topology surfaces into smaller pieces that can be parameterized with one or more planes. This introduces seams into the parameterization. It's possible to work around the seams by placing them where they're inconspicuous, or by writing code that specifically deals with the problem.

Manifolds provide a "nice" way of handling these boundaries. The individual parameterizations can be defined so they overlap a fair amount, which provides lots of room to transition from one parameterization to another. Since the parameterizations overlap there are no seams, just transition regions and equations for mapping from one parameterization to the next. They also have a built-in method for "blending" functions across parameterizations.

Most parameterization techniques focus on how to "flatten out" the surface into the plane while maintaining some properties as best as possible (such as area). These techniques are used to produce the mapping between the manifold and the surface.

The approach

The approach taken in this work is to produce a C^infinity manifold for each genus type (sphere, plane, n-holed torus, etc.). The manifolds have several desirable properties, such as unit square domains, substantial overlap, and a small number of parameterizations or charts.

Given a surface, we use the manifold with the same topology for the parameterization. The bulk of the work is in establishing a 1-1, onto correspondence between the surface and the manifold. This mapping is not necessarily smooth, since the original surface might not be (meshes, for example).

We can introduce geometry to the manifold by embedding it. We've experimented with spline and radial basis function embeddings. Using this embedding, we can produce a smooth approximation or interpolation of our input surface. Since the manifold embedding is analytical, we can calculate derivatives, curvature, etc.

Talks

Parameterizing N-Holed Tori , given at the Mathematics of Surfaces IX, Leeds 2003 . See below for paper.

Additional information. Some example pictures of the components of the embedding of a three-holed object.

People

Papers

Manifolds. Siggraph '95. I've included this paper because it has a good description of manifolds and how to construct one versus using manifolds to analyze an existing surface (the usual use of manifolds). The manifold construction itself is a bit cumbersome and expensive. It starts with a mesh and builds a parameterization for each element (vertex, edge, and face). Don't even bother looking at the embedding equations (horribly complex), although the method for blending functions on charts is the one we currently use.

Simple manifolds for parameterization, Shape Modeling International, 2002. This paper describes simple manifolds for a sphere, torus, and plane. It includes methods for establishing the 1-1, onto correspondence. The methods have since been simplified slightly, although the concept is the same.

Parameterizing N-holed Tori, The Mathematics of Surfaces IX, 2003. This paper describes simple manifolds for n-holed tori. The domain is a hyperbolic polygon, which is covered with 2n+2 charts.

Some definitions

Let S(u,v) -> R^3 be a surface, parameterized by u and v.

Previous and related work

I've included links where I could easily find them.


  • "Interactive Texture mapping", J. Maillot, H. Yahia and A. Verroust, Proceedings of Siggraph '93. This was one of the first papers to use the concept of an atlas, or collection of parameterizations. They "cut up" the mesh into regions based on curvature. Each of these regions was flattened out using an optimization procedure, with a parameter that trades distortion for non-flipping. More details.
  • Parametrization and smooth approximation of surface triangulations, Michael Floater, CAGD 1997. This paper is a classic for mapping a disk of triangles to the plane, using a linear least-squares solution. The boundary of the mesh is mapped to the boundary of the desired parameterization (usually a square). Each interior vertex tries to map to the centroid of its neighbors. This mapping is guaranteed not to fold, if the boundary is convex. More details.
  • Parametric tilings and scattered data approximation Michael Floater. International journal of Shape Modeling 4 (1998) pg. 165-187. This paper extends the work of his '97 paper to meshes with n-sided polygons (as opposed to triangles). It also relates this work to the Harmonic map of Eck, et al . More details.
  • Meshless parameterization and B-spline surface reconstruction Michael Floater. The Mathematics of Surfaces IX, 2000, pg 1-18.
  • Meshless parameterization for surface reconstruction , Michael Floater and M. Riemers, computer aided geometryc design 18 (2001) pg 77-92. These two papers extend the work of his '97 paper to data points without a mesh. Once the points are projected onto the plane a Delauny triangulation yields a triangular mesh, if desired. Includes techniques for ordering the boundary and picking weights for the interior vertices. More details.
  • Parameterization of Manifold Triangulations, Michael S. Floater and Kai Hormann and Martin Reimers. Approximation theory X: Abstract and Classical analysis, Vanderbilt Univ. Press, Nashville (2002), pg 197-209.

    This paper uses a mesh decimation routine to produce a small number of triangles. Each of these triangles represents some subset of the original mesh. These subsets are determined by finding geodesics between the vertex points. The subsets are then mapped to the triangle using the previous algorithms. Piecewise-linear wavelets are built on top of the patches to create a more regularly tessellated surface.



  • Non-distorted Texture Mapping for Sheared Triangulated Meshes, Bruno Levy and Jean-Laurent Mallet, Siggraph 1998.

    This paper splits up the problem of finding a triangulation into two optimization equations. The first optimization is essentially equivalent to Floater's 97 paper, except phrased as an optimization procedure. The second optimization is user-controlled, and lets the user specify desired isoparametric curves. More details.


  • Constrained Texture Mapping for Polygonal Meshes Bruno Levy. Proceedings of ACM SIGGRAPH 2001. pp. 417-424, 2001. Provides user-control over the parameterization (position, direction). Does an optimized search to meet constraints and the usual global smoothing. New from the previous paper: constraining the gradient and point constraints, different solver. Extension to n-sided convex polygons by introducing the centroid (equivalent to making the mesh triangular). Slightly different regularization optimization.
  • Least Squares Conformal Maps for Automatic Texture Atlas Generation, Bruno Levy, Sylvain Petitjean, Nicolas Ray, Jerome Maillot, Siggraph 2002. A technique for producing a conformal mapping of a set of polygons. No guarantees about folding. Very similar to Desbrun's technique for conformal mapping, but more expensive to compute. Contains methods to split up the mesh into sections and arrange them in the texture space. More details.

  • Multiresolution analysis of arbitrary meshes, M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. , Siggraph 1995, pg 173-182. This paper discusses more than just parameterization, but they do introduce a harmonic map parameterization as a sub-problem. Hence, this has become the paper to cite for a harmonic mapping of a mesh to the plane. This is essentially an edge-based method, which tries to minimize the square of the norm of the gradient of change in u and v. More details.
  • Lapped Textures, Emil Praun and Adam Finkelstein and Hugues Hoppe, Siggraph 2000. This is a technique for taking a mesh, covering it with small, irregularly shaped patches (look like puzzle pieces) and using that to texture map the surface with a tiling texture. Essentially creates an overlapped atlas with C^0 continuity. More details.
  • Spherical parameterization and Remeshing, E. Praun, and H. Hoppe. Siggraph 03. They use a regular polyhedral as the domain and map the mesh to this regular polyhedron, minimizing a measure of conformality plus stretch. More details.
  • Texture mapping progressive meshes, P. Sander, J. Snyder, S. Gortler, and H. Hoppe. Siggraph 01 pages 409-416.

  • Uses a grid to alter an existing parameterization, reducing size distortion while increasing angle distortion. Essentially, lay a grid across the mesh and grow or shrink the edges by the area ratio of the triangles within the grid cell.
  • Seam cutting of meshes to minimize distortion. More details.
  • Angle-based flattening. Basic idea: Every interior vertex of a flattened mesh must have a sum of angles equal to 2 pi. Does not fold (although it may overlap). More details.
  • Paper. C. Gotsman, X. Gu, A. Sheffer, Fundamentals of Spherical Parameterization for 3D Meshes, ACM Transactions on Graphics (Proc. SIGGRAPH 2003
  • A Sheffer, C. Gotsman, N. Dyn, Robust Spherical Parameterization of Triangular Meshes, 4th Israel-Korea Bi-National Conference on Geometric Modeling and Computer Graphics, 94-99,2003
  • Paper. V. Kraevoy, A. Sheffer, C. Gotsman, Matchmaker: Constructing Constrained Texture Maps, ACM Transactions on Graphics (Proc. SIGGRAPH 2003), to appear

  • Piecewise Surface Flattening for Non-Distorted Texture Mapping, , Chakib Bennis, Jean-Marc Vezien and Gerard Iglesias and Andre Gagalowicz, Siggraph '91. Works on 3D parametric surfaces (e.g., splines). Uses geodesics. More details.
  • Fitting Smooth Surfaces to Dense Polygon Meshes, V. Krishnamurthy and M. Levoy. Siggraph 96, pg 313-324. User-driven patch fitting to a dense polygonal model. The user defines the seams. A spring-relaxation technique is used to evenly distribute the mesh across the surface.
  • Optimal Texture Mapping, S.D. Ma and H. Lin, Optimal texture mapping. Eurographics '88 pg. 421-428. There is no copy of this on the web. As near as I can tell, this is an optimization technique, minimizing some version of the angle/length error.
  • J. Hoschek and U. Kietz, Smooth B-spline surface approximation to scattered data, Reverse Engineering, Hoschek and Dankwort (eds.), B.G. Teubner 1996, pg 143-152. Uses a planar projection as the parameterization.
  • Decorating implicit surfaces, H. Pederson, Siggraph 95 pages 291-300. Computes (approximate) geodesics on the iso surface and uses these to create patches/iso parameter lines. More details.
    Merging Polyhedral Shapes with Scattered Features , Marc Alexa, Shape modeling International '99, Subsequently in the Visual Computer, 16, 1, pg 26-37, 2000. Put a sphere around the mesh. Pin at least 4 vertices to the sphere. Iterate, moving each vertex towards the centroid of its neighbors. Once this is achieved, (no folding) project the vertices out to the sphere.
  • Normal meshes
  • Computing discrete minimal surfaces and their conjugates, U. Pinkall and K. Plthier, Experimental math 2(15) 1993
  • MAPS: Multiresolution Adaptive Parameterization of Surfaces, Aaron W. F. Lee and Wim Sweldens and Peter Schr{\"{o}}der and Lawrence Cowsar and David Dobkin, Siggraph 1998.
  • R. Zonenschein and J. Gornes and L. Velho and N. Rodgriguez, Towards interactivity on texturing implicit surfaces: A distributed approach, Ninth international conference in central Europe on Computer Graphics, visualization and interactive digital media (WSCG 2001)
  • Texture mapping using surface flattening via multi-dimensional scaling, G. Zigelman, R. Kimmel, and N. Kiryati, IEEE Transactions on Visualization and Computer Graphics, 2001. Uses a technique commonly found in vision for mapping a planar mesh to the plane. Essentially, assign a distance between every pair of vertices based on their desired distance on the mesh. Embed those points with those distances in an n-dimensional space. Now use eigen vectors to reduce the dimensionality of that n-dimensional space to 2. Not even sure about the conformal part.
  • Intrinsic parameterizations of surface meshes Mathieu Desbrun and Mark Meyer and Pierre Aliez, Eurographics 2002. Produces mappings from planar meshes. Has a knob which can go from area to angle preserving. Can either constrain the boundary or just fix the rotation and scale. Tends not to fold in the latter case, although no guarantees. Linear solution (very fast).
  • Geodesic curvature preservation in surface flattening through constrained global optimization P. N. Azariadis, N. A. Aspragathos. Computer-Aided Design. 33 (8), pp. 581-591, 2001.
  • Consistent Mesh Parameterizations, Emil Praun and Wim Sweldens and Peter Schroder, Siggraph 2001. An approach to "lining up" two parameterizations of two different models. Requires user intervention to create the line-up points. Uses the MAPS approach for mesh parameterization, which is hierarchical. Essentially, line up the lowest level of the mapping, then the next level, and so on.
  • Seamless Texture Mapping of Subdivision Surfaces by Model Pelting and Texture Blending, Dan Piponi and George D. Borshukov, Siggraph 2000. For characters. Cuts a seam down the belly, then stretches it out treating mesh edges as springs. I always think of this as the "skin the rat" paper.
  • Conformal Surface Parameterization for Texture Mapping , Steven Haker and Sigurd Angenent and Allen Tannenbaum and Ron Kikinis and Guillermo Sapiro and Michael Halle, IEEE TCGV April, 2000.
  • MIPS - an efficient global parametrization method.Hormann, K., and Gremer, Curve and Surface Design, P.J. Laurent, P. Sabloni\`{e}re and L. Schumaker, editors, 1999 pages 153-162, Vanderbilt University press 2000.
  • Quasi-conformally flat maapping the human cerebellum, M. Hurdal, P. Bowers, K. Stepheason, D. Sumaers, K. Rehuns, K. Schaper, and D. Rottenberg, Proc. of MICCAI '99, volume 1679 of Lecture Notes in Computer Science, pages 279-286, Springer-Verlag, 1999.
  • Globally Smooth Parameterizations with Low Distortion , Andrei Khodakovsky, Nathan Litke and Peter Schroder, Siggraph 2003.

    Manifold papers

  • Modelling surfaces from planar irregular meshes, J. Cotrina Navau and N. Pla Garcia, CAGD 2000. Another alternative for making a manifold from a (strictly planar) mesh. Basically uses Floater's algorithm or it's equivalent to map the mesh down to the plane. They then build spline functions on top of the parameterization.
  • Modeling surfaces from meshes of arbitrary topology, J. Cotrina Navau and N. Pla Garcia, CAGD 2000. Another alternative for making manifolds from meshes. Uses subdivision surface techniques to isolate the irregular vertices. They build a smooth projection for the irregular vertices, blending through the rectilinear portions of the mesh.