[1/n] There's been a lot of hubbub lately about the best known packing of 17 unit squares into a larger square, owing to this post:

https://twitter.com/KangarooPhysics/status/1625423951156375553

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

Has machine learning solved computer graphics?

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]

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] Our #SIGGRAPH2022 paper takes a major step toward this vision by building a bridge between PDEs & volume rendering: cs.dartmouth.edu/wjarosz/public…

Joint work with
@daseyb — darioseyb.com
@rohansawhney1 — rohansawhney.io
@wkjarosz — cs.dartmouth.edu/wjarosz/

[2/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

For the @CarnegieMellon computer graphics take-home final, students have to implement a basic molecular dynamics (MD) simulator.

MD is a basic tool in computational chemistry, drug discovery, and understanding diseases like COVID-19.

Give it a try here!
github.com/CMU-Graphics/m… 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.

Visualization is provided via the excellent #Polyscope library by CMU alumn @nmwsharp: polyscope.run

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

Suppose you have a pair of handcuffs linked together. Can you pull them apart without unlocking or breaking them, or letting them pass through themselves? With real handcuffs, definitely not! But if they're made of stretchy rubber, it turns out to be possible—as shown here. 1/9 This motion provides a surprising example of what is known in mathematics as an "ambient isotopy" of two surfaces: a continuous motion where the surface is not ripped, cut, pinched, or allowed to pass through itself. 2/9

Excited to share *two* papers appearing at #SIGGRAPHAsia2021, on "Repulsive Curves" and "Repulsive Surfaces."

Tons of graphics algorithms find nice distributions of points by minimizing a "repulsive" energy.

But what if you need to nicely distribute curves or surfaces? (1/14) We take a deep dive into this question, building fast algorithms for optimizing the recently developed "tangent-point energy" from surface theory.

Talk video:

Repulsive Curves: cs.cmu.edu/~kmcrane/Proje…
Repulsive Surfaces: cs.cmu.edu/~kmcrane/Proje…

(2/14)

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

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!

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] 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]

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…

https://twitter.com/msmathcomputer2/status/1404377428798197762

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.

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) 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)

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).

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)

https://twitter.com/nmwsharp/status/1279017688967393280

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)

Very excited to share #SIGGRAPH2020 paper w/ @rohansawhney1 on "Monte Carlo Geometry Processing"

cs.cmu.edu/~kmcrane/Proje…

We reimagine geometric algorithms without mesh generation or linear solves. Basically "ray tracing for geometry"—and that analogy goes pretty deep (1/n) Especially for problems with super complicated geometry, not having to mesh the domain provides a massive reduction in real world end-to-end cost. For instance, this model takes 14 hours to mesh and solve w/ FEM, but less than 1 minute to preview with Monte Carlo: (2/n)

Just uploaded a video on the Laplacian:

If you've heard of the Laplacian and always wondered what it was, or feel like you don't have great intuition for what it means, take a look—we explore how the Laplacian shows up in geometry, physics, & computation. This video is part of a series of lectures on #DiscreteDifferentialGeometry from Carnegie Mellon University @SCSatCMU.

You can find the playlist here: youtube.com/playlist?list=…

The course webpage, including notes & exercises can be found here:
geometry.cs.cmu.edu/ddg