空间划分结构

发表于 分类于 本文字数： 858 阅读时长 ≈ 3 分钟

空间划分结构

KD-Tree

基本概念

KD-Tree 是一种二叉树结构，用于在 k 维空间中对点集进行递归划分。每个节点表示一个超平面划分，该超平面与某一维的坐标轴对齐。

构建方式

  1. 给定一组 k 维点。
  2. 初始从根节点开始，选择一个维度（如 x 轴）作为划分维度。
  3. 找到该维度的中位数作为划分点，构建平面将空间分为左右两个子空间。
  4. 对两个子空间递归进行相同操作，每层轮换划分维度。

应用场景

  • 点云搜索（最近邻/范围查询）
  • 光线追踪（早期）
  • 机器学习（KNN 分类器）
  • 地图构建、碰撞检测

特点

  • 对静态点集效果良好
  • 不适合频繁插入和删除
  • 适合低维数据（2D~10D）

Octree（八叉树）

基本概念

Octree 是一种递归八叉划分结构，用于在 3D 空间中对场景/体素/点云进行管理。每个节点将空间分为 8 个等体积的子空间。

构建方式

  1. 从整个空间开始作为根节点。
  2. 若当前节点中包含的点/物体数量大于阈值：
    • 则将该节点划分为 8 个子立方体，并递归构建。
  3. 若子块为空则可不存储，形成稀疏结构。

应用场景

  • 3D 游戏碰撞检测
  • 点云压缩与表示（如 PCL）
  • 体绘制（volume rendering）
  • 地图建模（SLAM）

特点

  • 结构紧凑，适合稀疏3D数据
  • 动态更新比 KD-Tree 更方便
  • 空间局部性强，适合体素类操作

BSP（Binary Space Partitioning）

基本概念

BSP 是一种基于任意平面划分的二叉空间结构，最早用于2D/3D场景中快速可见性计算与绘制顺序排序。

构建方式

  1. 选择一个物体面片作为划分平面。
  2. 用该平面将场景划分为前后两部分：
    • 在该面前的物体放入“前子树”
    • 在该面后的物体放入“后子树”
    • 相交的要进行裁剪或特殊处理
  3. 递归对每个子空间执行相同划分。

应用场景

  • 经典 FPS 游戏（如《DOOM》）
  • 可见性计算（从某一点看有哪些物体）
  • 渲染排序（Painter’s algorithm）

特点

  • 可以使用任意方向平面（比 KD-Tree 更灵活）
  • 适合静态场景；动态场景构建代价高
  • 可用于处理非轴对齐几何体（如不规则墙面）

BVH（Bounding Volume Hierarchy）

基本概念

BVH 是一种用于快速相交检测的层次包围体结构，常用于光线追踪、碰撞检测等。每个节点代表一个包围体（如 AABB、OBB、球体等），其子节点代表更小的子物体或子包围体。

构建方式

  1. 对所有物体构建包围盒（如 AABB）。
  2. 将它们划分为两个子集合，使得两个集合的包围盒重叠最小（如用中轴或 SAH 面积启发式）。
  3. 递归构建左右子树，每个节点保存当前包围体信息。

应用场景

  • 光线追踪（ray tracing）
  • 碰撞检测
  • GPU 渲染加速

特点

  • 动态更新成本比 KD-Tree 小
  • 对复杂物体结构更友好
  • 使用启发式可提高构建质量（如 SAH）

扩展文章 : [Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves](