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.
Tree
has its own internal allocators, any pointers are completely local to the data structure. In[T; CHUNK_SIZE]
. The alternative "pointerless" octrees take up less memory, but are also more complexNodePtr
is simply an array lookup.NodeEntry
and Tree::child_entry
APIs allow for very simple code that fills entire trees with aVectorKey
for a custom key type, the addressable range can be extended toThis 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 NodePtr
s 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.
NodeKey
: O(depth)NodePtr
: O(1)size_of::<T>() + 4
bytesLicense: MIT OR Apache-2.0