Keenan Crane

CARNEGIE MELLON UNIVERSITY

A Laplacian for Nonmanifold Triangle Meshes

Symposium on Geometry Processing 2020

Best Paper Award

We describe a discrete Laplacian suitable for any triangle mesh, including those that are nonmanifold or nonorientable (with or without boundary). Our Laplacian is a robust drop-in replacement for the usual cotan matrix, and is guaranteed to have nonnegative edge weights on both interior and boundary edges, even for extremely poor-quality meshes. The key idea is to build what we call a “tufted cover” over the input domain, which has nonmanifold vertices but manifold edges. Since all edges are manifold, we can flip to an intrinsic Delaunay triangulation; our Laplacian is then the cotan Laplacian of this new triangulation. This construction also provides a high-quality point cloud Laplacian, via a nonmanifold triangulation of the point set. We validate our Laplacian on a variety of challenging examples (including all models from Thingi10k), and a variety of standard tasks including geodesic distance computation, surface deformation, parameterization, and computing minimal surfaces.

Presentation

nonmanifold-laplacian—C++ implementation; given any triangle mesh mesh, dumps a high-quality Laplacian to disk. Also includes an interactive visualization via Polyscope).

Thanks to Boris Springborn and Max Wardetzky for helpful discussions. This work was supported by NSF award 1943123, an NSF Graduate Fellowship, a Packard Fellowship, and gifts from Autodesk, Adobe, Activision Blizzard, Disney, and Facebook. Thanks to creators of meshes: Thingiverse user Ramenspork’s high school students and TurboSquid user Gatzegar.

@article{Sharp:2020:LNT,
author={Nicholas Sharp and Keenan Crane},
title={{A Laplacian for Nonmanifold Triangle Meshes}},
journal={Computer Graphics Forum (SGP)},
volume={39},
number={5},
year={2020}
}

Figures