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.