engine

《游戏引擎实现原理》7.2 脏标记传播与 world matrix 缓存

给场景图加上脏标记：改动一个节点只把它的子树标脏，更新时只重算被标脏的节点、并在重复标记时提前停止，再用一组确定性访问计数与逐字节像素比较，证明「脏更新」与「全量重算」产出的世界矩阵逐位一致、渲染画面也完全相同，从而让每帧只付出真正改动的那部分代价。

Leeting Yan 6 分钟阅读 2945 字

7.2 脏标记传播与 world matrix 缓存

7.1 每帧展平都要算一遍全部 world 矩阵。但《微光岛》里绝大多数礁石一帧都不动——全量重算是纯浪费。这一节给场景图加上脏标记：改动一个节点只标脏它的子树，更新时只重算被标脏的节点；并证明「脏更新」与「全量重算」产出逐位一致的矩阵。

本节产出 src/render/scene/transform-cache.ts（L1）与 src/render/scene/cache-pixels.ts（L2）。所有计数与像素差异都来自本机实跑。

脏从哪里开始传播

核心只有一条规则：改一个节点，脏它整棵子树。父节点动了，子的世界矩阵一定跟着变；但子的子节点是否要动，取决于它自己有没有独立改动——所以脏标记必须往下传到叶子。

实现上有两个关键点：

  • 早停。markDirty 遇到一个已经脏的节点就立即返回，不再往它的子树里走，因为那棵子树上一轮已经标过了。于是「同一棵子树连续改两次」的第二次是 O(1)。
  • 拓扑序更新。update() 按「父先于子」的下标顺序扫一遍，只对脏节点重算。父若脏，先算父，子重算时就能读到新的父世界矩阵。

这套机制和卷一 13.2《迭代与脏标记》同源：那边用脏标记跳过没变的实体查询，这边用它跳过没变的矩阵乘法，都是「只做必要的工作」。

可运行产物：脏传播到底省了多少

完整的 src/render/scene/transform-cache.ts 如下。它建一棵 16 节点的树（1 个根 + 3 个分组 + 每组 4 块礁石）：

// file: src/render/scene/transform-cache.ts
// tier: L1
// verify: node src/render/scene/transform-cache.ts
//
// helio 渲染 7.2：脏标记传播 + world 矩阵缓存。
// 改动一个节点的局部变换，只把它的子树标脏；update() 只重算被标脏的节点，
// updateAll() 无条件全量重算。两者产出的 world 矩阵必须逐位一致——
// 缓存只省时间，绝不改结果。纯计算，Node 26 直跑。

import { type Mat4, identity, multiply } from '../../core/mat4.ts';
import { composeTRS, type Transform } from '../../core/transform.ts';

export class TransformCache {
  #parent: Int32Array;
  #local: Transform[];
  #world: Mat4[];
  #dirty: Uint8Array;
  #children: number[][];
  #count = 0;
  #recomputed = 0; // 上一次 update/updateAll 真正重算的节点数
  #markVisits = 0; // markDirty 访问到的节点数（含早停的那次）

  constructor(capacity: number) {
    this.#parent = new Int32Array(capacity).fill(-1);
    this.#local = [];
    this.#world = new Array(capacity);
    this.#dirty = new Uint8Array(capacity);
    this.#children = Array.from({ length: capacity }, () => []);
  }

