《游戏引擎实现原理》14.1 Pass 依赖与资源生命周期

// file: src/render/framegraph/framegraph.ts
// tier: L1
// verify: npx vitest run src/render/framegraph/framegraph.test.ts
//
// helio 渲染卷 14.1：帧图的 IR、依赖推导与资源生命周期。
// 一个 Pass 只声明「读哪些资源、写哪些资源」。帧图据此做两件事：
//   1) dependencies()：数据流真依赖（写者 → 读者），与声明顺序无关，
//      拓扑排序只认它；
//   2) hazards()：按声明顺序分类出的三类 hazard（RAW / WAR / WAW），
//      用于屏障与别名推理。
// 再把每个资源的生命周期区间（首次使用 → 末次使用）算出来。全部在 CPU 侧。

export type PassId = string;
export type ResourceId = string;

/** 一个 Pass 节点：只声明「读写哪些资源」，不关心底层命令。 */
export interface PassNode {
  readonly name: PassId;
  readonly reads: readonly ResourceId[];
  readonly writes: readonly ResourceId[];
}

/** 三类数据依赖。RAW 是真依赖（写后读），WAR/WAW 是反依赖与输出依赖。 */
export type EdgeKind = 'RAW' | 'WAR' | 'WAW';

export interface Edge {
  readonly from: PassId;
  readonly to: PassId;
  readonly resource: ResourceId;
  readonly kind: EdgeKind;
}

/** 资源在拓扑序里的生命周期区间（下标都是拓扑序位置，闭区间）。 */
export interface Lifetime {
  readonly resource: ResourceId;
  /** 第一次被写的位置。 */
  readonly firstWrite: number;
  /** 第一次被读或被写的位置。 */
  readonly firstUse: number;
  /** 最后一次被读或被写的位置。 */
  readonly lastUse: number;
}

export class FrameGraphError extends Error {}

/** 帧图：按声明顺序收 Pass，再一次性推导依赖、顺序与生命周期。 */
export class FrameGraph {
  readonly #passes: PassNode[] = [];
  readonly #seen = new Set<PassId>();

  /** 声明一个 Pass。名字重复直接报错，避免依赖边指向歧义节点。 */
  addPass(node: PassNode): this {
    if (this.#seen.has(node.name)) {
      throw new FrameGraphError(`Pass 名字重复: ${node.name}`);
    }
    this.#seen.add(node.name);
    this.#passes.push(node);
    return this;
  }

  get passes(): readonly PassNode[] {
    return this.#passes;
  }

  /**
   * 数据流真依赖：对任意「A 写 R、B 读 R」的 Pass 对，生成一条 RAW 边 A→B，
   * 与二者谁先声明无关。这是拓扑排序唯一的输入。
   */
  dependencies(): Edge[] {
    const out: Edge[] = [];
    const seen = new Set<string>();
    for (const writer of this.#passes) {
      for (const reader of this.#passes) {
        if (writer.name === reader.name) continue;
        for (const res of intersect(writer.writes, reader.reads)) {
          const key = `${writer.name}->${reader.name}:${res}`;
          if (!seen.has(key)) {
            seen.add(key);
            out.push({ from: writer.name, to: reader.name, resource: res, kind: 'RAW' });
          }
        }
      }
    }
    return out;
  }

