文章标题:屏幕上的像素
正文: 你如何渲染一个 SVG?好吧,让我们从比 SVG 规范简单一点的地方开始:你如何渲染一组填充的贝塞尔形状?我们可以采用 Skia 的做法,把形状分解成三角形,让 GPU 来做栅格化(把它们变成屏幕像素),或者我们可以采用 Cairo 的做法,把它们展平成线段,然后由我们自己把它们变成像素。
Cairo 和 Skia 都是庞大的(10 万行以上)C/C++ 库,包含大量手工调优的算法和内存管理。但数学其实相当简单,全是些加加减减和偶尔的除法。有没有更好的方式来表达这条栅格化流水线,用一个人花几个小时就能读懂理解的代码量?
Dan Amelang 认为有,而这正是他 Gezira/Nile 项目的基础。我们可以用一种更高层的语言来表达这条流水线,他称之为 Nile,用源代码的形式,它看起来有点像这样:
DecomposeBeziers : Bezier >> EdgeSample
∀ (A, B, C)
inside = (⌊ A ⌋ = ⌊ C ⌋ ∨ ⌈ A ⌉ = ⌈ C ⌉)
if inside.x ∧ inside.y
P = ⌊ A ⌋ ◁ ⌊ C ⌋
w = P.x + 1 - (C.x ~ A.x)
h = C.y - A.y
>> (P.x + 1/2, P.y + 1/2, w × h, h)
else
ABBC = (A ~ B) ~ (B ~ C)
min = ⌊ ABBC ⌋
max = ⌈ ABBC ⌉
nearmin = | ABBC - min | < 0.1
nearmax = | ABBC - max | < 0.1
M = {min if nearmin, max if nearmax, ABBC}
<< (M, B ~ C, C) << (A, A ~ B, M)
这是一个 Nile kernel。它从队列接收 Bezier token 并发出 EdgeSample token;它还可以把 token 放回队列(一种递归)。这个 kernel 查看贝塞尔曲线,如果曲线能装进一个像素内,它就发出一个样本,否则就把它拆分,把两半都放回队列。Kernel 可以组合成更大的“流水线”。结果就是你可以得到这样一整条流水线:
Rasterize : Bezier >> CoverageSpan
⇒ DecomposeBeziers → SortBy (@x) → SortBy (@y) → CombineEdgeSamples
Bezier 从一端进去,CoverageSpan(在 x, y 处画一条长度为 l、覆盖 c% 的线)从另一端出来。
这门语言保持直接而小巧。它并非完全没有内存,kernel 可以保留自己的内部状态。所有优化、内存管理和执行的工作都在编译器里完成。
我一直在为 Nile 开发一个编译器/优化器/后端,大约有十年了。这儿做点小实验,那儿做点小实验。反复阅读源代码,把读到的可能有用的研究归档。我终于有了可以展示的东西:一只老虎。在此我要向那些在酒吧里被我这些想法无聊到的所有人道歉。
渲染整只老虎的 Nile 代码大约 300 行,其中大部分复用了 Amelang 的 Gezira。同样的 300 行编译到三个后端——JavaScript、WASM 和 WebGPU。目前的流水线非常像 Cairo 的形态,但我有兴趣做一条吐出三角形、让 GPU 干它栅格化本职工作的流水线。
这个编译器,umgeni,还非常处于开发中,而且它,呃,很有意思。
我试着用另一种我称为 mooi 的小语言来表示这门语言的语义。用 mooi 写成的 Nile 语义可以充当一种符号解释器:如果你把值传进去,它会解释这些值;如果你把符号传进去,你会得到一些 IR。它有一个小的 prelude,包含表示映射和折叠的有用函数,并针对后端能理解的十一种操作的小领域来编写。Nile 的语义(大部分!记得吧,还在开发中)只存在于少数几个 Mooi 文件里。我不知道这是不是个好主意,但我想看看能不能把 Nile 用于图形的想法扩展到 Mooi 用于编译。我们拭目以待。
要让它在合理的时间内真正把像素放到真实的屏幕上,还有若干阶段要做。
文章标题:屏幕上的像素
正文: 首先,Nile 代码会被预处理成一种没有显著空白的形式(Python 也做类似的事),然后我把它解析成 AST。
umgeni 精化器(elaborator)的工作是接收那个 AST,并从中生成一个 IR(中间表示)。它用 mooi 完成大部分工作,但它自己也会做一些内联和去函数化(defunctionalisation)替换。这个 IR 是标量化的,所有类型和结构都被抹去。在把它交给后端之前,我会做几轮优化。
我把内核“融合”在一起,去掉不必要的中间队列,并合并连续的排序。我会做一些尾调用优化,这样一来,如果一个内核的最后一步是重新入队一个 token,它就改为直接循环回去。另外,我还会运行一个 CSE(公共子表达式消除)过程,去掉不必要的赋值。最近的实验还包括一些死代码消除和常量折叠。呼。谢天谢地我去年上了那门编译器课程。
我刚加进去的最酷的东西之一是自动记忆化(memoisation),如果某些计算与上一帧相同,我就可以跳过一大串计算。这对演示帮助不大,但我认为对真实世界的使用来说它会是个很大的帮助。
我觉得这会是一个、并且已经是一个有趣的项目。而且几乎完全没用:由专家针对已知硬件模型手工调优的渲染引擎可能会快得多(但也只是快 50 倍左右而已)。
你怎么渲染一个 SVG?用 Cairo 或 Skia。但如果你想理解渲染是如何工作的,也许这个项目适合你。它也许还能让你一窥这样一种未来:系统不是由没人有足够时间在这辈子读完的百万行程序构成的,而是由聪明的编译器和你能在一个下午就搞懂的简单直接的语言构成的。
我的下一项工作是简化编译器/优化器。让它更可读、更容易理解。然后,我会把它收起来再放十年。大概还是会拿它在酒吧里让人无聊。我有没有提到过有一只老虎?
别处
在 Mastodons 上评论、分享或点赞。公开回复会显示在这里。