跳转到内容
Jason's Study

Meagher 1982 八叉树 — 把立方体一分为八，递归地装下一整个 3D 世界

是什么

八叉树（Octree）是一种把 3D 空间不断对半切的数据结构。日常类比：你想找出一座城市里”哪些格子有建筑”。最笨的办法是把城市切成 1 米 × 1 米 × 1 米的小方块，挨个检查——城市稍大就爆内存。

聪明办法：先把整个城市当一个大方块。如果这个方块整块都是建筑或者整块都是空气，那就一个标签搞定，不用细分。否则把它切成 8 个一样大的子方块（左前下、右前下、左后下、右后下、左前上、右前上、左后上、右后上），递归对每个子方块问同样的问题。

为什么是 8 个？因为 3D 空间有 3 个轴（x/y/z），每个轴对半切，2×2×2 = 8。

Meagher 1982 这篇论文系统地把这个想法变成可计算的数据结构 + 算法集合——存储、布尔运算（并、交、差）、几何变换、显示渲染——全部用八叉树做。从此 3D 几何引擎、体绘制、碰撞检测、Minecraft、稀疏体素都建在它上面。

为什么重要

  • 没有八叉树就没有 Minecraft：游戏世界不是一个 4096×4096×256 的大数组（那是 40 亿格），而是一棵八叉树。空气和岩石各自是大块，只在边界细分
  • GPU 体素全局光照（VXGI、Voxel Cone Tracing）每帧都在八叉树上 ray-march
  • 碰撞检测：物理引擎（Bullet、PhysX）用八叉树先剔除”显然不会碰”的物体对
  • 点云压缩：LiDAR 扫描得到几亿个点，八叉树存比裸数组小 10 倍以上
  • 稀疏体素八叉树（SVO） 是 NVIDIA 2010 后实时光追的关键数据结构
  • 核心洞见：3D 数据有大量”大片相同”的区域，递归切分让你只在边界花钱

核心要点

  1. 节点只有两种状态：要么是叶子（整块同色/同材质，存一个值就够），要么是内部节点（不同质，存 8 个孩子指针）。这个二分把”自适应分辨率”变成数据结构的天然属性

  2. 三种灰度：黑（全实心）/ 白（全空）/ 灰（混合，需要继续切）。算法一直递归到”黑或白”为止。论文里叫 BWG（Black/White/Gray）

  3. 布尔运算就是两棵树同步走：A ∪ B 时，两棵八叉树同时往下走。如果 A 当前节点全黑（实心），结果就是黑，不用看 B 的子树。这种”早停”让布尔运算的复杂度从 O(N³) 降到 O(表面积)

  4. 空间索引天然就是路径：从根到任意叶子的路径（每步 0-7 选一个子方块）就是一个 3 比特/层 的莫顿码（Z-order curve）。这意味着位置 = 路径，不需要额外索引结构

  5. 存储成本随”边界复杂度”而非”体积”涨：一个光滑球体的八叉树节点数大约是 O(R²)（正比于表面积），而不是 O(R³)（体积）。这就是它比裸 3D 数组高效的根本原因

一图看懂八叉树切分

想象一个 8×8×8 的立方体世界（512 个格子）。如果右上前那一小角有个”球”，其他全空：

  • 第 0 层：根节点（覆盖 8×8×8）—— 灰色（既有空又有实，需要切）
  • 第 1 层：8 个 4×4×4 的子节点 —— 7 个白（全空，叶子，停），1 个灰（继续切）
  • 第 2 层：那个灰节点切成 8 个 2×2×2 —— 大部分白，少数灰
  • 第 3 层：继续往下，直到每个叶子都”全黑”或”全白”

总节点数远小于 512——空气区一进去就被一个白叶子吃掉。这就是”按需细分”的视觉意义。

实践案例

案例 1：Minecraft 区块的本质

Minecraft 把世界切成 16×16×384 的区块（chunk）。看似是数组，实际现代版本里：

  • 每个 16×16×16 的子块（section）如果全是空气 → 不分配数组，存一个空指针
  • 如果全是同种方块（比如石头）→ 存一个值
  • 否则才展开成 4096 个槽位

这是一棵深度 4 的隐式八叉树。你挖一个洞 = 把”叶子节点”分裂成 8 个孩子。

案例 2：碰撞检测的剪枝

物理引擎要判断 1000 个物体之间是否两两碰撞 → 朴素 O(N²) = 50 万次检查。 用八叉树：把所有物体塞进树，只检查同一个子方块（或相邻子方块）里的物体对。 1000 个物体均匀分布时，每个子方块大概 10 个物体 → 100 个方块 × C(10,2) = 4500 次检查。100 倍提速。

案例 3：GPU 上的稀疏体素八叉树

NVIDIA 在 2010 后用 SVO 做实时全局光照：

  • 把场景烘焙成一棵八叉树存在显存里
  • 着色器对每个像素发一根光线，沿八叉树往下走（ray-march）
  • 走到第一个”非空叶子”就停，读颜色

