Skip to main content

Chapter 58: Octree and Grid Structures

三维场景的空间结构要回答一个直接问题：给定一个查询对象，系统怎样用较少的内存访问和较少的候选测试，找到真正相关的几何、体素、粒子或体积区域。上一章的 KD-Tree 把空间切成一串二叉平面，本章把视角切换到规则空间划分：Octree 用层级八分跳过大块空区域，Uniform Grid 用固定 cell 给查询提供稳定步进路径。

读完本章后，读者应能定位一次 ray query、volume sampling、particle neighbor search 或 visibility test 在 Octree 与 Grid 中经过哪些节点、cell、payload 和 GPU buffer；能判断 cell size、节点 occupancy、叶节点 payload、动态更新和稀疏分配怎样影响帧时间；也能在稀疏场景、密集场景、动态物体和体积数据之间选择结构组合。

本章贯穿一个测试帧：Frame_OctreeGrid_Test。这一帧包含稀疏山体、局部密集建筑、烟雾体积、移动碎片和相机拾取 ray。山体与建筑形成静态大场景，烟雾形成局部体积 brick，移动碎片每帧改变位置，拾取 ray 和阴影 ray 需要快速穿过空间结构。这个测试帧会持续作为解释对象，用来连接视觉结果、数据输入、管线阶段、GPU 资源和性能证据。

Octree 与 Grid 的共同目标是让查询成本跟“相关空间”接近，而非跟整个世界对象数量线性绑定。它们的差异来自划分规则：Octree 通过层级深度表达稀疏性，Grid 通过固定 cell 提供简单、连续、GPU 友好的寻址。工程选择的核心结论是：空区域跨度大、局部密度变化明显时，层级结构负责粗剔除；局部密度接近、ray 或邻域查询大量重复时，Grid 负责稳定遍历。

下面这条路径概括本章的贯穿材料。图中的结构构建和查询阶段可以出现在 CPU，也可以出现在 compute shader；关键差别在于数据一旦进入 GPU buffer，查询会受内存布局、分支一致性和 payload 局部性限制。

图中最关键的链路是 World Bounds → Spatial Index → Payload → Candidate Tests。空间结构本身不直接生成画面，它减少后续 shader、intersection、volume sample 或 collision test 的候选范围。画面中的阴影错误、烟雾采样断层、拾取延迟或粒子邻域抖动，通常都能回到这条链路中的 bounds、cell、payload 或更新时序。

58.1 八叉树（Octree）空间划分原理​

Octree 是一种三维层级空间划分结构。根节点覆盖一个三维包围盒，内部节点把当前空间按 x、y、z 三个方向各切一半，形成 2×2×2 共 8 个子空间。叶节点保存 payload，payload 可以是三角形索引、物体 ID、体素 brick 句柄、粒子列表或渲染 tile 引用。这个定义的工程意义在于：查询先经过大尺度节点，只有命中相关子空间时才继续下钻。

在 Frame_OctreeGrid_Test 中，根节点覆盖整个山谷。稀疏山体占据很大的世界范围，但真正有几何的区域分散在山脊和道路附近。Octree 的第一层会把山谷分成 8 个 octant，空的天空区域和地下区域可以用 occupancy 标记为 inactive；查询 ray 穿过这些区域时只做节点 bounds 判断，无需读取三角形列表。

Octree 节点至少要表达三个信息：节点空间范围、子节点占用状态和叶节点 payload。空间范围可以显式存 AABB，也可以用根 bounds、节点 Morton code 和层级 depth 推导。子节点占用状态通常用 8 bit mask 表示，bit 为 1 的 child 存在。叶节点 payload 存储当前空间中需要被后续测试的对象引用。GPU 上常用扁平数组表达节点，因为随机指针会破坏缓存局部性，也会增加跨平台序列化成本。

下面是一个面向 GPU buffer 的最小节点布局，代码只表达数据含义，具体压缩方式可以按平台修改。

struct OctreeNode {
    uint32_t childBase;      // 子节点连续存放时的起始下标
    uint32_t childMask;      // 低 8 bit 表示 8 个子节点是否存在
    uint32_t payloadOffset;  // 叶节点 payload 起始位置
    uint32_t payloadCount;   // 叶节点 payload 数量，内部节点通常为 0
};

