《游戏引擎实现原理》9.3 实例化与合批

// file: src/render/sort/batch.ts
// tier: L1
// verify: node src/render/sort/batch.ts
//
// helio 渲染卷 9.3：实例化与合批。
// 9.1 的键按 (pipeline, material) 分组，同一网格仍可能被拆成多次绘制。
// 这里换一条「批次键」：material 移出键、改按 (pipeline, mesh) 分组，材质
// 参数下沉为每实例数据；随后把连续同组的绘制并成一次实例化绘制。
// 纯计算（L1），Node 26 直跑：node src/render/sort/batch.ts
import { radixSortKeys } from './sort-key.ts';

export const BatchMode = { opaque: 0, alphaTest: 1, transparent: 2 } as const;
export type BatchMode = (typeof BatchMode)[keyof typeof BatchMode];

/** 参与合批的渲染项：材质已下沉为每实例属性，故这里只有 pipeline + mesh。 */
export type BatchItem = {
  readonly pipelineId: number;
  readonly meshId: number;
  readonly mode: number; // BatchMode
  readonly depth: number;
};

/** 批次键布局：mode 2 | pipeline 6 | mesh 10 | depth 14（32 位）。 */
export const BATCH_KEY_LAYOUT = { mode: 2, pipeline: 6, mesh: 10, depth: 14 } as const;
const DEPTH_MAX = (1 << 14) - 1;
const PIPELINE_MASK = (1 << 6) - 1; // 64
const MESH_MASK = (1 << 10) - 1; // 1024

/** 打包批次键：高 18 位决定「能否同一批实例化」，低 14 位是批内深度序。 */
export function packBatchKey(it: BatchItem): number {
  const dq = Math.min(DEPTH_MAX, Math.max(0, Math.round(it.depth * DEPTH_MAX)));
  const df = it.mode === BatchMode.transparent ? DEPTH_MAX - dq : dq;
  const key = ((it.mode & 3) << 30) | ((it.pipelineId & PIPELINE_MASK) << 24) |
    ((it.meshId & MESH_MASK) << 14) | df;
  return key >>> 0;
}

/** 一次实例化绘制：一批共享 pipeline+mesh 的实例，按 firstInstance 连续排布。 */
export type InstancedDraw = {
  readonly pipelineId: number;
  readonly meshId: number;
  readonly mode: number;
  readonly firstInstance: number;
  readonly instanceCount: number;
};

/**
 * 扫描按键排好序的下标序列，把连续的 (mode, pipeline, mesh) 相同项并成一批。
 * 返回的每一批对应后端的一次 drawIndexed(..., instanceCount)。
 */
export function buildBatches(items: readonly BatchItem[], order: Uint32Array): InstancedDraw[] {
  const draws: InstancedDraw[] = [];
  let i = 0;
  while (i < order.length) {
    const first = items[order[i]!]!;
    let j = i + 1;
    while (j < order.length) {
      const it = items[order[j]!]!;
      if (it.mode !== first.mode || it.pipelineId !== first.pipelineId || it.meshId !== first.meshId) break;
      j++;
    }
    draws.push({
      pipelineId: first.pipelineId, meshId: first.meshId, mode: first.mode,
      firstInstance: i, instanceCount: j - i,
    });
    i = j;
  }
  return draws;
}

/** 汇总：绘制次数、总实例数、最大/平均每批实例数。 */
export function summarize(draws: readonly InstancedDraw[]):
  { drawCalls: number; totalInstances: number; maxInstances: number; avgInstances: number } {
  let total = 0;
  let max = 0;
  for (const d of draws) {
    total += d.instanceCount;
    max = Math.max(max, d.instanceCount);
  }
  return {
    drawCalls: draws.length,
    totalInstances: total,
    maxInstances: max,
    avgInstances: draws.length === 0 ? 0 : total / draws.length,
  };
}

/** 确定性伪随机，取代 Math.random。 */
export function hashUnit(i: number, seed: number): number {
  let h = Math.imul(i ^ seed, 374761393);
  h = Math.imul(h ^ (h >>> 13), 1274126177);
  h ^= h >>> 16;
  return (h >>> 0) / 4294967296;
}

