In short: no matter how awful your mesh is, we compute beautiful high-quality texture coordinates.
(1/n)
For instance, just as a stress test we can try to flatten this crazy #Thingi10k model as a single piece, rather than cutting it up into many charts. We still get excellent texture coordinates, with no flipped triangles, no angle distortion, and little scale distortion.
(2/n)
In general, the algorithm is guaranteed to produce maps that do not locally fold over and are perfectly conformal in a discrete sense, for absolutely any triangle mesh. It also gives globally 1-to-1 maps to the sphere, and handles any configuration of "cone singularities" (3/n)
Our starting point is the "uniformization theorem": any smooth surface—no matter how crazy it looks—can be deformed into a constant-curvature space (e.g. a sphere) by a "conformal" or angle-preserving map
See here for an intro:
(4/n)
A recent "discrete uniformization theorem" provides a perfect analog of the smooth one: every polyhedral surface—no matter how crazy it looks—can be mapped to a discretely conformally equivalent one w/ given curvature
Great theorem—but how do you actually compute the map?! (5/n)
A key idea of the discrete uniformization theorem is to allow the mesh connectivity to change as you flatten the surface. This ensures that you always arrive at a solution—but leads to other challenges that need to be addressed if you want a real, working algorithm. (6/n)
We add three key pieces to ensure things really always work in practice:
A. Improved optimization via "Ptolemy flips" to skirt invalid edge lengths
B. A new integer-based data structure to track how triangulations intersect
C. High-quality interpolation in the "light cone" (7/n)
A. One key idea is that every triangle mesh can also be viewed as an "ideal hyperbolic polyhedron." And even if an edge flip yields lengths that violate the triangle inequality, the hyperbolic picture still makes sense! The algorithm can hence continue without any trouble. (8/n)
B. Another nice idea is that the way two triangulations cross can be recovered from just the *number* of crossings on each edge. We augment these so-called "normal coordinates" (common in topology) with a new mechanism called "roundabouts," needed to recover the final map. (9/n)
C. Finally, it's not enough to just know how triangulations cross—we must also map data (texture coordinates, color, etc.) back to the input surface. Here, the "light cone" model of hyperbolic geometry helps significantly improve on ordinary piecewise linear interpolation. (10/n)
The final algorithm is extremely robust, flattening almost all 32,744 connected components from #Thingi10k—a feat never achieved with prior "guaranteed injective" methods. Yet we guarantee not only injectivity, but also *quality*: all maps are exactly discretely conformal. (11/n)
There's much more to say here, and the theory runs pretty deep. Here are some good entry points:
Thanks to @SaulSchleimer, by the way, for some helpful discussions about/references to normal coordinates. (Forgot to acknowledge you on the webpage, but got it right in the paper!)
• • •
Missing some Tweet in this thread? You can try to
force a refresh
I realized this can be coded up in < 5 minutes in the browser via @UsePenrose, and gave it a try. Pretty darn close! 🧵
[2/n] To be clear, this 🧵 isn't about finding a better packing—or even finding it faster. Wizards like @KangarooPhysics surely have better tricks up their sleeves 🪄
Instead, it's about an awesome *tool* for quickly whipping up constraint-based graphics: penrose.cs.cmu.edu
[3/n] The "17 squares" problem provides a great demonstration of how Penrose works.
In fact, if you want to use this thread as a mini-tutorial, you can try it out at penrose.cs.cmu.edu/try/
Let's find out by trying to re-create a bunch of classic graphics images using #dalle2! A thread. 🧵 [1/n]
Left: original image
Right: DALL-E 2 image
In each case I tried many times & show the best result. Full query string given.
Let's start with a real classic: a chrome and glass ball over a checkerboard, from Turner Whitted's 1980 paper, "An Improved Illumination Model for Shaded Display": cs.drexel.edu/~david/Classes…
Pretty good job on reflection/refraction! Was hard to get the colors I wanted. [2/n]
Two more classics for the price of one: the Stanford Bunny in a Cornell Box.
Models in engineering & science have *way* more complexity in geometry/materials than what conventional solvers can handle.
But imagine if simulation was like Monte Carlo rendering: just load up a complex model and hit "go"; don't worry about meshing, basis functions, etc. [1/n]
Here's one fun example: heat radiating off of infinitely many aperiodically-arranged black body emitters, each with super-detailed geometry, and super-detailed material coefficients.
From this view alone, the *boundary* meshes have ~600M vertices. Try doing that with FEM! [3/n]
Here's another fun question: given two loops around an (infinite) pole, can you remove one loop without breaking it?
Amazingly enough... yes!
This is a surprising example of what's called an "ambient isotopy": a continuous deformation of space taking one shape to another. 1/n
People have made some great drawings of this transformation over the years (sometimes using a loop rather than an infinite pole—which is equivalent), but it can still be hard to interpolate between individual drawings in your head.
(...does a movie make it any clearer?!) 2/n
What's also fun about the motion in the movie above is that it was created without* human input: instead, the computer tries to nudge the shape around so that every point is as far as possible from itself. You can read all about it in this thread:
Disclaimer: this is a simplified exercise for a final exam and should not be used for serious scientific work! It omits important forces and uses nonphysical constants.
What's the nicest way to draw a shape with many "holes"?
We can use the principle of repulsion to explore this question: each point of the shape behaves like a charged particle, trying to repel all others. Surface tension prevents everything from shooting off to infinity. 1/n
For millennia people have been drawn to the question: what are the "nicest" possible shapes that exist?
This is really a basic question about nature: these shapes exist outside space and time; the same shapes can be discovered by civilizations anywhere in the universe. 2/n
"Nicest" could mean the most symmetric—for instance, the ancient Greeks discovered there were five so-called Platonic solids where every face and every vertex looks the same: the tetrahedron, cube, octahedron, dodecahedron, and icosahedron. 3/n