这段结构支撑两类查询。第一类是点或物体插入查询：根据位置和当前节点中心比较，生成 child index，例如 x >= center.x 提供一个 bit，三个方向组合成 0 到 7 的 child 编号。第二类是 ray 或 AABB overlap 查询：先测试当前节点 bounds，命中后根据 ray 方向或 child 距离排序进入子节点。前者强调快速寻址，后者强调少访问无关节点。

Occupancy 是 Octree 的核心信号。一个节点的 occupancy 表达“这个空间是否包含后续需要处理的内容”，而 payload 表达“命中这个空间后具体处理哪些对象”。在静态几何中，occupancy 可以由三角形 bounds 与节点 bounds 的相交关系产生；在体素场中，occupancy 可以由密度是否超过阈值产生；在场景管理中，occupancy 可以由 object bounds 覆盖决定。相同节点结构可以服务不同数据，只要 payload 的解释在查询阶段保持一致。

叶节点停止细分需要稳定规则。常见条件包括最大深度、最小 cell 尺寸、payload 数量阈值、空间密度变化、体素误差和屏幕误差。最大深度控制内存上限，payload 阈值控制候选测试成本，最小 cell 尺寸控制空间精度。对于本章测试帧，静态山体可以用较深层级表达稀疏空洞，局部建筑在达到三角形数量阈值后停止，烟雾体积在进入 brick 级别后交给局部 Grid 处理。

对象跨越多个子节点时会引出复制成本。一个大建筑外壳可能覆盖多个 octant，如果直接把同一个物体 ID 写进多个叶节点，查询候选会重复出现。可行做法有三种：在父节点保存大对象 payload；使用 loose octree，让节点 bounds 适度扩大以容纳跨界物体；查询阶段用对象 stamp 去重。三者的取舍不同：父节点 payload 查询简单但候选偏多，loose bounds 插入稳定但空间跳过能力下降，stamp 去重准确但需要额外状态。

在 GPU 遍历中，Octree 的主要开销来自不规则访问和分支路径差异。相邻像素发出的 ray 可能进入不同深度、不同 child 顺序，warp 或 wave 内线程会产生不同的循环次数。扁平节点数组、child mask、Morton 顺序和短 payload 区间可以改善局部性，但无法让层级遍历变成完全规则访问。因此 Octree 更适合跳过空区域或管理稀疏体素，再把局部连续工作交给 Grid 或 brick。

把本节结论放回测试帧：相机拾取 ray 从屏幕进入山谷时，Octree 先用根节点和高层 child 跳过天空与远处空山体，进入建筑叶节点后只读取局部三角形候选；烟雾区域命中叶节点后读取体积 brick 句柄；移动碎片如果直接写入静态 Octree，会导致频繁更新，因此后文会把动态对象放入单独结构或脏区更新路径。

58.2 Uniform Grid Cell Size Density and Traversal Model​

Uniform Grid 是固定尺寸三维格子。它把世界空间映射到整数 cell 坐标，每个 cell 保存落入该格子的 payload。Grid 的优势来自寻址简单：给定世界坐标 p 和 cell size h，cell 坐标就是 floor((p - origin) / h)。这个映射可以直接在 CPU、compute shader、ray traversal shader 或 particle simulation kernel 中使用。

在测试帧中，烟雾体积内部密度分布相对连续，粒子碎片在局部区域内大量移动。Uniform Grid 对这两类对象很合适，因为查询通常发生在相邻 cell 中：ray marching 沿方向逐格前进，粒子邻域搜索读取当前 cell 与周围 26 个 cell，碰撞 broad phase 先把物体放入 cell bucket。每次查询的控制流稳定，GPU lane 更容易走相似路径。

Cell size 是 Grid 的第一决策。cell 太大时，每个 cell 的 payload 很多，查询虽然访问的 cell 少，但每个 cell 内候选测试多；cell 太小时，每个 cell payload 变少，ray 或邻域查询要跨越更多 cell，内存索引和循环次数上升。判断 cell size 时需要看查询半径、几何尺寸、平均密度和最大密度。本章测试帧中的烟雾 brick 可以按体素采样步长或 ray marching 步长设置 cell；移动碎片的邻域 grid 可以按碰撞半径的 1 到 2 倍设置 cell。

Density imbalance 是 Uniform Grid 的主要风险。同一个世界中，开阔山体区域可能大量空 cell，建筑群和烟雾区域可能局部高密度。如果使用一个覆盖全世界的 dense grid，空 cell 会消耗内存；如果使用 hash grid，密集区域会让 bucket 过长。Grid 的性能判断应同时查看 cell 总数和 payload 分布。一个平均每 cell 只有 1 个对象的 grid，如果少数热点 cell 包含几千个粒子，查询尾部延迟仍然会很高。

