broccoli 5.0.5

Broccoli

Broccoli is a broad-phase collision detection library.

The base data structure is a hybrid between a KD Tree and Sweep and Prune.

Checkout it out on github and on crates.io. Documentation at docs.rs.

Screenshot

Screen capture from the inner demo project.

Example

use broccoli::tree::rect;
fn main() {
    let mut inner1 = 0;
    let mut inner2 = 0;
    let mut inner3 = 0;

    // Rect is stored directly in tree,
    // but inner is not.
    let mut aabbs = [
        (rect(00, 10, 00, 10), &mut inner1),
        (rect(15, 20, 15, 20), &mut inner2),
        (rect(05, 15, 05, 15), &mut inner3),
    ];

    // Construct tree by doing many swapping of elements
    let mut tree = broccoli::Tree::new(&mut aabbs);

    // Find all colliding aabbs.
    tree.find_colliding_pairs(|a, b| {
        // We aren't given &mut T reference, but instead of AabbPin<&mut T>.
        // We call unpack_inner() to extract the portion that we are allowed to mutate.
        // (We are not allowed to change the bounding box while in the tree)
        **a.unpack_inner() += 1;
        **b.unpack_inner() += 1;
    });

    assert_eq!(inner1, 1);
    assert_eq!(inner2, 1);
    assert_eq!(inner3, 2);
}

Optimisation

I've focused mainly on making finding colliding pairs as fast as possible primarily in distributions where there are a lot of overlapping aabbs.

Quick rundown of what i've spent effort on and a rough estimate of performance cost of each algorithm in general.

Numbers are out of 10 and are just rough made up numbers. For more in-depth analysis, see the broccoli book.

Name

If you shorten "broad-phase collision" to "broad colli" and say it fast, it sounds like broccoli. Broccoli are also basically small trees and broccoli uses a tree data structure.