Collision-Affording Point Trees: SIMD-Amenable Nearest Neighbors for Fast Collision Checking

For a full demonstration of CAPTs running in real-time, see this video.

This is a Rust implementation of the collision-affording point tree (CAPT), a data structure for SIMD-parallel collision-checking against point clouds. The CAPT supports extremely high-throughput collision checking, supporting online, real-time motion planning.

You may also want to look at the following other sources:

• The paper
• Demo video
• C++ implementation
• Blog post about it

If you use this in an academic work, please cite it as follows:

@InProceedings{capt,
  title = {Collision-Affording Point Trees: {SIMD}-Amenable Nearest Neighbors for Fast Collision Checking},
  author = {Ramsey, Clayton W. and Kingston, Zachary and Thomason, Wil and Kavraki, Lydia E.},
  booktitle = {Robotics: Science and Systems},
  date = {2024},
  url = {https://www.roboticsproceedings.org/rss20/p038.pdf},
}

Usage

The core data structure in this library is the Capt, which is a search tree used for collision checking.

use capt::Capt;

// list of points in tree
let points = [[1.0, 1.0], [2.0, 1.0], [3.0, -1.0]];

// range of legal radii for collision-checking
let radius_range = (0.0, 100.0);

let captree = Capt::new(&points, radius_range);

// sphere centered at (1.5, 1.5) with radius 0.01 does not collide
assert!(!captree.collides(&[1.5, 1.5], 0.01));

// sphere centered at (1.5, 1.5) with radius 1.0 does collide
assert!(captree.collides(&[1.5, 1.5], 0.01));

Installation

capt is available as a package on crates.io. This means that adding capt to your Rust project is as simple as asking Cargo to add it as a dependency.

cargo add capt

To use the SIMD-parallel features of CAPTs, make sure to include it as a feature.

cargo add capt --features simd

License

This work is licensed to you under the Apache 2.0 license. For further details, refer to LICENSE.md.