Grid 的 ray traversal 通常使用 DDA（Digital Differential Analyzer）步进模型。DDA 的工作方式是：先把 ray 起点转换到当前 cell，计算 ray 到三个方向下一条 cell 边界的参数距离 tMax，再计算跨过一个 cell 需要增加的参数距离 tDelta。每一步选择最小的 tMax 方向前进，更新 cell 坐标和对应的 tMax。Amanatides 与 Woo 的 Fast Voxel Traversal 是这个思路的经典来源。

下面的伪代码展示 DDA 的查询主干。它省略了 ray 与 grid bounds 的初始求交，只保留 cell 级步进和 payload 检查。

while (insideGrid(cell) && t <= rayMaxT) {
    testPayload(cell, ray);

    if (tMax.x <= tMax.y && tMax.x <= tMax.z) {
        cell.x += step.x;
        t = tMax.x;
        tMax.x += tDelta.x;
    } else if (tMax.y <= tMax.z) {
        cell.y += step.y;
        t = tMax.y;
        tMax.y += tDelta.y;
    } else {
        cell.z += step.z;
        t = tMax.z;
        tMax.z += tDelta.z;
    }
}

这段代码说明 Grid 遍历的稳定性：每次只移动到相邻 cell，主要状态是 cell、step、tMax 和 tDelta。它的成本大致由访问 cell 数量和每个 cell 的 payload 数量决定。若 ray 穿过空旷空间，DDA 仍会逐 cell 前进；若 cell size 过小，空 cell 数量会放大这个成本。这个弱点正好由 Octree 的粗层级弥补。

Hash Grid 用稀疏哈希表替代 dense 三维数组。它把 cell 坐标编码成 hash key，再映射到 bucket。GPU 实现常见流程是：先为每个对象计算 cell key，然后排序或计数，接着通过 prefix sum 生成 cell range，最终得到 cellKey → offset/count 的索引表。这个布局适合每帧重建的动态粒子，因为对象移动后只需要重新计算 key、排序或分桶。

Hash Grid 的边界在冲突和排序成本。哈希冲突会让不同空间位置进入同一 bucket，需要存原始 cell key 来过滤；排序能获得连续内存布局，但每帧对大量动态对象排序会形成固定成本。对于移动碎片数量较少的测试帧，CPU 分桶或 GPU atomic append 都可接受；对于百万粒子邻域搜索，排序加 prefix sum 通常更可控，因为它把随机写入转成连续区间扫描。

Uniform Grid 的 GPU 友好性来自三个方面。第一，cell 坐标计算是少量整数和浮点运算。第二，payload range 可以连续存放，cache line 利用率稳定。第三，相邻 ray、相邻粒子或相邻体素访问的 cell 接近，内存局部性更好。它的失败场景也清晰：世界范围巨大但有效内容稀疏，局部密度跨度极大，或者查询 ray 经常穿过长距离空区。

把本节结论放回测试帧：烟雾内部 ray marching 使用局部 dense grid，因为每条 ray 进入烟雾后需要按近似连续的步长采样；移动碎片使用 hash grid，因为它们每帧变换位置且邻域查询半径固定；山谷静态几何不使用全局 uniform grid，因为空区域跨度大，会让 DDA 长时间访问空 cell。

58.3 八叉树与网格混合方案设计​

Octree 与 Grid 的混合方案把空间结构拆成两层：粗层级负责跳过大范围空区域，局部 Grid 负责高频、规则、连续的查询。这个设计适合 Frame_OctreeGrid_Test 这类非均匀场景：山体、天空和远处地形很稀疏，建筑内部、烟雾体积和粒子碎片局部密集。单一 Octree 会让局部查询走大量层级分支，单一全局 Grid 会让空区域占用过多 cell。

一个稳定混合方案可以按四类资源组织。第一类是 coarse octree node buffer，保存大空间层级和 occupancy。第二类是 leaf record buffer，保存叶节点类型和局部资源句柄。第三类是 local grid 或 voxel brick buffer，保存叶节点内部的规则数据。第四类是 payload buffer，保存三角形范围、粒子列表、材质索引或体积采样参数。查询先命中 coarse octree leaf，再按 leaf type 选择局部处理路径。

