半透明的顺序执念：α 合成不可交换

over 算子为什么对次序敏感

半透明合成的基本算子是 over（Porter-Duff 合成）：把颜色 $c_s$、不透明度 $\alpha_s$ 的层盖在已有颜色 $C$ 上：

$C' = \alpha_s \, c_s + (1 - \alpha_s)\, C$

这个算子不满足交换律：$\mathrm{over}(A, B) \neq \mathrm{over}(B, A)$。一个具体算例，黑背景上两层 $\alpha = 0.5$ 的半透明层，$A$ 为纯红 $(1,0,0)$、$B$ 为纯蓝 $(0,0,1)$：

• 先 $B$ 后 $A$（$A$ 盖 $B$）：$C = 0.5(1,0,0) + 0.5 \times 0.5(0,0,1) = (0.5,\, 0,\, 0.25)$
• 先 $A$ 后 $B$：$C = (0.25,\, 0,\, 0.5)$

同样的两层，只是换了先后，重叠区颜色就不同。这就是”顺序就是语义”的代数原因。

不透明为什么可以乱序

令 $\alpha_s = 1$，公式退化为 $C' = c_s$——新颜色完全覆盖旧颜色，历史被抹去。于是不透明渲染只需回答”这个像素最近的表面是什么”，可以用深度缓冲（Z-buffer）解决：每个像素存一个深度，后画的片元比深度，近就覆盖，任意绘制顺序都得到同一结果。

半透明不行：每个片元的贡献都留在结果里，没有”覆盖”这回事，深度缓冲无从下刀。唯一的出路是排好序再按序合成。

错一位会怎样

under 递推里第 $i$ 层的贡献是 $c_i \alpha_i T_i$，其中透射率（transmittance）$T_i = \prod_{j<i}(1-\alpha_j)$ 依赖所有排在它前面的层。交换序列中任意两层，不只这两层自己的 $T$ 变了，它们之间所有层的 $T$ 链也全部错位——误差会沿链条传播，不是局部小扰动。

易错点

• “差不多深就不用排”不成立。深度接近的两层，交换后颜色变化量由各自的 $\alpha$ 和颜色差决定，可以很明显。
• Z-buffer 不能救半透明。它能选最近片元，但半透明需要整串片元的有序贡献。

参考

• Alpha compositing（维基百科）
• Porter & Duff, Compositing Digital Images (SIGGRAPH 1984)

over 与 under 的等价性证明

设沿视线从近到远有 $N$ 层，第 $i$ 层颜色 $c_i$、不透明度 $\alpha_i$（$i=1$ 最近）。

under：从近到远

维护累计颜色 $C$ 和透射率（transmittance）$T$，初值 $C=0,\ T=1$：

$C \mathrel{+}= c_i\,\alpha_i\, T_i, \qquad T_{i+1} = T_i\,(1-\alpha_i)$

其中 $T_i = \prod_{j<i}(1-\alpha_j)$，即”前面所有层都没挡住”的概率。展开：

$C = \sum_{i=1}^{N} c_i\,\alpha_i \prod_{j<i}(1-\alpha_j)$

over：从远到近

从最远的第 $N$ 层开始往回盖，递推是 $C_i = \alpha_i c_i + (1-\alpha_i)\, C_{i+1}$（$C_{N+1}=0$ 为背景）。展开同一递推：

$C_1 = \alpha_1 c_1 + (1-\alpha_1)\,\alpha_2 c_2 + (1-\alpha_1)(1-\alpha_2)\,\alpha_3 c_3 + \cdots = \sum_{i=1}^{N} c_i\,\alpha_i \prod_{j<i}(1-\alpha_j)$

两个递推展开成同一个式子：每项贡献是 $c_i\alpha_i$ 乘上它前方所有层的透射率之积。等价性不是近似，是同一个求和的两种扫描顺序。

等价了为什么还要选 under

工程差异在早退（early exit）：

