piet-gpu 进度：裁剪

作者:糖果
发布时间:2024-04-21 07:23:57 (3天前)
来源:https://raphlinus.github.io

这篇文章解释了它是如何工作的。这是一段相当长的旅程——实际上我一年多前就开始了这个草稿。从那以后，我不得不想出一个基本的新并行算法。它终于完成了。我认为剪辑是 piet-gpu 与其他 2D 渲染引擎不同的核心。

什么是剪辑？
裁剪的基本思想很简单，但它对整个成像模型的影响却是深远的。一方面，它引入了一个树形结构，而没有裁剪的绘图可以看作是层的线性序列。实现纯矢量裁剪有多种不同的方法，但我所采用的方法可以概括为混合，即下一个。

使用矢量路径进行剪辑会影响剪辑节点的所有子对象的绘制。路径内的点被绘制，路径外的点不被绘制。
![](/user/files/65nQoxmIPzV9i1zki5sTwqosuyRobydi3TSqsX7gQQo.png)
对于纯矢量路径剪辑，应用于每个（叶）绘图节点的有效剪辑是树上所有剪辑路径的交集。因此，一种可行的实现是在向量空间中进行路径交叉。但是，布尔路径操作很难实现，并且只有 CPU 实现是已知的；至少可以说，将它们移到 GPU 上会很困难。

相反，我们将（抗锯齿）裁剪视为混合操作——事实上，它是Porter-Duff “源输入”合成操作符的一个实例。从概念上讲，剪辑的子项被渲染到一个临时的、最初清晰的缓冲区中，剪辑蒙版被渲染到一个 alpha 通道中，然后临时缓冲区被合成在背景上，alpha 通道乘以蒙版。这种方法可以完全在 GPU 上完成，并且混合操作可以泛化。

Clips可以任意嵌套；一个剪辑节点可以是另一个剪辑节点的子节点。因此，一个完整的 2D 场景实际上是一棵树，它深刻地影响着绘图的方式。

边界框
2D 渲染中的一种常用技术是为每个绘图操作分配一个边界框。边界框是一个封闭的矩形（希望是紧凑的），因此绘图操作只影响矩形内的像素。为了渲染目标表面的任何子区域，可以忽略其边界框不与该边界框相交的任何对象。Piet-gpu 广泛使用边界框来组织并行绘图，首先是 256x256 像素箱，然后是 16x16 像素图块。边界框利用了大多数 2D 绘图是稀疏的这一事实，因为大多数绘图对象不接触大多数图块。

边界框当然与剪裁相互作用。树中的每个剪辑节点都有一个边界框，由相应的剪辑路径计算得出。然后，树中所有后代的边界框与该边界框相交。另一种表述方式是，绘图对象的裁剪边界框是对象自己的边界框，与从该节点到树根的路径中的所有裁剪路径的边界框相交。

计算这些边界框比渲染对象的工作量少，但不是免费的。特别是，我们希望在 GPU 而不是 CPU 上完成这项工作。

每瓦片优化
每块优化让事情变得更加有趣。piet-gpu 渲染管道被组织为一系列阶段，最后为目标中的每个 16x16 tile 编写一个 per-tile 命令列表（有时称为“tape”）。最后一个阶段是“精细光栅化”，它为图块中的所有像素播放这些命令。在一个 tile 中没有控制流；所有命令都针对所有像素进行评估。

在一般情况下，剪辑呈现如下。精细光栅器维护一堆每像素状态，特别是当前像素和混合堆栈。当前像素最初是透明的（alpha = 0）或背景色，普通绘图对象会合成到它上面（通常使用Porter-Duff “over”）。操作将BeginClip当前像素推送到混合堆栈上。剪辑的子项被渲染，合成到当前像素中。然后，在匹配EndClip时，剪辑蒙版被渲染为 alpha 蒙版，使用“source in”（基本上将 alpha 与蒙版相乘）与当前像素合成，然后合成该结果（Porter-Duff “over”）混合堆栈的顶部（弹出），成为新的当前像素。

然而，很多时候，我们不需要一般情况。Piet-gpu 渲染工作由 16x16 像素瓦片。流水线中的早期阶段计算应该在图块中发生的情况，最后阶段（精细光栅化）对图块中的所有像素执行一系列绘图操作。这让我们有机会进行一些优化。

