3.2 BVH 的构建
上一节把节点的布局与 slab 判据立住了，但没说这棵树是怎么长出来的。本节回答四个问题：按哪根轴分、在轴的哪个位置切、一个叶子装几个三角形、排序时那个除法该怎么算。边界仍然划在这里：实时剔除与可见性系统 里的 BVH 是为视锥剔除服务的——它关心「哪一簇物体整块不可见」，允许较慢的构建换更粗的粒度；本节建的是光追 BVH——它服务的是「一条光线尽快找到最近交点」，因此关心的是每条光线访问多少节点、测试多少三角形。同样的树结构，两种优化目标。
按最长轴分
最省事的划分轴选择是「盒子在哪一轴上最长，就沿哪一轴切」。对本场景统计 255 个内部节点的选择结果：轴 0 有 106 个、轴 1 有 36 个、轴 2 有 113 个。轴 1（竖直方向）只占 36 个——地形在 x/z 上铺开、在 y 上起伏有限，最长轴几乎总是水平的。这个分布不是设计者挑的，是几何自己决定的。
最长轴法的好处是便宜：只比较三个长度，一次都不需要算面积。它的代价是切分位置仍然随便——下面来看这一刀切在哪。
中位数划分离 SAH 最优有多远
业界更常见的是 SAH（表面积启发式）：对每个候选切分算 SA_L·N_L + SA_R·N_R，取最小。在一个固定节点内 SA_P（父盒表面积）与遍历代价都是常数，所以最小化 SAH 等价于最小化这个整数——不需要浮点，也不会因舍入而选出不同的切分。
本节的构建器用的是中位数划分（沿最长轴排序后对半分），不是 SAH。这是一个明确的取舍：中位数划分只需要一次排序，而 SAH 要为每个节点评估 3 × (n − 1) 个候选切分。代价是切分质量。脚本对每个内部节点穷举全部候选，把中位数切分的代价除以 SAH 最优代价：
中位数 / SAH 最优代价比：avg=1.318592 min=1.000000 max=2.802529
中位数恰为最优的节点：42 / 255
最差节点 #355: median=4033184724968 opt=1439123309400
平均 1.3186 倍、最差 2.8025 倍，255 个节点里只有 42 个（16.5%）中位数恰好就是 SAH 最优。换句话说，省掉 SAH 的评估工作，付出的代价是「每个节点的切分代价平均高约三成」。对本场景这个量级的树（511 个节点、树高 9）来说，构建时间是毫秒级，而遍历代价由下面的叶子容量决定——所以这里选了中位数。这是一个可替换的决定，不是「SAH 不好」。
叶子容量：为什么是 4
叶子容量 LEAF_SIZE 决定树深与叶内测试数的平衡：容量越小，树越深、访问的节点越多，但每个叶子里的三角形越少。脚本把容量从 1 扫到 32，每一档都重建整棵树，然后用同一批 76800 条主光线做纯求交，量出每条光线平均访问的节点数与测试的三角形数（完整表见本节末尾的实跑输出）。
「合计」是访问数与测试数之和，最小值出现在 LEAF_SIZE = 4（23.5774）。容量 1 的树有 1791 个节点、11 层，访问代价最高；容量 32 的树只有 63 个节点、6 层，但每条光线要测试 30.78 个三角形，合计反而涨到 40.65。
这里要如实说明口径：这个求和隐含了「访问一个节点」与「测试一个三角形」代价相同。实际上一次 Möller–Trumbore 比一次 slab 测试贵得多，所以真实的最优点会偏向更小的容量。4 是这条等权曲线上的最小值，不是「绝对最优」；它是本场景下这个代价模型给出的答案。
排序键必须走 floorDiv
中位数划分要先按质心坐标排序。质心坐标是三个顶点的和再除以 3——而这个除法的舍入语义在两个宿主上是不同的：Python 的 // 向下取整（floor），JavaScript 的 BigInt / 向零截断。两者只在负数上分叉。
本场景里负数一点都不稀有：质心坐标之和为负的三角形，x 轴有 448 个、z 轴有 448 个（y 轴 0 个，地形在 y 上不跨零点）。在这 896 个三角形里，两种除法给出不同排序键的数目是 x 轴 371 个、z 轴 363 个。
于是差异不会停留在键值上，它会改变整棵树。脚本用截断版除法重建一次整棵树：
floor 结构 sha : 30b0164703b26b6ba65d8b28df929ed191f5e7634a00e8067c56a3506e313431
变体 floor 复现 : 30b0164703b26b6ba65d8b28df929ed191f5e7634a00e8067c56a3506e313431（与底座一致 True）
截断 结构 sha : 9b1306aac94b3d01aa789689ff2b4de18424549fc271b50eb5e7b7c8f7c1a943（节点 511）
order 首处分叉 : 177（共 54 个位置不同）
节点数仍是 511（分叉的是排列，不是规模），但结构哈希从 30b01647… 变成 9b1306aa…，order 从下标 177 起共有 54 个位置不同。这正是「跨语言必须用同一个除法」的可证伪形式：同一份场景、同一个算法、同一个除号，只换舍入语义，逐字节判据就分叉。
把上面这些量出来
#!/usr/bin/env python3
# file: lantern/sim/cg_trace_03_2_bvh_build.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_trace_03_2_bvh_build.py
"""3.2 BVH 的构建：最长轴、中位数划分、叶子容量，以及排序键为什么要 floorDiv。
四个问题各给实跑数字：255 个内部节点各自选了哪根轴；中位数切分离 SAH 最优有多远
（穷举全部 n-1 个候选切分算出最优代价，再与中位数切分的代价相除）；`LEAF_SIZE` 从
1 扫到 32，每档重建整棵树并用同一批主光线纯求交；以及把排序键的除法换成向零截断后
重建整棵树，结构哈希如何分叉。
产物：out/cg_trace_03_2_build.json、out/cg_trace_03_2_leafsize.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 bounds_of, primary_rays, structure_text # noqa: E402
OUT = os.path.join(os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "out")
def centroid_key(t, axis, floor=True):
"""三角形质心在 `axis` 上的坐标（未除 3 的和）。`floor=False` 时用向零截断。"""
s = t[axis] + t[3 + axis] + t[6 + axis]
return s // 3 if floor else (abs(s) // 3) * (-1 if s < 0 else 1)
def area(lo, hi):
"""AABB 表面积 `2(dx·dy + dy·dz + dz·dx)`，Q16.16 的平方单位。"""
d = [hi[k] - lo[k] for k in range(3)]
return 2 * (d[0] * d[1] + d[1] * d[2] + d[2] * d[0])
def sah_optimal(idx, tris):
"""穷举三轴上全部 n-1 个切分，返回最优的 `SA_L·N_L + SA_R·N_R`（整数）。
同一节点内 `SA_P` 与遍历代价都是常数，故最小化 SAH 代价等价于最小化这个整数。
这里刻意用最笨的写法：每个候选切分都把左右两堆的包围盒重算一遍。它慢，但把
「SAH 到底在比较什么」摊平到没有优化可藏——3.3 量的是遍历代价，不是构建速度。
"""
n, best = len(idx), None
for axis in range(3):
o = sorted(idx, key=lambda i: centroid_key(tris[i], axis))
for j in range(1, n):
w = (area(*bounds_of(o[:j], tris)) * j
+ area(*bounds_of(o[j:], tris)) * (n - j))
if best is None or w < best:
best = w
return best
def sah_compare(nodes, order, tris):
"""对每个内部节点比较「中位数切分」与「SAH 最优切分」的代价，返回 `(节点, 中位数代价, 最优代价, 比值)`。"""
rows = []
def rec(i):
n = nodes[i]
if n[6] < 0:
return list(order[n[8]:n[8] + n[7]])
li, ri = rec(n[6]), rec(n[9])
w_med = area(*bounds_of(li, tris)) * len(li) + area(*bounds_of(ri, tris)) * len(ri)
w_opt = sah_optimal(li + ri, tris)
rows.append((i, w_med, w_opt, w_med / w_opt))
return li + ri
rec(0)
return rows
def build_bvh_keyed(tris, leaf_size, floor=True):
"""与 `cgtrace.build_bvh` 同结构，但排序键的除法可选 floor 或向零截断。
用来演示「同一个算法、同一个除法符号、只是舍入语义不同」会怎样改变整棵树。
"""
nodes, order = [], []
def build(idx):
lo, hi = bounds_of(idx, tris)
me = len(nodes)
nodes.append([lo[0], lo[1], lo[2], hi[0], hi[1], hi[2], -1, len(idx), len(order)])
if len(idx) <= leaf_size:
order.extend(idx)
return me
ext = [hi[k] - lo[k] for k in range(3)]
axis = max(range(3), key=lambda k: ext[k])
# 单键稳定排序：与底座逐字同式，差异**只**来自 centroid_key 的舍入语义。
idx = sorted(idx, key=lambda i: centroid_key(tris[i], axis, floor))
mid = len(idx) // 2
nodes[me][6], nodes[me][7], nodes[me][8] = build(idx[:mid]), 0, 0
nodes[me].append(build(idx[mid:]))
return me
if tris:
build(list(range(len(tris))))
return nodes, order
def depth_of(nodes, i=0, d=0):
"""以 i 为根的子树的层数。"""
if nodes[i][6] < 0:
return d + 1
return max(depth_of(nodes, nodes[i][6], d + 1), depth_of(nodes, nodes[i][9], d + 1))
def sha(nodes, order):
return hashlib.sha256(structure_text(nodes, order).encode("utf-8")).hexdigest()
def main():
spec = cglib.load_spec()
tris, _dropped = cgtrace.build_scene_tris(spec)
nodes, order = cgtrace.build_bvh(tris)
far = spec["camera"]["farQ16"]
axes = {0: 0, 1: 0, 2: 0}
for n in nodes:
if n[6] < 0:
continue
ext = [n[3 + k] - n[k] for k in range(3)]
axes[max(range(3), key=lambda k: ext[k])] += 1
ratios = sah_compare(nodes, order, tris)
vals = [r[3] for r in ratios]
worst = max(ratios, key=lambda r: r[3])
exact_opt = sum(1 for v in vals if abs(v - 1.0) < 1e-12)
neg = [sum(1 for t in tris if t[k] + t[3 + k] + t[6 + k] < 0) for k in range(3)]
keydiff = [sum(1 for t in tris if centroid_key(t, k) != centroid_key(t, k, False))
for k in range(3)]
tn, to = build_bvh_keyed(tris, 4, floor=False)
kn, ko = build_bvh_keyed(tris, 4, floor=True)
floor_sha, trunc_sha, keyed_sha = sha(nodes, order), sha(tn, to), sha(kn, ko)
diffs = [j for j in range(len(order)) if order[j] != to[j]]
# 叶子容量扫描：每档重建整棵树 + 同一批主光线纯求交
rays = primary_rays(spec)
rows = []
for ls in (1, 2, 4, 8, 16, 32):
nd, od = cgtrace.build_bvh(tris, leaf_size=ls)
st = {"visited": 0, "tested": 0}
for e, d in rays:
cgtrace.bvh_intersect(nd, od, tris, e, d, far, st)
rows.append((ls, len(nd), depth_of(nd), round(st["visited"] / len(rays), 4),
round(st["tested"] / len(rays), 4), st["visited"], st["tested"]))
os.makedirs(OUT, exist_ok=True)
cglib.write_csv(os.path.join(OUT, "cg_trace_03_2_leafsize.csv"),
["leaf_size", "nodes", "levels", "visited_per_ray", "tested_per_ray",
"visited_total", "tested_total"], rows)
out = {
"triangles": len(tris), "nodes": len(nodes),
"longestAxisHist": {str(k): v for k, v in axes.items()},
"sahNodes": len(ratios), "sahRatioAvg": round(sum(vals) / len(vals), 6),
"sahRatioMin": round(min(vals), 6), "sahRatioMax": round(max(vals), 6),
"sahMedianIsOptimal": exact_opt,
"sahWorstNode": {"node": worst[0], "medianW": worst[1], "optW": worst[2]},
"negativeCentroidTris": neg, "keyDiffTris": keydiff,
"floorSha256": floor_sha, "keyedFloorSha256": keyed_sha, "truncSha256": trunc_sha,
"truncNodes": len(tn), "orderFirstDiff": diffs[0], "orderDiffCount": len(diffs),
"leafSweep": [{"leafSize": a, "nodes": b, "levels": c, "visitedPerRay": d,
"testedPerRay": e, "visitedTotal": f, "testedTotal": g}
for a, b, c, d, e, f, g in rows],
"sweepRays": len(rays),
}
with open(os.path.join(OUT, "cg_trace_03_2_build.json"), "w", encoding="utf-8") as fh:
json.dump(out, fh, ensure_ascii=False, indent=2)
fh.write("\n")
print("== 3.2 BVH 的构建 ==")
print(f"三角形 / 节点 : {len(tris)} / {len(nodes)}")
print(f"最长轴直方图 : {axes}（内部节点 {sum(axes.values())} 个）")
print(f"中位数 / SAH 最优代价比：avg={out['sahRatioAvg']:.6f} "
f"min={out['sahRatioMin']:.6f} max={out['sahRatioMax']:.6f}")
print(f" 中位数恰为最优的节点：{exact_opt} / {len(ratios)}")
print(f" 最差节点 #{worst[0]}: median={worst[1]} opt={worst[2]}")
print(f"负质心三角形数 : x={neg[0]} y={neg[1]} z={neg[2]}")
print(f"排序键分叉的三角形：x={keydiff[0]} y={keydiff[1]} z={keydiff[2]}")
print(f"floor 结构 sha : {floor_sha}")
print(f"变体 floor 复现 : {keyed_sha}（与底座一致 {keyed_sha == floor_sha}）")
print(f"截断 结构 sha : {trunc_sha}（节点 {len(tn)}）")
print(f"order 首处分叉 : {diffs[0]}（共 {len(diffs)} 个位置不同）")
print(f"叶子容量扫描（{len(rays)} 条主光线，纯求交）：")
for a, b, c, d, e, _f, _g in rows:
print(f" LEAF_SIZE={a:2d} 节点={b:4d} 层={c:2d}"
f" 访问/光线={d:8.4f} 测试/光线={e:8.4f} 合计={d + e:8.4f}")
return 0
if __name__ == "__main__":
sys.exit(main())
跑一遍（工作区 lantern/）：
# snippet: 本机实跑（工作区 lantern/）
cd lantern
/opt/homebrew/bin/python3 sim/cg_trace_03_2_bvh_build.py
== 3.2 BVH 的构建 ==
三角形 / 节点 : 896 / 511
最长轴直方图 : {0: 106, 1: 36, 2: 113}（内部节点 255 个）
中位数 / SAH 最优代价比：avg=1.318592 min=1.000000 max=2.802529
中位数恰为最优的节点：42 / 255
最差节点 #355: median=4033184724968 opt=1439123309400
负质心三角形数 : x=448 y=0 z=448
排序键分叉的三角形：x=371 y=0 z=363
floor 结构 sha : 30b0164703b26b6ba65d8b28df929ed191f5e7634a00e8067c56a3506e313431
变体 floor 复现 : 30b0164703b26b6ba65d8b28df929ed191f5e7634a00e8067c56a3506e313431（与底座一致 True）
截断 结构 sha : 9b1306aac94b3d01aa789689ff2b4de18424549fc271b50eb5e7b7c8f7c1a943（节点 511）
order 首处分叉 : 177（共 54 个位置不同）
叶子容量扫描（76800 条主光线，纯求交）：
LEAF_SIZE= 1 节点=1791 层=11 访问/光线= 23.7100 测试/光线= 1.6633 合计= 25.3733
LEAF_SIZE= 2 节点=1023 层=10 访问/光线= 20.9390 测试/光线= 3.0563 合计= 23.9953
LEAF_SIZE= 4 节点= 511 层= 9 访问/光线= 17.5483 测试/光线= 6.0291 合计= 23.5774
LEAF_SIZE= 8 节点= 255 层= 8 访问/光线= 14.5324 测试/光线= 10.5557 合计= 25.0881
LEAF_SIZE=16 节点= 127 层= 7 访问/光线= 12.0637 测试/光线= 17.2809 合计= 29.3446
LEAF_SIZE=32 节点= 63 层= 6 访问/光线= 9.8651 测试/光线= 30.7803 合计= 40.6454
P 层把「结构分叉」钉死
P 层用 TypeScript 重写同一个构建器，排序键的除法可切换 floor / trunc，断言对象是整棵树的 sha256 与每档叶子容量下的精确整数计数（不是四舍五入后的每光线均值）：
// snippet: core/test/cg_trace_03_2_bvh_build.test.ts（节选：排序键与精确整数）
// verify: node --test 'core/test/cg_trace_03_2_bvh_build.test.ts'
const trunc = buildBvhDiv(tris, 4, "trunc");
assert.equal(sha256(structureText(trunc)), golden.truncSha256);
assert.notEqual(golden.truncSha256, golden.floorSha256, "截断版必须让结构哈希分叉");
assert.equal(trunc.nodes.length, bvh.nodes.length, "分叉的是排列，不是节点数");
// 负数上两种除法必然不同：-1 的 floor 是 -1，截断是 0
assert.equal(floorDiv(-1n, 3n), -1n);
assert.equal(-1n / 3n, 0n);
两组断言的分工是：floor 版必须复现底座（正例），截断版必须分叉（负例）。只测正例不够——一个用截断除法的实现如果只对「节点数是不是 511」这种弱判据，会顺利通过。
小结
- 划分轴按最长轴选：255 个内部节点里轴 0 占 106、轴 1 占 36、轴 2 占 113——地形铺在 x/z 上。
- 中位数划分平均花掉 SAH 最优代价的 1.3186 倍（最差 2.8025 倍），255 个节点里 42 个恰好最优。这是一个可替换的取舍。
LEAF_SIZE = 4让「访问 + 测试」的等权合计取到最小值 23.5774；该口径假设两种操作同价，真实最优会偏小。- 排序键的除法必须走 floorDiv：448 个三角形的质心为负，截断版让结构哈希从
30b01647…分叉到9b1306aa…，order54 个位置不同。
下一节不再看树怎么建，只看树怎么走：把 BVH 打开和关掉，用整数计数把遍历代价摆出来。
阅读导航：上一节：3.1 包围盒与 BVH · 下一节：3.3 BVH 的遍历与代价 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。