最近，piet gpu朝着实现其愿景迈出了一大步，将路径裁剪的计算从部分在CPU上完成转移到完全在gpu上完成。
这篇文章解释了它是如何工作的。这是一段相当长的旅程——事实上，我在一年多前就开始起草这篇文章了。从那以后，我不得不想出一个基本的新并行算法。终于完成了。我认为剪辑是piet gpu区别于其他2D渲染引擎的核心。
剪裁的基本思想很简单，但它对整个成像模型有着深远的影响。首先，它会产生一个树形结构，而不剪裁的绘图可以被视为一个线性的层序列。实现纯矢量剪辑的方法有很多种，但我使用的方法将其推广到混合，下一种是混合。
使用矢量路径进行剪裁会影响剪裁节点的所有子对象的绘制。绘制路径内的点，而不绘制路径外的点。
对于纯矢量路径剪裁，应用于每个（叶）图形节点的有效剪裁是树上所有剪裁路径的交点。因此，一个可行的实现是在向量空间中进行路径相交。然而，布尔路径操作很难实现，只有CPU实现是已知的；至少可以说，将它们转移到GPU是困难的。
相反，我们将（抗锯齿）剪切视为混合操作——事实上，它是Porter-Duff“source in”合成操作符的一个实例。从概念上讲，片段的子片段渲染到一个临时的、初始清晰的缓冲区中，片段遮罩渲染到alpha通道中，然后在背景上合成临时缓冲区，alpha通道乘以遮罩。这种方法完全可以在GPU上完成，混合操作也可以推广。
夹子可以任意嵌套；片段节点可以是另一个片段节点的子节点。因此，一个完整的2D场景实际上就是一棵树，它深刻地影响着绘画的方式。
二维渲染中的一种常见技术是为每个绘图操作指定一个边界框。边界框是一个封闭的矩形（希望是紧密的），因此绘图操作只影响矩形内的像素。对于渲染目标曲面的任何子区域，可以忽略其边界框不与该边界框相交的任何对象。Piet gpu广泛使用边界框来组织并行绘图，首先是256x256像素的单元，然后是16x16像素的平铺。边界框利用了大多数二维图形都是稀疏的这一事实，因为大多数绘制对象不会接触大多数瓷砖。
当然，边界框与剪裁相互作用。树中的每个剪辑节点都有一个根据相应剪辑路径计算的边界框。然后，树中所有子体的边界框与该边界框相交。另一种措辞方式是，绘制对象的剪裁边界框是对象自己的边界框，与从该节点到树根的路径中所有剪裁路径的边界框相交。
计算这些边界框的工作量比渲染对象少，但不是免费的。特别是，我们希望在GPU而不是CPU上完成这项工作。
每瓦优化会让事情变得更加有趣。piet gpu渲染管道被组织为一系列阶段，最后为目标中的每个16x16磁贴编写每个磁贴命令列表（有时称为“磁带”）。最后一个阶段是“精细光栅化”，它为平铺中的所有像素播放这些命令。瓷砖内部没有控制流；对所有像素计算所有命令。
在一般情况下，剪辑渲染如下。精细光栅化器保持一系列每像素状态，尤其是当前像素和混合堆栈。当前像素最初是清晰的（alpha=0）或背景色，普通绘制对象被合成到其上（通常使用Porter Duff“over”）。BeginClip操作将当前像素推送到混合堆栈上。将渲染片段的子对象，并合成到当前像素中。然后，在匹配的结束剪辑处，剪辑遮罩被渲染成alpha遮罩，该遮罩使用“源输入”（基本上是将alpha与遮罩相乘）与当前像素合成，结果与混合堆栈顶部（弹出）合成（Porter Duff“结束”），成为新的当前像素。
然而，很多时候，我们并不需要一般情况。Piet gpu渲染通过16x16像素的分片工作。管道中的早期阶段计算平铺中应该发生的事情，最后阶段（精细光栅化）对平铺中的所有像素执行一系列绘制操作。这让我们有机会进行一些优化。
特别是，缩放到单个分幅时，剪辑路径可能处于三种状态之一：零覆盖、部分覆盖或完全覆盖。部分覆盖仅在剪辑路径与平铺相交时发生。完全覆盖适用于完全位于剪辑路径内的分片，零覆盖适用于剪辑路径外的分片。
遮罩计算和合成只需要对部分覆盖图块进行（上图中显示为灰色）。其他的可以更有效地渲染。零覆盖平铺抑制子节点的渲染，基本上是从BeginClip到相应的EndClip。全覆盖瓷砖基本上是不可操作的；不需要渲染遮罩，子节点的渲染就像没有剪辑一样有效。
上一次迭代中，CPU对边界框进行了计算。piet gpu的一个主要目标是将尽可能多的计算转移到gpu。
基本任务是为每个绘制对象指定一个包含所有封闭片段交点的边框矩形。场景的线性化表示将包含BeginClip元素和EndClip元素。BeginClip还将引用一条路径，该路径有一个关联的边界框。
stack=[viewport_bbox]用于场景中的元素：如果元素是BeginClip（路径）：stack。push（intersect）（stack.last（），path）。bbox（））元素。有效_bbox=堆栈。最后一个（）elif元素是EndClip:element。有效_bbox=堆栈。最后一个（）堆栈。pop（）：元素。effective_bbox=intersect（stack.last（），元素）。bbox（））
作为一种顺序算法，这非常简单，几乎微不足道。有一堆边界框，该堆栈的大小以最大嵌套深度为边界。处理每个元素的成本也是O（1）。唯一的问题是，你真的，真的不想在GPU上运行顺序算法。
这就提出了一个问题：有没有办法让这种算法的并行版本在实际的GPU硬件上高效运行？这个问题已经困扰了我至少一年了。我很高兴地说，答案是肯定的。我做到了。
我的解决方案的核心是我所说的堆栈幺半群，它是研究得很好的括号匹配问题的一个变体。我在博客中提到了《重新访问堆栈幺半群》中的一个早期版本。从那以后，我做了一个改进版，峰值性能几乎是5倍，可移植性也更好。我不打算在这篇博文中详细介绍，我只想说解决方案可以通过magic获得，并将重点放在2D渲染问题的应用程序上。
基本上，我们使用括号匹配的结果来表示两件事。首先，每个EndClip都可以访问与相应BeginClip相同的路径和边界框数据。特别是，这让我们能够在粗光栅化中高效地进行逐块优化，因为该着色器不需要保持显著的状态。其次，它计算根路径上所有剪辑边界框的交点。谢天谢地，矩形交集是一个幺半群，所以这是可能的
本节是一个可以跳过的细节，但对于编写更高级GPU算法的人来说可能会感兴趣。
最初的piet gpu设计使用了一种“结构阵列”方法来描述场景，尤其是一个带有固定大小元素的单一阵列，每个元素都是各种绘图元素类型的标记并集，包括路径段。处理这个数组基本上需要一个大的switch语句来处理联合中的变量。我曾考虑在这个数组上做一个堆栈幺半群，但非常担心为这个数组中的每个元素计算堆栈幺半群的性能成本。我现在有了一个非常快速的堆栈monoid实现，但即使如此，我还是修改了架构，这样就不会有问题了。
新的体系结构（在新元素处理管道问题中有详细描述）更多地是一种“阵列结构”方法，由于其性能优势，在图形和游戏世界中非常流行。每个主要数据类型都有自己的流。此外，该类型的大部分逻辑都被转移到自己的着色器调度中，该调度只在该类型的对象上大量工作，没有大的开关语句。为了将这些数据拼接在一起，我们在这些数据流中使用一组索引，这些索引是使用计数的前缀和计算的。
具体来说，draw object stage执行流压缩并写入剪辑流，这是一个仅包含BeginClip和EndClip对象的数组。剪辑索引是指向该流的索引。同时，它为每个绘制对象指定一个剪辑索引。由同一剪辑包围的一系列绘制对象都具有相同的剪辑索引。在上图中，“clips”数组表示由draw object stage写入的剪辑流。将场景的不同部分关联在一起的箭头也会在“绘制对象”阶段使用前缀sum进行计算。
然后，剪辑阶段对剪辑流中的剪辑进行括号匹配和bbox相交。完成后，将为剪辑流中的每个对象指定一个边界框，与路径处理阶段已计算的剪辑路径的边界框相交，以生成剪辑边界框。它还将EndClip中的路径设置为引用与相应BeginClip相同的路径。
因此，剪辑阶段的工作与场景中剪辑的数量成正比，而不是与对象的总数成正比。这项工作需要大量的剪辑才能在个人资料中大量展示。我们使用了类似的流压缩技术，转向了更紧凑的路径编码，我计划将其应用到管道的其他部分。
剪辑的一个应用是在UI中定义滚动视图的视口。这可以在piet gpu中表示为剪辑节点，转换节点作为直接子节点，然后滚动内容作为转换节点的子节点。与transform节点关联的平移控制滚动位置（这种架构也可以进行缩放）。
piet gpu的一个设计目标是，这些内容中的大部分可以被编码一次并保留下来，因此，一个具有不同滚动位置的新场景可以在CPU端用很少的工作重新组装。在GPU方面，计算剪辑边界框需要相当小的工作量，这将能够在管道的早期剔除对象，
显然，这种方法适用于适度滚动，在这种情况下，所有资源都驻留在GPU上是可行的。对于巨大的滚动窗口，需要进行一些虚拟化，在它们滚动进出视图时交换资源。尽管如此，这仍然是一个值得探索的方向，因为平滑滚动仍然是UI工具包的一个挑战。
这项工作可能与大规模并行矢量图形最为相似。我们都将场景表示为一棵扁平的树，并允许任意嵌套深度。然而，他们的树算法要简单得多：对于n个嵌套深度，他们进行n次扫描，每个扫描处理一个嵌套级别。这项工作使用了一种新的算法，可以在不减速的情况下实现任意嵌套深度。（例如，工作系数与树的深度成比例的GPU树算法并不罕见）
在更传统的GPU渲染器中，进行混合的一般方法是分配一个临时纹理，渲染到该纹理中，然后通过在渲染目标中绘制一个四边形进行合成，从中间纹理进行采样。GPU对这类工作进行了高度优化，硬件支持纹理采样和“光栅运算”合成，但即便如此，它也需要到主内存的流量。我相信完全不用做这项工作会更快。
这里的技术类似于马特·基特（Matt Keeter）对复杂封闭形式隐式曲面的大规模并行渲染。剪裁基本上与构造几何（无论是2D还是3D）中的相交相同，该论文使用类似的技术来优化磁带，在每个区域的基础上利用代数简化。这些技术更通用，而这项工作更专门用于2D渲染任务。
现在已经很过时了，但是亚当·兰利关于铬元素剪辑的博文很有意思。讨论的主要问题是“合并工件”，alpha通道合成剪裁方法没有完全解决这一问题，但即便如此，它仍然是标准技术，主要是因为它或多或少受到W3C合成和混合规范和HTML画布绘制模型的强制。
您是否维护了支持有趣剪辑的2D渲染器？有没有我错过的好文章？让我知道，我很乐意添加链接。
这篇博文中缺少了一些东西，尤其是性能数据。现在，我在piet gpu的重点是使架构正确。感觉就像是在汇合，许多棘手的问题正在得到解决。
现在剪辑的基础设施已经到位，混合应该相对简单。需要做的大部分工作是在精细光栅化中添加额外的混合逻辑，当然还有通过管道输送相关元数据。再加上径向渐变和扫掠渐变，是支持下一个重大里程碑COLRv1表情符号所需的两个主要部分。