[−][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
Type | Name | Features | Downsides |
---|---|---|---|
(Rect<N>,&mut T) | Semi-direct | Fast | Uses more memory (aabb copied) |
(Rect<N>,T) | Direct | Space efficient | Original order not preserved |
&mut (Rect<N>,T) | Indirect | Simple | More cache misses for large n |
There are so many Tree types which one do I use?
Different variations are provided to give the user
more options on what kind of characteristics they want.
i.e. less memory vs faster vs less unsafe code.
Some also unlock more functions at the cost of a more restrictive api.
The collections
module goes into more depth as well as the book mentioned above.
TL;DR use Tree
and fill it with BBox<u32,&mut T>
(Semi-Direct) unless you want
to use functions like collections::TreeRefInd::collect_colliding_pairs
. See
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
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
].
The broccoli book mentioned above compares performance. 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 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 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.
nostd
Uses no_std
, but uses the alloc
crate.
Re-exports
pub use axgeom; |
pub use compt; |
pub use rayon; |
Modules
analyze | Contains code to help analyze the |
collections | Container trees that deref to |
convert | Helper functions to convert aabbs in floats to integers |
node | Contains node-level building block structs and visitors used for a |
par | 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. |
pmut | Provides a mutable pointer type that is more restrictive that |
prelude | The broccoli prelude. |
query | Module contains query related structs. |
Structs
BBox | A bounding box container object that implements |
NotSorted | 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 |
Rect | An axis aligned rectangle. Stored as two Ranges. It is a semi-closed rectangle. A point is considered inside the rectangle if it is in [start,end) for both x and y. |
Tree | The data structure this crate revoles around. |
Traits
Aabb | Trait to signify that this object has an axis aligned bounding box.
|
HasInner | 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. |
Num | The underlying number type used for the tree. 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. |
Functions
bbox | Shorthand constructor of |
default_axis | Returns the default axis type. |
new | Create a |
new_par | Create a |
rect | |
with_axis | Create a |
with_axis_par | Create a |
Type Definitions
DefaultA | The default starting axis of a |