search

nmwsharp / potpourri3d

An invigorating blend of 3D geometry tools in Python.
MIT License
414 stars 31 forks source link

readme

potpourri3d

A Python library of various algorithms and utilities for 3D triangle meshes and point clouds. Managed by Nicholas Sharp, with new tools added lazily as needed. Currently, mainly bindings to C++ tools from geometry-central.

pip install potpourri3d

The blend includes:

Installation

Potpourri3d is on the pypi package index with precompiled binaries for most configuations. Get it like:

pip install potpourri3d

If none of the precompiled binaries match your system, pip will attempt to compile the library from scratch. This requires cmake and a workng C++ compiler toolchain.

Note: Some bound functions invoke sparse linear solvers internally. The precompiled binaries use Eigen's solvers; using Suitesparse's solvers instead may significantly improve performance & robustness. To get them, locally compile the package on a machine with Suitesparse installed using the command below (relevant docs).

python -m pip install potpourri3d --no-binary potpourri3d

Documentation

Input / Output

Read/write meshes and point clouds from some common formats.

Mesh basic utilities

Mesh Distance

Use the heat method for geodesic distance to compute geodesic distance on surfaces. Repeated solves are fast after initial setup. Uses intrinsic triangulations internally for increased robustness.

import potpourri3d as pp3d

# = Stateful solves (much faster if computing distance many times)
solver = pp3d.MeshHeatMethodDistanceSolver(V,F)
dist = solver.compute_distance(7)
dist = solver.compute_distance_multisource([1,2,3])  

# = One-off versions
dist = pp3d.compute_distance(V,F,7)
dist = pp3d.compute_distance_multisource(V,F,[1,3,4])

The heat method works by solving a sequence of linear PDEs on the surface of your shape. On extremely coarse meshes, it may yield inaccurate results, if you observe this, consider using a finer mesh to improve accuracy. (TODO: do this internally with intrinsic Delaunay refinement.)

Mesh Vector Heat

Use the vector heat method to compute various interpolation & vector-based quantities on meshes. Repeated solves are fast after initial setup.

import potpourri3d as pp3d

# = Stateful solves
V, F = # a Nx3 numpy array of points and Mx3 array of triangle face indices
solver = pp3d.MeshVectorHeatSolver(V,F)

# Extend the value `0.` from vertex 12 and `1.` from vertex 17. Any vertex 
# geodesically closer to 12. will take the value 0., and vice versa 
# (plus some slight smoothing)
ext = solver.extend_scalar([12, 17], [0.,1.])

# Get the tangent frames which are used by the solver to define tangent data
# at each vertex
basisX, basisY, basisN = solver.get_tangent_frames()

# Parallel transport a vector along the surface
# (and map it to a vector in 3D)
sourceV = 22
ext = solver.transport_tangent_vector(sourceV, [6., 6.])
ext3D = ext[:,0,np.newaxis] * basisX +  ext[:,1,np.newaxis] * basisY

# Compute the logarithmic map
logmap = solver.compute_log_map(sourceV)

Mesh Geodesic Paths

Use edge flips to compute geodesic paths on surfaces. These methods take an initial path, loop, or start & end points along the surface, and straighten the path out to be geodesic.

This approach is mainly useful when you want the path itself, rather than the distance. These routines use an iterative strategy which is quite fast, but note that it is not guaranteed to generate a globally-shortest geodesic (they sometimes find some other very short geodesic instead if straightening falls into different local minimum).

import potpourri3d as pp3d

V, F = # your mesh
path_solver = pp3d.EdgeFlipGeodesicSolver(V,F) # shares precomputation for repeated solves
path_pts = path_solver.find_geodesic_path(v_start=14, v_end=22)
# path_pts is a Vx3 numpy array of points forming the path

In the functions above, the optional argument max_iterations is an integer, giving the the maximum number of shortening iterations to perform (default: no limit). The optional argument max_relative_length_decrease is a float limiting the maximum decrease in length for the path, e.g. 0.5 would mean the resulting path is at least 0.5 * L length, where L is the initial length.

Mesh Geodesic Tracing

Given an initial point and direction/length, these routines trace out a geodesic path along the surface of the mesh and return it as a polyline.

import potpourri3d as pp3d

V, F = # your mesh
tracer = pp3d.GeodesicTracer(V,F) # shares precomputation for repeated traces

trace_pts = tracer.trace_geodesic_from_vertex(22, np.array((0.3, 0.5, 0.4)))
# trace_pts is a Vx3 numpy array of points forming the path

Set max_iterations to terminate early after tracing the path through some number of faces/edges (default: no limit).

Point Cloud Distance & Vector Heat

Use the heat method for geodesic distance and vector heat method to compute various interpolation & vector-based quantities on point clouds. Repeated solves are fast after initial setup.

point cloud vector heat examples

import potpourri3d as pp3d

# = Stateful solves
P = # a Nx3 numpy array of points
solver = pp3d.PointCloudHeatSolver(P)

# Compute the geodesic distance to point 4
dists = solver.compute_distance(4)

# Extend the value `0.` from point 12 and `1.` from point 17. Any point 
# geodesically closer to 12. will take the value 0., and vice versa 
# (plus some slight smoothing)
ext = solver.extend_scalar([12, 17], [0.,1.])

# Get the tangent frames which are used by the solver to define tangent data
# at each point
basisX, basisY, basisN = solver.get_tangent_frames()

# Parallel transport a vector along the surface
# (and map it to a vector in 3D)
sourceP = 22
ext = solver.transport_tangent_vector(sourceP, [6., 6.])
ext3D = ext[:,0,np.newaxis] * basisX +  ext[:,1,np.newaxis] * basisY

# Compute the logarithmic map
logmap = solver.compute_log_map(sourceP)

Other Point Cloud Routines

Local Triangulation

Construct a local triangulation of a point cloud, a surface-like set of triangles amongst the points in the cloud. This is not a nice connected/watertight mesh, instead it is a crazy soup, which is a union of sets of triangles computed independently around each point. These triangles are suitable for running many geometric algorithms on, such as approximating surface properties of the point cloud, evaluating physical and geometric energies, or building Laplace matrices. See "A Laplacian for Nonmanifold Triangle Meshes", Sharp & Crane 2020, Sec 5.7 for details.