Crate dinotree

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.

The tree is comprised of copies of objects (rather than references) sorted to improve cache coherency. There is an alternative NoCopyDinoTree that does not allocate more space, but instead rearranges the bots in a user provided slice for better cache coherency.

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.
 

Unsafety

The HasAabb trait is marked as unsafe. See its description. Unsafety used to have slices of bots in the tree, but also a slice of all the bots so that we can efficiently return a slice of all the bots. Unsafety is used to reuse code between sequential and parallel build algorithms.

Analysis

Please see the dinotree_report github project, for a writeup of the design and analysis of the algorithms in this project.

Modules

bbox	A collection of different bounding box containers.
dinotree	The dinotree data structure.
dinotree_generic	Like a dinotree, but with a more generic interface. This comes at the cost of performance. Use this only to compare against the main one.
elem	Provies a slice that produces destructured bounding boxes as the elements, so as not to give the user mutable references to the elements themselves. If the user were to get these, they could swap elements in the tree and violate the invariants of the tree.
notsorted	A version of a dinotree where the bots that belong to a node are not sorted along an axis. So this is really a regular kd-tree.
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. If two HasAabb objects have aabb's that do not intersect, then it must be safe to have a mutable reference to each simultaneously.
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.