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 treelet points = [[1.0,1.0],[2.0,1.0],[3.0, -1.0]];// range of legal radii for collision-checkinglet 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 collideassert!(!captree.collides(&[1.5,1.5],0.01));// sphere centered at (1.5, 1.5) with radius 1.0 does collideassert!(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.