Spatial Data Structures & Subdivision

空间划分结构（Spatial Data Structures & Subdivision），是另一类用于加速碰撞检测、可见性测试、射线投射等问题的结构。相比 BVH 是“以物体为中心”的包围策略，空间划分结构是“以空间为中心”的策略。

1. Uniform Spatial Subdivision（均匀空间划分）

把整个模拟空间切成固定大小的格子（voxels），然后看每个物体占了哪些格子，最后只在同一个格子里的物体之间检测碰撞。

• To represent an object, only need to decide which cells are occupied.  To perform collision detection, check if any cell is occupied by two object
  • 不用关心物体的真实边界了，只关心它在哪些格子里。
  • 然后只检查同一个格子里是否被两个物体同时占用，就能判断是否“可能碰撞”。
• Storage:  to represent an object at resolution of n voxels per dimension requires up to n3 cells
  • cost 是立方级别的
• Accuracy:  solids can only be “approximated”
  • 因为用格子表示物体的包围，所以几何形状是“像素化”的
  • 比如曲面或斜线就会变成阶梯状（见下方图），只能大致接近真实物体
  • 适用于布料模拟、粒子模拟等，不适合需要高几何精度的检测

优点：结构简单，构建快

缺点：密度不均时浪费严重（大部分格子可能是空的）

2. Quadtree / Octree

• 2D 是 quadtree（每个节点 4 个子区域）

  • 把一个 2D 区域均分成四块（四个 quadrant）
  • 每一块如果“太复杂”就继续细分，形成树形结构

• 3D 是 octree（每个节点 8 个子区域）

  • Octree 是Quadtree的 3D 扩展，把一个 3D 空间均分成 8 个子立方体

• Use divide-and-conquer（分治思想）

  • 把整个空间看成一个大 cube：

    1. 判断里面是否“太满”

       → 比如含有超过 10 个物体

    2. 如果是，就把这个 cube 分成 8 小块（八个子 cube）

    3. 每个子 cube 递归处理

    直到每个 leaf node（叶子）内部只含少量物体。

• 相比 grid 更省空间

  • Uniform Grid 是全空间都分成格子，不管有没有物体（像像素图一样）
  • Octree 只对有内容的区域做细分，空的就不管了