Longer write-ups ↓

Tutte's Embeddings & UV Unwrapping

January 19, 2023

Tutte's embedding theorem

Given a 3-connected, planar graph, Tutte's spring embedding theorem is a result by W.T. Tutte from the 60s which guarantees existence of a (crossing-free) embedding of that graph into the plane. Moreover, it tells you how to find one (many) of them as well:

1. Arbitrarily map the nodes of the graph into the plane using your favorite method.

2. Pick any face of the graph (more on this below), and expand it out into a convex shape surrounding the rest of the nodes.

3. Pin it there, and treat the rest of the edges as 0 rest-length springs — and simply let go.

Remarkably, the springs will all settle into a stable configuration such that no two edges cross! The stable configuration turns out to be completely defined by a very simple property: Each vertex simply lies at the average of its neighbors. As such, it's possible to avoid explicit evolution of the spring system to reach stability, and you can just setup a single matrix solve to get to it. But it's far more fun to visualize the springs settling!

Now step 2 above requires us picking a face in the graph, which is different from any old cycle. To know whether a given cycle is a face, find any planar embedding of the graph and check whether that cycle encloses a region containing no other nodes. If so, that region itself is technically known as a "face" of the graph, but here, I'll use "face" to describe the boundary of that region. It is a face of 3-connected planar graphs that any cycle which is a face in one planar embedding is also a face in another planar embedding (even though it may look different). More precisely, this is often described as "invariance under homeomorphisms of S^2, the 2-sphere". Why sphere? Because technically one can object that the "expanding out" step violates our claim, because clearly we've taken a face in 1 embedding and produced an embedding in which that cycle is no longer a face as it contains nodes inside (all the other nodes, in fact). To resolve this issue, we consider the graph to lie on the sphere instead, on which the "outside" of the graph also counts as a valid face! These mathematicians... 😂

The question is: If we don't have ourselves a planar embedding already, how can we know whether a cycle is a valid face, a priori? To be honest, I'm still not 100% sure on the answer, but one way could be to use some trial and error and hope you can find a 3-cycle (which will always be a face) and use that to compute an embedding using Tutte. We can then use that embedding to find higher quality faces, which we can use to find higher quality embeddings, and so on ad infinitum.

Why do we need the graph to be 3-connected for this method to work? As hinted before, if the graph is not 3-connected, there's often no well-defined notion of "face". A cycle which is a face in one planar embedding might not be a face in another. See figure below, courtesy of Prof. Daniel Spielman. I think there's some intuition to be gained on the 3-connected requirement by playing around with spring simulations of graphs that fail to have this property as well, which is something I'd possibly like to do in the future.

Both here are valid planar embeddings of the graph, but because it's not 3-connected, a cycle which was a face in the left drawing, namely, (1,2,3,6,7,5) is no longer a face in the right drawing. Images from Prof. Daniel Spielman's talk on Tutte's theorem, which this project was partially inspired by. In his presentation, we animates the springs of this graph too, which cause nodes 7 and 8 to collapse onto each other. The other inspiration for my work comes from taking Dr. Daniele Panozzo's Intro to CG course at NYU!

UV-Unwrapping

This theorem & method ended up finding its engineering application in computer graphics some decades later, in the problem of UV-Mapping, which in short, involves computing an embedding of the mesh onto the plane in order to "texture" it using 2D images. (Just superimpose the embedding with the texture image of our choice, and for each point on the 3D mesh, simply look up the corresponding point in the 2D embedding, and copy over the image's color there.) Since most meshes in graphics applications are triangle-meshes, they're 3-connected. And because they're usually also manifold, they're planar too. The only real difficulty is the topology the mesh. As a graph, all the faces are "holes". But as a mesh, some faces are "filled in" and others represent the boundary. Our embedding must respect this. Therefore the usual protocol is to slice the mesh up into several pieces with disk-like topology, and unwrap each component individually. The side-effect is that this creates visible discontinuities in the texturing, often called "seams". 

To UV unwrap a disk-like mesh, Tutte's embeddings are typically the starting point of most algorithms in commercial 3D software, because of the amount of distortion they cause (even though the result is a planar embedding, the sizes of triangles are arbitrary and areas / distances are not preserved from the original mesh). This seminal paper which addresses this issue, by beginning with a Tutte's embedding, but using energy optimization techniques to further evolve the embedding into a (still intersection free) but minimal distortion configuration, by using neat tricks like representing the embedding as a composition of linear maps (one per triangle) and defining distortion energies as functions of singular values of these linear maps.

Another avenue for minimizing distortion is simply by introducing more seams (cuts) into the mesh. The downside, again, is the discontinuities this causes. Therefore there is this trade-off between distortion and discontinuity. In graphics applications, seams are often cleverly hidden in places which are not visible, like on a non-bald character's scalp (underneath the hair).

My work

I wanted to visualize this Tutte's spring embedding procedure on real meshes myself, so I wrote some Python code to do it. First, I modeled a human face mesh in Blender (with 3 holes; two for eyes, one for mouth) and imported its obj file into Python, where I then used Pygame to visualize the spring evolution by pinning various edges. To evolve the springs, I first tried applying the usual semi-implicit Euler updates, but it was severly unstable for any reasonably sized time-step. To solve this, I resorted to the implicit methods presented in the seminal cloth simulation paper "Large Steps in Cloth Simulation", which surprisingly worked really well. I call it "surprising" because the topology of a cloth mesh is very simple, usually just a regular grid. But this method works surprisingly well for unwrapping all kinds of crazy meshes, like the face I modeled and a dolphin mesh I also tried. It is, however, NOT real-time for the face mesh. 

The final algorithm, based on the implicit solver given in the cloth paper, is as follows (my own LaTeX):

Here is the narrated TikTok I made out of this code, and here is the actual code repository. I gave a presentation on this topic at UPenn's 660 course a few years ago, and below are the slides for that. (Some animations may not play properly though, so go to the iCloud viewing link and go to present mode to view those.)

Enjoy,

Aditya Abhyankar (@aiyopasta)