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