• under 边算边衰减 $T$。当 $T < 10^{-4}$ 时，后面所有层的总贡献上限就是 $10^{-4}$ 量级，直接 break，并用 n_contrib 记下截止下标。远处的层根本不参与计算。
• over 从最远端开始，任何时刻的 $C$ 都可能被后面（更近）的层以 $\alpha_i c_i + (1-\alpha_i)C$ 改写，必须扫完全部 $N$ 层才有最终值，无法中途止损。

对百万级高斯、每个像素挂几十上百个片元的场景，早退省掉的是大片尾部计算。

早退合法性的前提

$T_i = \prod_{j<i}(1-\alpha_j)$ 只在”前方层已按序处理完”时才是真实透射率。若顺序错了，提前 break 丢掉的可能是本该挡住一切的近处层。早退契约的正确性完全押在排序正确上——这也是本集把排序当主题的原因。

参考

• 3D Gaussian Splatting for Real-Time Radiance Field Rendering (Kerbl et al., 2023)

排序键：VP 矩阵第二行

键的定义

$\mathrm{key} = \mathrm{VP}_{\text{row}\,2}\cdot (x, y, z, 1)^{\mathsf T}$

$\mathrm{VP} = P \cdot V$：$V$ 是视图矩阵（世界→相机），$P$ 是投影矩阵（相机→裁剪空间）。注意这里的”第 2 行”是从 0 数起的第三行，即裁剪空间 $z$ 所在的那一行。vksplat 的 sorter.h 里就是 SortRequest.row2 四个分量，且用双精度计算。

为什么第三行恰好是深度

透视投影矩阵的 z 行形如 $(0, 0, A, B)$——$x$、$y$ 两列全是零。于是：

$\mathrm{key} = A\, z_v + B$

$z_v$ 是相机空间的前向坐标（$z_v = \mathrm{VP}$ 中 $V$ 的第三行点乘齐次坐标，即 $-\mathbf{f}\cdot(\mathbf{p}-\mathbf{c})$，$\mathbf{f}$ 为相机前向轴，$\mathbf{c}$ 为相机位置）。结论：键是前向深度的仿射函数，横向分量 $x_v$、$y_v$ 完全不参与。相机左右横移、FOV 缩放（那些只影响 $P$ 的第 0、1 行）都污染不了深度键。

为什么不用除以 w

裁剪空间完整的深度要算 $z/w$（透视除法）。但排序只需要全序：对相机前方的点 $w>0$，裁剪空间 $z$ 随真实深度单调变化，直接比 key 即可，省掉一次除法。相机后方的点本来会被裁剪剔除，不参与排序。

稳定比精确重要

键不必是欧氏距离，也不必是精确深度——它只需要把所有高斯排成一个正确的先后序列。任何关于深度单调的函数都可以当键。这一自由度换来两个实惠：

• 键可以量化成整数（下一块的 16 位桶）而不损失次序；
• 平移时全体键同步漂移，次序不变（再下一块的零重排）。

易错点

• 行序从 0 数。“第二行”在不同资料里可能指第三行；以产出裁剪空间 $z$ 的那行为准。
• 键算的是高斯中心深度，不是逐像素深度。两个深度接近、互相穿插的高斯，在重叠区可能出现逐像素的次序翻转（popping），这是按中心排序的固有近似，不是实现 bug。
• 构造键时用双精度：两个相近大数相减（$Az_v + B$ 中 $A z_v$ 与 $B$ 的量级差）在 fp32 下容易丢有效位。

参考

• antimatter15/splat（参考实现的排序键与 counting sort）

纯平移零重排的证明

设定

键是前向深度的仿射函数（见排序键一节）：

$\mathrm{key}_i = A\, z_{v,i} + B, \qquad z_{v,i} = -\mathbf{f}\cdot(\mathbf{p}_i - \mathbf{c})$

$\mathbf{f}$ 为相机前向单位向量，$\mathbf{c}$ 为相机位置，$\mathbf{p}_i$ 为高斯中心。

