[][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) Semi-direct
  • (Rect<N>,T) Direct
  • &mut (Rect<N>,T) Indirect

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

The container module lists the tree types and they are all described there, but the TL;DR is use Tree and fill it with BBox<N,&mut T> unless you want to use functions like collect_colliding_pairs. In which case use TreeRefInd.

Checkout the github examples.

Parallelism

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 doesnt understand, it will just arbitrary pick a result. So if there is even just one NaN, tree construction and querying will not panick, but would have unspecified results. If using floats, it's the users responsibility to not pass NaN numbers. 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 PMut<T> type that forbids mutating the aabbs.

Unsafety

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

query::Queries::multi_rect 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 node::Aabb trait is unsafe.

Name

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.

Re-exports

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

Modules

analyze

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

container

Container trees that deref to Tree

convert

Helper functions to convert aabbs in floats to integers

node

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

pmut

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.

prelude

The broccoli prelude.

query

Module contains query related structs.

Structs

Tree

The data structure this crate revoles around.

Functions

bbox

Shorthand constructor of node::BBox

new

Create a Tree using the default axis.

new_par

Create a Tree using the default axis in parallel.

rect

Convenience function to create a Rect.