2/n The story begins with the transition in the 19th century from thinking about geometry in terms of points in space (extrinsic) to thinking about the broader ways we can describe shapes without knowing how they’re embedded (intrinsic).
3/n Even though the intrinsic picture is now commonplace in mathematics, it’s still not how most people think about mesh processing. Almost universally we still describe the geometry of a mesh using Cartesian coordinates in a global coordinate system—just as we did in the 19th c.
4/n An alternative is to throw out the vertex coordinates and describe a mesh by its connectivity, plus edge lengths that describe just the local shape of each triangle. This is what I’ll call an “intrinsic triangulation.”
5/n Things get particularly interesting when this intrinsic triangulation actually comes from tracing out straight paths along a standard (“extrinsic”) triangulation. Even though these triangles look “bent,” they become ordinary triangles when unfolded into the plane.
6/n Ok, but why is it useful to “draw” one triangulation over another? It turns out there are a lot of good reasons, which can be motivated from three different angles.
7/n One angle is classic computational geometry. To improve a mesh in the plane while preserving its vertices, you can flip edges. But if you’re asked to also preserve the edges... that’s annoying! At best you can refine the mesh and hope the elements get better as you refine.
8/n Well, this “annoying” situation is *always* what you face in 3D: if you want to preserve the original geometry, you have to preserve vertices and edges—and hence refine like crazy. ...Unless you allow yourself to draw an intrinsic triangulation on top of the given one!
9/n In essence you’re now doing computational geometry on a polyhedral background domain, rather than a planar one. And so many classic planar algorithms can be “ported” to curved surfaces in a natural way.
10/n Another, related perspective is scientific computing, where your mesh must simultaneously play two roles: it defines the shape of the object being simulated, *and* provides the basis functions used to approximate the solution.
11/n When you start to build meshes in this setting it feels like a “no free lunch” situation. You want a good approximation of the geometry, with high-quality finite elements, while keeping the mesh small.
Traditionally, you get to pick just two.
12/n But if you relax your definition of a mesh, and allow your “simulation mesh” to be traced out over your “geometry mesh,” you can get the best of all worlds: a reasonably small mesh with great element quality and which perfectly captures the original geometry.
13/n What’s happened here is that you’ve de-coupled the mesh defining the bases from the one used to describe the geometry. And of course, even though the geometry is piecewise linear doesn’t mean your basis functions have to be.
14/n Finally, the intrinsic picture is natural for geometry processing, where many algorithms are expressed in terms of intrinsic objects (Laplacian, geodesic distance, Gaussian curvature...). Why then bother processing the mesh extrinsically?
15/n Another big motivation for intrinsic triangulations is robustness. Anyone who has worked with real data knows meshes can be really, really bad.
16/n And unfortunately this problem is not going to resolve itself. What we consider to be a “bad mesh” is just getting *worse* in time, as technologies like 3d scanning and printing become commonplace. How can we “hide” the challenges of meshes from most users?
17/n The elegant solution from numerical linear algebra is to encapsulate a series of complex transformations in a simple black box interface (like “backslash” in MATLAB). Turn the system into something nicer, that can be solved by less-robust algorithms.
18/n Likewise, rather than making geometric algorithms more robust one algorithm at a time, intrinsic triangulations help provide “robustness as a subroutine.” Retriangulate under the hood, run a standard algorithm, return the result—all without changing the geometry.
19/n Anyway, that’s just a little motivation & sneak preview. The lectures cover some of the latest and greatest data structures for doing this kind of thing, a bunch of fun algorithms, and a list of interesting open questions. Check it out!
• • •
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