2 unstable releases

0.2.0 Aug 27, 2022
0.1.0 Jan 17, 2022

#387 in Memory management


1.5K SLoC


Crates.io Docs.rs

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.


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

License: MIT OR Apache-2.0


~69K SLoC