这张图的边界是“空间索引如何选择局部数据结构”。它没有覆盖材质着色、光照积分和后处理。Octree leaf 的职责是把查询导向正确的局部数据；局部 Grid 或 brick 的职责是让同一片空间内的查询保持连续访问。

Coarse Octree 的深度应服务 streaming 和稀疏跳过。对于大世界，根节点和前几层可以对应世界分块或 streaming page。相机附近的节点保持 resident，远处节点只保留低分辨率 proxy 或空标记。这样一来，查询进入未加载节点时可以返回保守结果，例如“未知区域需要 fallback”或“只使用低精度碰撞代理”。这个策略比直接把全世界体素化成 dense grid 更适合开放场景。

Local Grid 的 cell size 应服务局部查询半径。烟雾 leaf 中的 grid 可以让 cell size 接近体素 brick 的采样尺度，DDA 进入 leaf 后沿局部坐标前进。粒子 leaf 中的 grid 可以让 cell size 接近邻域半径，使每个粒子只检查当前 cell 和邻近 cell。三角形密集 leaf 中也可以使用 micro grid，把大量小三角形分到局部 cell 中，降低叶节点内线性测试数量。

Sparse voxel 结构可以看成 Octree 与 Grid 的另一种混合。上层使用层级节点表达稀疏性，下层使用固定大小 voxel brick 保存连续体素。Laine 与 Karras 在 NVIDIA Research 的 Efficient Sparse Voxel Octrees 中展示了把稀疏体素、ray cast 和紧凑数据布局结合的思路；生产级体积管线中，OpenVDB / NanoVDB 也使用层级稀疏结构管理体积数据。工程上应关注同一件事：上层跳过空区域，下层保持块内连续访问。

GPU buffer 设计要把“节点”和“数据块”分离。节点 buffer 应尽量小，便于遍历阶段频繁读取；brick 或 payload buffer 可以更大，只有命中叶节点时读取。Leaf record 可以使用 type tag 区分 triangle leaf、grid leaf、volume brick leaf 和 dynamic bucket leaf。这样做的收益是遍历阶段不会被大 payload 拖慢，局部处理阶段又能按数据类型选择更合适的 shader 或 kernel。

混合方案还需要处理边界重叠。Ray 从 Octree leaf 进入 local grid 时，必须把世界空间 ray 转换到 leaf 局部坐标，并使用 leaf bounds 裁剪 t 范围。粒子或物体跨越 leaf 边界时，可以写入多个 leaf 的 dynamic bucket，也可以放到上层 loose node。体积 brick 之间需要 ghost voxel 或边界采样规则，否则 ray marching 在 brick 接缝处会出现密度断层。

Streaming update 是混合方案的优势。Coarse Octree 的叶节点可以对应资源页，leaf record 保存 page id 和 residency 状态。相机移动时，系统只更新进入视野或查询范围的叶节点。烟雾体积可以按 brick 上传，建筑三角形可以按 mesh cluster 上传，动态碎片可以每帧写入独立 dynamic grid。查询阶段看到 leaf 未 resident 时，使用低精度 fallback 或跳过非关键效果。

把本节结论放回测试帧：静态山谷进入 coarse Octree；建筑密集区域的 leaf 保存 triangle payload 或 micro grid；烟雾 leaf 指向 sparse voxel brick；移动碎片进入 dynamic hash grid；拾取 ray 先穿过 Octree，再在命中的 leaf 内进入三角形测试或 Grid DDA。这个组合让大范围空区、局部密集数据和每帧动态对象各自走合适的数据路径。

58.4 动态更新与稀疏体素优化策略​

动态更新要区分“结构变化”和“payload 变化”。结构变化指节点、cell、brick 的拓扑或分配发生变化，例如 Octree 分裂、合并、brick 新建或释放。Payload 变化指对象仍在已有结构内，只是位置、密度或引用列表改变。把这两类变化拆开后，系统可以把静态大结构留在 GPU，按帧更新较小的脏区。

在测试帧中，山体和建筑几乎静态，移动碎片每帧改变位置，烟雾密度会局部扩散。直接每帧重建整个 Octree 会浪费 CPU/GPU 时间，也会让 buffer residency 不稳定。更合适的路径是：静态 Octree 长时间复用；移动碎片写入 dynamic grid；烟雾只标记发生变化的 brick；必要时对局部 brick 做 compact 或重新分配。

