[][src]Crate broccoli

Broccoli is a broadphase 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 exlored more in depth in the broccoli book

  • (Rect<N>,&mut T) *recommended
  • (Rect<N>,T)
  • &mut (Rect<N>,T)

There are so many Tree types which one do I use?

Different variations are provided to give the user more or less control which rely or more or less unsafe code. The collections module goes into more depth as well as the book mentioned above.

TL;DR use collections::TreeRefInd.

Floating Point

The Num trait used for the aabbs inserted into the tree must implement Ord, thus you can't add f32 or f64. However, you can use the ordered_float crate, which is re-exported at [axgeom::ordered_float]. Construction and querying is very comparison heavy so prefer NotNan<T> over OrderedFloat<T>. However, check out the broccoli book mentioned above. However, for best performance, you will likely want to convert the floats to integers anyway.

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 PMut<T> type that forbids mutating the whole element.


Raw pointers are used for the container types in the container module and for caching the results of finding colliding pairs.

MultiRectMut uses unsafety to allow the user to have mutable references to elements that belong to rectangle regions that don't intersect at the same time. This is why the Aabb trait is unsafe.


If you shorten "broadphase collision" to "broad colli" and say it fast, it sounds like broccoli. Broccoli also have tree like properties and broccoli uses a tree data structure.


Uses no_std, but uses the alloc crate.


pub use axgeom;
pub use compt;
pub use rayon;



Contains code to help analyze the Tree structure. Only used to measure the performance of the structure.


Container trees that deref to broccoli::Tree


Helper functions to convert aabbs in floats to integers


Contains node-level building block structs and visitors used for a Tree.


Contains code to write generic code that can be run in parallel, or sequentially. The api is exposed in case users find it useful when writing parallel query code to operate on the tree.


Provides a mutable pointer type that is more restrictive that &mut T, in order to protect tree invariants. PMut is short for protected mutable reference.


The broccoli prelude.


Module contains query related structs.



A bounding box container object that implements Aabb and HasInner. Note that &mut BBox<N,T> also implements Aabb and HasInner.


A version of Tree where the elements are not sorted along each axis, like a KD Tree. For comparison, a normal kd-tree is provided by NotSorted. In this tree, the elements are not sorted along an axis at each level. Construction of NotSorted is faster than Tree since it does not have to sort bots that belong to each node along an axis. But most query algorithms can usually take advantage of this extra property.


The data structure this crate revoles around.



Trait to signify that this object has an axis aligned bounding box. get() must return a aabb with the same value in it while the element is in the dinotree. This is hard for the user not to do, this the user does not have &mut self, and the aabb is implied to belong to self. But it is still possible through the use of static objects or RefCell/ Mutex, etc. Using this type of methods the user could make different calls to get() return different aabbs. This is unsafe since we allow query algorithms to assume the following: If two object's aabb's don't intersect, then they can be mutated at the same time.


Trait exposes an api where you can return a read-only reference to the axis-aligned bounding box and at the same time return a mutable reference to a seperate inner section.


The underlying number type used for the dinotree. It is auto implemented by all types that satisfy the type constraints. Notice that no arithmatic is possible. The tree is constructed using only comparisons and copying.



Shorthand constructor of BBox


Returns the default axis type.


Create a broccoli::Tree using the default axis.


Create a broccoli::Tree using the default axis in parallel.


Create a broccoli::Tree using a specified axis.


Create a broccoli::Tree using a specified axis in parallel.

Type Definitions


The default starting axis of a broccoli::Tree. It is set to be the Y axis. This means that the first divider is a horizontal line since it is partitioning space based off of the aabb's Y value.