3D Mesh Parameterization and a Theorem of Tutte

some natural parametric domain, such as the plane or the sphere.
Parameterization is important for many applications in geometry processing,
including texture mapping, remeshing and morphing. The main objective is to
generate a bijective mapping between the mesh surface and the parametric
domain, which minimizes the distortion incurred in the transition in some
meaningful sense. Examples of possible distortion are metric (edge length)
distortion, conformal (angular) distortion and authalic (area) distortion.


A classical theorem of Tutte, originally designed to draw planar graphs,
shows how to embed a manifold graph with the topology of a disk in the
plane. This basic method was later generalized by Floater to arbitrary
convex combinations, and this can be used to embed a 3D mesh in the plane,
controlling the distortion by using convex weights derived from the
geometry of the mesh.


In this talk I will briefly survey some recent work of mine with colleagues
on various generalizations of Tutte's method which allow much more
flexibility in the embedding procedure:


1. We provide conditions under which Tutte's method produces bijective
embeddings even when the boundary is non-convex. This may be used to
generate free-boundary planar embeddings with constraints.


2. We generalize the theory of Tutte to embed a closed genus-0 mesh on the
sphere. This relies on recent algebraic characterizations of convex
embeddings due to Colin de Verdiere, and related eigenvector constructions
due to Lovasz and Schrijver.


3. We show how the concept of a one-form from differential geometry can be
defined on a discrete mesh. When such a one-form is harmonic, is may be
used to generate bijective embeddings in the plane, in analogy to the Tutte
method. The theory culminates in a discrete version of the Hopf-Poincare
Index theorem, which allows to construct, very simply, a doubly-periodic
embedding of the torus in the plane.