Thread by @keenanisalive

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)

The basic problem? Given a collection of points, curves, or surfaces in space, find a well-distributed arrangement that avoids (self-)intersection.

To make things interesting, you also usually have some constraints—like: the geometry is contained inside a bunny!
(3/14)

Why would you want to do this?

Well, *point* repulsion is already used in every major area of computer graphics: from image stippling to mesh generation to density estimation to fluid simulation!

But surprisingly little work has been done on repulsive curves & surfaces… (4/14)

And yet there are *all sorts* of things you can do with higher-dimensional repulsion—from better graph layouts, to generative modeling, to robotic path planning, to intersection-free modeling & illustration, to artificial tissue design, to unraveling mathematical mysteries!(5/14)

Repulsion goes far beyond (literally) traditional collision-aware design & modeling: rather than slamming on the brakes right before the moment of impact, repulsive optimization is all about finding a harmonious *global* balance of forces, long before collisions occur. (6/14)

Imagine, for instance, playing a game of pool with charged particles rather than rigid bodies.

In contrast to collision, where you can aggressively prune away distant barrier functions, the whole point of repulsive optimization is to get long-range forces into equilibrium (7/14)

Beyond just dealing with O(n²) interactions, repulsive energies lead to some rich & interesting challenges. For one thing, repulsive energies for points don't nicely generalize to curves & surfaces. For another, you have to deal w/ optimization of "fractional derivatives." (8/14)

…Rather than regurgitate everything here on Twitter, I'll point again to this talk:

Since I know it's easy to get lost in the math & switch off the video, I gave each section a level of difficulty. Don't feel bad about skipping to the fun stuff! (9/14)

You might also be interested in checking out this longer Twitter thread, which also goes deeper into the details for curves:

https://twitter.com/keenanisalive/status/1422318272800829440

But the generalization to repulsive surfaces lets us do some really beautiful things like never before. (10/14)

To end with just one cool example, consider this pair of handcuffs in a "linked" and "unlinked" configuration.

Do you think it's possible to unlink the handcuffs, without breaking them apart or letting them pass through each other? (11/14)

If you said "yes," you were right (hey, you had a 50% chance!)

But can you show me how?

There are lots of beautiful drawings of this counter-intuitive transition—but unless you have a good geometric imagination, they can be pretty hard to follow. (12/14).

However, we can use repulsive optimization to make this remarkable topological phenomenon come to life.

Just minimize tangent-point energy starting in both linked and unlinked configurations, then join the two movies together (the 2nd one playing backwards). Voilà! (13/14)

The paper/videos have lots of other examples of new & different things you can do with repulsive shape optimization.

But the real limitation is *our* own creativity!

I'd love to hear what ideas this sparks for you, and what problems, challenges, & creations it leads to…(14/14)