Longer write-ups ↓

Special Relativity & Simultaneity

September 3, 2024

Thought Experiment: A Zooming Television Set

Imagine a TV screen zooming past you at 0.75c in the vacuum of empty space. It's stuck endlessly playing the same video clip on loop. In reality, you would barely be able to register that you saw anything whizzing past you at all, but let's relax the speed of light to a mere c=1 meter per second. What would we see? Consider the instant when the TV screen is directly in front of your eyes. Because the speed of light is slow enough to be competitive with the rate at which the movie is playing, light beams leaving different points on the screen that reach your retina at different points in time would result in different portions of the screen playing different parts of the video simultaneously. Further, if we crudely approximate the TV set as a rectangular prism and assume we're in a well-lit environment in which all faces of the prism receive adequate light to reflect, we'd notice relativistic effects like Terrell rotation, where light-beams from normally occluded faces of the prism would be able to reach you because the parts of the prism occluding them move out of the way fast enough. 

But what I'd like to discuss here is what happens if we actually relax the finite light travel time assumption (FTL) as well; that is, if we assume that anything which falls within our field of view is *instantly* visible to us. This is, of course, a perfectly reasonable assumption made in any normal 3D rendering pipeline, because the travel time of light in reality (as well as for computer graphics purposes) might as well be instantaneous. Now returning to our thought experiment in *this* simplified situation, what would we see? At this point, anyone who's dabbled with some introductory special relativity could easily rattle out—"its length would appear contracted and its time would appear dilated". While both those things are correct (and interesting enough!), I feel like this standard introductory treatment of relativity dominant in highschool physics texts (perhaps for good pedagogical reason) leaves out a very important teachable lesson at the heart of what makes relativity so mind-bendingly amazing. 

It's not merely that lengths or timespans appear differently to different observers, it's far more mysterious than this—it's that what different observers perceive as space and as time *itself* changes. Or in the words of physicist Kip Thorne (responsible for the discovery of gravitational waves, and responsible for the relativistic VFX in the movie Interstellar): 

“If you and I move relative to each other, what I call space must be a mixture of your space and your time, and what you call space must be a mixture of my space and my time.”

Let's go back to our TV example. For simplicity, let's assume the video it's playing on loop is simply a full red screen, which slowly fades into blue, completing one loop. How would this appear in different reference frames? Going by the naive special relativity "mantra", one might guess the video plays through identically in all frames, albeit a difference in playback speed (slower, for example, in reference frames where the TV appears to move faster). As it stands, this interpretation turns out to be entirely incorrect! Instead, what some observers see (or most, depending on how you look at it) is what looks roughly like a set of looping red / blue stripes, much like a film-strip of the video! That is, even under our "no FTL assumption", they *still* see different portions of the TV playing different parts of the video simultaneously! How can this be? The answer lies in the Lorentz Transformation, which is a mathematical function describing how a given "event" in one frame appears in another. For example, consider the location of the top-left pixel of the TV, some position (x, y, z) at the instant that the TV is directly in front of you at some time t. Together, the 4-vector (t, x, y, z) comprises an "event", which the Lorentz-transformation eats and maps to a different such set of 4 coordinates describing how the event appears in another frame, say one moving with the TV itself. Now sure: The Lorentz transform *does* dilate the time or length interval between two given events, but this should not be the main point. Instead, one should see what the full transformation itself is doing: transforming *physical events* between frames. 

... <NEEDS FINISHING>

Tutte's Embeddings & UV Unwrapping

January 19, 2024

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)