9.1 排序键与前后绘制
上一章 8.3 GPU 驱动的剔除与 LOD 把不可见的物体挡在了绘制列表之外。这一章处理留下来的人：它们按什么顺序被画。顺序不是美学问题——不透明物体从近到远画，能最大化 early-Z 的收益；透明物体从远到近画，才能让混合结果正确。这一节把「顺序」做成一条可运行的数据链：一个渲染项 → 一条 32 位整数键 → 一次基数排序。
在 helio 的渲染循环里，排序发生在剔除之后、命令编码之前，输出是一个 Uint32Array 下标序列。命令编码器随后按这个序列遍历可见项，逐项设置状态、发出绘制。所以排序的质量直接决定了后端的「状态切换有多碎」——这也是本章三节首尾相连的地方。
本节产出一个完整可跑的
src/render/sort/sort-key.ts（L1，Node 直跑）。文中所有耗时与前后绘制结论都来自本机实跑，数值不可移植。
本章与站内既有内容的分工
本卷只做「在 helio 的 RHI 上从零搭出来、每节跑出真实产物」，渲染算法本身不重推，一律外链：
| 既有文章 | 它负责什么 | 本节只做什么 |
|---|---|---|
/graphics-culling-visibility-systems/ | 可见性判定与剔除算法 | 把可见项压成键、排出绘制顺序 |
/graphics-clustered-forward-rendering/ | 前向渲染的光照分簇 | 只做「项 → 键 → 批」的数据管线 |
/graphics-gpu-driven-rendering-lod/ | GPU 驱动的绘制与 LOD 选择 | 在 CPU 侧排出键序，为实例化铺路 |
/graphics-render-graph/ | 帧图的依赖与执行顺序 | 帧图之下的「帧内绘制列表」排序 |
从多字段比较到一条 32 位键
最直觉的排序写法是给一个比较器，逐字段比：先比通道、再比管线、再比材质、最后比深度。它正确，但慢——每比较一次就要解引用两个对象、走四层分支。渲染器的做法是先把这几件事打包成一个整数，让比较退化成一次整数减法。
键的布局由「什么该相邻」决定。批次归属（模式、管线、材质）放高位，让同状态的项挨在一起；深度放低位，只在同一批内决定前后。本节的 32 位键自高到低切四段：
- mode 2 位：不透明 / alpha 测试 / 透明。不同通道绝不能混排，故放最高位。
- pipeline 8 位：管线切换是最贵的状态变更，让它尽早在高位分组。
- material 8 位：材质绑定组次之。
- depth 14 位：把
[0,1]的归一化视深度量化成 16384 级。不透明通道取升序（近→远），透明通道取反（远→近）。
深度只给 14 位是有代价的：16384 级在千米级场景里每级约 6 厘米，对需要严格前后序的透明物体偏粗。生产引擎常用 24 位键，或把透明通道单独用浮点深度排。这里保留 14 位，是因为它换来了一个更重要的性质——整条键落在 32 位内，可以塞进 Uint32Array，而这正是下一段基数排序快起来的前提。
还要注意「排序键」和「绘制顺序」不是一回事。键的升序只是一种约定；真正被后端消费的是排完序的下标数组，引擎随后按这个数组逐项发命令。键里放什么、放多宽，本质上是在回答一个问题：为了让相邻的绘制共享状态、为了让 early-Z 早退，我愿意牺牲多少排序精度。这一节把精度让给了「键宽度」，下一节会看到让出去的这部分值不值。
可运行产物：打包键并三种排序对拍
下面完整的 src/render/sort/sort-key.ts 给出打包函数、多字段比较器（朴素基线）、以及两把「单键排序」的尺子：Array.sort 数值比较与 LSD 基数排序。基数排序做 4 趟 × 8 位，全用 >>> 与 & 255 的整数位运算。
// file: src/render/sort/sort-key.ts
// tier: L1
// verify: node src/render/sort/sort-key.ts
//
// helio 渲染卷 9.1：排序键与前后绘制。
// 把渲染项压进一个 32 位整数键，用「单键排序」替代「多字段比较器排序」，
// 再用 LSD 基数排序（整数位运算）替代 Array.prototype.sort。纯计算（L1），
// Node 26 直跑：node src/render/sort/sort-key.ts
/** 绘制通道：占键的最高 2 位。 */
export const SortMode = { opaque: 0, alphaTest: 1, transparent: 2 } as const;
export type SortMode = (typeof SortMode)[keyof typeof SortMode];
export type RenderItem = {
readonly pipelineId: number;
readonly materialId: number;
readonly meshId: number;
readonly mode: number; // SortMode
readonly depth: number; // 归一化视深度 [0,1]，0 = 最近
};
/** 32 位键的字段布局（自高到低）：mode 2 | pipeline 8 | material 8 | depth 14。 */
export const KEY_LAYOUT = { mode: 2, pipeline: 8, material: 8, depth: 14 } as const;
const DEPTH_MAX = (1 << 14) - 1; // 16383
const PIPELINE_MAX = (1 << 8) - 1; // 255
const MATERIAL_MAX = (1 << 8) - 1; // 255
/**
* 打包成 Uint32 键：mode/pipeline/material 高 18 位决定「批次归属」，
* depth 低 14 位决定同批内的前后顺序。透明通道把深度取反（远→近）。
*/
export function packKey(it: RenderItem): number {
const dq = Math.min(DEPTH_MAX, Math.max(0, Math.round(it.depth * DEPTH_MAX)));
const df = it.mode === SortMode.transparent ? DEPTH_MAX - dq : dq;
const key = ((it.mode & 3) << 30) | ((it.pipelineId & PIPELINE_MAX) << 22) |
((it.materialId & MATERIAL_MAX) << 14) | df;
return key >>> 0;
}
/** 多字段比较器排序：不做键打包的「朴素」基线，用于对照。 */
export function compareItems(a: RenderItem, b: RenderItem): number {
if (a.mode !== b.mode) return a.mode - b.mode;
if (a.pipelineId !== b.pipelineId) return a.pipelineId - b.pipelineId;
if (a.materialId !== b.materialId) return a.materialId - b.materialId;
const d = a.mode === SortMode.transparent ? b.depth - a.depth : a.depth - b.depth;
return d < 0 ? -1 : d > 0 ? 1 : 0;
}
/** LSD 基数排序：4 趟 × 8 位覆盖 32 位键，全整数位运算，不做任何浮点除法。 */
export function radixSortKeys(keys: Uint32Array, count: number): Uint32Array {
let src = new Uint32Array(count);
for (let i = 0; i < count; i++) src[i] = i;
let dst = new Uint32Array(count);
const hist = new Uint32Array(256);
for (let pass = 0; pass < 4; pass++) {
hist.fill(0);
const sh = 8 * pass;
for (let i = 0; i < count; i++) {
const b = (keys[src[i]!]! >>> sh) & 255;
hist[b] = hist[b]! + 1;
}
let sum = 0;
for (let b = 0; b < 256; b++) {
const c = hist[b]!;
hist[b] = sum;
sum += c;
}
for (let i = 0; i < count; i++) {
const s = src[i]!;
const b = (keys[s]! >>> sh) & 255;
dst[hist[b]!] = s;
hist[b] = hist[b]! + 1;
}
const t = src;
src = dst;
dst = t;
}
return src;
}
/** 单键比较排序：Array.prototype.sort + 一次整数减法，做基数排序的对照。 */
export function compareSortKeys(keys: Uint32Array, count: number): Uint32Array {
const arr = Array.from({ length: count }, (_, i) => i);
arr.sort((a, b) => keys[a]! - keys[b]!);
return Uint32Array.from(arr);
}
/** 确定性伪随机：同一 (i, seed) 永远同值，取代 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;
}
/** 造一批渲染项：pipeline/material 落在 8 位键字段内，5% 走透明通道。 */
export function makeItems(count: number, seed: number): RenderItem[] {
const items: RenderItem[] = new Array(count);
for (let i = 0; i < count; i++) {
items[i] = {
pipelineId: Math.floor(hashUnit(i, seed + 1) * (PIPELINE_MAX + 1)),
materialId: Math.floor(hashUnit(i, seed + 2) * (MATERIAL_MAX + 1)),
meshId: Math.floor(hashUnit(i, seed + 3) * 256),
mode: hashUnit(i, seed) < 0.05 ? SortMode.transparent : SortMode.opaque,
depth: hashUnit(i, seed + 4),
};
}
return items;
}
/** 判定下标序列是否真的按键非降序。 */
export function isSorted(keys: Uint32Array, order: Uint32Array): boolean {
for (let i = 1; i < order.length; i++) if (keys[order[i - 1]!]! > keys[order[i]!]!) return false;
return true;
}
if ((import.meta as { main?: boolean }).main) {
const N = 200000;
const items = makeItems(N, 11);
const keys = new Uint32Array(N);
for (let i = 0; i < N; i++) keys[i] = packKey(items[i]!);
const time = (f: () => void): number => {
let best = Infinity;
for (let r = 0; r < 5; r++) {
const t0 = performance.now();
f();
best = Math.min(best, performance.now() - t0);
}
return best;
};
let naiveOrder: Uint32Array = new Uint32Array(N);
const tNaive = time(() => {
const arr = Array.from({ length: N }, (_, i) => i);
arr.sort((a, b) => compareItems(items[a]!, items[b]!));
naiveOrder = Uint32Array.from(arr);
});
let keyOrder: Uint32Array = new Uint32Array(N);
const tKeySort = time(() => {
keyOrder = compareSortKeys(keys, N);
});
let radixOrder: Uint32Array = new Uint32Array(0);
const tRadix = time(() => {
radixOrder = radixSortKeys(keys, N);
});
// 前后绘制只在同一「批次」（mode+pipeline+material）内成立：组内量化深度单调。
let mono = true;
let prev = -1;
let gMode = -1;
let gPipe = -1;
let gMat = -1;
for (let i = 0; i < N; i++) {
const it = items[radixOrder[i]!]!;
if (it.mode !== gMode || it.pipelineId !== gPipe || it.materialId !== gMat) {
gMode = it.mode;
gPipe = it.pipelineId;
gMat = it.materialId;
prev = -1;
}
const dq = Math.round(it.depth * DEPTH_MAX);
if (it.mode === SortMode.opaque && dq < prev) mono = false;
if (it.mode === SortMode.transparent && prev >= 0 && dq > prev) mono = false;
prev = dq;
}
const f = (n: number) => n.toFixed(2);
console.log(`items ${N} (pipeline<=${PIPELINE_MAX} material<=${MATERIAL_MAX})`);
console.log(`naive cmp ${f(tNaive)} ms sorted=${isSorted(keys, naiveOrder)}`);
console.log(`keysort cmp ${f(tKeySort)} ms sorted=${isSorted(keys, keyOrder)}`);
console.log(`radix 32b ${f(tRadix)} ms sorted=${isSorted(keys, radixOrder)}`);
console.log(`radix/naive ${f(tNaive / tRadix)}x radix/keysort ${f(tKeySort / tRadix)}x`);
console.log(`opaque-near-to-far ${mono}`);
}
在 /tmp/enginebook 里 node src/render/sort/sort-key.ts（本机实测，数值不可移植）：
items 200000 (pipeline<=255 material<=255)
naive cmp 102.02 ms sorted=true
keysort cmp 55.90 ms sorted=true
radix 32b 2.97 ms sorted=true
radix/naive 34.30x radix/keysort 18.80x
opaque-near-to-far true
三种排序都通过了「结果按键非降序」的断言，说明它们排的是同一件事。差别在耗时：多字段比较器 102.02 ms，单键比较 55.90 ms，而基数排序 2.97 ms——比朴素比较器快 34.30 倍，比单键比较也快 18.80 倍。最后一行 opaque-near-to-far true 是对前后绘制的正面验收：在同一批次内，不透明项的量化深度确实非降。
读这组数字时要留意两点。第一，naive cmp 与 keysort cmp 都是 Array.sort，唯一差别是「比四个字段」还是「比一个整数」，却差了近一倍——这印证了键打包本身就是第一层优化。第二，三者都用同一份 items 与同一颗 seed，sorted=true 是对全部三项各自断言的结果，不是抽样。数字是单机单次的代表值，换机器会变，但「基数排序 > 单键比较 > 多字段比较」这个次序在本机是稳定的。
为什么基数排序能快两个数量级
Array.prototype.sort 在 V8 里是 TimSort，每次比较都要回调进 JS 函数，20 万项约需 340 万次比较，每次都是一次带分支的函数调用。基数排序反过来：它从不比较两个键，只做「数一遍桶、按桶搬一遍」。4 趟 × 20 万 = 80 万次读写，每次是一个 >>> 加一个数组下标，且全部在 Uint32Array 上做——没有装箱、没有对象解引用。
这里藏着一个很容易踩的坑：基数排序要快，键就必须是 32 位整数。如果把同一套逻辑写成 48 位、用 Math.floor(key / 2 ** (8 * p)) % 256 逐字节取——数值仍然正确，但因为键被迫存进 Float64Array、每字节都要做一次浮点除法，本机实测会从 2.97 ms 涨到近百毫秒，优势荡然无存。这也是为什么本节的键宁可把深度压到 14 位，也要留在 32 位里。
另一件常被忽略的事是稳定性。LSD 基数排序天生稳定：同一批次内深度相同的两项，排序后会保持它们在列表里的原有相对次序。对渲染来说这很关键——两个共面物体谁先画，若每帧结果不同，就会闪出可复现性极差的 z-fighting。Array.prototype.sort 在现代 V8 里也是稳定的，但一旦你换成自写的快排或不稳定的堆排，这一层保证就没了。本节的实现刻意只依赖基数排序的稳定性，不去赌比较排序的偶然行为。
小结
这一节把「绘制顺序」压缩成了一个整数问题：一条 32 位键编码了通道、管线、材质与深度，排序退化成一次整数减法，而基数排序把它进一步降到「数桶 + 搬运」。剔除决定了画什么，排序决定了按什么次序画。
值得一提的是，排序与剔除共用同一份「可见项列表」，两者都不碰 GPU——它们纯 CPU、纯数据，因此这一整节的产物可以在 Node 里逐行验证，不需要浏览器。本卷后面凡是「决定发什么命令」的阶段，几乎都保持这个性质；只有真正落到命令编码与像素时，才会需要 L2 的渲染验收。
这也解释了为什么本节没有 WGSL：排序根本不进着色器。它唯一的「产物」就是那个下标数组，以及一组可以复算的耗时数字。
排序只解决了一半——它让同状态的项挨在一起，但挨在一起不等于省下了状态设置。下一节写一个状态缓存，看它能砍掉多少次冗余的后端调用，以及它砍不掉的又是哪一部分。
阅读导航：上一节：回到目录 · 下一节：9.2 状态缓存与冗余剔除 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。