Crate dinotree

2d Tree Divider Representation:


   o   ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┃         ┆         o
 ┈┈┈┈┈┈┆     o      o     ┃     o   ┆   o                 o
 ───────o─────────────────┃         o┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
               ┆       o  o   o     ┆
       o       ┆    o     ┃┈┈┈┈┈o┈┈┈┆       o
               ┆   o      ┃         o             o
               ┆┈┈┈┈┈┈┈┈┈┈┃         ┆                   o
     o         o    o     ┃───────o────────────────────────
               ┆          ┃                ┆   o
 ┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆      o   o   o            ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
    o          ┆          ┃┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆         o
         o     ┆   o      ┃        o       ┆   o
               ┆          ┃                ┆

Axis alternates every level.
Divider placement is placed at the median at each level.
Objects that intersect a divider belong to that node.
Every divider keeps track of how thick a line would have to be
to 'cover' all the bots it owns.
All the objects in a node are sorted along that node's axis.

Overview

Provides the dinotree data structure and ways to traverse it. No actual query algorithms are provided in this crate. Only the data structure and a way to construct and traverse it are provided in this crate.

Data Structure

Three flavors of the same fundamental data structure are provided. They each have different characteristics that may make you want to use them over the others.

• DinoTree is made up of (Rect<N>,&mut T)
• DinoTreeDirect is made up of (Rect<N>,T)
• DinoTreeIndirect is made up of &mut (Rect<N>,T)

Data Structure Details

• DinoTree is the most well rounded and most performant in all cases. The aabb's themselves don't have a level of indirection. Broad-phase algorithms need to look at these very often. It's only when these algorithms detect a intersection do they need to look further, which doesnt happen as often. so a level of indirection here is not so bad. The fact that T is a pointer, also means that more aabb's will be in cache at once, further speeding up algorithms that need to look at the aabb's very often.

• DinoTreeDirect can be fairly fast in cases where there are many, many overlapping elements in the tree, but this comes at the cost of a more expensive base cost of constructing (and deconstructing) the tree. One benefit of using this tree, is that it owns the elements completely, so there are no lifetime references to worry about.

• DinoTreeIndirect has fast tree construction given that we are just sorting and swapping pointers, but there is no cache-coherence during the query phase, so this can cause real slow down to query algorithms if there are many overlapping elements.

BBox Differences

DinoTree and DinoTreeDirect both have the user provide a &mut [T] or Vec<T> and produce a (Rect<N>,&mut T) or (Rect<N>,T) from that slice and a user provided aabb construction function. This was done to minimize total memory used. In most cases, an elements aabb doesnt mean anything unless it exists in a space partitioning tree. So if the tree doesnt exist, the aabb is just taking up spacing in that object slowing down other algorithms that have to iterating over all the bots for some other purpose. So this api encourages the user to only make the abb on creation of the tree.

In the case of DinoTreeIndirect, we can hardly avoid it, since the tree is made up solely of pointers so the user must provide a slice with the aabb for each object already.

NotSorted

For comparison, a normal kd-tree is provided by NotSorted. In this tree, the elements are not sorted along an axis at each level.

User Protection

A lot is done to forbid the user from violating the invariants of the tree once constructed while still allowing them to mutate elements of the tree. The user can mutably traverse down the tree with a VistrMut and ElemSliceMut, but the elements that are returned have already been destructured in such a way that the user only has read-only access to the Rect<N>, even if they do have write access to the inner T.

Usage Guidlines

If you insert aabb's with zero width or zero height, it is unspecified behavior. It is expected that all elements in the tree take up some area (just like in real life).

Re-exports

pub use axgeom;

pub use compt;

pub use rayon;

Modules

bbox	A collection of different bounding box containers.
dinotree	The dinotree data structure. The tree is made up of: (Rect<N>,&mut T)
dinotree_direct	A version of dinotree where the tree is made up of (Rect<N>,T)
dinotree_indirect	A version of dinotree where the tree is made up of &mut (Rect<N>,T)
elem	Provies a slice that produces destructured bounding boxes as the elements.
notsorted	A version of a dinotree where the bots are not sorted.
par	Contains code to write generic code that can be run in parallel, or sequentially. Not intended to be used directly by the user. Used by algorithms that operate on the tree.
prelude	Prelude to include by using: pub use dinotree::prelude::*
tools	Provies some debugging and misc functions.
tree	Contains generic code using both all dinotree versions

Traits

HasAabb	Marker trait to signify that this object has an axis aligned bounding box.
HasAabbMut	This object can return an aabb and simultaneously return a inner object that can be mutated.
NumTrait	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.