  /**
   * 按声明顺序（i < j）分类出的 hazard 列表：
   *   i 写、j 读同一资源 → RAW；i 读、j 写 → WAR；两边都写 → WAW。
   * 与 dependencies() 不同，它带方向语义（谁先谁后），供屏障/别名推理使用。
   */
  hazards(): Edge[] {
    const out: Edge[] = [];
    const n = this.#passes.length;
    for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
        const a = this.#passes[i]!;
        const b = this.#passes[j]!;
        for (const r of intersect(a.writes, b.reads)) out.push({ from: a.name, to: b.name, resource: r, kind: 'RAW' });
        for (const r of intersect(a.reads, b.writes)) out.push({ from: a.name, to: b.name, resource: r, kind: 'WAR' });
        for (const r of intersect(a.writes, b.writes)) out.push({ from: a.name, to: b.name, resource: r, kind: 'WAW' });
      }
    }
    return out;
  }

  /**
   * 拓扑序（Kahn 算法）。**只按真依赖（RAW）排序**：写者必须先于读者，
   * 即使读者声明在前。WAR/WAW 由声明序兜底，不参与排序。孤立 Pass 保持声明序。
   * 真依赖成环（两个 Pass 互相读写同一资源）时抛错——帧图不允许有环。
   */
  topologicalOrder(): PassId[] {
    const edges = this.dependencies();
    const indeg = new Map<PassId, number>();
    const adj = new Map<PassId, Set<PassId>>();
    for (const p of this.#passes) {
      indeg.set(p.name, 0);
      adj.set(p.name, new Set<PassId>());
    }
    for (const e of edges) {
      const set = adj.get(e.from)!;
      if (!set.has(e.to)) {
        set.add(e.to);
        indeg.set(e.to, (indeg.get(e.to) ?? 0) + 1);
      }
    }
    const queue: PassId[] = this.#passes.filter((p) => indeg.get(p.name) === 0).map((p) => p.name);
    const order: PassId[] = [];
    while (queue.length > 0) {
      const cur = queue.shift()!;
      order.push(cur);
      for (const next of adj.get(cur)!) {
        const d = (indeg.get(next) ?? 0) - 1;
        indeg.set(next, d);
        if (d === 0) queue.push(next);
      }
    }
    if (order.length !== this.#passes.length) {
      throw new FrameGraphError('帧图存在真依赖环，无法拓扑排序');
    }
    return order;
  }

  /**
   * 每个资源的生命周期。先取拓扑序，再把「资源 → 拓扑序下标」扫一遍。
   * 没被任何 Pass 触碰的资源不会出现。
   */
  lifetimes(): Lifetime[] {
    const order = this.topologicalOrder();
    const pos = new Map<PassId, number>();
    order.forEach((name, idx) => pos.set(name, idx));
    const acc = new Map<ResourceId, { firstWrite: number; firstUse: number; lastUse: number }>();
    const touch = (r: ResourceId, at: number, isWrite: boolean): void => {
      const cur = acc.get(r);
      if (cur === undefined) {
        acc.set(r, { firstWrite: isWrite ? at : Number.POSITIVE_INFINITY, firstUse: at, lastUse: at });
        return;
      }
      if (isWrite) cur.firstWrite = Math.min(cur.firstWrite, at);
      cur.firstUse = Math.min(cur.firstUse, at);
      cur.lastUse = Math.max(cur.lastUse, at);
    };
    for (const p of this.#passes) {
      const at = pos.get(p.name)!;
      for (const r of p.writes) touch(r, at, true);
      for (const r of p.reads) touch(r, at, false);
    }
    return [...acc.entries()].map(([resource, v]) => ({ resource, ...v }));
  }
}

/** 两个资源列表的交集（去重，保留 a 的顺序）。 */
function intersect(a: readonly ResourceId[], b: readonly ResourceId[]): ResourceId[] {
  const setB = new Set(b);
  const out: ResourceId[] = [];
  const seen = new Set<ResourceId>();
  for (const r of a) {
    if (setB.has(r) && !seen.has(r)) {
      seen.add(r);
      out.push(r);
    }
  }
  return out;
}

shadow    writes=[shadowMap]
gbuffer   writes=[normal, albedo]
lighting  reads=[shadowMap, normal, albedo]   writes=[hdr]
post      reads=[hdr]                          writes=[ldr]
present   reads=[ldr]

$ npx vitest run src/render/framegraph/framegraph.test.ts
 ✓ 数据流依赖只有 RAW，方向是写者到读者
 ✓ hazard 按声明顺序分成 RAW / WAR / WAW 三类
 ✓ 拓扑序把写者排在读者之前（即使读者先声明）
 ✓ 互相读写同一资源形成真依赖环时抛错
 ✓ Pass 名字重复直接拒绝
 ✓ 跨两个 Pass 的纹理生命周期覆盖两段
 ✓ 只写不读的资源末次使用等于首次写
 Test Files  1 passed (1)
      Tests  7 passed (7)