Chapter 57: KD-Trees
KD‑Tree 解决的核心问题，是把一帧中的几何查询从“每条 ray 扫完整个 primitive 列表”改成“ray 按空间顺序访问少量候选区域”。本章用一个静态展厅场景作为贯穿材料：场景里有墙面、柱子、玻璃柜、雕塑和若干点采样数据，主相机发出 primary ray，阴影阶段还会发出 shadow ray。我们关心的对象不是最终材质效果，而是一条 ray 从场景包围盒进入后，如何通过 KD‑Tree 节点找到可能相交的 primitive、如何减少无效测试，以及如何判断 KD‑Tree 相比 BVH、uniform grid、octree 是否合适。
KD‑Tree 属于空间划分结构。每个内部节点用一个与坐标轴垂直的平面把当前空间区域切成两个子区域，叶节点保存与该区域重叠的 primitive 列表。这个定义带来一个直接后果：同一个三角形、曲面包围盒或体素块只要跨过切分平面，就可能同时出现在两个叶子里。它换来的收益，是 ray traversal 可以沿着 ray 的参数区间按前后顺序推进，先访问近处区域，再在需要时访问远处区域。
本章读完后，读者应能定位 KD‑Tree 在渲染管线中的位置，判断 split plane 如何改变构建成本和查询成本，追踪一条 ray 的 stack traversal，解释 mailboxing 处理重复 primitive 测试的原因，并把 KD‑Tree、BVH、uniform grid、octree 放在同一组维度中比较。后文的实现细节参考了 PBRT v3 的 Kd-Tree Accelerator 中的构建与遍历路径，但正文会把代码层对象整理成通用工程判断。
贯穿场景的输入可以简化为四类数据：scene bounds 表示整棵树覆盖的世界空间范围，primitive bounds 表示每个 primitive 的轴对齐包围盒，ray 表示查询路径，leaf primitive list 表示每个叶节点最终要执行的相交测试集合。KD‑Tree 的好坏可以从这四类数据的关系判断：节点是否把空空间切出来，primitive 是否被大量复制，ray 是否按近到远的顺序短路，叶节点里的相交测试是否集中在少量真实候选对象上。
57.1 KD‑Tree 的定义与适用场景
KD‑Tree 是一种二叉空间划分树。内部节点记录 axis、split 和两个 child，axis 表示当前切分平面垂直于 x、y、z 中哪一条轴，split 表示平面在该轴上的坐标，child 表示平面两侧的子空间。叶节点记录 primitive 列表，列表中的 primitive 与该叶节点覆盖的空间区域有重叠。
在展厅场景中，根节点覆盖整个房间。一次沿 x 轴的切分可以把左侧墙面和右侧玻璃柜分开；随后右侧区域再沿 z 轴切分，把前景雕塑和后景柱子分开。这个过程没有直接改变三角形本身。它改变的是 ray 查询的候选集合：一条从相机射向左侧墙面的 ray 可以先进入左侧空间，命中墙面后用更小的 ray.tMax 终止后续访问。
KD‑Tree 的空间划分和对象分组有一个关键差异。BVH 通常把 primitive 分到两个 object group 中，每个 group 再计算自己的包围盒；KD‑Tree 先划分空间，再把与空间重叠的 primitive 挂到对应区域。一个长条墙面跨过 split plane 时，它会进入左右两个 child 的 primitive list。这个复制会增加内存和叶节点测试次数，但它也让空区域成为真实可跳过的空间。
下面的图描述展厅中一条 ray 访问 KD‑Tree 的数据路径。图里只画查询阶段，不覆盖构建阶段的所有 split 候选评估。
这条路径的核心判断是 ray interval。ray 和 scene bounds 相交后得到一个参数区间 [tMin, tMax]。遍历内部节点时，算法计算 ray 到 split plane 的参数 tSplit。如果 tSplit 落在当前区间内，near child 先处理，far child 进入待访问栈。near child 找到更近命中后，ray.tMax 变小；当下一个待访问节点的 tMin 已经大于当前命中距离，遍历就可以结束。
KD‑Tree 适合的第一类对象是静态、空间分布不均匀、空空间比例高的几何。展厅里墙面、柱子和雕塑集中在少量区域，天花板下方和玻璃柜之间存在较多空空间。好的切分可以让 shadow ray 快速穿过空区域，把相交测试集中到可能遮挡光源的 primitive 上。
KD‑Tree 适合的第二类对象是点查询和邻域查询。点云、粒子采样、光子映射中的 photon lookup 也可以使用 KD‑Tree，因为查询对象经常是“给定位置附近有哪些点”。这类 KD‑Tree 常按点存储，分裂平面穿过点坐标，叶节点保存少量点。三角形 ray tracing 里的 KD‑Tree 更强调空间区域与 primitive bounds 的重叠关系，两者共享 axis-aligned splitting，但 payload 和查询终止条件不同。
KD‑Tree 适合的第三类对象是固定体素场或静态体数据的跳空查询。体渲染中的空区域、稀疏采样块或 signed distance field 的空间块可以用类似树结构记录 min/max 或 occupancy 信息。ray marching 进入空节点时，可以直接推进到节点出口。这种用法和三角形相交不同，但判断逻辑一致：节点存储的摘要必须能证明当前 ray 段无需更细测试。
KD‑Tree 的弱点来自构建和更新。动态场景中，skinned mesh、移动道具、破碎几何会让 primitive bounds 每帧变化。KD‑Tree 的 split plane 绑定世界空间区域，primitive 重新分类和复制成本高。展厅中如果只有相机移动，KD‑Tree 可以复用；如果玻璃柜、雕塑和柱子每帧大幅移动，构建成本会进入 frame budget，BVH refit 或两层结构通常更容易控制更新成本。
本节的可执行判断是：先看场景是否静态，再看空空间是否值得切出，再看 primitive 跨 split 的复制是否可控，最后看查询是否能利用 front-to-back 顺序提前结束。四个条件同时成立时，KD‑Tree 才可能把构建成本转换成查询收益。
57.2 划分平面选择算法分析
划分平面选择决定 KD‑Tree 的形状。它回答三个问题：沿哪条轴切，在哪个坐标切，什么时候停止继续切。展厅场景中的一条切分如果把墙面和雕塑分开，后续 ray 测试会减少；如果切分穿过一排长墙，墙面 primitive 被复制到两个子节点，叶节点数量和 primitive 引用数都会上升。
最简单的策略是最长轴中点切分。算法先计算当前 node bounds 在 x、y、z 上的长度，选择最长轴，再在该轴中点创建 split plane。它的优势是构建快、实现稳定、节点区域形状较均衡。它的代价是完全不看 primitive 分布。展厅中一侧几何密集、另一侧为空时，中点切分可能把密集区留在一个 child 中，空区虽然被切出，但密集 child 仍需要多次后续切分。
中值切分使用 primitive 中心点排序。算法选择一条轴，把 primitive bounds 的 centroid 投影到该轴，再按中位数位置切分。它让左右 child 的 primitive 数量接近，树深更稳定，构建过程也容易并行化。它的问题是 centroid 只代表对象中心，不代表对象覆盖范围。长墙的中心点可能落在一侧，但墙体 bounds 覆盖两侧空间，最终仍然进入两个 child。
SAH 是 KD‑Tree 构建中最常见的质量模型。SAH 的全称是 Surface Area Heuristic，工作定义是：用子空间表面积近似 ray 进入该子空间的概率，再用该概率乘以子空间里的 primitive 数量，估算一次 split 后的遍历和相交成本。常见形式可以写成：
其中 C_trav 是访问内部节点的成本，C_isect 是一次 primitive 相交测试成本，P_L 和 P_R 来自左右 child surface area 与 parent surface area 的比例，N_L 和 N_R 是左右 child 的 primitive 数量，b_empty 是空节点奖励。这个公式在图形工程中的意义很具体：split plane 的好坏不只看 primitive 数量，还看 ray 进入子空间的概率，以及空空间能否被快速跳过。
在展厅中，SAH 倾向于把玻璃柜旁边的大块空走廊切出来，因为一个空 child 的 N 为 0，shadow ray 穿过这段区域时无需执行 primitive 相交测试。SAH 也会惩罚穿过大量长条 primitive 的 split，因为这些 primitive 同时进入左右 child，N_L + N_R 可能大于原始数量。它把“切出空空间”和“控制复制”放进同一个成本表达式。
split candidate 的生成也影响构建成本。对三角形 bounds 来说，最低 SAH 成本通常出现在某个 primitive bounds 的 min face 或 max face 上。实现时可以对每条轴生成 2 * primitiveCount 个边界事件：start 表示 primitive bounds 的最小坐标，end 表示最大坐标。排序后沿轴扫描，维护当前 split 左侧和右侧的 primitive 数量，就能评估每个候选平面的成本。
空节点裁剪是 KD‑Tree 比很多对象分组结构更有特点的部分。空 child 代表 ray 可以穿过一段没有 primitive 的空间。这会降低 shadow ray、visibility ray 和 primary ray 在空区域中的无效测试。空节点奖励应当受控：奖励过高会让构建器过度追求空空间，产生很深的树；奖励过低会保留太多大叶子，查询阶段继续承受大量 primitive 测试。
最大深度和叶节点阈值是构建终止条件。maxDepth 控制递归深度，防止退化几何让树无限膨胀；maxPrims 控制叶节点内 primitive 数量。二者需要一起看。较小 maxPrims 会推动更多切分，可能减少叶节点测试，但会增加节点数量和 primitive 复制；较小 maxDepth 会压住内存，但可能留下过大的叶子。
平面选择可以按下面顺序判断：先选择候选轴和候选平面，再计算左右 child bounds 与 primitive 分类，再用 SAH 或简化成本模型比较，最后检查终止条件。这个顺序把“几何分布”“ray 进入概率”“相交测试成本”“内存增长”放在同一条构建链上。
57.3 实现高效 KD‑Tree 构建
高效构建的输入是 primitive bounds 和当前节点的 primitive id 列表，输出是连续节点数组、叶节点 primitive list 和构建阶段的临时工作区。工程实现的核心目标，是减少重复 bounds 计算、减少临时分配、控制 primitive 复制，并让 traversal 阶段的节点布局适合缓存访问。
第一步是预计算所有 primitive bounds。展厅场景中的每个三角形、曲面代理或体素块都可以提供一个 world-space AABB。构建器在根节点开始前把这些 AABB 放入数组。后续递归只传 primitive id，不反复调用几何对象的 bounds 计算函数。这个动作把几何求值成本从递归内部移到构建入口，便于控制构建时间。
第二步是生成 split candidate。每个 candidate 可以用 axis、position、primitiveId 和 eventType 表示。eventType 有 start 和 end 两类。沿某条轴排序后，扫描过程中遇到 end 先减少右侧数量，再计算当前位置成本，随后遇到 start 增加左侧数量。这个顺序能正确处理 primitive bounds 边界正好落在 split plane 上的情况。
下面的 C++ 风格伪代码展示构建阶段的关键数据流。它省略 allocator、浮点鲁棒性和并行调度，只保留 split candidate、primitive classification 和递归节点写入三件事。
struct PrimitiveBound {
Vec3 minPoint;
Vec3 maxPoint;
};
struct SplitEvent {
float position;
int primitiveId;
int type; // 0 = start, 1 = end
};
struct KdNode {
float split;
int axis;
int leftChild;
int rightChild;
int firstPrimitive;
int primitiveCount;
bool leaf;
};
int buildNode(Bounds nodeBounds, Span<int> primitiveIds, int depth) {
int nodeIndex = allocateNode();
if (primitiveIds.size() <= maxPrims || depth == maxDepth) {
writeLeaf(nodeIndex, primitiveIds);
return nodeIndex;
}
SplitChoice choice = findBestSplit(nodeBounds, primitiveIds);
if (!choice.valid || choice.cost >= leafCost(primitiveIds.size())) {
writeLeaf(nodeIndex, primitiveIds);
return nodeIndex;
}
ScratchList leftIds;
ScratchList rightIds;
classifyPrimitives(choice, primitiveIds, leftIds, rightIds);
Bounds leftBounds = nodeBounds;
Bounds rightBounds = nodeBounds;
leftBounds.maxPoint[choice.axis] = choice.position;
rightBounds.minPoint[choice.axis] = choice.position;
int leftChild = buildNode(leftBounds, leftIds, depth + 1);
int rightChild = buildNode(rightBounds, rightIds, depth + 1);
writeInterior(nodeIndex, choice.axis, choice.position, leftChild, rightChild);
return nodeIndex;
}
这段代码证明一个重要边界：primitive classification 使用的是 primitive bounds 与 split plane 的重叠关系。若 bound.max[axis] <= split，primitive 只进入左 child；若 bound.min[axis] >= split，primitive 只进入右 child；若二者跨过 split，则左右 child 都要记录该 primitive。分类结果直接决定叶节点 primitive list 的总长度。
节点分配应使用连续数组或 arena。traversal 会频繁访问内部节点，节点越小、布局越连续，CPU 端或 GPU compute 端的 cache 行利用率越高。一个常见布局是把 near child 放在父节点之后，把 far child 用 offset 记录。这样 ray 进入常见路径时，父节点和一个 child 更可能位于相邻内存区域。
leaf primitive list 可以单独放在一段 index buffer 中。叶节点只记录 firstPrimitive 和 primitiveCount。对于只有一个 primitive 的叶子，可以把 id 直接塞进节点字段，减少一次额外索引访问。这个优化应服从整体布局：如果它让节点字段分支过多或压缩逻辑过于复杂，调试成本会超过收益。
stack traversal 是查询阶段的关键路径。构建阶段必须写出支持 front-to-back traversal 的节点信息：split axis、split position、两个 child 的地址或 offset。查询时先计算 tPlane = (split - ray.origin[axis]) * invRayDir[axis]，再根据 ray origin 位于 split 哪侧决定 near child 和 far child。若 tPlane 落在当前 [tMin, tMax] 内，far child 连同它的参数区间压栈，near child 立即访问。
mailboxing 处理的是“同一个 primitive 被多个叶节点引用”带来的重复相交测试。展厅里的长墙可能横跨多个 KD‑Tree 叶子。一条 ray 穿过这些叶子时，如果每到一个叶子都测试这面墙，会浪费相交计算。mailbox 可以给每个 primitive 记录最后一次被哪条 ray 测试过；同一条 ray 再次遇到该 primitive 时直接跳过。
mailboxing 的边界来自并行执行。CPU 单线程 tracing 中，可以用 ray id 写入 primitive mailbox。多线程 CPU 或 GPU 上，多个 ray 同时访问同一个 primitive mailbox 会产生竞争。工程上常见的做法是把 mailbox 放在线程局部、ray 局部或小型哈希集合里，或者只在 primitive 复制非常严重的路径上启用。判断依据是重复测试节省的 C_isect 是否大于 mailbox 查询和同步的开销。
构建阶段的检查顺序可以固定为六步：预计算 bounds，生成 candidate，评估 split cost，分类 primitive，写入节点和叶子索引，统计构建结果。统计项至少包括 node count、leaf count、max depth、primitive reference count、empty leaf count 和 average leaf primitive count。没有这些指标，KD‑Tree 的性能问题很难和 split 策略建立因果关系。
57.4 KD‑Tree 在渲染/光线追踪中的使用案例
KD‑Tree 在渲染中的主要用法是加速查询。查询可以是 ray-triangle intersection、shadow visibility、point nearest neighbor、range query 或体素空空间跳过。它们的共同点是：查询对象在空间中有一条路径或一个范围，KD‑Tree 用空间划分缩小候选集合。
在静态几何 ray tracing 中，展厅场景先构建一次 KD‑Tree，随后每帧相机和光源发出大量 ray。primary ray 进入 scene bounds 后，按照 split plane 的前后顺序访问节点。叶节点里只测试与该空间区域重叠的 primitive。若最近命中已经位于当前待访问节点之前，后续节点可以停止访问。这条 front-to-back 特性对 primary ray 和 shadow ray 都有意义。
shadow ray 的判断更偏向 early-out。它只需要知道从 shading point 到 light 的线段之间是否存在遮挡物。KD‑Tree traversal 可以在命中任意遮挡 primitive 后立即返回。展厅中从雕塑表面指向天窗的 shadow ray 如果先进入空走廊，再进入柱子附近叶节点，命中柱子后就无需继续走到远处墙面。此时优化目标是减少到第一个 blocker 之前的节点和 primitive 测试。
点云查询使用另一种 payload。点云 KD‑Tree 的叶子保存 point index，查询输入通常是一个位置和半径，或一个位置和最近邻数量。展厅中的扫描点云可以用 KD‑Tree 支持局部法线估计：给定一个点，查找附近点集合，再拟合局部平面。这里的 split plane 仍然是 axis-aligned，但 traversal 的终止条件变成“节点 bbox 到查询点的最短距离是否已经大于当前搜索半径”。
体素场景中的 KD‑Tree 关注 occupancy 或 min/max 摘要。假设展厅被烘焙成稀疏体素体，节点可以记录子空间是否为空、密度范围或材质范围。ray marching 进入空节点时，可以把 ray 参数直接推进到节点出口。进入非空叶子后，再执行固定步长采样或更细粒度的 DDA。这个用法把 KD‑Tree 从 triangle accelerator 扩展为 space skipping structure。
静态几何案例中，KD‑Tree 的调试证据来自三组指标。第一组是构建统计：节点数、叶子数、primitive reference count 和最大深度。第二组是查询统计：每条 ray 访问的 node 数、leaf 数、primitive test 数和 early-out 比例。第三组是视觉或功能结果：最近命中距离、shadow visibility、点云邻域数量或体素采样结果是否稳定。
可以用一个小型 frame capture 或自定义 debug overlay 观察 KD‑Tree 的作用。对展厅场景发出相同的相机 ray 集合，分别记录关闭 KD‑Tree、启用中值切分 KD‑Tree、启用 SAH KD‑Tree 的 primitive test 数。正确的观察方式是先固定相机、光源、场景 bounds 和 ray 数量，再比较每种结构下的平均 primitive tests、P95 primitive tests 和构建时间。只看平均值会掩盖少量退化 ray；P95 能暴露穿过长墙、玻璃柜边缘或密集柱子区域的坏路径。
KD‑Tree 也适合做可视化调试。可以给每个叶节点生成一个半透明 AABB，颜色映射到 primitive count 或 ray visit count。展厅中如果某些叶节点 primitive count 很高，说明 split 没有把复杂区域继续拆开；如果某些空叶子 ray visit count 很高，说明空空间被频繁穿过，切出空节点产生了实际收益；如果同一片长墙导致相邻叶子都含同一批 primitive，说明 primitive duplication 已经影响查询。
这类案例的结论应落回 frame budget。离线渲染可以接受更慢构建换取更低 traversal cost；实时编辑器或动态可视化需要把构建时间、内存和查询时间一起算。KD‑Tree 的优势不是固定存在，它依赖场景静态性、ray 分布、split 质量和 primitive 复制程度。
57.5 与其他空间结构的对比分析
KD‑Tree、BVH、uniform grid 和 octree 都能减少空间查询中的候选集合，但它们减少候选集合的方式不同。比较时应使用同一组维度：划分对象、构建成本、更新成本、内存增长、查询路径、退化场景和调试证据。
KD‑Tree 划分空间。它的 split plane 是世界空间中的轴对齐平面，叶节点保存与区域重叠的 primitive。它适合静态、空空间明显、ray 查询频繁的场景。它的风险是 primitive 跨平面复制和构建成本高。展厅里固定墙面和雕塑适合 KD‑Tree；每帧移动的玻璃柜会让重建成本上升。
BVH 划分对象集合。内部节点记录 child bounds，叶节点保存 primitive 或 primitive group。primitive 通常只进入一个 child，更新时可以 refit bounds。BVH 对动态场景更友好，构建速度和内存增长也更容易控制。它的查询会访问包围体，包围体之间可能重叠；ray 穿过重叠区域时，两个 child 都可能被访问。对现代实时 ray tracing 管线来说，BVH 更常作为通用加速结构的工程选择。
Uniform grid 划分规则网格。它的 cell size 决定查询成本。cell 太大时，每个 cell 里 primitive 太多；cell 太小时，ray 需要穿过大量 cell，内存也会膨胀。它适合密度相对均匀、对象尺寸接近、查询路径可以用 DDA 稳定推进的场景。展厅中如果所有细节集中在雕塑附近，uniform grid 会在空区域浪费大量 cell，或者在密集区域留下过多 primitive。
Octree 递归八分空间。它比 uniform grid 更能表达稀疏空间，也比 KD‑Tree 的二叉切分更规则。它适合体素、稀疏 occupancy、层级 LOD 和大世界空间管理。它的节点 fan-out 更高，遍历分支和内存布局需要仔细设计。展厅体素化后，octree 可以自然表达空房间和局部细节；三角形 ray tracing 中，octree 的叶子 primitive 分布未必比 SAH KD‑Tree 更优。
下面的表把四种结构放在同一组工程维度中。表中的结论用于设计判断，具体项目仍需用构建统计和查询统计复核。
| 结构 | 划分对象 | 动态更新 | 查询特点 | 主要风险 |
|---|---|---|---|---|
| KD‑Tree | 空间区域 | 重建成本高 | ray 可按 near 到 far 推进，空区域可跳过 | primitive 复制、构建慢、深树 |
| BVH | primitive group | refit 和 rebuild 更灵活 | bounds test 多，child overlap 会增加访问 | bounds 重叠、树质量依赖构建器 |
| Uniform grid | 固定 cell | 局部更新简单 | DDA traversal 规则，适合均匀密度 | cell size 敏感、稀疏空间浪费 |
| Octree | 递归八分空间 | 局部更新可控 | 稀疏空间表达好，层级查询自然 | fan-out、节点布局、非均匀叶子成本 |
选择结构时可以按查询问题倒推。若目标是每帧动态物体的实时 ray query，先评估 BVH 或两层结构；若目标是静态场景中大量 ray 的软件 tracing，KD‑Tree 值得测试；若目标是粒子邻域或点云局部分析，点 KD‑Tree 或 spatial hash 都应进入候选；若目标是稀疏体素和大范围空空间跳过，octree、sparse grid 或 clipmap 更自然。
动态更新是 KD‑Tree 的主要边界。BVH 可以把叶子 bounds 改掉后向上 refit；KD‑Tree 的 split plane 已经固定为空间区域，primitive 移动后可能跨越更多节点，或者原本空节点变成非空节点。局部修补会破坏树质量，全量 rebuild 会增加 frame cost。工程中常见折中是把静态背景放在 KD‑Tree 或 BVH 中，把动态对象放入单独 BVH，再在查询阶段合并结果。
查询成本也需要按 ray 分布判断。primary ray 方向相干，front-to-back traversal 容易受益；secondary ray 方向分散，cache 命中和节点访问顺序会变差；shadow ray 有明确最大距离，early-out 价值更高；点查询没有 ray 方向，判断依据变成 node bounds 到查询点或查询球的距离。结构选择应绑定查询类型，不能用一个静态平均复杂度替代 frame 中真实 ray 分布。
最终的选择流程可以固定为：先定义查询类型和更新频率，再统计场景密度和对象尺寸，再实现一个可复核的基准结构，最后比较构建时间、内存、node visits、primitive tests 和 P95 查询成本。KD‑Tree 在这个流程中是一个强候选，但它的收益必须由数据证明。
最小自检任务
给定一个静态展厅场景：场景 bounds 为一个长方体房间，左侧是一面很长的墙，右侧有一个密集雕塑，房间中间有大块空走廊。你需要为 CPU 端软件 ray tracing 选择并调试 KD‑Tree。请回答三个问题：第一，根节点 split plane 应优先考虑哪些候选位置；第二，如何判断一个 split 产生了有效收益；第三，如果长墙被大量复制到多个叶子，应如何定位和处理这个问题。
答案要点
根节点 split plane 应优先考虑 primitive bounds 的 min face 和 max face 候选，并用 SAH 比较不同 axis 与 position 的成本。中间空走廊如果能形成空 child 或低 primitive count child，shadow ray 和 primary ray 可以减少相交测试；长墙的 bounds 如果跨过 split plane，它会进入两个 child，候选成本中应体现 primitive reference count 增长。
有效收益应通过构建统计和查询统计共同判断。构建统计看 node count、leaf count、max depth、primitive reference count、empty leaf count 和 average leaf primitive count；查询统计看每条 ray 的 node visits、leaf visits、primitive tests、early-out 比例和 P95 查询成本。若 split 后 primitive tests 下降，但 primitive reference count 和节点访问显著上升，需要继续比较总时间。
长墙大量复制时，先用 leaf primitive count 或 primitive reference heatmap 找到重复引用区域，再检查 split plane 是否反复穿过墙面 bounds。处理顺序是调整 split 成本中的复制惩罚，增大叶节点阈值或限制最大深度，对重复测试明显的路径加入 ray 局部 mailbox。多线程或 GPU 路径中，mailbox 的同步开销需要单独计入。
本章知识点总结
- 空间划分：KD‑Tree 用轴对齐平面递归划分空间，叶节点保存与空间区域重叠的 primitive 列表。
- 查询路径：ray 先与 scene bounds 得到参数区间，再按 split plane 的 near 到 far 顺序访问节点。
- 对象复制：primitive 跨过 split plane 时会进入多个 child，复制量直接影响内存和重复测试。
- 适用场景：静态几何、空空间明显、ray 查询频繁的场景更容易从 KD‑Tree 获得收益。
- SAH 判断：SAH 用子空间表面积近似 ray 进入概率，并把 traversal cost、intersection cost 和 primitive 数量放进同一成本模型。
- 空节点收益：空 child 可以让 ray 直接推进到下一个空间区域，尤其有利于 shadow ray 和可见性查询。
- 终止条件：max depth、maxPrims 和 split cost 共同决定叶节点大小、树深和 primitive reference count。
- 构建路径：高效构建需要预计算 bounds、生成 split events、扫描候选、分类 primitive 并连续写入节点。
- 节点布局：连续节点数组和紧凑字段可以降低 traversal 阶段的缓存开销。
- Mailboxing：mailboxing 用 ray 局部记录减少重复 primitive 测试，但并行路径需要计入同步或局部存储开销。
- 案例证据：KD‑Tree 调试应同时观察构建统计、查询统计和可视化 heatmap。
- 结构对比：KD‑Tree 强在静态空间划分，BVH 强在动态更新，uniform grid 强在均匀密度，octree 强在稀疏层级空间。