Crate grid_tree

Pixel quadtrees and voxel octrees.

Store any type in an OctreeI32, OctreeU32, QuadtreeI32, or QuadtreeU32, all of which are specific instances of the generic Tree. A Tree represents a map from (Level, Integer Coordinates) to T. Thus it is useful for storing pixel or voxel data with level-of-detail. The tree also requires that if a node slot is occupied (has data), then all ancestor slots are also filled.

Design Advantages

• Since a Tree has its own internal allocators, any pointers are completely local to the data structure. In principle, this makes it easy to clone the tree for e.g. uploading to a GPU (although we haven’t tried it for ourselves).
• The level 0 allocator does not store pointers, only values. Pointer overhead at higher levels can be amortized using chunked data, i.e. [T; CHUNK_SIZE]. The alternative “pointerless” octrees take up less memory, but are also more complex to edit and traverse.
• By using a hash map of root nodes, the addressable space is not limited by the height of the tree, and it is not necessary to “translate” the octree as it follows a focal point.
• By having a very simple data layout, access using a NodePtr is simply an array lookup.
• The NodeEntry and Tree::child_entry APIs allow for very simple code that fills entire trees with a single visitor closure.
• By implementing VectorKey for a custom key type, the addressable range can be extended to coordinates of arbitrary precision.

Performance

This structure is optimized for iteration speed and spatial queries that benefit from a bounding volume hierarchy (like raycasting). Finding a single node by NodeKey starting from the root should be minimized as much as possible, so you might find it useful to cache NodePtrs or amortize the search with a full tree traversal. Memory usage is decent given the simplicity of the implementation, and the pointer overhead is easily amortized by using dense chunk values.

• random access with NodeKey: O(depth)
• random access with NodePtr: O(1)
• iteration: O(nodes)
• memory usage per node:
  • level 0: size_of::<T>() bytes
  • level N > 0: size_of::<T>() + CHILDREN * 4 bytes
  • where CHILDREN=4 for a quadtree and CHILDREN=8 for an octree

Re-exports

pub use glam;

Structs

ChildPointers

All children pointers for some branch node. Some may be empty.

ChildRelation

A child NodePtr and its Parent.

NodeKey

Uniquely identifies a node slot in the Tree.

NodePtr

Uniquely and stably identifies an occupied node in the Tree (until the node is removed).

OccupiedNodeEntry

Parent

Info about a node’s parent.

RootNode

Tree

A generic “grid tree” which can be either a quadtree or an octree depending on the type parameters.

VacantNodeEntry

Enums

NodeEntry

VisitCommand

Constants

EMPTY_ALLOC_PTR

An AllocPtr that doesn’t point to anything.

Traits

BranchShape

The shape of a single node’s children. E.g. 2² for a quadtree and 2³ for an octree.

VectorKey

An integer vector that can be used as a key for Tree.

Type Aliases

AllocPtr

Points to a node owned by an internal allocator.

ChildIndex

A linear index of a node relative to its parent.

Level

A “level of detail” in a Tree.

OctreeI32

The default octree with i32 coordinates.

OctreeShapeI32

A BranchShape for signed octrees.

OctreeShapeU32

A BranchShape for unsigned octrees.

OctreeU32

The default octree with u32 coordinates.

QuadtreeI32

The default quadtree with i32 coordinates.

QuadtreeShapeI32

A BranchShape for signed quadtrees.

QuadtreeShapeU32

A BranchShape for unsigned quadtrees.

QuadtreeU32

The default quadtree with u32 coordinates.