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.
- Some surfaces are defined by these mappings (such as lines,
spheres, and splines). In this case, we can use the parameterization
to "chop up" the surface into pieces that can be approximated by
triangles.
- Texture mapping. In this case, an image is placed onto the domain
of the object and mapped onto the object.
- Distributing and interpolating data on a surface. For example,
you might measure the pressure on the surface of the heart at several
points, then interpolate (using the parameter space to determine the
closest points) to get data elsewhere.
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.
- Alla Sheffer, Smoothing an Overlay Grid to Minimize Linear
Distortion in Texture Mapping, Workshop on Geometric Modeling and
Animation, FoCM 2002, invited.
- Paper
A. Sheffer, E. de Sturler, Smoothing an Overlay Grid to Minimize
Linear Distortion in Texture Mapping, ACM Transactions on Graphics,
21(4), 2002.
Seam cutting of meshes to minimize distortion. More details.
- Alla Sheffer, Applying texture to models with high curvature
using seam cutting, First UK-Israel Workshop on Computer Graphics,
2002.
-
Paper. A. Sheffer, J. Hart, Seamster: Inconspicuous
Low-Distortion Texture Seam Layout, IEEE Visualization (Vis02),
291-298, 2002.
- Paper
A. Sheffer, Spanning Tree Seams for Reducing Parameterization
Distortion of Triangulated Surfaces, Shape Modelling International,
61-66, 2002
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.
- Alla Sheffer, Eric de Sturler, Angle Based Flattening of
Tesselated Surfaces, SIAM Conference on Geometric Design and
Computing, 2001, invited.
-
Paper. A. Sheffer, E. de Sturler, Parameterization of CAD
Surfaces for Meshing by Triangulation Flattening. Proc. 7th
International Conference on Numerical Grid Generation in Computational
Field Simulation, 699-708, 2000.
- A. Sheffer, E. de Sturler, Surface Parameterization for Meshing
by Triangulation Flattening. Proc. 9th International Meshing
Roundtable, 161-172, 2000. Journal version (EWC) listed above.
- A. Sheffer and E. de Sturler, Parameterization of Faceted Surfaces for
Meshing Using Angle Based Flattening, Engineering with Computers, 17
(3), 326-337, 2001.
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.