特别是，放大单个图块时，剪辑路径可能处于以下三种状态之一：零覆盖、部分覆盖或完全覆盖。部分覆盖仅发生在剪辑路径与图块相交的情况下。完全覆盖适用于完全在剪辑路径内的图块，零覆盖适用于剪辑路径外的图块。
![](/user/files/B1L15sD0nwGYehfAANXxvQnDWL0mlojb7wEWQKU1h2M.png)
掩码计算和合成只需要对部分覆盖图块进行（上图中显示为灰色）。其他的可以更有效地渲染。零覆盖图块抑制子节点的渲染，基本上从BeginClip到对应的EndClip. 并且全覆盖图块基本上是无操作的；不需要渲染遮罩，并且渲染子节点，就好像没有有效的剪辑一样。

剪辑边界框的 GPU 计算
之前的迭代计算了由 CPU 完成的边界框。piet-gpu 的一个主要目标是将尽可能多的计算转移到 GPU 上。

基本任务是为每个绘制对象分配一个边界框矩形，该矩形包含所有封闭剪辑的交集。场景的线性化表示将具有一个BeginClip元素和一个EndClip元素。BeginClip还将引用路径，并且该路径具有关联的边界框。

以下是该计算的样子，作为一种顺序算法：
```java
stack = [viewport_bbox]
for element in scene:
    if element is BeginClip(path):
        stack.push(intersect(stack.last(), path.bbox()))
        element.effective_bbox = stack.last()
    elif element is EndClip:
        element.effective_bbox = stack.last()
        stack.pop()
    else:
        element.effective_bbox = intersect(stack.last(), element.bbox())
```
作为一种顺序算法，这非常简单，几乎是微不足道的。有一堆边界框，该堆栈的大小受最大嵌套深度的限制。处理每个元素的成本也是 O(1)。唯一的问题是，你真的，真的不想在 GPU 上运行顺序算法。

这就提出了一个问题：有没有办法制作这个算法的并行版本，在实际的 GPU 硬件上高效运行？至少一年来，这个问题一直是我的主要困扰。我很高兴地说，答案是肯定的。我已经做到了。

我的解决方案的核心是我所说的堆栈 monoid，它是经过充分研究的括号匹配问题的变体。我写了一篇关于stack monoid revisited的早期版本的博客。从那时起，我制作了一个改进版本，其峰值性能几乎提高了 5 倍，而且便携性也更好。我不打算在这篇博文中详细介绍，我只会说解决方案可以通过魔法获得，并专注于 2D 渲染问题的应用程序。

基本上，我们将括号匹配的结果用于两件事。首先，每个EndClip都能够访问与对应的相同的路径和边界框数据BeginClip。特别是，这让我们可以有效地在粗光栅化中进行每块优化，因为该着色器不需要保持重要状态。其次，它计算到根路径上所有剪辑边界框的交集。幸运的是，矩形交集是一个幺半群，所以它是可能的

流压缩
本节是一个可以跳过的细节，但可能对编写更高级 GPU 算法的人感兴趣。

最初的piet-gpu 设计使用“结构数组”方法来描述场景，特别是具有固定大小元素的单个数组，每个元素都是各种绘图元素类型的标记联合，包括路径段。处理这个数组基本上需要一个大的 switch 语句来处理联合中的变体。我曾考虑在这个数组上做一个堆栈 monoid，但非常担心为这个数组中的每个元素计算堆栈 monoid 的性能成本。我现在有一个非常快速的堆栈 monoid 实现，但即便如此，我也重新设计了架构，所以这不是问题。

新架构（在新元素处理管道问题中有详细描述）更像是一种“数组结构”方法，由于其性能优势，它在图形和游戏世界中非常流行。每个主要数据类型都有自己的流。此外，该类型的大部分逻辑都被转移到它自己的着色器调度中，它只在该类型的对象上批量工作，没有大的 switch 语句。为了将它们拼接在一起，我们在这些流中使用了一堆索引，这些索引是使用计数的前缀总和计算的。
![](/user/files/wHkEf3lPEIFCayW4qffRfte2xYzcVP1Guwyr0uXIIFk.png)
具体来说，绘制对象阶段执行流压缩并写入剪辑流，BeginClip它是一个仅包含和EndClip对象的数组。剪辑索引是该流的索引。同时，它为每个绘制对象分配一个剪辑索引。由同一剪辑包围的一系列绘图对象都具有相同的剪辑索引。在上图中，“clips”数组表示由绘图对象阶段写入的剪辑流。将场景的不同部分关联在一起的箭头也在绘制对象阶段使用前缀和进行计算。

