13.2 累积的确定性
站内 /posts/books/渲染引擎/ 那套讲的是 TypeScript 引擎架构：RHI 抽象、帧图调度、可见性剔除，关心的是结构怎么摆、每帧的代价怎么摊。本节换一个尺度——架构不变、算法不变，只问一件事：同一份输入，能不能每次拼出同一个字节。13.1 管的是一条光线；本节管的是一批光线拼出来的那张图。
累加顺序：加法可结合，乘法的截断不可结合
第一层是好消息。4096 个 Q16.16 采样分别用正序、逆序、两两配对（树形归约）求和：
- 三个和完全相同：都是 135287899，差异 0 处。
整数加法是可结合的，这一层没有不确定性。破坏结合律的是乘法的截断。同一批采样，一种口径是「先精确求和、最后降一次精度」(Σ x) >> 12，另一种是「逐个降精度再累加」Σ (x >> 12)：
- 先累加后移位 33029，逐个移位 30958，差 2071。
- 逐个移位那一侧对顺序不敏感（逆序同样是 30958）——移位是逐元素操作；而「先累加后移位」把顺序的全部差异压进了那一次移位里。
fmul 本身的两个反例计数：交换律 0 组、结合律 1005 / 4096 组。第 4.2 节在同一台机器上量过 979/4096；两次的种子与样本集不同，所以数字不同，但结论完全一致——(a * b) >> 16 的向下取整在不同分组点截断，少截断一次就落回另一侧。
再看一个真实估计器：递推均值 m += fmul(x - m, alpha)（alpha = 1/8）。
- 正序 34326、逆序 32320，差 2006。
- 批量均值（先精确求和再
// n）是 33029。
三种算法算的是同一个实数，得到三个不同的整数。这不是 bug，是估计器的路径依赖：每一步都在一个截断过的中间值上继续。所以「可复现」的准确含义是路径固定，不是「算法等价」。
遍历顺序：结果不变，代价变
把 896 个三角形按确定性 Fisher–Yates 重排，重建 BVH，再跑一遍主光线：
- 命中像素数：43731 → 43731（不变）。
t序列摘要：c030dd7c… → c030dd7c…（不变）。- BVH 访问节点数：1347708 → 1347210；三角形测试：463033 → 462926（都变了）。
代价少了 498 个节点、107 次测试，图像一个字节没变。原因是最近命中唯一：暴力扫描 1024 条抽样光线，t 并列 0 条。只要没有两条三角形在同一个 t 上打平，「取最小」就是与顺序无关的运算。反过来，一旦并列，r[0] < best_t 里的严格小于号会让先被访问到的那条获胜——顺序就从后门进来了。这也解释了为什么本节要专门去数并列：顺序无关不是「显然的」，它有一个可检验的前提。
口径说明：上表里的访问 / 测试只统计主光线 76800 条；本卷基线记的 3238333 是主光线加阴影光线的合计，两者不可直接比。
RNG 流结构：可复现不等于可并行
换成一张 64×48 的小图，每像素抽 4 个 Q16.16 采样求平均，两种随机流：
- 全局流（一个状态按遍历顺序推进）：按行扫和按列扫得到两张图，3049 / 3072 个像素不同。
- 逐像素流（状态由像素坐标派生）：两张图逐字节相同，摘要
00899158…。
「同一个种子跑两次结果一样」是最弱的可复现——单线程顺序执行时，全局流也满足。真正要的是与调度无关：按瓦片并行时，全局流会随线程调度改变每个像素取到的采样序号，图就变了；逐像素流把随机性绑死在坐标上，调度怎么变都一样。第 5 章的分层采样、第 12 章的收敛曲线都依赖这条性质。
完整脚本
#!/usr/bin/env python3
# file: lantern/sim/cg_trace_13_2_accumulation.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_trace_13_2_accumulation.py
"""13.2 累积的确定性：同种子可复现、累加顺序、遍历顺序与 RNG 流结构。
13.1 把**一条**光线的误差关进闭式界；本节换到**一批**光线。图像是几万次累加拼出来的，
问的是同一份输入能不能每次拼出同一个字节。四组实验：
1. **累加顺序**。整数加法本身可结合（三序零差异）；破坏结合律的是**乘法的截断**：
`(Σ x) >> k` 与 `Σ (x >> k)` 不等价，`fmul` 的结合律反例复现第 4.2 节的同一现象，
递推均值 `m += fmul(x - m, alpha)` 与批量均值也不等价。
2. **遍历顺序**。重排三角形 -> 重建 BVH -> 遍历顺序随之改变：图像摘要与命中像素数
不变，BVH 访问节点数变。顺序无关的前提是**最近命中唯一**，故暴力扫描统计 t 并列。
3. **RNG 流结构**。全局流下按行 / 按列遍历会得到两张不同的图；逐像素流下两张图逐字节
相同——「可复现」不等于「可并行」。
产物：out/cg_trace_13_2_accumulation.json
"""
import hashlib
import json
import os
import struct
import sys
import numpy as np
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
import cgtrace # noqa: E402
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
OUT = os.path.join(ROOT, "out")
ONE = cglib.ONE
FMUL, FDIV = cglib.fmul, cglib.fdiv
BASELINE_SHA = "213b413069ca66c9f0cc091bce5328eac0f540d075afa3bab37788aea335ba71"
SAMPLES, SEED, SHIFT = 4096, 20261016, 12
GW, GH = 64, 48 # RNG 流实验的小图（1/25 面积，够看出结构）
def draw(n, seed):
st, xs = seed, []
for _ in range(n):
st, q = cgtrace.rng_q16(st)
xs.append(q)
return xs
def sum_seq(xs):
a = 0
for x in xs:
a += x
return a
def sum_pair(xs): # 两两配对求和（树形归约）
cur = list(xs)
while len(cur) > 1:
nxt = [cur[i] + cur[i + 1] for i in range(0, len(cur) - 1, 2)]
if len(cur) % 2:
nxt.append(cur[-1])
cur = nxt
return cur[0]
def exp_accumulation(xs):
"""累加顺序：加法可结合，乘法的截断不可结合。"""
seq, rev, pair = sum_seq(xs), sum_seq(list(reversed(xs))), sum_pair(xs)
sh = [x >> SHIFT for x in xs]
after, before, before_rev = seq >> SHIFT, sum_seq(sh), sum_seq(list(reversed(sh)))
st, comm, assoc = SEED, 0, 0 # fmul 的交换律 / 结合律
for _ in range(SAMPLES):
st, a = cgtrace.rng_q16(st)
st, b = cgtrace.rng_q16(st)
st, c = cgtrace.rng_q16(st)
comm += FMUL(a, b) != FMUL(b, a)
assoc += FMUL(FMUL(a, b), c) != FMUL(a, FMUL(b, c))
alpha = ONE >> 3 # 递推均值：alpha = 1/8
fwd = revm = 0
for x in xs:
fwd += FMUL(x - fwd, alpha)
for x in reversed(xs):
revm += FMUL(x - revm, alpha)
return {
"seq": seq, "rev": rev, "pair": pair, "orderDiffAdd": int(seq != rev) + int(seq != pair),
"afterShift": after, "beforeShift": before, "beforeShiftRev": before_rev,
"shiftDiffFwd": abs(after - before), "shiftDiffRev": abs(after - before_rev),
"fmulCommDiff": comm, "fmulAssocDiff": assoc, "alpha": alpha,
"runningMeanFwd": fwd, "runningMeanRev": revm, "runningMeanDiff": abs(fwd - revm),
"batchMean": seq // len(xs),
}
def permutation(n, seed): # 确定性 Fisher–Yates（rng_below 拒绝采样，无取模偏置）
idx = list(range(n))
for i in range(n - 1, 0, -1):
seed, j = cgtrace.rng_below(seed, i + 1)
idx[i], idx[j] = idx[j], idx[i]
return idx
def primary_pass(spec, tris, nodes, order, keep_dirs=False):
"""主光线最近命中一遍：返回 (t 序列摘要, stats, 方向表)。"""
cam = spec["camera"]
eye = tuple(cam["eyeQ16"])
view = cglib.mat_look_at(eye, tuple(cam["targetQ16"]), tuple(cam["upQ16"]))
right, up, back = view[0:3], view[4:7], view[8:11] # 相机基取**行**
w, h = spec["width"], spec["height"]
th, tmax = cam["tanHalfFovYQ16"], cam["farQ16"]
tx = FMUL(th, FDIV(cglib.f_from_int(w), cglib.f_from_int(h)))
stats = {"visited": 0, "tested": 0, "rays": 0, "hits": 0}
buf, dirs = bytearray(), []
for py in range(h):
ay = FMUL(FDIV(cglib.f_from_int(2 * (h // 2 - py) - 1), cglib.f_from_int(h)), th)
for px in range(w):
ax = FMUL(FDIV(cglib.f_from_int(2 * (px - w // 2) + 1), cglib.f_from_int(w)), tx)
d = cglib.v_norm((FMUL(ax, right[0]) + FMUL(ay, up[0]) - back[0],
FMUL(ax, right[1]) + FMUL(ay, up[1]) - back[1],
FMUL(ax, right[2]) + FMUL(ay, up[2]) - back[2]))
stats["rays"] += 1
hit = cgtrace.bvh_intersect(nodes, order, tris, eye, d, tmax, stats)
if hit is None:
buf += struct.pack("<q", -1)
else:
stats["hits"] += 1
buf += struct.pack("<q", hit[0])
if keep_dirs:
dirs.append(d)
return hashlib.sha256(bytes(buf)).hexdigest(), stats, dirs
def tie_scan(eye, dirs, tris, step):
"""暴力扫描抽样光线：统计「最小 t 被多个三角形同时达到」的光线数。"""
checked = ties = 0
for i in range(0, len(dirs), step):
d, best, cnt = dirs[i], None, 0
for rec in tris:
r = cgtrace.intersect_triangle(eye, d, (rec[0], rec[1], rec[2]),
(rec[3], rec[4], rec[5]), (rec[6], rec[7], rec[8]))
if r is None:
continue
if best is None or r[0] < best:
best, cnt = r[0], 1
elif r[0] == best:
cnt += 1
checked += 1
ties += cnt > 1
return checked, ties
def stream_img(col_major=None):
"""全局流（col_major 给出时按列推进）/ 逐像素流（col_major=None，与顺序无关）。"""
img = np.zeros((GH, GW), dtype=np.uint8)
coords = ([(px, py) for px in range(GW) for py in range(GH)] if col_major else
[(px, py) for py in range(GH) for px in range(GW)])
st = SEED
for px, py in coords:
if col_major is None: # 逐像素种子：由坐标派生，与遍历顺序无关
st = (SEED + (py * GW + px) * cgtrace.RNG_GOLDEN) & cgtrace.RNG_MASK
s = 0
for _ in range(4):
st, q = cgtrace.rng_q16(st)
s += q
img[py, px] = (s >> 2) >> 8
return img
def main():
spec = cglib.load_spec()
tris, _ = cgtrace.build_scene_tris(spec)
nodes, order = cgtrace.build_bvh(tris)
acc = exp_accumulation(draw(SAMPLES, SEED))
d0, s0, dirs = primary_pass(spec, tris, nodes, order, keep_dirs=True)
d0b, _, _ = primary_pass(spec, tris, nodes, order) # 同顺序再跑一遍
perm = permutation(len(tris), SEED ^ 0x5DEECE66D)
tris_p = [tris[i] for i in perm]
nodes_p, order_p = cgtrace.build_bvh(tris_p)
d1, s1, _ = primary_pass(spec, tris_p, nodes_p, order_p) # 重排 + 重建 BVH
eye = tuple(spec["camera"]["eyeQ16"])
checked, ties = tie_scan(eye, dirs, tris, 75)
gr, gc, pp = stream_img(False), stream_img(True), stream_img(None)
sha = cgtrace.digest
g_diff = int(np.count_nonzero(gr != gc))
print("== 13.2 累积的确定性 ==")
print(f"累加顺序 : seq/rev/pair = {acc['seq']} / {acc['rev']} / {acc['pair']}"
f"（差异 {acc['orderDiffAdd']} 处：整数加法可结合）")
print(f"先累加后移位 : {acc['afterShift']} vs 逐个移位 {acc['beforeShift']}"
f"（差 {acc['shiftDiffFwd']}，逆序差 {acc['shiftDiffRev']}）")
print(f"fmul 归因 : 交换律反例 {acc['fmulCommDiff']} / 结合律反例 "
f"{acc['fmulAssocDiff']}（{SAMPLES} 组三元组）")
print(f"递推均值 alpha=1/8: 正序 {acc['runningMeanFwd']} / 逆序 {acc['runningMeanRev']}"
f"（差 {acc['runningMeanDiff']}，批量均值 {acc['batchMean']}）")
print(f"\n遍历顺序（原始） : 命中 {s0['hits']} 像素，访问 {s0['visited']} 节点，"
f"测试 {s0['tested']} 次")
print(f"遍历顺序（重排） : 命中 {s1['hits']} 像素，访问 {s1['visited']} 节点，"
f"测试 {s1['tested']} 次")
print(f"两次摘要 : {'相同' if d0 == d1 else '不同'}"
f"（同顺序再跑 {'相同' if d0 == d0b else '不同'}）")
print(f"最近命中唯一性 : 暴力扫描 {checked} 条光线，t 并列 {ties} 条")
print(f"\n== RNG 流结构 ==\n全局流 行/列 : 不同像素 {g_diff} / {GW * GH}"
f"（摘要 {'相同' if sha(gr) == sha(gc) else '不同'}）")
print(f"逐像素流 : 不同像素 0（摘要 {sha(pp)[:8]}… 可重复）")
os.makedirs(OUT, exist_ok=True)
payload = {
"samples": SAMPLES, "seed": SEED, "shift": SHIFT, "baselineSha": BASELINE_SHA,
"accumulation": acc, "orderSameSha": d0 == d1, "repeatSameSha": d0 == d0b,
"shaOriginal": d0, "shaPermuted": d1, "statsOriginal": s0, "statsPermuted": s1,
"tieRaysChecked": checked, "tieRays": ties, "gridW": GW, "gridH": GH,
"globalRowSha": sha(gr), "globalColSha": sha(gc), "perPixelSha": sha(pp),
"globalDiffPixels": g_diff, "perPixelDiffPixels": 0,
}
with open(os.path.join(OUT, "cg_trace_13_2_accumulation.json"), "w", encoding="utf-8") as f:
json.dump(payload, f, ensure_ascii=False, indent=2)
f.write("\n")
print("\n落盘 out/cg_trace_13_2_accumulation.json")
return 0
if __name__ == "__main__":
sys.exit(main())
== 13.2 累积的确定性 ==
累加顺序 : seq/rev/pair = 135287899 / 135287899 / 135287899（差异 0 处：整数加法可结合）
先累加后移位 : 33029 vs 逐个移位 30958（差 2071，逆序差 2071）
fmul 归因 : 交换律反例 0 / 结合律反例 1005（4096 组三元组）
递推均值 alpha=1/8: 正序 34326 / 逆序 32320（差 2006，批量均值 33029）
遍历顺序（原始） : 命中 43731 像素，访问 1347708 节点，测试 463033 次
遍历顺序（重排） : 命中 43731 像素，访问 1347210 节点，测试 462926 次
两次摘要 : 相同（同顺序再跑 相同）
最近命中唯一性 : 暴力扫描 1024 条光线，t 并列 0 条
== RNG 流结构 ==
全局流 行/列 : 不同像素 3049 / 3072（摘要 不同）
逐像素流 : 不同像素 0（摘要 00899158… 可重复）
落盘 out/cg_trace_13_2_accumulation.json
P 层
// snippet: 节选自 lantern/core/test/cg_trace_13_2_accumulation.test.ts
// verify: node --test 'core/test/cg_trace_13_2_accumulation.test.ts'
assert.equal(g.orderDiffAdd, 0, "整数加法三序必须零差异");
assert.ok(assoc > 0, "结合律必须有反例，否则定点语义变了");
assert.notEqual(base.stats.visited, permBase.stats.visited, "代价必须随顺序变");
assert.equal(base.sha, permBase.sha, "最近命中唯一时，遍历顺序不应改变图像");
两条断言的方向相反，这是刻意的：摘要必须相等，代价必须不等。如果哪天有人把 BVH 遍历「优化」成不依赖顺序的固定代价，第三条会失败；如果有人改坏了最近命中的选择（比如把 < 改成 <=），第一条会失败。P 层在这里守的不是「跑得快」，而是这两件事必须仍然分开——结果确定，代价可以不确定。
小结
- 整数加法三序同值（135287899，差异 0）；
(Σ x) >> 12与Σ (x >> 12)差 2071。 fmul交换律 0 反例、结合律 1005 / 4096 反例（4.2 节同现象量到 979/4096，样本不同）。- 递推均值路径依赖：正序 34326、逆序 32320、批量均值 33029。
- 重排三角形重建 BVH：命中 43731 与摘要不变，访问节点 1347708 → 1347210；前提是
t并列 0 条（1024 条抽样）。 - 全局 RNG 流下换遍历顺序 3049 / 3072 像素改变；逐像素流下逐字节相同——可复现 ≠ 可并行。
单机内部这一层确定性理清了，下一节把它抬到语言边界上：同一份 scene_spec.json 交给 Python 和 TypeScript，像素缓冲的 sha256 能不能逐字节相同。
阅读导航：上一节：13.1 求交的容差边界 · 下一节：13.3 跨语言对照 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。