平移：全体键加同一常数

相机平移向量 $\mathbf{t}$，即 $\mathbf{c} \to \mathbf{c} + \mathbf{t}$，朝向 $\mathbf{f}$ 不变：

$z'_{v,i} = -\mathbf{f}\cdot(\mathbf{p}_i - \mathbf{c} - \mathbf{t}) = z_{v,i} + \mathbf{f}\cdot\mathbf{t}$

每个键的增量都是同一个数：

$\Delta = A\,(\mathbf{f}\cdot\mathbf{t})$

$\Delta$ 不含 $i$——与哪个高斯无关。所有键整体平移，两两之差 $\mathrm{key}_i - \mathrm{key}_j$ 原封不动，排序结果可以直接复用，无需重排。特例：垂直于视线的横移有 $\mathbf{f}\cdot\mathbf{t} = 0$，键连数值都不变。

旋转：每个点各漂各的

旋转改变的是 $\mathbf{f}$ 本身。设新前向轴 $\mathbf{f}'$：

$z'_{v,i} - z_{v,i} = -(\mathbf{f}' - \mathbf{f})\cdot(\mathbf{p}_i - \mathbf{c})$

增量里有 $\mathbf{p}_i$——逐点不同。原本等键的两个高斯可能分出先后，原本的顺序可能整个翻过来。所以一转头就必须重排。

工程含义

漫游交互里平移占大头（WASD 平移、推拉镜头）。键设计把”平移”从排序触发器清单里划掉后，排序线程只在旋转帧才真正干活——这是选”前向轴投影”而不是”欧氏距离 $\|\mathbf{p}-\mathbf{c}\|$“当键的直接红利：欧氏距离在平移下逐点变化，每帧都要重排。

易错点

• “零重排”指次序不变，不是”键不变”。沿前向平移时键数值确实在动，只是动得整齐划一。
• 该结论依赖”键只含前向轴”。若键里混入 $x_v$、$y_v$ 分量，横移也会打乱次序。

counting sort（计数排序）三步手演

输入：4 个高斯 A、B、C、D，整数键 [2, 7, 2, 5]，桶编号 0–7。

第一步：计数

扫一遍输入，每桶记下落入的元素个数：

桶	2	5	7	其余
计数	2	1	1	0

第二步：独占前缀和

把计数换成每个桶的起始槽位——exclusive prefix sum（独占前缀和，不含自己）：

$\mathrm{start}[b] = \sum_{b' < b} \mathrm{count}[b']$

桶 2 从槽位 0 起，桶 5 从槽位 2 起（前面有 2 个元素），桶 7 从槽位 3 起。“独占”是关键：起始槽位恰好是”排在我前面的元素总数”，所以散射时各桶互不越界。

第三步：稳定散射

按输入原顺序 A→B→C→D 依次入槽，每放一个，该桶槽位指针加一：

元素	键	落槽	该桶指针变化
A	2	槽 0	start[2]: 0→1
B	7	槽 3	start[7]: 3→4
C	2	槽 1	start[2]: 1→2
D	5	槽 2	start[5]: 2→3

输出序列：A、C、D、B。

稳定性从哪来

同键的 A、C 输出中仍是 A 在前——因为散射严格按输入顺序进行，同桶元素先到先得连续槽位。这就是稳定（stable）排序：等键元素的相对次序保持不变。

对高斯排序这不是锦上添花：同桶意味着深度差小于量化精度，此时保持上帧或输入的相对次序，可以避免帧间无谓的次序抖动。

伪代码

count[0..k-1] = 0
for g in input:        count[key[g]]++        // ① 计数
start[0] = 0
for b in 1..k-1:       start[b] = start[b-1] + count[b-1]   // ② 独占前缀和
for g in input:        out[start[key[g]]++] = g             // ③ 稳定散射

总代价 $O(n + k)$：三遍顺序扫描，无任何比较。

