Crate broccoli[−][src]
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
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 in general
use Tree
unless you want
to use functions like collect_colliding_pairs
.
In which case use TreeInd
.
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 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 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.
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.
Re-exports
Modules
Assertion functions to ensure correct results.
Contains code to help build the Tree
structure with more options than
just using broccoli::new
.
Container trees that deref to Tree
Helper functions to construct objects from closures that implement query traits.
Naive query functions to compare against broccoli.
Contains node-level building block structs and visitors used for a Tree
.
Items to parallel build/query functions.
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.
Items related to querying.
Structs
A space partitioning tree.