Moving object 的更新可以使用三种策略。第一，独立 dynamic grid：每帧根据物体 bounds 计算 cell key，重建动态 bucket，静态结构保持不变。第二，loose octree：节点 bounds 放宽，物体在小范围移动时仍留在原节点，超过 loose bounds 后再迁移。第三，上层动态列表：大物体或移动范围大的对象放入较高层节点，由查询阶段额外测试。三种策略的选择依据是移动幅度、对象数量和查询频率。

Dirty region 是体积和 voxel 更新的核心单位。烟雾模拟写入密度场后，可以把发生变化的 voxel 范围扩展一圈作为 dirty brick，因为插值和滤波会读取邻近值。上传时只传 dirty brick，重建时只更新相关 occupancy 和 brick metadata。若某个 brick 的密度全部低于阈值，可以释放或标记为空；若某个空区域密度增长，则分配新 brick 并更新上层 occupancy。

Sparse allocation 需要一套可复用的资源池。GPU 上常见布局是 brick pool、free list、allocation bitmap 和 compacted active list。CPU 或 compute shader 标记需要分配的 brick，prefix sum 生成写入位置，随后把 active brick 写成连续列表供 ray marching 或 volume pass 使用。这样可以把稀疏体积从“巨大三维数组”转成“活跃 brick 列表 + 层级索引”。

Clipmap 适合相机周围的连续体积或地形数据。它使用多个以相机为中心的网格层级，近处层级分辨率高，远处层级分辨率低。相机移动时，系统滚动更新新进入范围的 slice。对于测试帧中的烟雾和远处低频地形密度，clipmap 可以把近处采样质量和远处内存成本分开。它的边界是局部细节必须能被层级采样表达，且跨层过滤规则要稳定。

GPU compaction 把活跃对象、活跃 cell 或活跃 brick 收集到连续数组中。典型流程是 mark、scan、scatter。Mark 阶段写出每个元素是否活跃，scan 阶段计算活跃元素的输出位置，scatter 阶段把活跃元素写入 compact buffer。后续 draw、dispatch 或 ray marching 只遍历 compact buffer，可以减少空元素扫描。这个流程依赖 prefix sum，会引入额外 pass，但在稀疏数据占比高时收益明显。

动态更新的同步边界需要明确。CPU 写入 GPU buffer 后，图形 API 需要资源状态转换或 barrier，保证后续 shader 读取到完整数据。Compute pass 更新 occupancy 后，ray marching pass 或 draw pass 要等待写入完成。Vulkan、Direct3D 12、Metal 的具体 barrier 写法不同，但判断对象一致：谁写入、谁读取、读写发生在哪个 queue、数据范围是否重叠。错误的同步会表现为偶发漏采样、旧帧数据残留或某些 leaf payload 为空。

稀疏体素还需要处理时间稳定性。若 occupancy 阈值过于贴近密度噪声，brick 会在相邻帧反复分配和释放，画面上可能出现闪烁，性能上会出现 allocation 峰值。工程上可以使用滞回阈值、最小驻留帧数、dirty brick 合并和延迟释放。这样做会增加少量内存占用，但能换取稳定的 streaming 和更平滑的帧时间。

把本节结论放回测试帧：山体和建筑的 coarse Octree 在加载阶段构建；移动碎片每帧进入 dynamic hash grid；烟雾模拟把变化区域标记为 dirty brick，随后更新 sparse allocation 与 active brick list；渲染阶段用 barrier 连接 compute 更新和 volume sampling。性能问题出现时，先看每帧重建范围，再看 active brick 数量，接着看 barrier 与 payload buffer 是否形成同步等待。

58.5 性能评估：空间结构在场景中的表现​

空间结构的性能评估要把“构建成本、更新成本、遍历成本、payload 测试成本和内存成本”分开。一个结构可能构建很快但遍历很慢，也可能遍历高效但动态更新昂贵。对实时图形系统而言，帧时间的关键来自当前 frame 中哪些 pass 读取了哪些 buffer、访问是否连续、分支是否一致、候选测试是否收敛；理论复杂度只能提供初步方向。

在 Frame_OctreeGrid_Test 中，可以把同一套场景分别放入五种观察条件：稀疏静态场景、局部密集场景、动态碎片场景、烟雾体积场景和混合大世界场景。每个条件都看同一组指标：结构内存大小、构建或更新时间、平均遍历节点或 cell 数、平均 payload 数、最坏热点 payload 数、GPU pass 时间和画面错误。这样能把结构选择从经验判断变成可复查证据。

