3.3 BVH 的遍历与代价
前两节把树建好了：511 个节点、树高 9、叶子容量 4。但「建了一棵加速结构」本身不是结论——结论应该是「这棵树在遍历时到底省掉了什么，省得够不够多」。本节用整数计数来回答，不用秒表。边界再划一次：实时剔除与可见性系统 里量的是实时管线的可见性代价（视锥剔除率、Hi-Z 通过率、每帧的绘制调用数）；本节量的是离线光追的遍历代价——每条光线访问多少节点、测试多少三角形。前者是「一帧内省下多少东西不用画」，后者是「一条光线省下多少次求交」。
同一条代码路径，只换遍历
三个模式跑的是完全相同的 render_trace 与完全相同的着色器，唯一的差别是模块级 bvh_intersect 被换成三个实现之一：
bvh：底座实现，slab 判据用已收缩的best_t做上界；noshrink：其余一字不改，slab 判据改用原始的tmax（即不收缩best_t）；linear：完全没有 BVH，逐条光线线性扫描全部 896 个三角形。
计数分两笔，对应遍历里两件成本不同的事：visited 是从栈里弹出并做过 slab 测试的节点数，tested 是真正跑过 Möller–Trumbore 的三角形数。两者再按光线种类拆开——主光线的起点恒等于相机位置 eye，阴影光线的起点是命中点加法线偏移，用 orig == eye 一个判据就能分开，不必改动底座签名。
收缩 best_t 到底省了什么
遍历时维护一个当前最近命中距离 best_t，初始为 far；每次命中就把它收缩到新的 t。收缩后的值会作为 slab 判据的上界传下去（tmax = min(tmax, t_hit)）——盒子的进入时刻晚于当前已知的最近命中，这棵子树就不可能贡献更近的交点，整棵剪掉。把它关掉，节点访问数与三角形测试数都应当变大，而命中结果一个字都不该变——这正是下面负例要验的。
三个模式的整数计数
#!/usr/bin/env python3
# file: lantern/sim/cg_trace_03_3_bvh_traversal_cost.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_trace_03_3_bvh_traversal_cost.py
"""3.3 BVH 的遍历与代价：同一份场景、同一条代码路径，只换遍历方式。
三个模式跑的是**完全相同的** `cgtrace.render_trace` 与着色器（`render_trace.make_shader`），
唯一的差别是模块级 `cgtrace.bvh_intersect` 被换成三个实现之一：`bvh`（底座，slab 判据用
**已收缩的** `best_t` 做上界）、`noshrink`（其余不变，slab 判据改用**原始的** `tmax`）、
`linear`（完全没有 BVH，逐条光线线性扫描全部 896 个三角形）。
计数分两笔：`visited` 是从栈里弹出并做过 slab 测试的节点数，`tested` 是真正跑过
Möller–Trumbore 的三角形数；再按光线种类拆开——主光线起点恒等于相机位置 `eye`，阴影
光线起点是命中点加法线偏移，用 `orig == eye` 一个判据即可分开，无需改动底座签名。
产物：out/cg_trace_03_3_cost.json、out/cg_trace_03_3_cost.csv
"""
import json
import os
import sys
import time
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
import cgtrace # noqa: E402
import render_trace as rt # noqa: E402
OUT = os.path.join(os.path.dirname(os.path.dirname(os.path.abspath(__file__))), "out")
BASELINE_SHA = "213b413069ca66c9f0cc091bce5328eac0f540d075afa3bab37788aea335ba71"
MODE, EYE = "bvh", None
BUCKETS = {}
def tri_at(tris, ti):
t = tris[ti]
return (t[0], t[1], t[2]), (t[3], t[4], t[5]), (t[6], t[7], t[8])
def linear_intersect(nodes, order, tris, orig, dirv, tmax, stats=None):
"""无加速结构：线性扫描全部三角形，取最小正 `t`。
它**没有**提前退出的余地——必须看完全部 896 个三角形才知道谁最近，所以
「每次遍历 896 次测试」是结构决定的下界，不是实现的偷懒。
"""
best_t, best = tmax, None
for ti in range(len(tris)):
if stats is not None:
stats["tested"] += 1
r = cgtrace.intersect_triangle(orig, dirv, *tri_at(tris, ti))
if r is not None and r[0] < best_t:
best_t, best = r[0], (r[0], ti, r[1], r[2])
return best
def noshrink_intersect(nodes, order, tris, orig, dirv, tmax, stats=None):
"""与底座同结构，**唯一**差别：slab 判据用原始 `tmax` 而不是收缩后的 `best_t`。
叶内的接受判据仍用 `best_t`，所以「选哪个三角形」的规则没变，变的是**有多少
节点通过了 slab 测试**——这正是「收缩」在计数上留下的痕迹。
"""
best_t, best = tmax, None
stack = [0] if nodes else []
while stack:
node = nodes[stack.pop()]
if stats is not None:
stats["visited"] += 1
if not cgtrace._slab_hit(node[0:3], node[3:6], orig, dirv, tmax):
continue
if node[6] < 0:
for j in range(node[8], node[8] + node[7]):
ti = order[j]
if stats is not None:
stats["tested"] += 1
r = cgtrace.intersect_triangle(orig, dirv, *tri_at(tris, ti))
if r is not None and r[0] < best_t:
best_t, best = r[0], (r[0], ti, r[1], r[2])
else:
stack.append(node[6])
stack.append(node[9])
return best
IMPL = {"bvh": cgtrace.bvh_intersect, "noshrink": noshrink_intersect,
"linear": linear_intersect}
def dispatch(nodes, order, tris, orig, dirv, tmax, stats=None):
"""三模式共用的入口：一次遍历的计数同时记进调用方的 stats 与按种类分的桶。
分桶判据只有一个：主光线的起点恒等于相机位置 `eye`，阴影光线的起点是命中点
加法线偏移，两者永不相等。这样就不必改动 `cgtrace.trace` 的签名。
"""
local = {"visited": 0, "tested": 0}
res = IMPL[MODE](nodes, order, tris, orig, dirv, tmax, local)
if stats is not None:
stats["visited"] += local["visited"]
stats["tested"] += local["tested"]
b = BUCKETS["primary" if orig == EYE else "shadow"]
b["calls"] += 1
b["visited"] += local["visited"]
b["tested"] += local["tested"]
return res
def run(mode, spec, eye):
"""跑一次完整渲染（主光线 + 阴影光线 + 着色），返回像素缓冲与计数。"""
global MODE, EYE, BUCKETS
MODE, EYE = mode, eye
BUCKETS = {k: {"calls": 0, "visited": 0, "tested": 0} for k in ("primary", "shadow")}
cgtrace.bvh_intersect = dispatch
t0 = time.time()
color, stats = cgtrace.render_trace(spec, spec["width"], spec["height"], rt.MAX_DEPTH,
rt.make_shader,
{"stats": {"shadow_rays": 0, "shadow_hits": 0}})
ms = int((time.time() - t0) * 1000)
cgtrace.bvh_intersect = IMPL["bvh"]
return color, stats, dict(BUCKETS), ms
def pixel_diff(a, b, rays):
"""两张颜色缓冲的逐像素分歧数（缓冲是 (h, w, 3) 的 numpy 数组）。"""
fa = a.reshape(-1, 3) if hasattr(a, "reshape") else a
fb = b.reshape(-1, 3) if hasattr(b, "reshape") else b
return sum(1 for i in range(rays) if tuple(fa[i]) != tuple(fb[i]))
def main():
only = [a for a in sys.argv[1:] if not a.startswith("-")] or ["bvh", "noshrink", "linear"]
spec = cglib.load_spec()
eye, far = tuple(spec["camera"]["eyeQ16"]), spec["camera"]["farQ16"]
rays = spec["width"] * spec["height"]
tris, _dropped = cgtrace.build_scene_tris(spec)
ntris = len(tris)
results, colors = {}, {}
for mode in only:
print(f"... 跑 {mode}", flush=True)
color, stats, buckets, ms = run(mode, spec, eye)
colors[mode] = color
calls = buckets["primary"]["calls"] + buckets["shadow"]["calls"]
results[mode] = {
"sha256": cgtrace.digest(color),
"visited": stats["visited"], "tested": stats["tested"], "traversals": calls,
"visitedPerPrimaryRay": round(stats["visited"] / rays, 4),
"testedPerPrimaryRay": round(stats["tested"] / rays, 4),
"visitedPerTraversal": round(stats["visited"] / calls, 4),
"testedPerTraversal": round(stats["tested"] / calls, 4),
"primary": buckets["primary"], "shadow": buckets["shadow"], "ms": ms,
}
r = results[mode]
r["matchesBaseline"] = r["sha256"] == BASELINE_SHA
print(f" sha={r['sha256'][:16]}… visited={r['visited']} tested={r['tested']}"
f" traversals={calls} ms={ms}", flush=True)
pix = {}
for a, b in (("bvh", "noshrink"), ("noshrink", "linear")):
if a in colors and b in colors:
pix[f"{a}Vs{b}"] = pixel_diff(colors[a], colors[b], rays)
base = results.get("bvh")
ratio = None
if base and "linear" in results:
ratio = {
"perTraversal": round(results["linear"]["testedPerTraversal"]
/ base["testedPerTraversal"], 4),
"perPrimaryRay": round(ntris / base["testedPerPrimaryRay"], 4),
}
out = {
"triangles": ntris, "primaryRays": rays, "modes": results,
"baselineSha256": BASELINE_SHA, "pixelDiff": pix,
"linearTotalTested": ntris * base["traversals"] if base else None,
"ratioLinearOverBvh": ratio,
}
os.makedirs(OUT, exist_ok=True)
with open(os.path.join(OUT, "cg_trace_03_3_cost.json"), "w", encoding="utf-8") as fh:
json.dump(out, fh, ensure_ascii=False, indent=2)
fh.write("\n")
rows = [(m, r["visited"], r["tested"], r["traversals"], r["visitedPerPrimaryRay"],
r["testedPerPrimaryRay"], r["primary"]["visited"], r["primary"]["tested"],
r["shadow"]["visited"], r["shadow"]["tested"], r["ms"], r["sha256"][:16])
for m, r in ((m, results[m]) for m in ("bvh", "noshrink", "linear") if m in results)]
cglib.write_csv(os.path.join(OUT, "cg_trace_03_3_cost.csv"),
["mode", "visited", "tested", "traversals",
"visited_per_primary", "tested_per_primary",
"primary_visited", "primary_tested", "shadow_visited", "shadow_tested",
"ms", "sha16"], rows)
print("== 3.3 BVH 的遍历与代价 ==")
print(f"三角形 / 主光线 : {ntris} / {rays}")
for m in ("bvh", "noshrink", "linear"):
if m not in results:
continue
r = results[m]
print(f"[{m:8s}] sha256={r['sha256'][:16]}… 基线={r['matchesBaseline']}")
print(f" 遍历次数={r['traversals']:7d} 访问节点={r['visited']:9d}"
f" 测试三角形={r['tested']:10d} 耗时={r['ms']:7d} ms")
print(f" 每主光线 访问={r['visitedPerPrimaryRay']:9.4f}"
f" 测试={r['testedPerPrimaryRay']:9.4f}"
f" | 每次遍历 访问={r['visitedPerTraversal']:7.4f}"
f" 测试={r['testedPerTraversal']:7.4f}")
print(f" 主光线 访问={r['primary']['visited']:9d}"
f" 测试={r['primary']['tested']:9d}"
f" | 阴影 访问={r['shadow']['visited']:9d}"
f" 测试={r['shadow']['tested']:9d}")
if base and "noshrink" in results:
nb = results["noshrink"]
dv, dt = nb["visited"] - base["visited"], nb["tested"] - base["tested"]
print(f"收缩 vs 不收缩：访问 {dv:+d}（{dv / nb['visited'] * 100:+.2f}% 相对不收缩）"
f" 测试 {dt:+d}（{dt / nb['tested'] * 100:+.2f}%）")
if "noshrinkVslinear" in pix:
print(f"noshrink 与 linear 图像逐像素分歧 : {pix['noshrinkVslinear']} / {rays}"
f"（sha 相同 {results['noshrink']['sha256'] == results['linear']['sha256']}）")
if "bvhVsnoshrink" in pix:
print(f"bvh 与 noshrink 图像逐像素分歧 : {pix['bvhVsnoshrink']} / {rays}")
if base:
print(f"无 BVH 全量测试数 : {ntris} × {base['traversals']}"
f" = {ntris * base['traversals']}")
if ratio:
print(f"测试数之比 线性/BVH : 每次遍历 {ratio['perTraversal']:.4f}"
f" 每主光线 {ratio['perPrimaryRay']:.4f}")
return 0
if __name__ == "__main__":
sys.exit(main())
跑一遍（工作区 lantern/，linear 模式约需四分钟）：
# snippet: 本机实跑（工作区 lantern/）
cd lantern
/opt/homebrew/bin/python3 sim/cg_trace_03_3_bvh_traversal_cost.py
== 3.3 BVH 的遍历与代价 ==
三角形 / 主光线 : 896 / 76800
[bvh ] sha256=213b413069ca66c9… 基线=True
遍历次数= 154011 访问节点= 3238333 测试三角形= 1119804 耗时= 6874 ms
每主光线 访问= 42.1658 测试= 14.5808 | 每次遍历 访问=21.0266 测试= 7.2709
主光线 访问= 1347708 测试= 463033 | 阴影 访问= 1890625 测试= 656771
[noshrink] sha256=213b413069ca66c9… 基线=True
遍历次数= 154011 访问节点= 3484731 测试三角形= 1309882 耗时= 7837 ms
每主光线 访问= 45.3741 测试= 17.0558 | 每次遍历 访问=22.6265 测试= 8.5051
主光线 访问= 1584942 测试= 647774 | 阴影 访问= 1899789 测试= 662108
[linear ] sha256=213b413069ca66c9… 基线=True
遍历次数= 154011 访问节点= 0 测试三角形= 137993856 耗时= 247549 ms
每主光线 访问= 0.0000 测试=1796.7950 | 每次遍历 访问= 0.0000 测试=896.0000
主光线 访问= 0 测试= 68812800 | 阴影 访问= 0 测试= 69181056
收缩 vs 不收缩：访问 +246398（+7.07% 相对不收缩） 测试 +190078（+14.51%）
noshrink 与 linear 图像逐像素分歧 : 0 / 76800（sha 相同 True）
bvh 与 noshrink 图像逐像素分歧 : 0 / 76800
无 BVH 全量测试数 : 896 × 154011 = 137993856
测试数之比 线性/BVH : 每次遍历 123.2310 每主光线 61.4507
怎么读这张表
遍历次数 154011 = 76800 条主光线 + 77211 条阴影光线，三个模式完全相同——换的是遍历方式，不是发多少条光线。
两个口径要分清楚。 「每次遍历」= 计数 ÷ 154011（含主光线与阴影光线）；「每主光线」= 计数 ÷ 76800。bvh 的三角形测试是 1119804 次，于是每次遍历 7.2709 个、每主光线 14.5808 个。无 BVH 时每次遍历恒为 896 个（全部三角形）、每主光线 1796.7950 个——因为每条主光线平均还要发约 2 条阴影光线，分母却是主光线条数。「测试数之比 线性/BVH」两个数（123.2310 与 61.4507）的差别只来自分母不同，不是两次测量。
这两个比值是计数之比，不是速度之比。 耗时那一列（6874 / 7837 / 247549 ms）只说明本机这一次的顺序，不构成任何「快 N 倍」的结论：一次 linear 遍历要做 896 次 Möller–Trumbore，而 bvh 平均只做 7.27 次，但两者的单次成本并不相同，Python 的循环开销也在里面。本节全部结论都只建立在整数计数上，它们逐条可复现。
主光线与阴影光线的成本不一样。 bvh 下主光线访问 1347708 个节点、测试 463033 个三角形；阴影光线访问 1890625 个节点、测试 656771 个三角形。阴影光线的节点访问更多（它们从命中点出发，穿过更多子树），而阴影光线根本不需要找「最近的」交点——只要找到任何一个遮挡就可以停。这里如实报告：底座没有为阴影光线做任何提前退出优化，它和主光线走的是同一条遍历。
负例：不收缩会怎样
noshrink 只改了一处——slab 判据的上界从收缩后的 best_t 换回原始 tmax。结果是访问 +246398（相对不收缩 +7.07%）、测试 +190078（+14.51%）。多出来的访问与测试集中在主光线侧（主光线测试从 463033 涨到 647774），阴影侧几乎不变（656771 → 662108）——因为阴影光线本来就在第一个遮挡处停止收缩。
关键在最后两行：bvh 与 noshrink 的图像逐像素分歧 0 / 76800，noshrink 与 linear 也是 0 / 76800，三个模式的 sha256 与卷三基线 213b4130… 逐字节相同。多访问了 24 万个节点、多测了 19 万个三角形，没有任何一条光线的命中结果被改变——这才是「剪枝是保守的」这句话的可证伪形式：省掉的工作确实是不必要的工作，而不是把本该命中的交点一起省掉了。
P 层把计数钉死
P 层在 TypeScript 侧重跑同一批主光线，断言的是精确整数而不是四舍五入后的均值，负例则要求「计数严格变大、命中逐条相同」两件事同时成立：
// snippet: core/test/cg_trace_03_3_bvh_traversal_cost.test.ts（节选：负例）
// verify: node --test 'core/test/cg_trace_03_3_bvh_traversal_cost.test.ts'
assert.ok(unshrunk.visited > shrunk.visited, "不收缩必然多访问节点");
assert.equal(unshrunk.visited - shrunk.visited, 237234);
// 关键：多出来的访问与测试**没有改变任何一条光线的命中结果**——剪枝是保守的。
for (let i = 0; i < rays.length; i += 1)
assert.deepEqual(unshrunk.hits[i], shrunk.hits[i], `第 ${i} 条主光线的命中必须相同`);
小结
- 遍历次数 154011 = 76800 主光线 + 77211 阴影光线，三个模式一致；
bvh三角形测试 1119804（每主光线 14.5808、每次遍历 7.2709），无 BVH 时每次遍历恒为 896、全量 137993856 次。 - 计数之比 线性/BVH：每次遍历 123.2310、每主光线 61.4507；两个口径只是分母不同，且都是计数之比，不是速度之比。
- 关掉
best_t收缩：访问 +246398、测试 +190078，但逐像素分歧 0 / 76800，三个模式 sha256 与基线逐字节相同；阴影光线占了节点访问的 1890625 / 3238333（约 58%），而底座没为它做提前退出。
下一章从「光线被挡住之后」接着走：阴影光线本身怎么发、偏移向量为什么不是起点。
阅读导航：上一节：3.2 BVH 的构建 · 下一节：4.1 硬阴影与阴影光线 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。