空间树

空间树（又称 QuadTrees、OctTrees、LodTrees）是一组快速树型数据结构，支持在各种细节级别上进行复杂的空间查询。它们特别适合于稀疏数据存储和邻域查询。

致谢

内部结构部分基于

• https://stackoverflow.com/questions/41946007/efficient-and-well-explained-implementation-of-a-quadtree-for-2d-collision-det
• https://github.com/Dimev/lodtree

目标

本 crate 的目标是提供一个通用、易于使用的树型数据结构，可用于创建各种实时应用程序（例如游戏或 GIS 软件）的 Quadtrees 和 Octrees。

内部，树尝试在内存片池中分配所有所需的内存，以避免内存碎片化和分配器压力。所有操作，在可能的情况下，使用堆栈分配或最多分配一次。

特性

• 高度可调，适用于不同尺度（从 8 位到 64 位坐标），2D、3D、N-D 如果需要。
• 最小化内存（重新）分配和移动
• 提供选择迭代器以在特定范围内查找块
• 支持在线数据块碎片整理以优化所有块上的顺序操作
• 可以使用外部数据块缓存来允许在内存权衡下重用块

接受的设计折衷方案

• 空间上相邻的数据块不一定在树的内存中的相邻位置。
• 除了从头开始重建树（这意味着内存使用量加倍）之外，没有其他方法可以碎片整理节点存储内存
• 像任何树一样，随着深度的增加，效率会降低。请考虑使用最多 8 级深度，并用 空间哈希 连接更大的区域。

示例

• rayon：展示了如何使用 rayon 与树并行生成新块，并缓存已生成的块。
• glium：展示了如何使用 glium 进行基本绘图设置，并执行绘图。

用法

导入 crate

use spatialtree::*;

树是其自己的结构体，接受一个块（任何实现了 Sized 的东西）和坐标向量（任何实现了 LodVec 特性的东西）。

# use spatialtree::*;
struct Chunk {
  //important useful fileds go here
  }
// a new OctTree with no capacity
let mut tree = OctTree::<Chunk, OctVec>::new();
// a new OctTree with 32 slots for nodes and 64 slots for data chunks
let mut tree = QuadTree::<Chunk, QuadVec>::with_capacity(32, 64);

给定的LodVec实现（OctVec和QuadVec）分别接受4个和3个参数。前3/2个参数是树中的位置，这取决于LOD级别。最后一个参数是LOD级别。对于这个目标将不会生成比这更小的LOD。

# use spatialtree::*;
// QuadVec takes x,y and depth
let qv1 = QuadVec::build(1u8, 2, 3);
let qv2 = QuadVec::new([1u8, 2], 3);
assert_eq!(qv1, qv2);
// OctVec takes x,y,z and depth
let ov1 = OctVec::build(1u8, 2, 3, 3);
let ov2 = OctVec::new([1u8, 2, 3], 3);
assert_eq!(ov1, ov2);

当以大批次执行插入时，效率最高，因为这最小化了树遍历开销。

# use spatialtree::*;
# struct Chunk {}
// create a tree
let mut tree = QuadTree::<Chunk, QuadVec>::with_capacity(32, 64);
// create a few targets
let targets = [
  QuadVec::build(1u8, 1, 3),
  QuadVec::build(2, 2, 3),
  QuadVec::build(3, 3, 3),
  ];
// ask tree to populate given positions, calling a function to construct new data as needed.
tree.insert_many(targets.iter().copied(), |_| Chunk {});

或者，如果您想一次插入一块数据

# use spatialtree::*;
// create a tree with usize as data
let mut tree = QuadTree::<usize, QuadVec>::with_capacity(32, 64);
// insert/replace a chunk at selected location, provided lambda builds the content
// we get chunk index back
let idx = tree.insert(QuadVec::new([1u8,2], 3), |p| {p.pos.iter().sum::<u8>() as usize} );
// we can access chunks by index (in this case to make sure insert worked ok)
assert_eq!(tree.get_chunk(idx).chunk, 3);

可以使用轴对齐的边界框（AABB）来选择所需区域，从而有效地在树中进行查找

# use spatialtree::*;
let mut tree = OctTree::<usize, OctVec>::new();
let min = OctVec::new([0u8, 0, 0], 3);
let max = OctVec::new([7u8, 7, 7], 3);