参考

• Counting sort（维基百科）

十六位深度桶：65536 档够不够

量化

浮点深度键先归一化再落到整数桶：

$b = \left\lfloor \frac{\mathrm{key} - \mathrm{key}_{\min}}{\mathrm{key}_{\max} - \mathrm{key}_{\min}} \times 65536 \right\rfloor,\qquad b \in [0, 65535]$

边界要 clamp：$\mathrm{key} = \mathrm{key}_{\max}$ 的点会算出 65536，必须压回 65535，否则越界写坏计数数组。

为什么 16 位够

排序买的是次序，不是深度值本身。65536 档把深度轴切成六万多个薄片，两片以内的相邻高斯落进同桶，由 counting sort 的稳定性保持原次序——而它们的深度差小于一个量化步长，交换后对合成颜色的影响通常低于视觉阈值。再往上加位宽，只是让计数数组更大、缓存更不友好，次序几乎不再变。

为什么数数不比较

• 基于比较的排序有信息论下限 $\Omega(n \log n)$；
• counting sort 是 $O(n + k)$，$k = 65536$ 为桶数。

代入实际规模：splatfacto 成品 122.6 万高斯，比较排序约 $1.226\times10^6 \times \log_2(1.226\times10^6) \approx 2.5\times10^7$ 次比较；counting sort 约 $n + k \approx 1.3\times10^6$ 次顺序读写，差近 20 倍，且没有分支、没有随机访存，CPU 单线程就能跟上 60fps 的旋转重排。

代价是 $k$ 个桶的内存：65536 个 32 位计数器仅 256 KB，完全划算。这也是它要求键是小范围整数的原因——16 位量化既省内存又定下 $k$。

与参考实现的关系

antimatter15 的网页查看器（main.js）就是这套设计：CPU counting sort + 16 位深度桶，排完把顺序表交给 GPU 做 instanced quad 渲染。vksplat 逐字复刻该语义：CPU 常驻线程跑 counting sort，结果直写 Vulkan 映射的 order 缓冲（sorter.h/cpp）。

易错点

• 每帧的 $\mathrm{key}_{\min}/\mathrm{key}_{\max}$ 会变（场景可见范围随相机变），量化区间要随之更新，否则大批键挤进两端桶里，排序退化成稳定但粗粒度。
• 桶数 $k$ 是内存换时间的旋钮，不是精度旋钮：位宽从 16 加到 24，视觉几乎无感，内存翻 256 倍。

参考

• antimatter15/splat（CPU 16 位 counting sort 参考实现）

GPU 管线四名词

instance（实例）

一次绘制命令画出 $N$ 份同一份几何体，每份喂不同的属性数据——实例化绘制（instancing）。3DGS 查看器里几何体只是一个四边形（两个三角形，6 个顶点），每个高斯占一个实例，实例数据是位置、协方差、颜色。vksplat 就是一次 vkCmdDraw：6 顶点 × $N$ 实例，百万高斯一次 draw call 出完，避免了逐高斯一次调用的 CPU 开销。

tile（瓦片）

把屏幕切成 16×16 像素的格子，每个高斯只影响它投影覆盖的那几格。INRIA 原版 CUDA 光栅器按瓦片做 binning：先算出每个高斯碰哪些瓦片，再按”瓦片 × 深度”排序，每个线程块只处理自己瓦片内的短列表。这是论文官方实现的做法；本系列的查看器（沿 antimatter15 路线）用全局一遍排序 + instanced quad，不做逐瓦片分箱——语义更简，代价是片元阶段的过绘稍多。

fragment（片元）

光栅器把四边形覆盖到的每个像素各生成一个片元，片元着色器对每个片元求值一次：

$\alpha = o \cdot \exp(\mathrm{power})$

$o$ 是高斯不透明度，$\mathrm{power}$ 是该像素相对高斯中心的马氏距离项（EP03 的 conic 计算）。混合——$\alpha$ 与帧缓冲里已有颜色的合成——就发生在这个阶段。所以”排序”管的是实例/片的先后，“混合”发生在片元粒度。

