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.