Crate box_intersect_ze

Provides algorithms for broad phase collision detection. Specifically, implements Zomorodian and Edelsbrunner’s hybrid algorithm using streamed segment trees, pruning and scanning, described in Fast software for box intersections. Takes much inspiration from the implementation in CGAL.

Examples

use box_intersect_ze::set::BBoxSet;
use box_intersect_ze::boxes::Box3Df32;
use rand_chacha::ChaCha8Rng;
use rand::SeedableRng;

// create some boxes
let box0 = Box3Df32::new([0.0, 0.0, 0.0], [10.0, 10.0, 10.0]);
let box1 = Box3Df32::new([5.0, 5.0, 5.0], [15.0, 15.0, 15.0]);
let box2 = Box3Df32::new([10.0, 10.0, 10.0], [20.0, 20.0, 20.0]);

// add them to a BBoxSet
let mut boxes = BBoxSet::with_capacity(3);
boxes.push(0, box0);
boxes.push(1, box1);
boxes.push(2, box2);
boxes.sort(); // sort it in dimension 0

let mut result = Vec::with_capacity(2); // set capacity according to expected number of intersections to avoid resizing
box_intersect_ze::intersect_ze(&boxes, &boxes, &mut result, &mut ChaCha8Rng::seed_from_u64(1234)); // get the intersections

assert!(result.contains(&(1,0)));
assert!(result.contains(&(2,1)));
assert!(!result.contains(&(2,0)));
assert!(!result.contains(&(0,2)));

Modules

boxes	Boxes of various types and dimensions that can be checked for intersection
internals	Implementations of the algorithms provided by this crate. You probably want to call the wrappers at the top level of the crate instead.
set	Sets of boxes that can be passed to the intersection finding algorithms

Traits

HasInfinity	Trait for box boundary types
Rng	Trait for random number generator used in intersect_ze for approximate median calculation

Functions

intersect_brute_force	Finds box intersections by checking every box in a against every box in b. Performs well for on the order of 100 boxes. O(n^2)
intersect_scan	Finds all intersections between boxes in a and b using a scanning algorithm. Should perform reasonably up to approximately 1,000 boxes
intersect_ze	Finds all intersections between boxes in a and b using Zomorodian and Edelsbrunner’s hybrid algorithm (streamed segment trees pruned with a cutoff).
intersect_ze_custom	Like intersect_ze but with a customizable cutoff.