frontend 设计

设计目标

前端是 3D 场景不再是 3D 的地方。它负责所有输出都相同的每一步（模型与视图变换、投影、可见性、光照和阴影），并交给后端一个由屏幕空间三角形组成的扁平列表，每个三角形一个亮度。这样一来，一个下午就能写出一个后端：它只需决定给定亮度的三角形在其设备上是什么样子。同一边界还让 TUI、Canvas 和 SVG 后端能从同一个 DrawList 显示相同的画面。

数学背景

管线

对每个网格顶点为 $p$、模型矩阵为 $M$ 的对象，以及视图矩阵为 $V$、投影为 $\pi$ 的相机（见 view 设计），build_draw_list 计算

$$p_w = M p,\qquad p_c = V p_w,\qquad (x_s, y_s, z) = \pi(p_c),$$

并对每个相机空间法向量为 $\hat n_F$、中心为 $c_F$ 的面 $F$ 计算：

$$\text{emit } F \iff \hat n_F \cdot (0 - c_F) > 0,\qquad I_F = \max(0, \hat n_F \cdot \ell_c)\,\big(\alpha + (1 - \alpha)\, v_F\big),$$

其中相机位于相机空间原点，$\ell_c = \operatorname{normalize}(V \ell)$ 是相机空间中的光照方向（它是方向，所以 $w = 0$），环境因子 $\alpha = 0.35$，阴影可见度 $v_F \in [0, 1]$ 见下文。由于 $V$ 是刚体运动，$\hat n_F \cdot \ell_c$ 等于世界空间中的朗伯项；在相机空间中计算可以避免第二套法向量。每个输出的四边形变为 triangulate_quad 的两个三角形，二者都带有 $I_F$。

阴影贴图

当某个其他表面位于一个点与光源之间时，该点处于阴影中。对方向光，所有光线都平行于 $\ell$，因此测试归结为在平行（正交）投影中比较沿 $\ell$ 的距离。¹1 Lance Williams 在 SIGGRAPH 1978 的 “Casting curved shadows on curved surfaces” 中提出了深度图技术。

光源相机。 设 $c$ 为场景世界空间包围盒的中心，$\rho = \max(1, \max_p \lVert p - c \rVert)$。前端把一个 Camera3 放在 $c + (2\rho + 1)\,\ell$ 处并朝向 $c$，向上方向 $= +y$（当 $|\ell \cdot y| > 0.99$ 时改用 $+z$，以免标架退化）。每个顶点都位于它前方至少 $\rho + 1$ 个单位处。在该相机空间中，$x_\ell$ 和 $y_\ell$ 是横跨光线的坐标，$z_\ell$ 是沿光线远离光源的距离。

网格。 在所有顶点于光源空间中的包围盒上（每侧外扩 $\max(0.05 \cdot \text{span}, 0.25)$），贴图铺设一个 $N \times N$ 的网格，$N = 128$：

$$X = \frac{x_\ell - x_{\min}}{x_{\max} - x_{\min}}\,(N - 1),\qquad Y = \frac{y_{\max} - y_\ell}{y_{\max} - y_{\min}}\,(N - 1).$$

深度遍。 每个对象的每个三角形（无论正面还是背面）都按下文的规则光栅化到网格中，每个纹素保留最小的 $z_\ell$（离光源最近的表面）。深度用重心坐标线性插值，这在这里是精确的：在 $c \ne 0$ 的平面 $a x + b y + c z = d$ 上，$z = (d - a x - b y)/c$ 是 $(x, y)$ 的仿射函数，而网格映射也是仿射的。

查询。 为测试世界空间中的点 $q$，前端把它朝光源移动两倍偏移量 $b$，映射到网格中，并舍入到最近的纹素 $(X^\ast, Y^\ast)$。由于光源相机的前向轴是 $-\ell$，沿 $\ell$ 移动 $2b$ 恰好使 $z_\ell$ 减小 $2b$。若该点落在网格之外、纹素为空，或者满足

$$z_\ell(q) - 2b \le D(X^\ast, Y^\ast) + b \iff z_\ell(q) \le D(X^\ast, Y^\ast) + 3b ,$$

则视其为受光，因此有效容差为 $3b$，其中 $b = \max(0.005 \cdot \text{depth span}, 10^{-4})$。

为何需要偏移。 由于网格分辨率有限而导致表面给自己投下阴影的现象称为阴影痤疮（shadow acne）。舍入到最近的纹素中心会使查询位置在每个轴上至多偏移半个纹素 $\Delta/2$，其中 $\Delta$ 是以光源空间单位计的纹素大小。如果过 $q$ 的表面在光源空间中的深度梯度为 $(z_x, z_y)$，则其所在纹素中存储的深度与 $z_\ell(q)$ 至多相差

$$|D - z_\ell(q)| \le \big(|z_x| + |z_y|\big)\,\frac{\Delta}{2} .$$

