3.1 包围盒与 BVH
上一章把「一条光线与一个三角形怎么求交」钉死了：896 个三角形，每次求交都是一次 Möller–Trumbore。加速结构要解决的就是「每条光线都去问一遍全部 896 个三角形」这件事——那会让一张 320×240 的图做 76800 × 896 = 68812800 次求交，这个数字在本章第三节会被完整地量出来。边界先划清楚：实时剔除与可见性系统 讲的是实时管线里的 BVH——视锥剔除、Hi-Z、遮挡查询，目标是在一帧内决定「哪些东西根本不用画」；本章讲的是离线光追里的 BVH——一棵为「一条光线尽快找到最近交点」而建的树，关心的是构建方式与遍历代价。两者都叫 BVH，优化目标却不同：前者按视锥与屏幕空间剪，后者按光线与包围盒剪。
本节只立三件事：把节点布局钉成一段整数数组、写出 BVH 必须满足的两条不变量、把 slab 判据逐轴展开。后两节全部建在这三件东西上。
节点是一个整数数组，不是对象树
BVH 最常见的实现形态是一堆带指针的对象，但在本卷的底座里它是一段扁平的整数数组。叶子节点 9 个整数：
[lo0, lo1, lo2, hi0, hi1, hi2, left, count, start]
下界 3 个、上界 3 个、左子索引 1 个、三角形数 1 个、起始下标 1 个。内部节点多一个整数——右子索引放在下标 9：
[lo0, lo1, lo2, hi0, hi1, hi2, left, count, start, right]
叶子用 left == -1 标记。这个哨兵值是整棵树唯一的「类型标签」：遍历时只看 left 的符号就知道该继续压栈还是该扫三角形，不需要额外的标志位，也不需要虚函数表。这 511 个节点装在一段连续整数里，于是「整棵树」可以一次性序列化成字符串、算一个 sha256——本节的判据就建立在这个哈希上。
两条不变量
BVH 的正确性只有两条内容：父盒包含两个子盒（否则 slab 判据会在父节点就剪掉本该命中的子树），叶盒包含它引用的每一个三角形（否则叶内的三角形会被误判为不可能命中）。两条都不是「大概成立」的期望，而是必须逐节点验证的不变量。
树形本身也完全规整：中位数切分保证左右子树大小最多差 1，叶子容量又是常数 4，于是树必然长成一棵满二叉树。下面脚本会把节点数、深度直方图、两条不变量的违反次数、order 是否排列、根盒是否等于全局盒全部算出来。
slab 判据：逐轴展开
一个轴对齐包围盒与一条光线的求交，可以逐轴做成一维的「板」（slab）问题。对第 k 轴，光线进入与离开这块板的参数是 t1 = (lo_k − o_k) / d_k、t2 = (hi_k − o_k) / d_k。两个值可能反序（取决于方向分量的符号），所以先交换成 t1 ≤ t2，再取所有轴上 t1 的最大值作为进入时刻、所有轴上 t2 的最小值作为离开时刻；进入晚于离开就没穿过这个盒子。
方向分量恰好为 0 时除法没有意义，判据退化成「原点是否落在这一轴的板内」的半区间测试——这不是特例分支，而是同一个判据在 1/0 = ±inf 下的极限：t1 = −inf、t2 = +inf，该轴对区间不产生约束，唯一的条件是原点必须在板内。
脚本还会放一个负例：把逐轴区间里的 if a > b: swap 那一行去掉，其余不变。正面断言全部通过不能证明判据是对的——一个恒返回 True 的实现也能全过；只有一个明显错误的变体在同一批光线上大面积分叉，才说明判据在起作用。
#!/usr/bin/env python3
# file: lantern/sim/cg_trace_03_1_aabb_bvh.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_trace_03_1_aabb_bvh.py
"""3.1 包围盒与 BVH：节点布局、两条不变量、slab 判据的逐轴展开。
本节立起三件东西，后两节都建在它们上面：
1. **节点布局**：BVH 是一段扁平的整数数组，不是对象树。每个节点 9 个整数
（下界 3 + 上界 3 + 左子 1 + 三角形数 1 + 起始下标 1），内部节点再多一个右子索引
变成 10 个。叶子用 `left == -1` 标记——这个哨兵值是整棵树唯一的「类型标签」。
2. **包围盒不变量**：父盒必须**包含**两个子盒，叶盒必须包含它引用的每一个三角形。
这两条是 BVH 正确性的全部内容；不成立则 slab 判据会误杀。
3. **slab 判据**：逐轴算 `t1 = (lo-o)/d`、`t2 = (hi-o)/d`，取 `max(t_enter)` /
`min(t_exit)`。方向分量为 0 时除法无意义，退化成「原点是否落在这一轴的板内」
的半区间测试——这不是特例分支，是同一个判据在 `1/0 = ±inf` 下的极限。
产物：out/cg_trace_03_1_bvh.json、out/cg_trace_03_1_depth.csv
"""
import hashlib
import json
import os
import sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
import cgtrace # noqa: E402
from cg_trace_03_common import ONE, bounds_of, camera_ray, contains, structure_text # noqa: E402
OUT = os.path.join(os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "out")
def depth_histogram(nodes):
"""每个深度的 `[节点数, 叶子数, 内部节点数]`（深度以根为 0 计）。"""
hist = {}
def walk(i, d):
slot = hist.setdefault(d, [0, 0, 0])
slot[0] += 1
if nodes[i][6] >= 0:
slot[2] += 1
walk(nodes[i][6], d + 1)
walk(nodes[i][9], d + 1)
else:
slot[1] += 1
if nodes:
walk(0, 0)
return hist
def check_invariants(nodes, order, tris):
"""两条不变量：父包含子、叶包含其引用的三角形。返回各自的违反次数。"""
bad_parent = bad_leaf = 0
for n in nodes:
if n[6] >= 0:
for c in (n[6], n[9]):
if not contains((n[0:3], n[3:6]), (nodes[c][0:3], nodes[c][3:6])):
bad_parent += 1
else:
for j in range(n[8], n[8] + n[7]):
t = tris[order[j]]
tri = ([min(t[k], t[3 + k], t[6 + k]) for k in range(3)],
[max(t[k], t[3 + k], t[6 + k]) for k in range(3)])
if not contains((n[0:3], n[3:6]), tri):
bad_leaf += 1
return bad_parent, bad_leaf
def slab_intervals(lo, hi, orig, dirv, tmax):
"""把 slab 判据逐轴展开：返回 `(rows, t_enter, t_exit, 命中)`。
方向分量为 0 时不做除法，直接判「原点是否落在该轴的板内」——数学上就是
`t1 = -inf`、`t2 = +inf` 的极限，该轴对区间不产生约束。
"""
t0, t1 = 0, tmax
rows = []
for k in range(3):
d = dirv[k]
if d == 0:
inside = lo[k] <= orig[k] <= hi[k]
rows.append((k, d, None, None, t0, t1, inside))
if not inside:
return rows, t0, t1, False
continue
inv = cglib.fdiv(ONE, d)
a = cglib.fmul(lo[k] - orig[k], inv)
b = cglib.fmul(hi[k] - orig[k], inv)
if a > b:
a, b = b, a
if a > t0:
t0 = a
if b < t1:
t1 = b
rows.append((k, d, a, b, t0, t1, t0 <= t1))
if t0 > t1:
return rows, t0, t1, False
return rows, t0, t1, True
def slab_hit_unsorted(lo, hi, orig, dirv, tmax):
"""负例：**不排序**逐轴区间的 slab 判据（少了 `if a > b` 交换）。
原点落在板内时 `t1` 可能大于 `t2`，不交换就等价于用一个反向区间求交，结果必然
与正确判据分叉。这是「判据通过不说明问题、必须配负例」的现场演示。
"""
t0, t1 = 0, tmax
for k in range(3):
d = dirv[k]
if d == 0:
if orig[k] < lo[k] or orig[k] > hi[k]:
return False
continue
inv = cglib.fdiv(ONE, d)
a = cglib.fmul(lo[k] - orig[k], inv)
b = cglib.fmul(hi[k] - orig[k], inv)
t0 = max(t0, a)
t1 = min(t1, b)
if t0 > t1:
return False
return True
def main():
spec = cglib.load_spec()
tris, _dropped = cgtrace.build_scene_tris(spec)
nodes, order = cgtrace.build_bvh(tris)
far = spec["camera"]["farQ16"]
leaves = [n for n in nodes if n[6] < 0]
leaf_sizes = {}
for n in leaves:
leaf_sizes[n[7]] = leaf_sizes.get(n[7], 0) + 1
hist = depth_histogram(nodes)
height_edges, levels = max(hist), max(hist) + 1
bad_parent, bad_leaf = check_invariants(nodes, order, tris)
perm_ok = sorted(order) == list(range(len(tris)))
glo, ghi = bounds_of(range(len(tris)), tris)
root_is_global = nodes[0][0:3] == glo and nodes[0][3:6] == ghi
# 一条真的打到地形的主光线，用来看 slab 区间怎么逐轴收缩
eye, dirv = camera_ray(spec, 160, 200)
hit = cgtrace.bvh_intersect(nodes, order, tris, eye, dirv, far)
rows, te, tx, ok = slab_intervals(nodes[0][0:3], nodes[0][3:6], eye, dirv, far)
# 轴平行光线 d = (0, 1, 0)：两根分别落在 x 板内 / 板外
axis_dir = (0, ONE, 0)
axis_in = slab_intervals(nodes[0][0:3], nodes[0][3:6], (0, 0, 0), axis_dir, far)
axis_out = slab_intervals(nodes[0][0:3], nodes[0][3:6], (ghi[0] + ONE, 0, 0), axis_dir, far)
# 负例：正确判据 vs 不排序判据，在 320x240 的全部主光线上逐条比对根盒结果
rlo, rhi = nodes[0][0:3], nodes[0][3:6]
disagree = 0
for py in range(spec["height"]):
for px in range(spec["width"]):
e, dv = camera_ray(spec, px, py)
if cgtrace._slab_hit(rlo, rhi, e, dv, far) != slab_hit_unsorted(rlo, rhi, e, dv, far):
disagree += 1
os.makedirs(OUT, exist_ok=True)
cglib.write_csv(os.path.join(OUT, "cg_trace_03_1_depth.csv"),
["depth", "nodes", "leaves", "internal"],
[(d, hist[d][0], hist[d][1], hist[d][2]) for d in sorted(hist)])
out = {
"triangles": len(tris), "nodes": len(nodes), "leaves": len(leaves),
"internal": len(nodes) - len(leaves), "nodeWidths": sorted({len(n) for n in nodes}),
"leafSizeHist": {str(k): v for k, v in sorted(leaf_sizes.items())},
"heightEdges": height_edges, "levels": levels,
"depthHist": {str(k): v[0] for k, v in sorted(hist.items())},
"invariantBadParent": bad_parent, "invariantBadLeaf": bad_leaf,
"orderIsPermutation": perm_ok, "rootIsGlobalBox": root_is_global,
"rootLo": nodes[0][0:3], "rootHi": nodes[0][3:6],
"rootChildren": [nodes[0][6], nodes[0][9]],
"structureSha256": hashlib.sha256(structure_text(nodes, order).encode()).hexdigest(),
"demoRayPixel": [160, 200], "demoRayDir": list(dirv),
"demoRayHitT": None if hit is None else hit[0],
"demoRayHitTri": None if hit is None else hit[1],
"demoRootEnter": te, "demoRootExit": tx, "demoRootSlabHit": ok,
"axisDirZeroInside": axis_in[3], "axisDirZeroOutside": axis_out[3],
"unsortedDisagree": disagree, "unsortedChecked": spec["width"] * spec["height"],
}
with open(os.path.join(OUT, "cg_trace_03_1_bvh.json"), "w", encoding="utf-8") as fh:
json.dump(out, fh, ensure_ascii=False, indent=2)
fh.write("\n")
q = lambda x: f"{x / ONE:+.4f}" # noqa: E731 Q16.16 -> 打印用小数，不参与判据
print("== 3.1 包围盒与 BVH ==")
print(f"三角形 / 节点 : {len(tris)} / {len(nodes)}")
print(f"叶子 / 内部 : {len(leaves)} / {len(nodes) - len(leaves)}")
print(f"节点整数个数 : {out['nodeWidths']}（叶子 {len(leaves[0])}，内部 {len(nodes[0])}）")
print(f"叶子容量分布 : {dict(sorted(leaf_sizes.items()))}")
print(f"树高 : {levels} 层（边数 {height_edges}）")
print(f"深度直方图 : {out['depthHist']}")
print(f"不变量 父包含子 : 违反 {bad_parent} ; 不变量 叶含三角 : 违反 {bad_leaf}")
print(f"order 是排列 : {perm_ok} ; 根盒 == 全局盒 : {root_is_global}")
print(f"根节点整数 : {nodes[0]}")
print(f"根的两子 : {nodes[0][6]}, {nodes[0][9]}")
print(f"首叶节点整数 : {leaves[0]}")
print(f"演示光线 像素 : (160, 200) 方向={tuple(round(v / ONE, 6) for v in dirv)}")
print(f" 命中 t={out['demoRayHitT']} tri={out['demoRayHitTri']}")
for k, d, a, b, t0, t1, okk in rows:
if d == 0:
print(f" 轴{k} d=0 : 半区间测试 板内={okk} t=[{q(t0)}, {q(t1)}]")
else:
print(f" 轴{k} t1={q(a)} t2={q(b)} -> t=[{q(t0)}, {q(t1)}] ok={okk}")
print(f"根盒 slab 命中 : {ok} t=[{q(te)}, {q(tx)}]")
print(f"轴平行(0,1,0)板内: {axis_in[3]} 板外(x 超上界): {axis_out[3]}")
print(f"结构 sha256 : {out['structureSha256']}")
print(f"负例 不排序判据 : {disagree} / {out['unsortedChecked']} 条光线与正确判据分歧")
return 0
if __name__ == "__main__":
sys.exit(main())
跑一遍（工作区 lantern/）：
# snippet: 本机实跑（工作区 lantern/）
cd lantern
/opt/homebrew/bin/python3 sim/cg_trace_03_1_aabb_bvh.py
== 3.1 包围盒与 BVH ==
三角形 / 节点 : 896 / 511
叶子 / 内部 : 256 / 255
节点整数个数 : [9, 10]（叶子 9，内部 10）
叶子容量分布 : {3: 128, 4: 128}
树高 : 9 层（边数 8）
深度直方图 : {'0': 1, '1': 2, '2': 4, '3': 8, '4': 16, '5': 32, '6': 64, '7': 128, '8': 256}
不变量 父包含子 : 违反 0 ; 不变量 叶含三角 : 违反 0
order 是排列 : True ; 根盒 == 全局盒 : True
根节点整数 : [-1441792, 8856, -1441792, 1441792, 425984, 1441792, 1, 0, 0, 256]
根的两子 : 1, 256
首叶节点整数 : [-1441792, 66510, -1441792, -1081344, 112944, -1261568, -1, 3, 0]
演示光线 像素 : (160, 200) 方向=(0.002228, -0.509552, -0.860443)
命中 t=563803 tri=464
轴0 t1=-9875.2876 t2=+9875.2876 -> t=[+0.0000, +64.0000] ok=True
轴1 t1=-0.9812 t2=+11.5098 -> t=[+0.0000, +11.5098] ok=True
轴2 t1=+2.3244 t2=+53.4605 -> t=[+2.3244, +11.5098] ok=True
根盒 slab 命中 : True t=[+2.3244, +11.5098]
轴平行(0,1,0)板内: True 板外(x 超上界): False
结构 sha256 : 30b0164703b26b6ba65d8b28df929ed191f5e7634a00e8067c56a3506e313431
负例 不排序判据 : 67200 / 76800 条光线与正确判据分歧
这组数字各是什么
- 896 / 511：896 个三角形建成 511 个节点；256 个叶子 + 255 个内部，正是一棵满二叉树该有的数目。
- 节点整数个数 [9, 10]：叶子 9、内部 10。根节点第 6 项是 1、第 9 项是 256，右子索引确实在下标 9；首叶第 6 项是 −1、
count = 3、start = 0。 - 叶子容量分布 {3: 128, 4: 128}：128 个叶装满 4 个三角形，另外 128 个剩 3 个——奇数分裂留下的痕迹。
- 深度直方图逐层翻倍（1, 2, 4, …, 256），树高 9 层 / 8 条边。
- 两条不变量违反 0 次；
order是0..895的排列；根盒等于全局盒。 - 演示光线的逐轴收缩：轴 0 的区间宽到罩住整个
[0, far]，t_enter仍是 0；真正把进入时刻推到 2.3244 的是轴 2；最终区间[2.3244, 11.5098]与命中t = 563803（约 8.60）一致。 - 轴平行光线：
d = (0, 1, 0)时板内为True、x 超上界为False，退化分支两侧都对。 - 结构 sha256
30b01647…：把 511 个节点连同order排列序列化后的哈希，下一节的「排序键换舍入语义」就靠它判分叉。 - 负例 67200 / 76800：去掉区间排序后，87.5% 的主光线上判据结论改变——判据不是恒真的。
小结
- BVH 在本卷底座里是一段扁平整数数组：叶子 9 个整数、内部节点 10 个，
left == −1是唯一的类型标签。 - 896 个三角形建成 511 个节点（叶子 256、内部 255），树高 9 层，深度直方图逐层翻倍。
- 两条不变量——父包含子、叶含三角——实跑违反 0 次。
- slab 判据逐轴算
t1 = (lo − o) / d、t2 = (hi − o) / d，取max(t_enter)/min(t_exit)；d = 0退化成半区间测试。
下一节把「这棵树是怎么长出来的」拆开：最长轴怎么选、中位数划分离 SAH 最优有多远、叶子容量为什么是 4。
阅读导航：上一节：2.3 容差与自交 · 下一节：3.2 BVH 的构建 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。