/** 造一批渲染项：mesh 均匀分布在 meshes 个网格上，mesh 与 pipeline 一一对应。 */
export function makeBatchItems(count: number, seed: number, meshes: number, transparentRate: number): BatchItem[] {
  const items: BatchItem[] = new Array(count);
  for (let i = 0; i < count; i++) {
    const meshId = Math.floor(hashUnit(i, seed + 1) * meshes);
    items[i] = {
      pipelineId: meshId % 32,
      meshId,
      mode: hashUnit(i, seed) < transparentRate ? BatchMode.transparent : BatchMode.opaque,
      depth: hashUnit(i, seed + 2),
    };
  }
  return items;
}

if ((import.meta as { main?: boolean }).main) {
  const N = 200000;
  console.log(`items ${N}  draw calls: naive ${N}（每对象一次）`);
  console.log('meshes   draws    cut     avgInst  maxInst');
  for (const meshes of [8, 64, 256, 1024]) {
    const items = makeBatchItems(N, 21, meshes, 0);
    const order = radixSortKeys(Uint32Array.from(items, packBatchKey), N);
    const r = summarize(buildBatches(items, order));
    console.log(
      `${String(meshes).padStart(6)}  ${String(r.drawCalls).padStart(7)}  ` +
      `${(N / r.drawCalls).toFixed(0).padStart(5)}x  ${r.avgInstances.toFixed(1).padStart(7)}  ${String(r.maxInstances).padStart(7)}`,
    );
  }
  // 透明通道：即使同一网格，也必须逐实例按深度排，实例化收益随之缩水。
  const tItems = makeBatchItems(N, 21, 64, 1);
  const tOrder = radixSortKeys(Uint32Array.from(tItems, packBatchKey), N);
  console.log(`transparent-only  draws ${summarize(buildBatches(tItems, tOrder)).drawCalls}  (全透明场景，mesh 64)`);
}

items 200000  draw calls: naive 200000（每对象一次）
meshes   draws    cut     avgInst  maxInst
     8        8  25000x  25000.0    25513
    64       64   3125x   3125.0     3270
   256      256    781x    781.3      874
  1024     1024    195x    195.3      239
transparent-only  draws 64  (全透明场景，mesh 64)

// file: shaders/instanced-quads.wgsl
// tier: L2
// verify: node tools/run-l2.mjs src/render/sort/instanced-draw.ts
//
// 9.3 的实例化绘制：一个单位四边形，靠 @builtin(instance_index) 索引存储缓冲
// 里的每实例数据（偏移 + 颜色），一次 draw(6, 4) 画出 4 个彩色方块。

struct Instance {
  offset: vec2<f32>, // @0
  color: vec4<f32>,  // @16（vec4 需 16 字节对齐，故 offset 后补 8 字节）
};

@group(0) @binding(0) var<storage, read> instances: array<Instance>;

struct VSOut {
  @builtin(position) pos: vec4<f32>,
  @location(0) color: vec4<f32>,
};

@vertex
fn vs(@builtin(vertex_index) vi: u32, @builtin(instance_index) ii: u32) -> VSOut {
  var quad = array<vec2<f32>, 6>(
    vec2<f32>(0.0, 0.0), vec2<f32>(1.0, 0.0), vec2<f32>(0.0, 1.0),
    vec2<f32>(0.0, 1.0), vec2<f32>(1.0, 0.0), vec2<f32>(1.0, 1.0),
  );
  let inst = instances[ii];
  let local = quad[vi] * 0.5 + inst.offset; // 缩到半个象限，再平移到该实例的 offset
  var o: VSOut;
  o.pos = vec4<f32>(local.x * 2.0 - 1.0, local.y * 2.0 - 1.0, 0.0, 1.0);
  o.color = inst.color;
  return o;
}

@fragment
fn fs(in: VSOut) -> @location(0) vec4<f32> {
  return in.color;
}

// file: src/render/sort/instanced-draw.ts
// tier: L2
// verify: node tools/run-l2.mjs src/render/sort/instanced-draw.ts
//
// helio 渲染卷 9.3：实例化绘制的 L2 验收。
// 一次 draw(6, 4) 用 @builtin(instance_index) 画出 4 个彩色方块，各占一个象限，
// 渲染到 8x8 纹理后 copyTextureToBuffer 回读，逐象限核对颜色。
// 需 headless Chromium + 本地 http 服务（navigator.gpu 只在安全上下文可用）。

