计算机图形学 18：怎样减少求交次数
第 17 篇每条射线询问场景中的全部图元。128 个球、16,384 条射线，就要执行 2,097,152 次球体求交，即使每条射线附近实际上只有一个球。
本篇给图元建立包围盒层级。验收不只观察渲染图，还逐射线比较最近交点，分别计数包围盒测试、节点访问和精确图元求交。分离球体与完全重叠球体采用同一份实现，观察结构何时有效、何时只增加开销。
一个盒子怎样排除整组图元
如果一个盒子包含组内全部几何，射线没有经过盒子，就不可能碰到组内几何。这个单向推理是加速结构的基础。射线经过盒子却不一定碰到表面，因为盒内允许有空白。
第 16 篇已有轴对齐包围盒 Bounds。球的盒为 center±radius；三角形的盒对三个顶点逐轴取最小、最大。父盒合并子盒的 low 和 high，不需要重新访问孩子内部的所有顶点。
保守包围意味着可以多保留候选，但不能漏掉真实几何。盒子过大主要损害速度，盒子过小会改变渲染结果。这里不使用包围盒命中代替球或三角形命中，它只决定是否继续调用第 17 篇的精确求交函数。
对于 X 轴，盒内要求 lowₓ≤oₓ+t dₓ≤highₓ。当 dₓ 非零时，除法得到进入与离开这一对平行平面的参数；方向为负时需交换两个端点。Y、Z 轴分别得到另外两个参数区间，最终取交集：
只有 enter>leave 才能直接判定错过。enter=leave 可能是擦过棱角，也可能是射线穿过一个零厚度三角形盒，不能一概拒绝。最终是否接受 t=min 仍由图元求交的开下界规则决定，粗筛可以保留这个边界候选。
对盒 [−1,1]³，起点 (0,0,−3)、方向 (0,0,1)，几何区间为 [2,4]；把射线 maximum 限制到 1，区间为空。从盒内原点沿 −Z 出发，则与射线有效范围相交后为 [0,1]。
零方向不能直接当普通除法
当某个方向分量为 0，射线在该轴上不移动。起点落在 slab 范围内，该轴不限制 t；起点落在外面，整条射线错过盒子。正零和负零都走这个分支。
如果直接计算倒数，虽然浮点无穷有时能传播出预期结果，但起点恰在边界时还会遇到 0×∞ 或 0/0。NaN 与 min/max 的交互不应靠偶然行为决定。当前实现明确判断 d==0，分别处理内外位置。
极小的非零方向不等于零方向。把所有 |d| 小于固定 epsilon 的轴都当作静止，可能漏掉远处真实交点。这里只分支精确零，其余按除法求区间。
代码对计算出的进入参数向负无穷、离开参数向正无穷各调用一次 nextafter，给区间增加一格浮点余量。这是有界教学实验的边界保护，不是完整舍入误差证明：坐标相减、除法、原始包围盒都可能已经含误差，一次扩张不能覆盖任意尺度与消减情况。
PBRT 第四版 §6.8.2 对保守盒求交有误差分析。当前实现没有复制其完整保证，沿用有限、非退化的实验输入，不把测试通过扩大到极端尺度。普通 double 三角形求交的既有限制也仍然存在。
用中位数构造一棵有限深度的树
BVH 的叶节点保存一小组图元，内部节点保存两个孩子与覆盖它们的包围盒。图元只分配到一个叶子，但不同孩子的空间范围可以重叠。这与“空间被切成互不相交的两半”不是同一件事。
当前构造器保存一份图元副本和一份索引数组。每个节点表示索引数组中的半开范围 [begin,end)，范围不超过两个图元就成为叶子，否则继续划分。
划分轴选择当前整个包围盒最长的轴；比较键是每个图元包围盒的中心坐标。使用 nth_element 将索引按中位数分为两组，左右各递归构建。中心计算省略共同的二分之一，不影响排序。
当所有中心相同时，比较器改用原始索引决胜。左右范围仍按数量平分，因此每次递归都会缩小。不能写成“找一个坐标分割平面，失败后继续递归同一组”，否则重合几何可能使构造无法终止。
这是一种按数量平衡的基线，不是表面积启发式 SAH。长轴与中位数能保持树深度约为对数级，但不能保证空间重叠少。每层求界与划分仍需访问图元；实现没有预先缓存所有盒中心，比较器会重复计算小型图元的盒。对于本次规模这足够直接，但构建计时会包含这部分工作。
节点保存在 vector 中。递归构造孩子时 vector 可能扩容，因此只保留父节点的整数索引，不保留引用；孩子完成后再用索引写回。构造器最多接受一百万图元，以免节点编号超出当前整数设计，空场景则不创建根节点。
找到一个交点以后还需要搜索吗
需要。遍历从根开始，用显式栈保存待处理节点。节点出栈后先与当前射线区间求交，错过就跳过整棵子树；叶节点内再调用原有图元求交。
发现更近候选时，记录交点，并把 maximum 收紧到候选 t。之后排除的必须是“不可能提供更近或同距优先候选”的范围。当前固定先左后右遍历，不按射线进入参数排序，因而先访问的孩子不一定包含最近表面。
反例使用八个同心球，半径从 0.2 增加到 0.9，射线从 z=−3 向 +Z。较大的球表面反而先到达。前面子树给出一个交点后，后面的子树仍需更新为编号 7、t=2.1。检查器单独验证这个结果，避免“看到任何命中就返回”的错误。
等距规则与第 17 篇保持一致：t 完全相同时选较小编号。maximum 是闭上界，后面的等距候选不会被排除。四个完全重合的球按编号 9、7、5、3 输入，横跨两个叶子，最后必须返回 3。
当前没有近子树优先、包围盒进入距离排序或固定大小栈优化。它们可以减少不必要访问或分配，但不改变最近命中的定义。把这些优化留在性能证据之后，可以先检查最基本的剪枝是否正确。
同一个场景应得到同一幅图
混合场景复用第 17 篇两个球、两个地面三角形，抽取到 ray_demo.hpp，没有复制第二套场景参数。相机、像素中心、分辨率、法线显示与 sRGB 编码也保持原值。
左半幅是暴力遍历，右半幅是 BVH，各 256×256。程序逐射线核对命中状态、图元编号、参数与世界交点；全部 65,536 条一致，命中数仍为 42,952。写出后还逐通道核对左右图块，完全相同。
相同图像只说明当前样本的结果相同。两边复用同一个球体与三角形求交函数，因此共享的内核错误仍可能同时出现。第 17 篇的解析根、重心和独立球体几何 oracle 继续运行；本篇新增的检查主要证明层级筛选没有改变这些结果。
第二张图不是表面明暗。像素灰度表示本条射线调用精确图元求交的次数除以 4，最后经过 sRGB 编码；黑色为 0，白色为 4。当前场景的大块白区意味着多数射线仍测试四个图元。
原因在于两个地面三角形的盒范围很大，中位数分组后的子盒重叠严重。总图元测试为 199,608 次，比暴力的 262,144 次少，但收益有限；节点出栈 165,852 次，还带来额外盒测试。这里没有测量这个小场景的渲染耗时，不能只按减少比例断言帧率提高。
计数和计时分别回答什么
性能实验另用 128 个半径 0.25 的球。分离布局的中心为 (3k,0,0)，k 从 0 到 127；每个球前方 z=−2 发射一条 +Z 射线，整组重复 128 遍，共 16,384 条。每条最近 t 都应为 1.75。
重叠布局把全部球心改为原点，射线也全部从 (0,0,−2) 出发。图元数量与射线数量不变，所有球完全重合，等距比较仍必须保留较小编号。两种布局都执行三次，不使用随机数或提前终止条件。
| 布局 | 暴力图元测试 | BVH 图元测试 | BVH 节点访问 | BVH 盒测试 |
|---|---|---|---|---|
| 分离 | 2,097,152 | 32,768 | 212,992 | 212,992 |
| 完全重叠 | 2,097,152 | 2,097,152 | 2,080,768 | 2,080,768 |
图元计数就在实际调用求交函数前增加，两种路径都如此。节点访问定义为从栈弹出一个节点，包含随后被盒测试拒绝的节点；当前每次访问恰好测试一个盒，所以这两列相等。不能把这个定义与“进入盒内的节点数”混用。
分离布局平均每条射线测试两个图元，符合每叶两个图元的选择。完全重叠时全部 127 个节点都被访问，每条射线仍测试 128 个球。树深度保持平衡，并不能阻止空间重叠造成的遍历退化。
使用 steady_clock 在当前本机 C++17、clang++ -O2 下得到以下毫秒记录。三次保留原顺序，不只挑最快一次：
| 布局/运行 | 构建 ms | 暴力查询 ms | BVH 查询 ms |
|---|---|---|---|
| 分离 0 | 0.013958 | 7.419166 | 3.074041 |
| 分离 1 | 0.018125 | 6.868625 | 5.289458 |
| 分离 2 | 0.016500 | 7.035708 | 2.924709 |
| 重叠 0 | 0.011917 | 20.196083 | 40.296042 |
| 重叠 1 | 0.013625 | 15.492750 | 33.716583 |
| 重叠 2 | 0.013500 | 14.431958 | 33.582375 |
构建时间包括图元副本、索引和节点分配，不含场景与射线生成。查询计时包括结果数组写入、计数器开销，以及 BVH 每射线的栈分配；比较结果和图像写出在计时之外。两种算法都运行相同射线与求交精度，没有降画质来换速度。
这些是 CPU 查询批次耗时，不是 GPU 执行时间，也不是帧间隔。机器同时有其他工作，记录中的波动真实保留，没有声明严格隔离的基准环境。分离布局这三次较快，重叠布局这三次较慢；图元测试减少 64 倍不等于总时间减少 64 倍。
如果场景不断变化，还需把重新构建或更新盒的成本算进去。静态场景可把构建成本分摊给很多射线，动态场景则要比较重建、refit 与质量下降之间的代价。本篇只构建静态树，没有实现动态更新。
复跑与练习
1 | |
新增代码为 bvh.hpp、bvh_check.cpp，共享场景为 ray_demo.hpp。数值与三次计时在 writing-plans/computer-graphics/evidence/18-cpu.txt；18-images.txt 保存图像检查与第 17 篇结果未变的哈希证据。
边界检查包括平行外部射线、负零边界、盒内负方向、区间截断、零厚盒、空树、单三角形叶、后子树更近，以及跨叶等距编号替换。它们没有把普通 double 运算变成任意输入下的精确几何库。
练习一：沿某轴方向为 0，起点恰等于盒的 low。该轴应拒绝、约束一个有限区间，还是不增加约束？
答案：不增加约束。起点在闭 slab 内且该坐标始终不变。若起点在 low 以下或 high 以上才拒绝；不要通过 0/0 处理这个判断。
练习二：BVH 左右孩子的图元集合不相交，是否能推出两个孩子的包围盒也不相交？这会影响怎样的优化？
答案：不能。几何可以互相穿插，包围盒也可包含大片空白。不能因射线在左孩子找到一个命中就跳过右孩子，必须结合当前最近 t 与右盒区间判断。
练习三：图元测试从 128 次降到 2 次，为什么总耗时可能只下降几倍？
答案：还要计算盒区间、读节点、操作栈、分配内存和记录结果；不同类型的操作成本也不相同。应同时看实际调用计数与总查询时间，并保留构建成本，不用单项计数直接推导帧率。
系列导航与资料
前篇：17：一条光线先碰到什么。系列入口。下一篇：19：表面颜色从哪里来。
PBRT 第四版 §6.1.2 核对 slab 区间；§7.3.1、§7.3.2 与 §7.3.5 核对图元分组、构建与最近交点遍历；§6.8.2 核对保守边界与舍入误差限制。以上于 2026-09-20 实际读取，摘录见 research-17-19.md。