// create iterator over all possible positions in the tree
let pos_iter = iter_all_positions_in_bounds(min, max);
// fill tree with important data
tree.insert_many(pos_iter, |_| 42 );
// iterateing over data in AABB yields both positions and associated data chunks
// only populated positions are yielded, empty ones are quietly skipped.
for (pos, data) in tree.iter_chunks_in_aabb(min, max) {
    dbg!(pos, data);
}

以这种方式选择块将永远不会深入到AABB限制中最深的块。两个限制应该具有相同的深度。

高级用法

此结构可用于渐进式LOD等目的。

如果您想由于相机移动而更新块，可以使用lod_update。它接受3个参数。

目标：是要生成最多细节的周围位置的数组。

细节：目标的细节程度。默认实现将此定义为围绕目标块的目标LOD级别周围的块数量。

chunk_creator：当需要新块时调用的函数；evict_callback：从数据结构中逐出块时调用的函数

evict_callback的目的是启用诸如缓存、对象重用等操作。如果这样做，最好将块保持得相对较小，这样在树和缓存之间移动它们就不会太昂贵。

# use spatialtree::*;
# use std::collections::HashMap;
# use std::cell::RefCell;
# use std::borrow::BorrowMut;
// Tree with "active" data
let mut tree = QuadTree::<Vec<usize>, QuadVec>::with_capacity(32, 64);
// Cache for "inactive" data
let mut cache: RefCell<HashMap::<QuadVec,Vec<usize>>> = RefCell::new(HashMap::new());
# fn expensive_init(c:QuadVec, d:&mut Vec<usize>){ }

//function to populate new chunks. Will read from cache if possible
let mut chunk_creator = |c:QuadVec|->Vec<usize> {
  match cache.borrow_mut().remove(&c){
    Some(d)=>d,
    None => {
      let mut d = Vec::new();
      // run whatever mystery function may be needed to populate new chunk with reasonable data
      expensive_init(c, &mut d);
      d
      }
    }
};

//Function to deal with evicted chunks. Will move them to cache.
let mut  chunk_evict = |c:QuadVec, d:Vec<usize>|{
  println!("Chunk {d:?} at position {c:?} evicted");
  cache.borrow_mut().insert(c,d);
};

// construct vector pointing to location that we want to detail
let qv = QuadVec::from_float_coords([1.1, 2.4], 6);
// run the actual update rebuilding the tree
tree.lod_update(&[qv], 2, chunk_creator, chunk_evict);

内部，lod_update将重建树以匹配所需节点结构，该结构反映了所有目标的位置。因此，在lod_update之后永远不需要defragment_nodes。您可能想要在将要迭代它们时进行defragment_chunks。

优化内存布局

为了最佳性能和内存紧凑性，您可能希望确保块存储在连续的数组中。虽然树将尽力确保这一点，但它不会移动不需要移动的数据，除非明确指示。因此，在多次删除后，可能需要整理存储。

# use spatialtree::*;
# let mut tree = QuadTree::<usize, QuadVec>::with_capacity(32, 64);

// make sure there are no holes in chunks array for fast iteration
tree.defragment_chunks();

请注意，如果块数组中没有空洞，则defragment_chunks不会做任何事情，因此每次您怀疑可能需要时都可以安全地调用它。

同样，可以重建和整理节点存储，但这是一项成本更高的操作，并且需要分配内存。因此，只有当您有强有力的理由（例如基准测试）时才调用此操作。

# use spatialtree::*;
# let mut tree = QuadTree::<usize, QuadVec>::with_capacity(32, 64);

// make sure there are no holes in nodes array for fast iteration
tree.defragment_nodes();

一旦结构被整理，就可以通过以下方式回收释放的内存

# use spatialtree::*;
# let mut tree = QuadTree::<usize, QuadVec>::with_capacity(32, 64);

tree.shrink_to_fit();

路线图

0.2.0:

• 目前还没有修剪节点的方法。它们不会占用太多RAM，但可能会成为问题。
• 更好地组织基准测试

0.3.0:

• 交换L和C，使键（位置）在块之前，这与Rust中其他键值数据类型一致
• 使用泛型const表达式来改进模板

许可证

在以下任一许可证下发布

• GPL，版本3.0（LICENSE.txt）
• 商业用途的专有许可证（请联系作者安排许可）

贡献

除非您明确说明，否则您提交给作品以供包含的任何贡献将按上述方式许可，不附加任何其他条款或条件。