2 unstable releases
0.2.0 | Aug 27, 2022 |
---|---|
0.1.0 | Jan 17, 2022 |
#951 in Data structures
62KB
1.5K
SLoC
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
andTree::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 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.
- 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 andCHILDREN=8
for an octree
- level 0:
License: MIT OR Apache-2.0
Dependencies
~4.5MB
~120K SLoC