法向量与 $\ell$ 成 $\theta$ 角的面有 $\lVert (z_x, z_y) \rVert = \tan\theta$，因此在掠射入射时误差无界增长。只要 $\sqrt2\,\tan\theta\,\Delta/2 \le 3b$，容差 $3b$ 就能消除痤疮。不满足时，$\theta$ 接近 $90°$，朗伯因子 $\cos\theta$ 已使该面变暗，因此残留的痤疮难以察觉。偏移的代价是阴影在接触点处会稍晚出现（“彼得潘”现象），晚约 $3b$ = 场景深度跨度的 1.5%。

面的可见度。 前端测试每个面的中心和四个顶点并取平均：

$$v_F = \tfrac15 \sum_{q \in \{c_F, v_a, v_b, v_c, v_d\}} \mathbb{1}[q \text{ lit}] \in \{0, 0.2, 0.4, 0.6, 0.8, 1\}.$$

跨越阴影边界的面会得到一个中间值，从而以面的分辨率柔化边界，而不是在平面着色的面上画出锯齿状的边。环境项让完全处于阴影中的面保留其朗伯亮度的 $\alpha = 35\%$，使形状在阴影中依然可辨。背向光源的面不做查询；其亮度为 $0$。

基于边函数的光栅化

LumaBuffer::draw_triangle（以及使用相同规则的 TUI 和阴影贴图光栅化器）用边函数判定覆盖。对屏幕平面中的点 $a$、$b$、$p$，令

$$E(a, b; p) = (p_x - a_x)(b_y - a_y) - (p_y - a_y)(b_x - a_x),$$

它是 $p$ 的仿射函数，在直线 $ab$ 上为零，并在穿过该直线时变号；$|E(a, b; p)|$ 是三角形 $abp$ 面积的两倍。对三角形 $p_0 p_1 p_2$，令

$$A = E(p_0, p_1; p_2),\qquad w_0 = E(p_1, p_2; p),\quad w_1 = E(p_2, p_0; p),\quad w_2 = E(p_0, p_1; p).$$

每个 $w_i$ 都是 $p$ 的仿射函数，并在 $p_i$ 以外的两个顶点处为零。在 $p = p_i$ 处它等于 $A$，因为带符号面积在顶点循环置换下不变。因此 $w_0 + w_1 + w_2 - A$ 是一个在三个不共线点处为零的仿射函数，所以

$$w_0 + w_1 + w_2 = A \quad\text{for every } p, \qquad \lambda_i = \frac{w_i}{A}$$

就是 $p$ 的重心坐标（$\lambda_i(p_j) = \delta_{ij}$，$\sum \lambda_i = 1$）。点位于闭三角形内当且仅当所有 $\lambda_i \ge 0$，即所有 $w_i$ 与 $A$ 同号或为零。代码对两种符号都做测试，因此三角形在屏幕上的环绕方向无关紧要：剔除已在 3D 中完成。像素在其中心 $(x + \tfrac12, y + \tfrac12)$ 采样，只在三角形包围盒内进行，$|A| \le$ DEPTH_EPSILON 的三角形会被跳过。被覆盖像素处的深度为透视校正的 $\big(\sum \lambda_i / z_i\big)^{-1}$。

深度缓冲

set_if_closer 仅在新深度比已存深度小超过 $\varepsilon$ = DEPTH_EPSILON 时才写入像素。对已绘制的三角形做归纳：画完 $T_1, \dots, T_k$ 后，每个像素保存覆盖它的三角形中深度最小者的亮度，若有多个三角形与该深度相差在 $\varepsilon$ 以内，则保存最先绘制的那个。基础情形是深度为 $10^{30}$ 的空缓冲。归纳步中，$T_{k+1}$ 恰好在严格更近超过 $\varepsilon$ 时替换已存值。因此除了近似平局外，最终图像与绘制顺序无关，这就是绘制列表不排序的原因。

边是包含在内的，没有“左上”平局规则：恰好位于两个三角形公共边上的像素中心会被两者同时覆盖。深度测试保留其中之一。一个四边形的两个三角形亮度相同，因此这在面内部是看不出来的。

曝光与光流

快门时间为 $T$ 的相机在每个像素处记录 $\int_0^T L(x, t)\,dt$。前端用 $N$ 个渲染采样上的黎曼和来近似归一化曝光，

$$\bar L(x) = \frac1T \int_0^T L(x, t)\,dt \approx \frac1N \sum_{k=0}^{N-1} L(x, t_k),$$

由权重为 $1/N$ 的 LumaBuffer::add_weighted_sample 实现。运动的边缘会拖成运动模糊。

可选的光流对齐假设亮度恒定 $L_{\text{prev}}(x + d) \approx L_{\text{cur}}(x)$，并通过穷举块匹配逐像素估计整数位移 $d$：

