Expand description

Broccoli is a broad-phase collision detection library. The base data structure is a hybrid between a KD Tree and Sweep and Prune.

Data Structure

Using this crate, the user can create three flavors of the same fundamental data structure. The different characteristics are explored more in depth in the broccoli book

  • (Rect<N>,&mut T) Semi-direct
  • (Rect<N>,T) Direct
  • &mut (Rect<N>,T) Indirect

Checkout the github examples.


Parallel versions of construction and colliding pair finding functions are provided. They use rayon under the hood which uses work stealing to parallelize divide and conquer style recursive functions.

Floating Point

Broccoli only requires PartialOrd for its number type. Instead of panicking on comparisons it doesn’t understand, it will just arbitrary pick a result. So if you use regular float primitive types and there is even just one NaN, tree construction and querying will not panic, but would have unspecified results. If using floats, it’s the users responsibility to not pass NaN values into the tree. There is no static protection against this, though if this is desired you can use the ordered-float crate. The Ord trait was not enforced to give users the option to use primitive floats directly which can be easier to work with.

Protecting Invariants Statically

A lot is done to forbid the user from violating the invariants of the tree once constructed while still allowing them to mutate parts of each element of the tree. The user can mutably traverse the tree but the mutable references returns are hidden behind the AabbPin<T> type that forbids mutating the aabbs.


pub use axgeom;


Extended query functions

Contains query modules for each query algorithm.

Provides the broccoli tree building blocks and code, but no querying code.


Compare query results between Tree and the easily verifiable Naive versions.

Easily verifiable naive query algorithms.

A tree where the elements in a node are not sorted.

Sweep and prune collision finding algorithm

A broccoli Tree.

An owned version of Tree


Abstract over containers that produce &mut [T]