场景条件更适合的结构主要收益主要风险观察指标
稀疏静态山体Coarse Octree跳过大块空区域深层节点随机访问节点访问数、payload 命中率
局部密集建筑Octree + micro grid粗剔除后局部连续查询跨 leaf 重复 payload叶节点 payload 数、去重成本
大量移动碎片Hash Grid每帧重建简单，邻域查询稳定bucket 热点和排序成本bucket 长度分布、构建 pass 时间
烟雾体积Sparse brick + local grid空体素不存储，brick 内连续采样接缝和分配抖动active brick 数、采样步数
混合大世界Coarse Octree + local gridsstreaming 与局部查询分离资源句柄和同步复杂resident page 数、barrier 等待

这张表的用途是建立评估维度。它不直接给出全平台固定答案，因为不同 GPU、API、场景资源和查询类型会改变瓶颈。表中每一行都可以对应一次 profiling：RenderDoc 可以查看 pass、draw、dispatch、buffer 绑定和资源状态；Nsight Graphics 可以进一步观察 warp 分支、内存吞吐、cache 行为和 shader 时间；Xcode GPU tools 可以在 Apple 平台观察 encoder、resource 和 tile 相关成本。工具输出要回到同一组问题：访问了多少空间单元、每个空间单元带来多少候选、内存是否连续、同步是否阻塞。

稀疏场景下，Octree 通常能减少大量空区域查询。若 profiling 显示 ray 或 frustum query 访问了很多空 leaf，说明上层 occupancy、root bounds 或停止细分规则失效。若节点访问数少但 payload 测试数仍高，说明大对象跨节点复制过多或叶节点阈值过宽。此时应优先检查 leaf payload 分布，而非直接加深整棵树。

密集场景下，Uniform Grid 的优势取决于密度是否均匀。建筑内部三角形如果尺寸接近、分布连续，micro grid 可以让 ray 只测试经过 cell 中的候选。若某些 cell 集中大量三角形，payload 测试会成为热点。此时应调整 cell size、把大三角形放入上层列表，或对局部区域再做二级结构。Grid 的失败证据通常是少数 cell 的 payload count 远高于平均值。

动态场景下，更新成本常常超过查询成本。移动碎片若每帧触发 Octree 节点分裂、合并和 payload 去重，帧时间会出现尖峰。Hash Grid 或 dynamic bucket 的收益在于重建路径规则：计算 key、分桶、排序或 scan，然后连续写入 bucket range。若动态对象数量大，排序 pass 和 atomic 冲突要单独计时；若对象数量小，CPU 分桶再上传可能更直接。

体积数据下，评估指标要关注 active brick 与采样步数。Sparse structure 减少空区域存储，但 ray 进入 active brick 后仍要采样密度、做插值和累积。若画面出现接缝，先检查 brick 边界采样和 ghost voxel；若帧时间抖动，先检查 brick 分配释放频率和 active list compact 成本。体积结构的正确性证据来自画面连续性，性能证据来自 active brick 数、ray marching 步数和 volume pass 时间。

混合大世界下，最有价值的评估顺序是从粗到细。先看 coarse Octree 或 page table 是否让查询进入正确 resident 区域；再看 local grid 或 brick 的 cell size 是否匹配查询半径；接着看 payload buffer 是否连续；最后看更新 pass 和渲染 pass 之间的 barrier 是否形成等待。这个顺序能防止优化误判：若上层 page 选择已经错误，局部 shader 再优化也无法修正漏数据；若 payload 热点很严重，增加 Octree 深度也未必降低热点 cell 的候选数。

本章的最终判断可以压缩成一句：Octree 适合管理“哪里有内容”，Grid 适合处理“进入局部后怎样连续查询”。当场景同时包含大范围空区、局部密集内容、动态对象和体积数据时，稳定方案通常是粗层级 Octree 加局部 Grid、sparse brick 或 dynamic hash grid。评价这种方案时，必须看 frame 中真实发生的构建、更新、遍历、payload 测试和同步路径。

最小自检任务​

给定一个实时渲染场景：世界范围是 4 公里山谷，只有道路、建筑和山脊上有静态三角形；相机附近有一团 80 米宽的烟雾体积；场景中有 20,000 个移动碎片用于碰撞和特效；每帧需要做鼠标拾取 ray、体积 ray marching、粒子邻域查询和可见性粗剔除。请设计一套 Octree / Grid 混合结构，并说明性能评估顺序。要求回答覆盖结构分工、cell size 判断、动态更新、稀疏分配和工具证据。

