Skip to content

Mesh containment and line segment intersection queries in Python (over rust)

License

Notifications You must be signed in to change notification settings

clbarnes/ncollpyde

Repository files navigation

ncollpyde

Actions Status Documentation Status

A python library for spatial queries of points and line segments with meshes. ncollpyde wraps around a subset of the parry rust library (formerly its predecessor ncollide).

Install

pip install ncollpyde

Pre-built wheels are available for Linux, MacOS, and Windows. If you have a stable rust compiler, you should also be able to install from source.

Features

  • Checking whether points are inside a volume defined by a triangular mesh
  • Checking the intersection of line segments with the mesh
  • Get the (signed) distance from points to the boundary of a mesh

Usage

This library implements most of its functionality through the Volume class, instantiated from an array of vertices, and an array of triangles as indices into the vertex array.

# get an array of vertices and triangles which refer to those points
import meshio
mesh = meshio.read("meshes/teapot.stl")

# use this library
from ncollpyde import Volume

volume = Volume(mesh.points, mesh.cells_dict["triangle"])

# or, for convenience
volume = Volume.from_meshio(mesh)

# containment checks: singular and multiple
assert [-2.30, -4.15,  1.90] in volume
assert np.array_equal(
    volume.contains(
        [
            [-2.30, -4.15, 1.90],
            [-0.35, -0.51, 7.61],
        ]
    ),
    [True, False]
)

# line segment intersection
seg_idxs, intersections, is_backface = volume.intersections(
    [[-10, -10, -10], [0, 0, 3], [10, 10, 10]],
    [[0, 0, 3], [10, 10, 10], [20, 20, 20]],
)
assert np.array_equal(seg_idxs, [0, 1])  # idx 2 does not intersect
assert np.array_equal(seg_idxs, [0, 1])
assert np.allclose(
    intersections,
    [
        [-2.23347309, -2.23347309, 0.09648498],
        [ 3.36591285, 3.36591285, 5.356139],
    ],
)
assert np.array_equal(
    is_backface,
    [False, True],
)

# distance from boundary (negative means internal)
assert np.array_equal(
    volume.distance([[10, 10, 10], [0, 0, 3]]),
    [10.08592464, -2.99951118],
)

See the API docs for more advanced usage.

Known issues

  • Performance gains for multi-threaded queries are underwhelming, especially for ray intersections: see this issue
  • Very rare false positives for containment
    • Due to a bug in the underlying library
    • Only happens when the point is outside the mesh and fires a ray which touches a single edge or vertex of the mesh.
    • Also affects is_backface result for ray intersection checks
  • manylinux-compatible wheels are built on CI but not necessarily in your local environment. Always allow CI to deploy the wheels.
  • If you are installing from a source distribution rather than a wheel, you need a compatible rust toolchain
  • Meshes with >= ~4.3bn vertices are not supported, as the underlying library uses u32 to address them. This is probably not a problem at time of writing; such a mesh would take up hundreds of GB of RAM to operate on.

ncollpyde v0.11 was the last to support meshio < 4.0.

Acknowledgements

Thanks to top users Philipp Schlegel (check out navis!) and Nik Drummond for their help in debugging and expanding ncollpyde 's functionality.

Thanks also to pyo3/ maturin developers @konstin and @messense for taking an interest in the project and helping along the way.

About

Mesh containment and line segment intersection queries in Python (over rust)

Resources

License

Stars

Watchers

Forks

Packages

No packages published