Thread by @keenanisalive

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)

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)

However, coming up with a discrete Laplacian that works well on any mesh (or point cloud) is hard, because data found "in the wild" can be really awful/crazy!

(4/n)

As @nmwsharp points out in his talk, there are a lot of different things that can go wrong with a mesh. For instance:

1. it doesn't accurately represent the shape
2. it has bad elements (like skinny triangles)
3. it has crazy connectivity (e.g., nonmanifold)

(5/n)

Though we can't do much about (1), our Laplacian provides a "black box" solution to (2) and (3): give us any crazy mesh you want, with bad triangles and arbitrary connectivity, and we'll spit out a high-quality Laplacian. Best of all: it's just a standard V x V matrix. (6/n)

How does it work? In short, "under the hood" we replace your mesh with a double cover where all edges are manifold—and all vertices are nonmanifold! (Sounds crazy, I know…).

We call this contraption the "tufted cover," because it looks a bit like tufted upholstery.

(7/n)

Initially, the triangles of this tufted cover are just as bad (or good) as they were in the original mesh. But since the edges are now manifold, we can perform edge flips to improve quality—ultimately getting an "intrinsic Delaunay triangulation" (8/n)

What's so great about an intrinsic Delaunay triangulation? For one thing, it provides a 100% guarantee that there are no negative edge weights—which can cause massive problems for algorithms (see below). Also, it tends to improve the basis functions, increasing accuracy. (9/n)

The great thing is that all this "tufting" and flipping didn't change the vertex set: we still have the same V vertices. So if we go and build the usual cotan-Laplace matrix, we get a V x V matrix that can be used *directly on the original mesh*—but works much better. (10/n)

So how much better does this work? For "good" meshes, it will behave just like the usual cot-Laplacian, but for "bad" meshes it can make a world of difference. For instance, here's a comparison of computing geodesic distance with our Laplacian vs. the usual cot-Laplace: (11/n)

And here's an example of doing shape deformation on a mesh that was created from a bunch of (rather nasty) mesh boolean operations: (12/n)

Ok, what about point clouds? Here we do the usual thing of grabbing the k nearest neighbors and building local triangulations. But instead of the usual weighting schemes (Gaussian, sum of cotans, …), we join these triangles together and build our new "tufted" Laplacian! (13/n)

The beauty of this approach is that the accuracy and robustness we had in the mesh case carries over directly to point clouds. For example, Green's functions computed using earlier point cloud Laplacians can have artifacts like underflow or negative values. Not in our case!(14/n)

Also, since our point cloud Laplacian comes from a mesh, it's super sparse: about 7 nonzeros per row/column (vs. about 30 or so for schemes like Belkin). Between the sparsity, accuracy, and reliability, point cloud processing starts to feel a lot more like mesh processing. (15/n)

Anyway, that's a taste of what we're up to—check out the paper/video/code for more!

And if you have a chance, attend the (free!) Symposium on Geometry Processing @GeometryProcess next week, where you'll see this and many other terrific new papers on geometry processing! (n/n)