GPU Gems 2 · Chapter 37. Octree Textures on the GPU

先别急着把模型摊平

想象你要给一只皱褶很多的模型贴纸。把它压成一张平面纸，贴纸会被拉伸，还必须在某些地方剪开；而且模型表面的大部分空间其实并没有贴到东西。

本章解决的问题是：能不能让每个表面点直接在包围模型的空间里找到自己的颜色？如果没有这套方法，复杂模型会被迫维护接缝密集的平面坐标，过滤和表面模拟也容易把“空白区域”当成真实数据。

1. 从 UV 平面转向体积中的表面采样

传统纹理把网格顶点映射到 (u, v) 平面；复杂模型的弯折、孔洞和接缝会让这个映射变得难以维护。octree texture 反过来把纹理放进包围物体的立方体，只在体积与表面相交的区域保存颜色，因此不需要为每个顶点设计一套摊平规则。

这不是把整个 256³ 体积都填满：八叉树会保留空区域为叶节点，只继续细分碰到表面的节点。结果是采样网格仍然规则，表面颜色不会因为 UV 拉伸而变形。GpuGems2Ch37ParameterizationCompareDiagram 展示了“摊平”与“按三维位置查找”的差别。

2. N³-tree：把空间分成可追踪的层级

八叉树的根节点是一个立方体；每次细分都把它变成 2 × 2 × 2 个孩子。孩子要么继续成为内部节点，要么成为叶节点。叶节点保存颜色，空节点直接标记为空；只有包住表面的节点才继续向下展开。

每深入一层，每个方向的分辨率乘 2，所以深度 D 的完整网格分辨率是 2^D。将每条边切成更大的 N 会减少树深，但表面附近会留下更多没有用的格子；这正是存储效率与查找深度之间的取舍。

3. 把指针改成纹理中的索引

GPU 版本把 CPU 树中的指针换成 3D texture 里的索引。每个节点对应一个 N × N × N 的 indirection grid；一个 cell 的 RGB 可以是下一级 grid 的位置，也可以直接是叶节点颜色，alpha 则告诉 shader 应该继续查找还是停下。

fragment 在栅格化时已经获得未变换的表面坐标 M。它从根索引开始，根据 M 在当前节点内的相对位置计算 cell 坐标，再读一次 indirection pool。如果 alpha 表明它是 child，就把 RGB 解码成下一级索引；如果 alpha 表明它是 leaf，就返回颜色。老硬件不能保证动态循环，因此应以最大深度的固定循环为底线，支持动态分支时再提前退出。

vec4 lookupOctree(vec3 M, sampler3D indirectionPool) {
  vec3 localPoint = M;
  vec3 gridIndex = vec3(0.0);
  vec4 cell = vec4(0.0);
  for (int depth = 0; depth < MAX_DEPTH; depth++) {
    vec3 P = (localPoint + gridIndex) * INV_POOL_SIZE;
    cell = texture(indirectionPool, P);
    if (cell.a > 0.9) return cell;
    if (cell.a < 0.1) discard;
    gridIndex = floor(cell.rgb * 255.0 + 0.5);
    localPoint *= N;
  }
  return cell;
}

这段伪 GLSL 把“指针树”改写成一串 dependent lookup：gridIndex 不是 CPU 地址，而是下一轮查找要使用的纹理索引。discard 对应空 cell；固定的 MAX_DEPTH 让同一段代码可以在没有动态分支的设备上运行。

4. 过滤与 LOD：让结果在远处仍然稳定

八叉树查找得到的最近叶颜色还不等于高质量纹理。三维线性插值需要八个相邻样本；如果建树时只收录恰好穿过表面的点，缺少的邻居会让背景色渗入。解决办法是在建树时扩大用于相交测试的盒子，把过滤所需的邻居一起纳入。

mipmap 的 finest level 是原始颜色叶节点；更粗的一层把同一父节点的孩子颜色合并成平均值。shader 根据屏幕导数选择一个合适的深度：近处深入树保留细节，远处在较浅层从 LOD pool 取平均颜色，避免单个叶样本造成 aliasing。

5. 用同一棵树支持绘制与表面模拟

建树时先把模型缩放进 unit box，再从根开始检查每个子盒是否和多边形相交；到达目标深度就创建颜色叶，否则继续创建 child，未相交的格子直接标记为空。绘制时，画笔是沿表面移动的小球，只局部更新被覆盖的叶节点，并通过 3D texture 的局部上传减少带宽。

void createNode(int depth, Polygons polygons, Box box) {
  for (Child child : childrenOf(box)) {
    Box childBox = computeSubBox(child, box);
    if (depth + 1 == paintingDepth) {
      setChildColor(child, white);
    } else if (intersects(childBox, polygons)) {
      createChild(child);
      createNode(depth + 1, polygons, childBox);
    } else {
      setChildAsEmpty(child);
    }
  }
}

这段建树逻辑的关键不是递归本身，而是“只为相交区域创建路径”。绘制时可以把 setChildColor 换成基于画笔距离的颜色混合，并只调用局部 texture 更新；显示复杂场景时，则可以在细节可见时使用八叉树，在远处切换到过滤好的 2D 表示。

第二种应用把八叉树当作表面地址层，而不是直接存液体密度。每个叶节点保存 density map 的索引，neighbor textures 把一个叶节点映射到空间邻居，再从 density map 读取邻居值，下一轮 GPU cellular automaton 只更新 2D 状态纹理。表面通常只需要约 9 个邻居，不必为完整 3D 的 26 个方向都固定一张纹理。

三步验收：从坐标到可用的表面数据

先猜一猜：在下面的实验里把 tree depth 调大、把 surface coverage 调小，再从 lookup 切换到 liquid，哪些指标会分别变化？动手试时一次只改一个控件，观察 lookup steps、selected LOD、occupied cells 和 neighbor reads。

本章小结

• octree texture 用表面三维坐标替代复杂 UV 参数化。
• N³-tree 只细分相交区域，深度决定分辨率与查找成本。
• indirection pool 用 RGB 索引和 alpha 标志实现 GPU 树查找。
• 过滤需要邻居补全，LOD pool 用父节点平均色抑制远处 aliasing。
• 同一棵树既能支撑 3D 绘制，也能给表面模拟提供邻居地址。