A powerful idea in math (that nobody teaches you directly…):

If you don't know how to map between two "things," you can often map each of them to the same "canonical thing."

Then you can just go from the 1st thing to the canonical thing, and back to the 2nd thing. [1/n] Image
This idea shows up all over the place.

I'll give a few examples—but would love to hear about more of them, that show up your neck of the woods.
🌴🌳🌲🐇

[2/n]
One basic question is: how do I express a change of basis between two arbitrary bases (u1,u2) and (v1,v2)?

Answer: the matrix U with columns u1, u2 takes you from the standard basis e1=(1,0), e2=(0,1) to the basis u1,u2. (Just try hitting e1 and e2 with U!)

Then compose…[3/n] Image
Different question: given two triangulations of the sphere, can I always get from one to the other by flipping edges?

Answer: yes! Pick any triangle abc and flip until c has degree 3. Keep repeating on triangle abx, where x is the remaining neighbor of c.

Then compose… [4/n] Image
Totally different question: how do I find a nice, bijective map between two smooth surfaces of genus-0?

I won't try to prove this in a tweet, but the answer is: keep smoothing out the curvature until you get a round sphere (Riemann mapping/Yamabe flow).

Then compose… [5/n] Image
What are some other instances of "difficult maps made simple" by first mapping to a canonical object? [n/n]

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Keenan Crane

Keenan Crane Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @keenanisalive

2 Aug
Think knots are easy to untangle?

As a companion to our recent paper on "Repulsive Curves," we're releasing a dataset of hundreds of *extremely* difficult knots: cs.cmu.edu/~kmcrane/Proje…

In each case, a knotted & canonical embedding is given. Can you recover the right knot? 1/5
We've already tried a few dozen methods—from classics like "KnotPlot", to baselines like L-BFGS, to bleeding-edge algorithms like AQP, BCQN, etc.

For many knots, most these methods get "stuck," and don't reach a nice embedding.

Even our method doesn't hit 100%—but is close! 2/5
But this is a pretty unique problem relative to "standard" energies in geometry processing

For one thing, it considers all O(n²) pairs of points rather than just neighbors in a mesh

For another, you can't just *avoid* collisions—you have to maximize your distance from them. 3/5
Read 6 tweets
2 Aug
New paper with Chris Yu & Henrik Schumacher: cs.cmu.edu/~kmcrane/Proje…

We model 2D & 3D curves while avoiding self-intersection—a natural requirement in graphics, simulation & visualization.

Our scheme also does an *amazingly* good job of unknotting highly-tangled curves!

[1/n]
[2/n] Here's a short movie that summarizes some of what we do:

And if you don't care *how* it works, here's the code!
github.com/icethrush/repu…

Otherwise, read on to find out more!
[3/n] A classic problem is deciding if a curve is an "unknot": can it be untangled into a circle, without passing through itself?

We don't solve this problem conclusively—but can use untangling as a stress test for our method

Typically, we can untangle crazy knots, crazy fast!
Read 43 tweets
14 Jun
Uniform edge lengths are a reasonable proxy for mesh quality, since equilateral triangles have good angles. But if you have more specific criteria, you can usually do better. "Hodge-Optimized Triangulations" provides a nice discussion of this perspective: geometry.caltech.edu/pubs/MMdGD11.p…
A popular approach in graphics is something like Botsch & Kobbelt, "Remeshing for Multiresolution Modeling" (Sec. 4): graphics.rwth-aachen.de/media/papers/r…

Basic idea: iteratively move vertices to equalize areas, split long edges, collapse short edges, & flip edges to improve vertex valence.
In this class of algorithms, I really like Chen & Holst, "Efficient mesh optimization schemes based on Optimal Delaunay Triangulations": math.uci.edu/~chenlong/Pape…

Here there's a clear notion of optimality, & an efficient preconditioner. For surfaces: restrict to tangential motions
Read 12 tweets
25 May
Excited to share a new #SIGGRAPH2021 paper with @markgillesie81 and Boris Springborn that is a pretty big breakthrough in mesh parameterization: cs.cmu.edu/~kmcrane/Proje…

In short: no matter how awful your mesh is, we compute beautiful high-quality texture coordinates.

(1/n) Image
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) Image
Read 13 tweets
11 May
1/n This past weekend I gave two lectures @HarvardCMSA on “intrinsic triangulations” and how they can open new doors in geometric computing.

Videos here:



And details about the (terrific!) event here: cmsa.fas.harvard.edu/frg-2021/
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.
Read 19 tweets
3 Jul 20
Excited to share new work w/ @nmwsharp on a Laplace operator that works great for both point clouds and arbitrary, nonmanifold triangle meshes—aimed at geometry processing & learning:

web: cs.cmu.edu/~kmcrane/Proje…
code: github.com/nmwsharp/nonma…
video: youtube.com/watch?v=JY0koz…
(1/n) Image
First of all, if you don't know what a Laplace operator is or why it's important (and are curious to find out!), I've recorded an intro lecture here with a bunch of animations and examples:

youtube.com/watch?v=oEq9RO…

(2/n)
Just like the Fast Fourier Transform (FFT) is the foundation of a lot of classical signal processing, the Laplacian is the foundation for a lot of modern algorithms in geometry processing and geometric learning:

cs.cmu.edu/~kmcrane/Proje…

(3/n) Image
Read 16 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us on Twitter!

:(