这条 GPU 八叉树遍历代码，思想 100% 来自 Meagher 1982，只是搬到了并行硬件上。

案例 4：CSG 实体建模的求值

CAD 软件让你写：球 ∪ 立方体 - 圆柱。怎么算结果？把每个基础体素化成八叉树，再按论文的布尔规则两两合并：

  • 并：两节点一黑就是黑，两白才是白，否则继续递归
  • 交：两节点一白就是白，两黑才是黑
  • 差：A 减 B，B 黑就是白，B 白则保 A

整个 CSG 表达式的求值就是几次八叉树两两遍历。1980 年代的实体建模工业全部跑在这套算法上。

算法骨架（伪代码视角）

最核心的”切分构造”是这样：

build(volume):
  if volume 全黑:
    return Leaf(BLACK)
  if volume 全白:
    return Leaf(WHITE)
  if 已到最大深度:
    return Leaf(主导色)
  children = []
  for i in 0..7:
    sub = volume 的第 i 个 2×2×2 子方块
    children.append(build(sub))
  return Node(children)

布尔并操作几乎一样优雅：

union(A, B):
  if A 全黑 or B 全黑: return Leaf(BLACK)
  if A 全白: return B
  if B 全白: return A
  return Node([union(A.child(i), B.child(i)) for i in 0..7])

整篇论文的算法本质都是”递归 + 两个早停条件 + 8 路展开”。一旦看穿这个模板，体绘制、变换、点查询全是变体。

踩过的坑

  1. 不是所有 3D 数据都适合八叉树：如果你的数据”到处都不一样”（高频噪声、湍流、毛发），八叉树会一直分到最深，比裸数组还费——多了所有内部节点的指针开销。规则：有大片同质区才选八叉树

  2. 指针八叉树缓存不友好：每跳一层都要解一次指针，CPU 缓存命中率低。现代实现用线性八叉树（Linear Octree，把节点按莫顿码排进数组）或完全展开的紧凑表示（每节点 8 字节存 8 个孩子的相对偏移）

  3. 平衡 vs 自由：论文原版的八叉树是”自由切”——某层可能左半边切到第 8 层，右半边只切到第 3 层。但有些算法（比如 Marching Cubes 跨层接缝）要求相邻叶子深度差不超过 1，这叫”受限八叉树”（Restricted Octree），需要额外的修复步骤

  4. 2D 类比不能完全照搬：很多人先学四叉树（Quadtree，2D 版本，4 个孩子），以为 octree 就是它的 3D 推广。基本对，但 3D 的常数因子（8 vs 4）让”自由分裂”的退化情况更糟，存储需要更小心

适用 vs 不适用场景

适用：

  • 体素世界 / 体绘制 / 医学 CT 数据（大片同质组织）
  • 点云 / LiDAR（点稀疏分布在 3D 空间）
  • 静态场景的碰撞检测、可见性剔除
  • 基于网格的物理模拟（自适应网格细化 AMR）

不适用：

  • 高频细节均匀分布（每个体素都不同）→ 用裸数组或 BVH
  • 大量动态物体（每帧都在动）→ 重建八叉树成本高，用 Bounding Volume Hierarchy
  • 表面已用网格（mesh）表达 → 用 BVH 或 KD-tree

历史小故事（可跳过）

  • 1980 年：Donald Meagher 在伦斯勒理工学院（RPI）写技术报告，提出八叉树编码
  • 1982 年：正式期刊版本《Geometric Modeling Using Octree Encoding》发表在 CGIP（Computer Graphics and Image Processing）
  • 同年 Jackins-Tanimoto 也发表了类似想法，但 Meagher 的版本最系统（包括 boolean、变换、显示）
  • 1980s：CAD/CAM 行业大量采用，做实体建模（CSG 树的求值底座）
  • 1990s：游戏引擎（Quake 系列的 BSP 是表亲，八叉树用于体素和遮挡剔除）
  • 2010s：NVIDIA SVO、Minecraft 全民化、点云处理（PCL 库默认数据结构）

40 多年过去，八叉树仍是 3D 计算最常被复用的”积木”之一。

学到什么

  1. 递归 + 早停 = 自适应——只在数据真的不均匀时才花存储，是计算机科学最朴素的省钱思想之一
  2. 空间到比特路径的映射：3 比特/层的莫顿码让”位置”和”内存地址”统一，是后续很多空间索引（R-tree、Geohash）的源头之一
  3. 数据结构跟数据特性强绑定：同质区多 → 八叉树赢；噪声高 → 裸数组赢。没有”通用最好”的结构
  4. 40 年前的论文今天仍是工业基石：图形学的很多核心数据结构（八叉树、KD 树、BVH）都诞生在 1975-1985 这十年

延伸阅读

关联

反向链接