export interface L2Check { readonly name: string; readonly ok: boolean; readonly detail: string }
export interface L2Result {
  readonly checks: L2Check[];
  readonly data: Record<string, unknown>;
}

// 每实例 8 个 float：offset.xy + 2 个补齐 + color.rgba（对齐 WGSL 的 32 字节 stride）。
const INSTANCES = new Float32Array([
  0.0, 0.0, 0, 0, 1, 0, 0, 1, // 红 @ 左下
  0.5, 0.0, 0, 0, 0, 1, 0, 1, // 绿 @ 右下
  0.0, 0.5, 0, 0, 0, 0, 1, 1, // 蓝 @ 左上
  0.5, 0.5, 0, 0, 1, 1, 0, 1, // 黄 @ 右上
]);
const COUNT = 4;

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 (await fetch('/shaders/instanced-quads.wgsl')).text();
  const module = device.createShaderModule({ code: wgsl });
  const info = await module.getCompilationInfo();
  const errs = info.messages.filter((m) => m.type === 'error')
    .map((m) => `${m.lineNum}:${m.linePos} ${m.message}`);
  push('wgsl 编译 0 error', errs.length === 0, errs.join('; ') || 'no diagnostics');

  const pipeline = device.createRenderPipeline({
    layout: 'auto',
    vertex: { module, entryPoint: 'vs' },
    fragment: { module, entryPoint: 'fs', targets: [{ format: 'rgba8unorm' }] },
    primitive: { topology: 'triangle-list' },
  });
  const instBuf = device.createBuffer({
    size: INSTANCES.byteLength,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,
  });
  device.queue.writeBuffer(instBuf, 0, INSTANCES);
  const bind = device.createBindGroup({
    layout: pipeline.getBindGroupLayout(0),
    entries: [{ binding: 0, resource: { buffer: instBuf } }],
  });

  const width = 8, height = 8, bytesPerRow = 256; // copyTextureToBuffer 要求 256 对齐
  const tex = device.createTexture({
    size: [width, height], format: 'rgba8unorm',
    usage: GPUTextureUsage.RENDER_ATTACHMENT | GPUTextureUsage.COPY_SRC,
  });
  const rb = device.createBuffer({
    size: bytesPerRow * height,
    usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ,
  });

  const enc = device.createCommandEncoder();
  const pass = enc.beginRenderPass({
    colorAttachments: [{
      view: tex.createView(),
      clearValue: { r: 0, g: 0, b: 0, a: 1 },
      loadOp: 'clear', storeOp: 'store',
    }],
  });
  pass.setPipeline(pipeline);
  pass.setBindGroup(0, bind);
  pass.draw(6, COUNT); // 6 个顶点 × 4 个实例 = 一次绘制
  pass.end();
  enc.copyTextureToBuffer({ texture: tex }, { buffer: rb, bytesPerRow }, [width, height]);
  device.queue.submit([enc.finish()]);

  await rb.mapAsync(GPUMapMode.READ);
  const px = new Uint8Array(rb.getMappedRange().slice(0));
  rb.unmap();
  device.destroy();

  const at = (x: number, y: number): number[] =>
    Array.from(px.slice(y * bytesPerRow + x * 4, y * bytesPerRow + x * 4 + 4));
  const tl = at(2, 2), tr = at(6, 2), bl = at(2, 6), br = at(6, 6);
  data.quadrants = { tl, tr, bl, br };

  // 四个象限中心应各是一种纯色（输出值 0/1 映射到 8bit 精确 0/255）。
  const eq = (a: number[], b: number[]): boolean => a.every((v, i) => v === b[i]);
  push('右上=黄', eq(tr, [255, 255, 0, 255]), JSON.stringify(tr));
  push('左上=蓝', eq(tl, [0, 0, 255, 255]), JSON.stringify(tl));
  push('右下=绿', eq(br, [0, 255, 0, 255]), JSON.stringify(br));
  push('左下=红', eq(bl, [255, 0, 0, 255]), JSON.stringify(bl));
  push('一次绘制 4 实例', true, `draw(6, ${COUNT})`);
  return { checks, data };
}

PASS  wgsl 编译 0 error  no diagnostics
PASS  右上=黄  [255,255,0,255]
PASS  左上=蓝  [0,0,255,255]
PASS  右下=绿  [0,255,0,255]
PASS  左下=红  [255,0,0,255]
PASS  一次绘制 4 实例  draw(6, 4)