$$d(x) = \operatorname*{arg\,min}_{\lVert d \rVert_\infty \le R}\ \sum_{\lVert o \rVert_\infty \le P} \big( L_{\text{prev}}(x + o + d) - L_{\text{cur}}(x + o) \big)^2 .$$

在累积之前按各自的光流扭曲每个采样（align_with_flow），会把运动内容重新对准到当前帧上，以模糊换取更清晰、重影更少的边缘。估计值是整数。它受孔径问题影响：在均匀块中任何 $d$ 都吻合，此时扫描顺序返回 $(-R, -R)$。

设计决策

绘制列表是边界

问题：三个输出模型迥异的后端（字符网格、像素画布、保留模式的 SVG 节点）必须显示同一个场景。可选方案是交给它们网格（每个后端重新实现投影和光照）、像素（SVG 后端失去矢量输出），或已投影并着色的三角形。最终选择了最后一种。DrawTriangle 恰好包含每个后端所需的东西：屏幕坐标、用于遮挡的相机深度，以及每个后端映射到自己调色板的 $[0, 1]$ 中的亮度。投影、剔除、光照和阴影只在一个地方计算一次，也只测试一次。

每个四边形平面着色

每个面一个亮度，与演示程序分面的低多边形外观和终端的粗糙分辨率相匹配，并使绘制列表保持精简。平滑着色需要 core 所没有的逐顶点法向量，以及 SVG 后端无法表达的逐像素插值亮度。

阴影放在前端

阴影需要整个场景的世界空间几何，而后端从不接触这些，因此阴影属于前端。选择阴影贴图而不是光线投射：它只需从光源视角光栅化一次场景、每个采样点一次查询，复用现有光栅化器，也不需要加速结构。分辨率固定为 128 × 128，因为每个面只采样五次可见度；更精细的贴图不会改变平面着色的输出。边界每帧都拟合到场景上，因此总能用满全部分辨率。

共享的标量缓冲

LumaBuffer 位于前端而不是某个后端中，因为有三个使用者需要带深度的标量图像：Canvas 后端、曝光累积和光流。TUI 后端为直接渲染保留自己的字符缓冲，并在曝光效果中（通过 draw_list_to_tui_luma）使用 LumaBuffer。

时间即数据

Timeline、ScalarTrack、ExposureSettings 以及光流函数都是纯数据和缓冲的函数；它们从不调用时钟。何时渲染、采样哪些时刻由演示程序决定，这使前端保持确定性且易于测试。

正确性与不变量

• 输出的三角形朝向相机（在相机空间中 $\hat n \cdot (0 - c) > 0$），当光照方向为单位向量时，其亮度位于 $[0, 1]$ 中（在舍入意义下，一个完全受光的面可能得到 $1 + 2^{-52}$）；后端会对其截断。
• 绘制列表按场景顺序逐个对象、逐个面排列；每个可见四边形对应两个三角形。
• 如上所示，LumaBuffer 在每个像素处保存覆盖它的最近三角形的值（$\varepsilon$ 平局时取最先绘制的）。
• 阴影查询从不使位于贴图之外或空纹素下的点变暗；可见度是 $0.2$ 的倍数。
• ExposureSettings 始终满足 $0 < \text{shutter} \le \text{frame\_dt}$ 且至少有一个采样；auto 恰好得到一个采样（在计算采样数之前快门已被截断）。
• Timeline::frame_count 至少为 1；采样时刻为 $k/\mathit{fps}$；进度被截断到 $[0, 1]$。

每帧开销：变换、剔除和着色为 $O(V + F)$；光栅化与每个三角形覆盖的包围盒面积成正比（阴影贴图和 LumaBuffer 都是如此）；每个受光的可见面五次阴影查询；光流为 $O(W H (2R+1)^2 (2P+1)^2)$。

被否决的方案

• 按深度排序绘制列表。 在 TUI 和 Canvas 后端中，正确的遮挡来自深度缓冲；SVG 后端因为没有深度缓冲而自行排序。在前端排序会把一种策略强加给所有后端。
• Gouraud 或 Phong 着色。 见“每个四边形平面着色”；它还会让 TUI 输出更嘈杂，而不是更好。
• 在相邻纹素上做百分比渐近过滤（PCF）。 每个面五个采样已经提供了平面着色所能显示的中间值。
• 以不同方式截断 ExposureSettings::auto。 允许快门长于一帧会让 auto 返回多个采样，但会使一帧积分了下一帧区间内的光。

边界

前端不会：

• 针对视景体或近平面裁剪几何体：所有顶点都必须位于相机前方；
• 支持点光源或聚光灯、彩色光、多个光源、材质或纹理；
• 生成字符、颜色、设备上的像素或文件；
• 在帧之间排序、批处理或缓存绘制列表；
• 估计亚像素或稠密变分光流。

Footnotes

1. Lance Williams 在 SIGGRAPH 1978 的 “Casting curved shadows on curved surfaces” 中提出了深度图技术。 ↩