  get count(): number { return this.#count; }
  get recomputed(): number { return this.#recomputed; }
  get markVisits(): number { return this.#markVisits; }

  add(parent: number, local: Transform): number {
    const i = this.#count++;
    this.#parent[i] = parent;
    this.#local[i] = local;
    if (parent >= 0) this.#children[parent]!.push(i);
    this.#dirty[i] = 1;
    return i;
  }

  /** 改局部变换，并把该节点及其整棵子树标脏（遇到已脏节点立即停，不再下探）。 */
  setLocal(i: number, local: Transform): void {
    this.#local[i] = local;
    this.#markDirty(i);
  }

  #markDirty(i: number): void {
    this.#markVisits++;
    if (this.#dirty[i] === 1) return; // 子树已经脏了，重复标记是 O(1)
    this.#dirty[i] = 1;
    for (const c of this.#children[i]!) this.#markDirty(c);
  }

  #recompute(i: number): void {
    const local = composeTRS(this.#local[i]!);
    const p = this.#parent[i]!;
    this.#world[i] = p < 0 ? local : multiply(identity(), this.#world[p]!, local);
    this.#dirty[i] = 0;
    this.#recomputed++;
  }

  /** 只重算被标脏的节点。节点按父先于子登记，故一次正序扫描即拓扑序。 */
  update(): number {
    this.#recomputed = 0;
    for (let i = 0; i < this.#count; i++) if (this.#dirty[i] === 1) this.#recompute(i);
    return this.#recomputed;
  }

  /** 无条件全量重算，作为「正确性基准」。 */
  updateAll(): number {
    this.#recomputed = 0;
    for (let i = 0; i < this.#count; i++) this.#recompute(i);
    return this.#recomputed;
  }

  /** 重置标记统计，方便在 demo 里分段观察。 */
  resetCounters(): void { this.#markVisits = 0; this.#recomputed = 0; }

  world(i: number): Mat4 { return this.#world[i]!; }
  isDirty(i: number): boolean { return this.#dirty[i] === 1; }
}

/** 逐位比较两个 4x4（都来自同一套 f32 运算，可用严格相等）。 */
export function mat4Equal(a: Mat4, b: Mat4): boolean {
  for (let k = 0; k < 16; k++) if (a[k] !== b[k]) return false;
  return true;
}

// ---- 直接运行时打印一份「脏传播到底省了多少」的账（Node 26 import.meta.main）----
if ((import.meta as { main?: boolean }).main) {
  const trs = (t: [number, number, number], s = 1): Transform => ({
    translation: t, rotation: identity(), scale: [s, s, s],
  });
  // 1 个根 + 3 个分组 + 每组 4 块礁石 = 16 个节点
  const cache = new TransformCache(32);
  const root = cache.add(-1, trs([0, 0, 0]));
  const groups: number[] = [];
  const rocks: number[][] = [];
  for (let gi = 0; gi < 3; gi++) {
    const g = cache.add(root, trs([gi * 4, 0, 0]));
    groups.push(g);
    const rs: number[] = [];
    for (let r = 0; r < 4; r++) rs.push(cache.add(g, trs([r, 0, gi], 0.5)));
    rocks.push(rs);
  }

  const full = cache.updateAll();
  console.log(`节点 ${cache.count}  首次全量 updateAll 重算 ${full} 次`);

  // 场景 A：动一个叶子礁石
  cache.resetCounters();
  cache.setLocal(rocks[2]![0]!, trs([9, 0, 0], 0.5));
  const leaf = cache.update();
  console.log(`改 1 块礁石   markDirty 访问 ${cache.markVisits}   update 重算 ${leaf}   （全量需 ${cache.count}）`);

  // 场景 B：动整个分组（它下面挂 4 块礁石）
  cache.resetCounters();
  cache.setLocal(groups[1]!, trs([100, 0, 0]));
  const group = cache.update();
  console.log(`改 1 个分组   markDirty 访问 ${cache.markVisits}   update 重算 ${group}   （全量需 ${cache.count}）`);

  // 场景 C：同一子树连续标记两次——第二次遇到已脏节点立即停
  cache.resetCounters();
  cache.setLocal(groups[1]!, trs([101, 0, 0]));
  const again = cache.markVisits;
  cache.setLocal(groups[1]!, trs([102, 0, 0]));
  cache.update(); // 把最后一次改动刷进缓存，再和全量基准比
  console.log(`同一分组连标两次   markDirty 访问 ${again} 然后 ${cache.markVisits - again}（早停）`);

  // 正确性：脏更新的结果必须和全量重算逐位一致
  const dirtyWorlds = Array.from({ length: cache.count }, (_, i) => cache.world(i));
  cache.updateAll();
  const same = dirtyWorlds.every((m, i) => mat4Equal(m, cache.world(i)));
  console.log(`脏更新 == 全量重算（逐位）: ${same}`);
}

node src/render/scene/transform-cache.ts（本机实测）：

节点 16  首次全量 updateAll 重算 16 次
改 1 块礁石   markDirty 访问 1   update 重算 1   （全量需 16）
改 1 个分组   markDirty 访问 5   update 重算 5   （全量需 16）
同一分组连标两次   markDirty 访问 5 然后 1（早停）
脏更新 == 全量重算（逐位）: true

读法：全量重算是 16 次矩阵乘法；改一块叶子礁石只重算 1 次（省 15 次）；改一个挂着 4 块礁石的分组，markDirty 访问 5 个节点、update 重算 5 次（省 11 次）。最后两行是重点：同一棵子树连标两次，第二次只访问 1 个节点就早停；而脏更新的结果与全量重算逐位相同——缓存只省时间，绝不改结果。

可运行产物：脏更新的画面与全量重算逐字节相同

「逐位相同」是矩阵层面的，真正的验收是画面层面。src/render/scene/cache-pixels.ts（L2）用 7.1 的 instanced 渲染器，把「脏更新后的矩阵」和「全量重算的矩阵」各画一帧，逐像素比较：

// file: src/render/scene/cache-pixels.ts
// tier: L2
// verify: node tools/run-l2.mjs src/render/scene/cache-pixels.ts
//
// 7.2 的 L2 验收：缓存只省时间、不改结果。同一棵 16 节点场景，
// 用「脏更新后的 world 矩阵」和「全量重算的 world 矩阵」各渲染一帧，
// 逐像素比较——必须完全一致；同时改动确实让画面变了（前后两帧不同），
// 证明这条像素断言不是空转。需 headless Chromium + 本地 http 服务。

import { TransformCache } from './transform-cache.ts';
import { renderInstances, loadWgsl, type L2Check, type L2Result } from './render-instances.ts';
import { type Mat4, identity } from '../../core/mat4.ts';
import { type Transform } from '../../core/transform.ts';

const trs = (t: [number, number, number], s = 1): Transform => ({
  translation: t, rotation: identity(), scale: [s, s, s],
});

function buildTree(): { cache: TransformCache; rocks: number[][] } {
  const cache = new TransformCache(32);
  const root = cache.add(-1, trs([0, 0, 0]));
  const rocks: number[][] = [];
  for (let gi = 0; gi < 3; gi++) {
    const g = cache.add(root, trs([gi * 4, 0, 0]));
    const rs: number[] = [];
    for (let r = 0; r < 4; r++) rs.push(cache.add(g, trs([r, 0, gi], 0.5)));
    rocks.push(rs);
  }
  return { cache, rocks };
}

const worlds = (cache: TransformCache): Mat4[] =>
  Array.from({ length: cache.count }, (_, i) => cache.world(i));

export async function runL2(): Promise<L2Result> {
  const checks: L2Check[] = [];
  const data: Record<string, unknown> = {};
  const push = (name: string, ok: boolean, detail: unknown): void => {
    checks.push({ name, ok, detail: String(detail) });
  };

  const adapter = await navigator.gpu.requestAdapter();
  if (!adapter) throw new Error('requestAdapter() returned null');
  const device = await adapter.requestDevice();
  const wgsl = await loadWgsl('/shaders/instance-transform.wgsl');

  const { cache, rocks } = buildTree();
  const SIZE = 128;
  // 每个节点一种颜色，保证「移动某个节点」一定改变像素（避免同色叠盖掩盖差异）
  const colors = Array.from({ length: cache.count }, (_, i) => [
    ((i * 40) % 200 + 30) / 255, ((i * 70) % 200 + 30) / 255, ((i * 110) % 200 + 30) / 255, 1,
  ]);

  cache.updateAll();
  const pxBefore = await renderInstances(device, wgsl, worlds(cache), colors, SIZE);

  // 改动一块礁石：脏更新后的矩阵
  cache.setLocal(rocks[0]![0]!, trs([-20, 0, 0], 0.5));
  cache.update();
  const pxDirty = await renderInstances(device, wgsl, worlds(cache), colors, SIZE);

  // 同样这棵场景，改用全量重算
  cache.updateAll();
  const pxFull = await renderInstances(device, wgsl, worlds(cache), colors, SIZE);

  const diff = (a: Uint8Array, b: Uint8Array): number => {
    let d = 0;
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) d++;
    return d;
  };
  const dCacheVsFull = diff(pxDirty, pxFull);
  const dBeforeVsAfter = diff(pxBefore, pxDirty);
  data.diffCacheVsFull = dCacheVsFull;
  data.diffBeforeVsAfter = dBeforeVsAfter;
  data.bytes = pxDirty.length;

  push('脏更新 == 全量重算（逐字节）', dCacheVsFull === 0, `diff=${dCacheVsFull}`);
  push('改动确实改变了画面（断言非空转）', dBeforeVsAfter > 0, `diff=${dBeforeVsAfter}`);

  device.destroy();
  return { checks, data };
}

本机实跑：

PASS  脏更新 == 全量重算（逐字节）  diff=0
PASS  改动确实改变了画面（断言非空转）  diff=432

第一行 diff=0：两帧 65536 字节完全相同。第二行是对照——我特意把一块礁石移到屏幕外，前后两帧差 432 字节，证明这条像素断言不是空转（若渲染根本没画出东西，两帧会一样「全 0 差异」而骗过第一行）。

小结

脏标记把「每帧重算 N 个矩阵」压成「每帧重算被改动的那几棵子树」。代价是每个节点多一个字节的脏位和一次向下传播，换来的是静态场景几乎零成本。

矩阵缓存解决了「算得少」，下一节解决「看什么、点哪里」：相机、裁剪面与拾取射线。

阅读导航：上一节：7.1 场景图与变换层级 · 下一节：7.3 相机、裁剪面与拾取射线 。

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「engine」更多文章

  1. 《游戏引擎实现原理》工程与实战 目录
  2. 《游戏引擎实现原理》9.3 选型与自研的判断标准
  3. 《游戏引擎实现原理》9.2 同一个特性在不同引擎里的实现路径