15.3 场景图与遍历
前两节把几何造出来、又选好了内存表示。本节把若干片几何摆进世界，并回答一个问题：遍历序会不会改变画面。站内的 glTF 资产管线 讲的是场景怎么从外部文件被组装出来；本节讲的是场景图自身的遍历语义——层级变换怎么合成、遍历序在什么条件下才影响最终像素。
场景图：节点、局部变换、世界变换
场景图是一棵树。每个节点带一个局部变换（本节只用到平移与缩放，都写成 Q16.16 的 4×4 矩阵），节点的世界变换由根到它的路径合成：world = 父 * 子，从根往下依次右乘。叶子节点持有一片几何，它最终的顶点位置是 mvp * world * 顶点。
顺序不能反。矩阵乘法不交换：父是「先平移 1、再缩放 0.5」而子是「平移 1」，把原点分别按 父 * 子 与 子 * 父 变换，落点一个是 $1.5$、一个是 $2.0$——脚本把这两个值钉成断言，也把「两个乘积矩阵必须不同」钉成断言。写渲染器时把层级合成写反，是最常见的静默错误之一。
遍历序与绘制顺序
遍历树时叶子被塞进绘制列表，塞入的先后就是绘制顺序。这里的 z-buffer 用严格小于比较（新深度 < 旧深度才写），于是：
- 深度不相等的像素，顺序无关——后画的更远就被挡掉，谁先谁后都得到同一结果；
- 深度恰好相等的像素，先画的赢——后画的深度不小于它，被丢弃。
这与第 6 章「共享边像素归属由绘制顺序决定」同源，只是那里比的是边函数的值。脚本用三组场景把这条结论量出来：apart（两片四边形完全不交叠）、overlap（部分交叠）、stack（完全重合）。正向与反向遍历各渲染一次，逐像素比对。
可运行产物
下面这个脚本把层级合成、三组场景的顺序敏感性、以及交叠场景的像素缓冲全部钉成断言，并把正向渲染的 RGB 写成 .rgb 供 TypeScript 复现：
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_15_3_scene_graph.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_15_3_scene_graph.py
"""15.3 场景图与遍历：层级变换的合成顺序，以及遍历序对绘制顺序的影响。
场景图是一棵树：每个节点带一个局部变换（平移 + 缩放），世界变换 = 父 * 子。叶子节点持有
一片几何，遍历序决定叶子被塞进绘制列表的先后。z-buffer 用严格小于比较，故顺序对普通像素
无影响 —— 只有深度完全相等的交叠像素由「先画的赢」决定（与第 6 章「共享边像素归属由绘制
顺序决定」同源）。三组场景验证这条结论：apart（不交叠，顺序无关）、overlap（部分交叠）、
stack（完全重合）。
产物：out/cg_raster_15_3_graph.json、out/cg_raster_15_3_{apart,overlap,stack}.png、
out/cg_raster_15_3_overlap.rgb。
"""
import hashlib
import json
import os
import sys
import numpy as np
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
W, H = 64, 48
HALF = 32768 # 0.5 世界单位（叶子四边形的半边长）
COL_A = (210, 70, 60)
COL_B = (60, 140, 220)
def leaf_quad(h=HALF):
"""叶子四边形（局部坐标，z = 0）：屏幕空间 y 向下，故环绕取 (0,2,1)/(0,3,2)。"""
c0, c1 = (-h, -h, 0), (h, -h, 0)
c2, c3 = (h, h, 0), (-h, h, 0)
return [(c0, c2, c1), (c0, c3, c2)]
def world_chain(root, chain):
"""按「父 * 子」顺序合成层级变换：world = root * local1 * local2 * ..."""
m = root
for local in chain:
m = cglib.mat_mul(m, local)
return m
def build_mvp():
"""固定相机：eye (0,0,4)、看向原点、tanHalfFovY = 0.5。"""
aspect = cglib.fdiv(cglib.f_from_int(W), cglib.f_from_int(H))
view = cglib.mat_look_at((0, 0, 262144), (0, 0, 0), (0, cglib.ONE, 0))
return cglib.mat_mul(cglib.mat_perspective(32768, aspect, 32768, 4194304), view)
def render(mvp, leaves, bg):
"""leaves: [(world_matrix, color)]，按给定遍历序组装并光栅化。"""
rtris = []
for m, col in leaves:
mvp_world = cglib.mat_mul(mvp, m) # 叶子的世界变换先合成进 MVP
for tri in leaf_quad():
scr = []
for v in tri:
p = cglib.project(mvp_world, v)
if p is None:
scr = None
break
sx, sy = cglib.to_screen(p[0], p[1], W, H)
scr.append((sx, sy, p[2]))
if scr is None:
continue
rtris.append((scr[0][0], scr[0][1], scr[0][2], col[0], col[1], col[2],
scr[1][0], scr[1][1], scr[1][2], col[0], col[1], col[2],
scr[2][0], scr[2][1], scr[2][2], col[0], col[1], col[2]))
color, depth, covered, culled = cglib.rasterize(rtris, W, H, bg)
return color, covered, culled
def leaves_for(tx):
"""两层链：父、子各平移 tx -> 左叶中心 -2tx、右叶中心 +2tx。"""
def chain(sign):
return [cglib.mat_model(translate=(sign * tx, 0, 0)) for _ in range(2)]
return [(world_chain(cglib.mat_identity(), chain(-1)), COL_A),
(world_chain(cglib.mat_identity(), chain(1)), COL_B)]
def main():
spec = cglib.load_spec()
bg = tuple(spec["backgroundQ8"])
mvp = build_mvp()
out = os.path.join(ROOT, "out")
os.makedirs(out, exist_ok=True)
# 合成顺序：T(p)S(s) 与 S(s)T(p) 不是同一个矩阵（乘法不交换）
par = cglib.mat_model(translate=(cglib.f_from_int(1), 0, 0), scale=(HALF, HALF, HALF))
chd = cglib.mat_model(translate=(cglib.f_from_int(1), 0, 0))
o = (0, 0, 0, cglib.ONE)
pc_o = cglib.mat_vec4(cglib.mat_mul(par, chd), o)
cp_o = cglib.mat_vec4(cglib.mat_mul(chd, par), o)
assert cglib.mat_mul(par, chd) != cglib.mat_mul(chd, par), "父*子 与 子*父 必须不同"
assert pc_o != cp_o, "同一原点在两种合成顺序下落到不同位置"
scenes = {"apart": leaves_for(cglib.f_from_int(1) // 2), # 叶子中心 x = ±1.0（不交叠）
"overlap": leaves_for(cglib.f_from_int(1) // 8), # 叶子中心 x = ±0.25（部分交叠）
"stack": leaves_for(0)} # 叶子中心 x = 0（完全重合）
result = {}
for name, leaves in scenes.items():
fwd_color, fwd_cov, fwd_cull = render(mvp, leaves, bg)
rev_color, _, _ = render(mvp, list(reversed(leaves)), bg)
diff = int((fwd_color != rev_color).any(axis=2).sum())
fwd_sha = hashlib.sha256(np.clip(fwd_color, 0, 255).astype(np.uint8).tobytes()).hexdigest()
if name == "apart":
assert diff == 0, "不交叠场景：遍历序必须不影响图像"
else:
assert diff > 0, f"{name}：交叠场景必须出现顺序相关的像素"
png = cglib.save_png(os.path.join(out, f"cg_raster_15_3_{name}.png"), fwd_color)
if name == "overlap":
with open(os.path.join(out, "cg_raster_15_3_overlap.rgb"), "wb") as fh:
fh.write(np.clip(fwd_color, 0, 255).astype(np.uint8).tobytes())
result[name] = {"covered": int(fwd_cov.sum()), "culled": fwd_cull, "diff_pixels": diff,
"fwd_sha256": fwd_sha, "png_bytes": png}
stats = {"canvas": [W, H],
"compose_order": {"origin_after_T_S": [pc_o[0], pc_o[1], pc_o[2]],
"origin_after_S_T": [cp_o[0], cp_o[1], cp_o[2]]},
"scenes": result, "sha256_overlap_rgb": result["overlap"]["fwd_sha256"]}
with open(os.path.join(out, "cg_raster_15_3_graph.json"), "w", encoding="utf-8") as fh:
json.dump(stats, fh, ensure_ascii=False, indent=2)
print(f"画布 : {W}x{H}，1 像素 = {cglib.SUB1} 单位")
print(f"合成顺序 父*子 : 原点 -> {pc_o}（x = {cglib.f_to_int(pc_o[0])}）")
print(f"合成顺序 子*父 : 原点 -> {cp_o}（x = {cglib.f_to_int(cp_o[0])}）")
print("三组场景（遍历序正向 vs 反向）:")
for name in ("apart", "overlap", "stack"):
r = result[name]
tag = "逐字节相同" if r["diff_pixels"] == 0 else "顺序敏感"
print(f" {name:8s} covered={r['covered']:4d} culled={r['culled']:2d}"
f" diff_pixels={r['diff_pixels']:4d} {tag}")
print(f"overlap 正向 sha256: {result['overlap']['fwd_sha256']}")
print(f"png : apart {result['apart']['png_bytes']} / overlap "
f"{result['overlap']['png_bytes']} / stack {result['stack']['png_bytes']} bytes")
return 0
if __name__ == "__main__":
sys.exit(main())
实测输出：
画布 : 64x48，1 像素 = 64 单位
合成顺序 父*子 : 原点 -> (98304, 0, 0, 65536)（x = 1）
合成顺序 子*父 : 原点 -> (131072, 0, 0, 65536)（x = 2）
三组场景（遍历序正向 vs 反向）:
apart covered= 288 culled= 0 diff_pixels= 0 逐字节相同
overlap covered= 216 culled= 0 diff_pixels= 72 顺序敏感
stack covered= 144 culled= 0 diff_pixels= 144 顺序敏感
overlap 正向 sha256: dc581c058589bf3597855c36de9b4fcb67e0c0658af78df34c29a60129b2ba9e
png : apart 199 / overlap 199 / stack 187 bytes
三行读数正好对上上面的分析：不交叠场景 diff_pixels = 0，两遍渲染逐字节相同；部分交叠场景 72 个像素分叉，正是那片交叠区；完全重合时两片四边形覆盖的 144 个像素全部由「先画的赢」决定，所以差异数等于覆盖数。另外注意 overlap 的正向 sha256 与反向 sha256 不同，图像真的变了，不是统计口径的问题。
跨语言断言：同一份场景，两种语言
层级合成与绘制列表组装在 Python 与 TypeScript 两侧必须给出同一串像素。下面的模块用 BigInt 重写同一套合成与遍历；测试读 S 侧写出的 out/cg_raster_15_3_overlap.rgb，逐字节比对，并断言 apart 场景下正反两遍的 sha256 相同。
// file: lantern/core/src/lantern/cg_raster_15_scenegraph.ts
// tier: P
// verify: node --test 'core/test/cg_raster_15_3_scene_graph.test.ts'
// 15.3 的场景图与遍历：层级变换合成 + 按遍历序组装绘制列表。
// 与 Python 侧 sim/cg_raster_15_3_scene_graph.py 逐字对齐。
//
// 顶点变换走 BigInt（Q16.16），逐像素光栅化复用共享底座 raster.ts（Number + Math.floor）。
// 层级合成一律「父 * 子」：world = root * local1 * local2 * ...；顺序反了落点就不同。
import { ONE } from "./fixed.ts";
import { type Mat4, matIdentity, matLookAt, matModel, matMul, matPerspective } from "./mat.ts";
import { project, toScreen } from "./project.ts";
import { type RTri, type RasterResult, rasterize } from "./raster.ts";
import type { Vec3 } from "./vec.ts";
export const HALF = 32768n; // 0.5 世界单位（叶子四边形半边长）
/** 叶子四边形（局部坐标，z = 0）：屏幕空间 y 向下，故环绕取 (0,2,1)/(0,3,2)。 */
export function leafQuad(): [Vec3, Vec3, Vec3][] {
const c0: Vec3 = [-HALF, -HALF, 0n];
const c1: Vec3 = [HALF, -HALF, 0n];
const c2: Vec3 = [HALF, HALF, 0n];
const c3: Vec3 = [-HALF, HALF, 0n];
return [
[c0, c2, c1],
[c0, c3, c2],
];
}
/** 按「父 * 子」顺序合成层级变换。 */
export function worldChain(root: Mat4, chain: Mat4[]): Mat4 {
let m = root;
for (const local of chain) m = matMul(m, local);
return m;
}
/** 固定的正交式相机：eye (0,0,4)、看向原点，tanHalfFovY = 0.5。 */
export function buildMvp(width: number, height: number): Mat4 {
const aspect = (BigInt(width) << 16n) / BigInt(height);
const view = matLookAt([0n, 0n, 262144n], [0n, 0n, 0n], [0n, ONE, 0n]);
const proj = matPerspective(32768n, aspect, 32768n, 4194304n);
return matMul(proj, view);
}
export type SceneLeaf = { world: Mat4; color: number[] };
/** 按给定遍历序组装绘制列表并光栅化。 */
export function renderLeaves(
mvp: Mat4,
leaves: SceneLeaf[],
width: number,
height: number,
background: readonly number[],
): RasterResult {
const rtris: RTri[] = [];
for (const leaf of leaves) {
const mvpWorld = matMul(mvp, leaf.world);
for (const tri of leafQuad()) {
const xy: [number, number][] = [];
const d: number[] = [];
let ok = true;
for (const v of tri) {
const p = project(mvpWorld, v);
if (p === null) {
ok = false;
break;
}
const [sx, sy] = toScreen(p.ndcX, p.ndcY, width, height);
xy.push([Number(sx), Number(sy)]);
d.push(Number(p.depth));
}
if (!ok) continue;
rtris.push({ xy, d, c: [leaf.color, leaf.color, leaf.color] });
}
}
return rasterize(rtris, width, height, background);
}
/** 逐像素差异计数（任一通道不同即计一个像素）。 */
export function diffPixels(a: Uint8Array, b: Uint8Array): number {
let n = 0;
for (let i = 0; i < a.length; i += 3) {
if (a[i] !== b[i] || a[i + 1] !== b[i + 1] || a[i + 2] !== b[i + 2]) n += 1;
}
return n;
}
node --test 'core/test/cg_raster_15_3_scene_graph.test.ts' 实测 6 条断言全绿：
ℹ tests 6 ℹ pass 6 ℹ fail 0
最后一条是负例：把渲染实现改成「只画遍历到的最后一个叶子」，apart 场景立刻随顺序分叉——这条负例的作用是证明 apart 的 diff == 0 有区分力：判据不拒绝一个明显错误的实现，它的 PASS 就不可信。
阅读导航：上一节：15.2 网格的表示与加载 · 下一节：16.1 光栅化管线的装配 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。