robust-laplacians-py

Build high-quality Laplace matrices on meshes and point clouds in Python. Implements [Sharp & Crane SGP 2020].

The Laplacian is at the heart of many algorithms across geometry processing, simulation, and machine learning. This library builds a high-quality, robust Laplace matrix which often improves the performance of these algorithms, and wraps it all up in a simple, single-function API!

Sample: computing eigenvectors of the point cloud Laplacian

Given as input a triangle mesh with arbitrary connectivity (could be nonmanifold, have boundary, etc), OR a point cloud, this library builds an NxN sparse Laplace matrix, where N is the number of vertices/points. This Laplace matrix is similar to the cotan-Laplacian used widely in geometric computing, but internally the algorithm constructs an intrinsic Delaunay triangulation of the surface, which gives the Laplace matrix great numerical properties. The resulting Laplacian is always a symmetric positive-definite matrix, with all positive edge weights. Additionally, this library performs intrinsic mollification to alleviate floating-point issues with degenerate triangles.

The resulting Laplace matrix L is a "weak" Laplace matrix, so we also generate a diagonal lumped mass matrix M, where each diagonal entry holds an area associated with the mesh element. The "strong" Laplacian can then be formed as M^-1 L, or a Poisson problem could be solved as L x = M y.

A C++ implementation and demo is available.

This library implements the algorithm described in A Laplacian for Nonmanifold Triangle Meshes by Nicholas Sharp and Keenan Crane at SGP 2020 (where it won a best paper award!). See the paper for more details, and please use the citation given at the bottom if it contributes to academic work.

Example

Build a point cloud Laplacian, compute its first 10 eigenvectors, and visualize with Polyscope

pip install numpy scipy plyfile polyscope robust_laplacian

import robust_laplacian
from plyfile import PlyData
import numpy as np
import polyscope as ps
import scipy.sparse.linalg as sla

# Read input
plydata = PlyData.read("/path/to/cloud.ply")
points = np.vstack((
    plydata['vertex']['x'],
    plydata['vertex']['y'],
    plydata['vertex']['z']
)).T

# Build point cloud Laplacian
L, M = robust_laplacian.point_cloud_laplacian(points)

# (or for a mesh)
# L, M = robust_laplacian.mesh_laplacian(verts, faces)

# Compute some eigenvectors
n_eig = 10
evals, evecs = sla.eigsh(L, n_eig, M, sigma=1e-8)

# Visualize
ps.init()
ps_cloud = ps.register_point_cloud("my cloud", points)
for i in range(n_eig):
    ps_cloud.add_scalar_quantity("eigenvector_"+str(i), evecs[:,i], enabled=True)
ps.show()

API

This package exposes just two functions:

  • mesh_laplacian(verts, faces, mollify_factor=1e-5)
    • verts is an V x 3 numpy array of vertex positions
    • faces is an F x 3 numpy array of face indices, where each is a 0-based index referring to a vertex
    • mollify_factor amount of intrinsic mollifcation to perform. 0 disables, larger values will increase numerical stability, while very large values will slightly implicitly smooth out the geometry. The range of reasonable settings is roughly 0 to 1e-3. The default value should usually be sufficient.
    • return L, M a pair of scipy sparse matrices for the Laplacian L and mass matrix M
  • point_cloud_laplacian(points, mollify_factor=1e-5, n_neighbors=30)
    • points is an V x 3 numpy array of point positions
    • mollify_factor amount of intrinsic mollifcation to perform. 0 disables, larger values will increase numerical stability, while very large values will slightly implicitly smooth out the geometry. The range of reasonable settings is roughly 0 to 1e-3. The default value should usually be sufficient.
    • n_neighbors is the number of nearest neighbors to use when constructing local triangulations. This parameter has little effect on the resulting matrices, and the default value is almost always sufficient.
    • return L, M a pair of scipy sparse matrices for the Laplacian L and mass matrix M

Installation

The package is availabe via pip

pip install robust_laplacian

The underlying algorithm is implemented in C++; the pypi entry includes precompiled binaries for many platforms.

Very old versions of pip might need to be upgraded like pip install pip --upgrade to use the precompiled binaries.

Alternately, if no precompiled binary matches your system pip will attempt to compile from source on your machine. This requires a working C++ toolchain, including cmake.

Known limitations

  • Mesh input must not have any unreferenced vertices.
  • For point clouds, this repo uses a simple method to generate planar Delaunay triangulations, which may not be totally robust to collinear or degenerate point clouds.

Dependencies

This python library is mainly a wrapper around the implementation in the geometry-central library; see there for further dependencies. Additionally, this library uses pybind11 to generate bindings, and jc_voronoi for 2D Delaunay triangulation on point clouds. All are permissively licensed.

Citation

@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}
}

For developers

This repo is configured with CI on appveyor to build wheels across platform.

Deploy a new version

  • Commit the desired version to the master branch, be sure the version string in setup.py corresponds to the new version number.
  • Watch th appveyor builds to ensure the test & build stages succeed and all wheels are compiled.
  • While you're waiting, update the docs.
  • Tag the commit with a tag like v1.2.3, matching the version in setup.py. This will kick off a new Appveyor build which deploys the wheels to PyPI after compilation.

GitHub