答案要点​

静态山谷应使用 coarse Octree 或类似层级结构管理世界 bounds 和静态几何 occupancy。它负责让拾取 ray、可见性粗剔除和资源 streaming 跳过大范围空区。叶节点保存静态三角形 payload、建筑局部结构句柄或体积 brick 句柄；过大的静态对象可以保存在父节点或 loose node 中，以控制跨 leaf 复制。

烟雾体积应使用 sparse brick 加 local grid。Coarse Octree leaf 只负责定位烟雾所在区域，进入 leaf 后把 ray 转换到局部坐标，用 DDA 或固定步长 ray marching 访问 brick 内体素。Cell size 或 brick voxel 尺寸应接近体积采样步长，并检查 brick 接缝、ghost voxel 和 active brick list。若烟雾每帧变化，只更新 dirty brick，并通过 mark、scan、scatter 维护 active list。

20,000 个移动碎片应放入 dynamic hash grid 或独立 dynamic bucket。Cell size 应与碰撞半径或邻域搜索半径匹配，使每个碎片主要检查当前 cell 与邻近 cell。每帧计算 cell key，分桶或排序，再生成连续 bucket range。这样静态 Octree 不需要随碎片每帧重建，动态路径的成本也能通过 bucket 长度分布和构建 pass 时间复查。

性能评估先看结构分工是否正确，再看局部参数。第一步检查 coarse Octree 的节点访问数、leaf payload 命中率和 resident page 数；第二步检查烟雾 active brick 数、ray marching 步数和接缝画面；第三步检查 hash grid 的 bucket 长度分布、排序或分桶 pass 时间；第四步检查 payload buffer 是否连续、是否存在热点 leaf 或热点 cell；第五步检查 compute 更新和渲染读取之间的 barrier 是否造成等待。RenderDoc 可用于确认 pass、dispatch、buffer 绑定和资源状态；Nsight 或 Xcode GPU tools 可用于观察 GPU 时间、内存访问和分支相关症状。

本章知识点总结​

  • Octree 定位：Octree 通过三维递归八分表达稀疏空间，让查询先经过大尺度节点，再进入相关叶节点 payload。
  • Occupancy：Occupancy 表达空间是否含有后续处理内容，payload 表达命中后需要测试或采样的具体对象。
  • 停止细分：最大深度、最小 cell 尺寸、payload 阈值和空间密度变化共同决定叶节点何时停止分裂。
  • 跨界对象：跨越多个节点的对象可以放在父节点、loose node 或多个 leaf 中，选择依据是候选数量、更新成本和去重成本。
  • Grid 寻址：Uniform Grid 用世界坐标到整数 cell 坐标的映射提供稳定寻址，适合局部连续查询。
  • Cell Size：Cell size 决定每次查询访问多少 cell 以及每个 cell 内有多少 payload，需要结合查询半径和密度分布判断。
  • DDA 遍历：DDA 用 cell、step、tMax 和 tDelta 逐格推进 ray，成本由访问 cell 数和 cell 内 payload 数共同决定。
  • Hash Grid：Hash Grid 适合动态对象和稀疏 cell，通过 key、bucket、prefix sum 或排序生成可遍历的 cell range。
  • 混合结构：Coarse Octree 负责跳过大范围空区，local grid、micro grid 或 sparse brick 负责 leaf 内连续查询。
  • Sparse Brick：稀疏体素通常使用上层层级索引管理空区，下层固定 brick 保存连续体素数据。
  • 动态更新：动态更新应区分结构变化和 payload 变化，把静态大结构复用，把移动对象和 dirty brick 放入局部更新路径。
  • GPU Compaction：Mark、scan、scatter 可以把活跃 cell、brick 或对象收集为连续数组，减少后续 pass 的空扫描。
  • 同步边界：Compute 更新 occupancy 或 payload 后，渲染读取前需要正确 barrier，核心判断是写者、读者、queue 和数据范围。
  • 性能评估：空间结构评估应同时查看构建、更新、遍历、payload 测试、内存访问和同步等待。
  • 选择结论：Octree 适合回答哪里有内容，Grid 适合回答进入局部后怎样连续查询，混合方案适合大范围稀疏加局部密集的实时场景。