grid-tree

像素四叉树和体素八叉树。

将任何类型存储在 OctreeI32、OctreeU32、QuadtreeI32 或 QuadtreeU32 中，这些都是泛型 Tree 的具体实例。一个 Tree 表示从 (Level, 整数坐标) 到 T 的映射。因此，它适用于存储具有细节级别的像素或体素数据。该树还要求如果一个节点槽被占用（有数据），则所有祖先槽也必须被填充。

设计优势

• 由于 Tree 有自己的内部分配器，任何指针都完全本地于数据结构。从原则上讲，这使得它很容易克隆树，例如上传到GPU（尽管我们还没有亲自尝试）。
• 第0级分配器不存储指针，只存储值。通过分块数据，可以在较高级别分摊指针开销，即 [T; CHUNK_SIZE]。替代的“无指针”八叉树占用更少的内存，但编辑和遍历也更为复杂。
• 通过使用根节点哈希表，可寻址空间不受树高度的限制，并且不需要像八叉树那样“转换”焦点。
• 通过一个非常简单的数据布局，使用 NodePtr 进行访问仅仅是数组查找。
• NodeEntry 和 Tree::child_entry API 允许编写非常简单的代码，使用单个访问闭包填充整个树。
• 通过为自定义键类型实现 VectorKey，可寻址范围可以扩展到任意精度的坐标。

性能

该结构针对迭代速度和受益于边界体层次结构（如光线投射）的空间查询进行了优化。从根节点开始通过 NodeKey 查找单个节点应尽可能减少，因此您可能会发现缓存 NodePtr 或通过完整的树遍历分摊搜索是有用的。考虑到实现的简单性，内存使用量适中，并且可以通过使用密集块值轻松分摊指针开销。

• 使用 NodeKey 的随机访问：O(深度)
• 使用 NodePtr 的随机访问：O(1)
• 迭代：O(节点数)
• 每个节点的内存使用量
  • 第 0 层: size_of::<T>() 字节
  • 第 N 层 > 0: size_of::<T>() + CHILDREN * 4 字节
  • 其中 CHILDREN=4 对于四叉树，CHILDREN=8 对于八叉树

许可证：MIT OR Apache-2.0