空间索引本质上是一种数据结构，用来组织和检索具有“位置属性”的数据。就像二叉树一样，它可以提高检索的效率，只不过是处理一维数据。
空间索引常分为层级式索引和网格化索引。
层级式（Hierarchical）包括

  • Octree（八叉树）：将空间递归、均匀的分为 8 块，适合体素表示和快速踢除空旷空间
  • kd-tree（k-维树）：按照点的分布交替切分轴，最适合高维空间的最近邻搜索（KNN）搜索
  • BVH（Bounding Volume Hierarchy）：用包围盒（球体或长方体）把物体包起来。这是光线追踪和碰撞检测的核心。
    网格化（Grid-based）包括：
  • Uniform Grid（网格）：将空间切成大小一致的方格（像 Minecraft 那样）。简单但浪费内存。
  • Spatial Hashing（空间哈希）：将空间坐标映射到哈希表，适合处理物体不断运动的动态场景。

Octree（八叉树）

切分逻辑：

  1. 将一个立方体空间在 x，y，z 边的正中间切分，平分成 8 个子立方体。
  2. 如果子空间内的点数少于某个阈值，或者切分层级达到某个阈值，则停止切分。
    特点
    平均
    稀疏性支持：如果某个空间内没有点，则在数据结构上不会给它分配内存。

优点：
结构极其规整，非常容易通过坐标定位。特别适合体素化。
缺点：
灵活性较差，如果物提恰好在切分线上，或者分布很不均匀，会出现很多无意义的空间点。

kd-tree（k-dimensional tree）

切分逻辑

  1. 在当前点集中选择一个维度（比如第一层选 X 轴，第二层选 Y 轴，第三层选 Z 轴）
  2. 找到该维度上的中位数点，画一个垂直于该轴的平面，将空间一分为二。
  3. 在左右两个子集中重复上数过程
    特点
    平衡性：好的 kd-tree 会尽量保证左右子树的点数平衡。
    优点
    能够完美适应数据分布。无论点云多么不平均，都能保持 O(logn) 的搜索复杂度。
    缺点
    维护成本高，如果点云是动态增加或移动的，频繁重构 kd-tree 非常耗时。