然后，剪辑阶段对剪辑流中的剪辑进行括号匹配和 bbox 交集。完成后，它为剪辑流中的每个对象分配一个边界框，与路径处理阶段已经计算的剪辑路径的边界框相交，以生成剪辑边界框。它还将路径设置EndClip为引用与对应的相同路径BeginClip。

因此，剪辑阶段的工作与场景中剪辑的数量成正比，而不是与对象的总数成正比。这项工作需要大量剪辑才能在配置文件中显示出任何显着数量。我们使用了类似的流压缩技术来转向更紧凑的路径编码，我也计划将其应用到管道的其他部分。

剪辑和滚动
裁剪的一种应用是在 UI 中定义滚动视图的视口。这可以在 piet-gpu 中表示为带有变换节点的剪辑节点作为直接子节点，然后滚动的内容作为变换节点的子节点。与变换节点关联的平移控制滚动位置（此架构也可以进行缩放）。

piet-gpu 的设计目标是这些内容中的大部分可以被编码一次并保留，因此可以在 CPU 端用很少的工作重新组装具有不同滚动位置的新场景。在 GPU 方面，计算剪辑边界框的工作量相当小，这将能够在管道的早期剔除对象，

显然，这种方法适用于适度滚动，在这种情况下，将所有资源都驻留在 GPU 上是切实可行的。对于巨大的滚动窗口，需要一些虚拟化，资源在滚动进出视图时交换进出。即便如此，这是一个吸引人的探索方向，因为平滑滚动对于 UI 工具包来说仍然是一个挑战。

相关工作
这项工作可能与Massively Parallel Vector Graphics最相似。我们都将场景表示为扁平树，并允许任意嵌套深度。但是，他们的树算法要简单得多：对于 n 的嵌套深度，他们会进行 n 次扫描，每次都处理一层嵌套。这项工作使用了一种新算法，该算法允许任意嵌套深度而不会减慢速度。（工作因子与树的深度成正比的 GPU 树算法并不少见；例如）

在更传统的 GPU 渲染器中，进行混合的一般方法是分配一个临时纹理，渲染到其中，然后通过将四边形绘制到渲染目标中进行合成，从中间纹理中采样。GPU 为此类工作进行了高度优化，硬件支持纹理采样和合成“光栅操作”，但即便如此，它也需要主内存的流量。我相信完全不必做这项工作会更快。

这里的技术类似于 Matt Keeter 的Massively Parallel Rendering of Complex Close-Form Implicit Surfaces中的技术。剪裁与构造几何（无论是 2D 还是 3D）中的交集基本相同，并且该论文使用类似的技术来优化磁带，利用每个区域的代数简化。这些技术更通用，而这项工作更专业于 2D 渲染任务。

它现在已经过时了，但是 Adam Langley 的关于Chromium 剪辑的博客文章很有趣。正在讨论的主要问题是“合并伪影”，alpha 通道合成方法没有完全解决这个问题，但即便如此，它仍然是标准技术，主要是因为它或多或少受 W3C合成和混合规范的要求和HTML 画布绘图模型。

您是否维护具有有趣剪辑支持的 2D 渲染器？有没有我错过的好文章？让我知道，我很乐意添加链接。
下一步
这篇博文中缺少一些东西，尤其是性能数据。现在，我对 piet-gpu 的关注是让架构正确。感觉就像在融合，许多难题正在得到解决。

现在裁剪的基础设施已经到位，混合应该相对简单。大部分需要发生的是精细光栅化中的额外混合逻辑，当然还有通过管道连接相关元数据。加上径向和扫描渐变，是支持COLRv1 表情符号的两个主要部分，这是下一个重要里程碑。

1 条回复

动动手指，沙发就是你的了！

登录后才能参与评论