NDC（归一化设备坐标）

Normalized Device Coordinates：裁剪空间坐标 $(x_c, y_c, z_c, w)$ 除以 $w$ 之后的结果：

$\mathrm{ndc} = (x_c/w,\; y_c/w,\; z_c/w)$

$x, y$ 一律压进 $[-1, 1]$，是光栅化的”母语”：视口变换再把 $[-1,1]^2$ 线性映射到像素坐标。除以 $w$ 这一步叫透视除法（perspective divide），近大远小就发生在这里。注意 $z$ 的范围因 API 而异：OpenGL 是 $[-1,1]$，Vulkan/D3D 是 $[0,1]$——写投影矩阵时配错会整屏消失。

一条流水线串起来

顶点着色器拿到实例数据做 EWA 投影、摆好四边形 → 裁剪空间除 $w$ 进 NDC → 光栅化出片元 → 片元着色器算 $\alpha$ 并混合。CPU 侧排好的实例顺序，保证片元按从近到远的次序到达混合单元。

参考

• Graphics pipeline（维基百科）
• 3D Gaussian Splatting (Kerbl et al., 2023)

排序 + 混合：伪代码逐段解读

课程给出的可抄最小版：

// ① 每帧:构造排序键(双精度,VP 第 2 行)
for g in gaussians: key[g] = dot(VP_row2, pos[g], 1)
// ② counting sort:计数 → 独占前缀和 → 稳定散射(近 → 远)
order = counting_sort_16bit(key)
// ③ 逐像素 under 合成(沿 order)
C = 0; T = 1
for i in order:
    α = o·exp(power); C += c·α·T; T *= (1−α)
    if T < 1e-4: n_contrib = i; break

① 构造键

VP_row2 是视图投影矩阵从 0 数起的第 2 行（产出裁剪空间 $z$ 的那行），点乘齐次坐标得到前向深度的仿射函数。用双精度算：相邻高斯键值常靠大数相减区分，fp32 有效位不够会让同序高斯随机换位。

② 排序

counting_sort_16bit 把键量化到 $[0, 65535]$ 后三步走：计数、独占前缀和、稳定散射，$O(n+k)$ 线性。输出 order 是从近到远的实例下标序列——混合循环只认这个顺序，它是早退合法性的全部前提。

③ 合成与早退契约

逐像素沿 order 做 under 递推，三个存档各有用途：

• T：透射率，$\prod(1-\alpha)$ 链。$T < 10^{-4}$ 意味着后面所有层的总贡献不超过万分之一量级，break 丢弃它们。
• C（课程里也记 acc）：累计颜色，前向的最终产物。
• n_contrib：实际参与合成的层数。它不是性能统计，是反向传播的契约——反向重放时只倒带前 n_contrib 层，截止点之后梯度严格为零。前向没碰过的层，反向也必须当作不存在，否则梯度链会和前向对不上（错位一个 $(1-\alpha)$ 因子级别的错误）。

读这堵墙容易漏的点

• 循环体里 $\alpha$ 是逐像素的（exp(power) 依赖像素位置），而 order 是逐实例的：排序按高斯中心深度一次性排好，逐像素复用。中心深度排序是近似，深度接近且互相穿插的高斯在重叠区可能逐像素次序翻转（popping），属方法固有代价。
• T *= (1−α) 必须在 C += 之后执行：第 $i$ 层的贡献用 $T_i$（不含自己），衰减后才是 $T_{i+1}$。两行对调等于每层少乘一次 $(1-\alpha)$，整体偏亮。
• 阈值 $10^{-4}$ 是画质/性能权衡：调大更省算力但暗部尾部细节被截；调小趋于精确但早退收益缩水。

参考

• 3D Gaussian Splatting for Real-Time Radiance Field Rendering (Kerbl et al., 2023)