沃诺克：利用GPU几何放大技术处理矢量图形

《Proceedings of the ACM on Computer Graphics and Interactive Techniques》：Warnock: Harnessing GPU Geometry Amplification for Vector Graphics

　　摘要
AI总结：要查看此由AI生成的总结，您需要拥有高级访问权限。了解更多信息并登录。

摘要
Warnock是一种新的2D矢量图形库，它利用了GPU的可编程几何放大功能。Warnock通过提供一种实用的像素空间质量度量标准来完善极坐标描边理论；此外，它还将极坐标描边扩展到能够填充路径。Warnock将路径转换为单个紧凑的GPU缓冲区，这样该缓冲区就包含了填充和描边路径所需的所有数据。与以往的技术不同，这个GPU缓冲区可以处理各种变换、描边宽度、端点处理以及连接样式的变化。Warnock支持带有细分着色器的较旧的DirectX 11类GPU，而带有网格着色器的新型GPU则能实现最佳效果。

AI总结（实验性）：此总结是通过自动工具生成的，并非由文章作者撰写或审核。提供该总结是为了便于查找相关内容，帮助读者判断文章的相关性，以及帮助来自相关研究领域的读者理解本文内容。它旨在补充作者提供的摘要，后者仍是论文的主要总结内容。完整文章才是权威版本。点击此处了解更多信息。点击此处对该总结的准确性、清晰度及实用性发表意见，您的反馈将有助于进一步优化和生成未来的版本。要查看此由AI生成的通俗语言总结，您需要拥有高级访问权限。

图1：Warnock的渲染流程始于HPG 2026标志的单一统一GPU存储数据表示形式（最左侧），首先按四步依次完成对标志路径的描边（顶部）、填充（底部），最终得到结果（最右侧），这一过程通过GPU细分着色器或网格着色器实现的极坐标细分来完成。

1 引言
Warnock和Wyatt在1982年提出的关于二维矢量图形的基础研究，确立了2D分辨率无关图形的基本渲染操作，尤其是曲线路径的填充和描边功能。他们早期的实现方式是使用基于CPU的扫描线光栅化器来渲染图像。随着GPU可编程性的提升，原本为3D图形设计的图形硬件也被巧妙地改造用于渲染2D矢量图形，这一功能如今已在全球范围内的网页浏览器及其他应用中得到广泛应用。

1.1 用于路径细分的GPU几何放大功能
然而，现有的方法并未充分利用GPU的几何放大功能，尤其是GPU细分以及最近的网格着色技术。我们所提出的GPU细分和网格着色技术将路径渲染中的几何扩展步骤完全交由GPU处理，而且重要的是，无论是填充还是描边，都只需从一个紧凑的GPU缓冲区中获取数据即可。

我们将其命名为Warnock，以此向已故的John Warnock[Beach 1989; Risen 2023]致敬，他最早对2D矢量图形进行了系统化研究。我们的Warnock软件库充分利用GPU的几何放大功能，通过采用适合GPU并行处理的创新细分算法来实现路径渲染。在Warnock中，将特定路径从常规的CPU表示形式（即一系列路径指令及对应的控制点）转换为GPU表示形式仅需一次线性时间转换即可完成。一旦路径的GPU表示形式被转换并下载到GPU中，且被纳入图形处理管线后，只需最少的3D API命令即可启动可编程GPU着色器来填充或描绘原始路径，如图1所示。

与以往的技术不同，当改变渲染状态时，如坐标空间变换、填充规则、描边宽度、笔形、连接样式、端点处理或着色状态等，无需修改路径的GPU缓冲区。相反，只需进行简单的缓冲区绑定，或者可能更换不同的着色器程序，即可实现常见的2D矢量图形模式切换。这是因为所有必要的路径细分操作都在GPU内部完成，从而减少了CPU在绘制路径过程中的参与，同时也完全消除了CPU在路径细分中的作用。

此前尚未有在任何GPU图形处理管线中运行的路径渲染方法具备以下特点：
(1) 对于任何路径，都存在一个用于填充和描边的单一紧凑型GPU缓冲区表示形式；
(2) 几何放大、裁剪以及像素空间误差范围计算都在GPU高效的可编程图形处理管线内部完成；
(3) 仅通过更换着色器程序、纹理或GPU缓冲区，即可支持多种标准的2D矢量图形渲染模式（甚至包括投影变换和基于纹理的虚线效果）。

Warnock之所以能够同时具备这三种特性，是因为极坐标描边理论[Kilgard 2020c]及其在极坐标填充中的应用，使得GPU能够在为路径的每个线段、连接点或端点进行初始设置时，先计算出为满足规定的像素空间质量标准而需要的几何放大程度，从而在真正进行几何扩展之前完成相应处理。

1.2 论文贡献与结构
1.2.1 我们的贡献：
(1) 开发并实现了极坐标填充技术，这是一种基于GPU加速的路径填充方法，它与极坐标描边共享相同的极坐标评估理论，同时还能适应可编程GPU细分以及网格着色器，而且设计上要求输入用于填充和描边的都是同一种紧凑型GPU表示形式；
(2) 提出了一种用于极坐标细分的像素空间细分度量标准，并将其应用于极坐标描边和填充功能中。

1.2.2 文章结构
第2节回顾了有关GPU加速矢量图形的现有研究成果。第3节介绍了我们将路径分解为各个片段、通过极坐标细分实现几何放大，以及所采用的像素空间误差度量标准等相关方法。第4节详细阐述了我们在GPU细分着色器和网格着色器中实现的极坐标填充与描边功能、通过可绑定缓冲区管理渲染状态以及其他相关细节。第5节通过实验评估了Warnock在利用GPU几何放大功能处理矢量图形方面的效果。第6节为结论部分。

2 现有研究
2.1 基于CPU的矢量图形渲染
早期的路径渲染软件依赖于基于CPU的扫描线光栅化器。即便在今天，基于CPU的路径渲染系统仍主要以扫描线光栅化器为基础。扫描线光栅化器[Ackland and Weste 1981; Kallio 2007; Wallis 1990]所需的内存资源相对较少。“扫描线”这一术语指的是每条路径都是逐行水平扫描线进行光栅化的。

为了填充曲线段内部的区域，通常首先将路径简化为近似的线段条带。而要描边路径，则需要通过描边偏移功能，使路径边界在其切线方向上沿垂直方向各偏移一段等于描边半径的距离，这样就可以对偏移后的区域进行填充。对于二次贝塞尔曲线和三次贝塞尔曲线的偏移处理在数学上较为复杂[Farouki and Neff 1990a; 1990b]，因此人们提出了多种近似方法[Elber et al. 1997]，其中Yzerman [2020]以及Levien和Uguray [2024]提出了最新的处理方案。

2.2 基于GPU的矢量图形渲染
虽然已有专门用于实现扫描线光栅化器的硬件解决方案[Huang and Chae 2006; Kim et al. 2008; Lin et al. 2012; Shen et al. 2010]，但相比那些基于现有GPU图形处理管线构建的高性能解决方案，专门用于2D矢量图形的硬件所带来的额外成本往往难以被合理解释。

2.2.1 GPU图形处理管线方法
与我们的工作最为相似的现有研究，主要是那些利用传统GPU图形处理管线来实现路径填充和描边的方法。微软的Direct2D [Kerr 2009] API建立在Direct3D之上，它将填充和描边的路径分解为梯形，然后由GPU以三角形对的形式批量渲染。不过，由于路径被分解为梯形的过程是在CPU上完成的，因此Direct2D更多只能算是借助GPU的力量，而非真正实现GPU加速。

Loop和Blinn [2005]提出了一种在片段着色器内部高效处理曲线边缘光栅化的方法。Kokojima等人[2006]则将Loop-Blinn方法与模板缓冲区[Akeley and Foran 1995]结合使用，用来计算帧缓冲区样本相对于TrueType字体轮廓的缠绕次数。Slug [Lengyel 2017]在渲染基于轮廓字体的填充字形方面效率极高。通过将预细分过的TrueType字形的网格着色器几何放大功能与条件性的二次贝塞尔曲线边缘光栅化相结合，就可以实现文本的渲染[Meyer et al. 2024]。Kilgard和Bolz [2012]将Kokojima的方法推广到了更广泛的路径渲染功能，包括椭圆形路径段、描边、虚线效果以及与任意路径的裁剪功能。他们的“先模板处理，再覆盖”方法被作为OpenGL扩展功能实现，名为NV_path_rendering [Kilgard 2012]。Batra等人[2015]在NV_path_rendering的基础上进一步实现了PDF [Adobe Systems 2008]所需的各种功能，包括图层、打印用CMYK颜色模型以及渐变网格功能。

目前，用于2D矢量图形的主流GPU加速系统是谷歌的Skia [Skia team 2025]，它为Android系统、Chrome浏览器以及微软的.NET框架[SkiaSharp team 2025]提供渲染功能。Skia经过不断发展，采用了多种细分以及“先模板处理，再覆盖”的方法来实现路径的填充和描边功能。Skia中最复杂的着色器会使用实例化顶点着色器来对填充和描边的路径进行细分。借助实例化顶点着色器[Gold et al. 2008]，CPU只需发出一条绘制指令，就能在GPU上生成n个相同的几何图形副本，而这n组图形中的每一个都可以通过当前的顶点着色器进行不同的变换处理。具体的n值必须由CPU计算并指定。与GPU几何放大功能相比，实例化顶点着色器会导致冗余的工作量，同时还要求CPU提前预估最坏情况下的几何扩展规模。

2.2.2 GPU计算方法
随着可在GPU内部但脱离其传统图形处理管线的情况下进行可编程并行计算的技术出现（例如NVIDIA的CUDA [Nickolls et al. 2008]），又出现了一种实现路径渲染GPU加速的新途径。这种方法源自矢量纹理技术[Nehab and Hoppe 2008; Parilov and Zorin 2008; Qin et al. 2008]，在这种技术中，分辨率无关的边界可以在GPU的片段着色器内部进行计算。通过利用GPU的通用计算能力，一些研究团队[Dokter et al. 2019; Ganacim et al. 2014; Li et al. 2016]为整个矢量图形场景构建了驻留在GPU内的加速结构，从而可以程序化地对该场景进行光栅化处理。还有一种混合式方法，即先运行计算着色器来并行处理描边计算，然后再利用传统图形处理管线，依靠直线和圆弧来渲染得到的近似结果[Levien and Uguray 2024]。不过，这些方法往往存在场景构建速度慢（对于动态场景尤为麻烦）、内存使用范围难以预测、负载均衡效果差、功能集不完整（例如缺乏描边、虚线效果、裁剪、图层或其他重要功能）以及难以与已使用现有图形库的应用程序集成等问题。

3 我们的方法
3.1 路径极坐标细分的泛化
GPU在计算机图形处理中能够发挥强大的并行计算能力，但这些计算功能主要是为绘制连续的均匀3D三角形而设计的，而非用于处理尺寸不固定的2D路径——这类路径包含各种复杂的元素，如不同的路径指令及其对应的控制点以串行方式交织在一起，还存在许多几何上的复杂情况，比如孔洞、凹凸形状、重叠现象、曲线形状、端点处理、连接方式以及尖点等。

由于存在上述各种几何复杂因素，要精确地对填充和描边的2D路径的覆盖区域进行细分其实相当困难[Fabris et al. 1997; Kilgard 2020a; Nehab 2020]。采用简单的均匀参数化细分方法，即便在同一个曲线段内，也容易出现过细分或欠细分的情况，而且无法确保像素空间细分误差处于一定范围内。虽然递归式曲线分割算法能够提供较好的误差控制效果——就像在基于CPU的扫描线路径渲染器中所做的那样——但这种递归结构与GPU着色器的并行处理理念相悖。

3.1.1 极坐标描边
极坐标描边方法[Kilgard 2020c]基于成熟的理论，通过统一的梯度角度变化步长来进行处理。这里的“极坐标”指的是，以极坐标形式表示的曲线段梯度，可以通过统一的极坐标角度步长来进行逐步处理，从而沿着曲线以恒定的转角增量推进细分过程。通过对梯度角度变化的限制，也可以限制细分后的面角大小[Kilgard 2020b]，使其不超过梯度角度变化值的两倍。在Warnock对极坐标描边方法的实现中，有一个重要的改进之处，那就是在用于极坐标描边的曲线段间隔的两端，增加一段梯度角度变化为半步长的细分步骤，因为面角可能达到梯度角度变化两倍的情景通常出现在曲线的拐点附近，也就是间隔的末端。这样的半步长措施实际上有助于更好地限制面角的大小。

不过，这样的角度限制并不能也无法为像素空间的位移误差设定上限。因此，我们提出并实现了一种无需递归的有效策略，用于计算梯度角度变化值，从而能够合理地控制细分过程中的像素空间位移误差（详见第3.6节）。图1展示了以绿色标记的描边步骤。3.1.2 极坐标填充。Warnock通过调整极坐标描边方式，在填充路径时为每条路径轮廓生成锚定三角形扇形结构，并以与描边相同的方式限制像素空间内的位移误差。假设模板缓冲区被初始化为某个常量值，那么通过为路径中的所有轮廓渲染这些锚定三角形扇形，同时增加正面三角形的模板计数并减少背面三角形的模板计数，就可以在模板缓冲区中确定路径的填充范围[Neider等人，1993]。随后，会渲染一个预先计算好的、能够覆盖路径所有轮廓的凸多边形（即覆盖几何体），以此为路径内的所有被覆盖像素着色，同时重置模板缓冲区，为下一条路径的渲染做准备。图1中以橙色标记的即为这种填充步骤。3.2 将路径分解为链接图2展示了路径中可能存在的不同类型链接的分类：每个端点位置都有对应的端点样式，而连接样式则决定了每个连接的几何形状。在GPU对已填充或已描边的路径进行细分和渲染之前，Warnock必须先将路径分解为更简单的组成部分，即链接。这一过程被称为路径烘焙，它将每条路径分解为两个数组：(1)链接数组，以及(2)控制点坐标数组。每个链接包含链接类型以及指向控制点坐标数组的六个索引。不同的链接类型（如图2中所展示的分类）决定了这些索引的具体含义。Warnock共定义了十种链接类型：•三次贝塞尔线段链接，包括用于表示线段的退化三次曲线；•二次贝塞尔线段链接；•以标准化有理二次贝塞尔线段形式表示的圆锥形链接[Lee，1987]；•端点链接：起始路径端点、结束路径端点、起始虚线端点以及结束虚线端点；•连接链接；•尖点链接（与连接链接类似，但忽略连接样式，且始终为圆形）；以及•用于表示隐式闭合轮廓的隐式闭合链接。路径链接数组中的每个链接都独立地规定了如何利用GPU的几何放大功能来对该路径进行细分。无论是在GPU细分模式下还是网格着色模式下，Warnock对链接的编码方式有所不同，但从概念上讲，这两种编码方式都会将信息转化为链接类型以及一组坐标索引，从而从路径的控制点坐标数组中获取该链接相关的控制点。虽然每个链接有六个控制点索引，但实际上最多只能指定四个唯一的(x, y)控制点位置。连接链接及各种端点链接类型分别用于生成描边时的连接部分和端点部分，但在填充操作中则会被忽略。隐式闭合链接则会扩展为一段锚定线段，用以闭合那些没有通过ClosePath命令明确闭合的填充轮廓。与连接链接和端点链接不同，隐式闭合链接在填充操作时会被处理，而在描边操作时则会被忽略。端点的实际样式（平面、三角形、正方形或圆形）由着色器根据着色器状态来确定，这些状态建立了端点位置与端点样式之间的映射关系。同样，连接的样式（无连接、斜接、三角形或锐角连接）也取决于着色器状态。3.2.1 位置控制点与渐变控制点。一旦确定了每个链接的类型，就会为该链接在路径坐标数组中的控制点索引进行分配。虽然三次贝塞尔线段只需要四个控制点，但六个控制点索引使得可以独立于线段的控制点来指定链接的起始和结束渐变。对于三次贝塞尔曲线类型的链接，虽然有四个控制点用于构成曲线，但还有两个额外的控制点用于指定起始和结束渐变控制点。通常情况下，渐变控制点会重复使用中间两个控制点的索引；不过，当位置控制点处于同一位置时，渐变控制点则会指示第一个非同位置的控制点，以便通过差分计算出合适的、非退化的起始或结束渐变值。对于线段而言，前两个和后两个位置控制点处于同一位置，而渐变控制点则分别是起始渐变和结束渐变的对应位置控制点。对于二次贝塞尔链接，则只需三个位置控制点，但渐变控制点仍然用于指定起始和结束渐变，以弥补控制点处于同一位置的情况。对于圆锥形链接，第二个（中间的）控制点是以带有w坐标的二维齐次坐标(x, y, w)的形式存储的。对于三次贝塞尔曲线或w值为无穷大的圆锥形曲线，其尖点处有四个位置控制点处于同一位置，但此时会有渐变控制点来指定尖点的起始渐变和结束渐变。连接链接和端点链接的所有四个位置控制点也处于同一位置。对于连接部分，渐变控制点用于指示连接的进入和退出方向；而对于端点部分，一个渐变控制点则可决定端点的负法线和正法线方向。3.2.2 将弧线视为圆锥样条。在路径烘焙过程中，路径渲染标准中规定的各种圆形和椭圆形弧线参数表示方法会被转换为等效的圆锥形链接和连接链接序列。由于数值上的原因，那些w值接近零或无穷大的退化圆锥形曲线，对于线段和尖点来说，必须被转换为一系列三次贝塞尔链接。3.2.3 额外的填充状态。用于填充的路径烘焙还包括：(1)一个包含(x, y)坐标值的锚定控制点数组，每个路径轮廓对应一个控制点；(2)额外的一到六个链接序列，用于表示路径线段链接构成的凸包；以及(3)该覆盖几何体的(x, y)控制点坐标。在已填充的路径中，每个轮廓都有其独立的烘焙路径链接序列以及对应的锚定控制点。第3.5节将介绍在填充操作中如何使用这些状态。随后，极坐标描边和填充的完整烘焙状态会被存储到一个统一的GPU内存缓冲区中，如图1所示。3.3.1 GPU细分技术。图3展示了GPU中的细分技术概览。图4则展示了任务着色器和网格着色器的概览。3.3.1 GPU细分技术。图5根据Direct3D的规定[Microsoft，2025]（15.16.1有效位置范围），在渲染之前，GPU会丢弃那些由一个或多个具有NaN（非数字）位置坐标的顶点构成的图元（左图）。示例中的描边路径位于右上角；右中图为示例中每个链接在(u, v)贴图空间中的GPU细分网格；右下图则为该示例的最终整体细分结果。细分着色器的两阶段处理流程[Purcell，2010]（如图3所示）首先会生成初始控制着色器（OpenGL版本）或轮廓着色器（DirectX 11版本），这类着色器接收与路径中某个链接相对应的六个控制点输入贴图，然后根据某种质量指标——可以是像素空间范围内的限制——计算出极坐标评估所需的参数，包括需要进行的极坐标评估次数。之后，后续的评估着色器（OpenGL版本）或域着色器（DirectX 11版本）会执行针对每个顶点的极坐标评估，并输出一个贴图顶点。Warnock采用了一种我们称之为“NaN污染”的创新技术，对传统的四边形输出贴图几何结构进行改造，将其“切割成条带”，从而形成连续的三角形条带，用于描边操作（见图5），或者“切割成扇形”用于填充操作。另一种方法是，使用等值线细分着色器将数据传递给几何着色器，进而形成三角形条带。这些三角形要么构成用于填充操作的锚定三角形扇形，要么构成用于描边操作的由成对三角形组成的四边形条带，随后这些条带会被送入光栅化器。经过光栅化后的片段在更新模板缓冲区和颜色缓冲区之前，还会经过着色和覆盖范围计算。3.3.2 网格着色技术。借助当前世代GPU所具备的网格着色功能[Kubisch，2018；Kubisch和Brown，2018]，两阶段的细分过程（如图4所示）被分为任务着色器和后续的网格着色器两部分来执行。任务着色器会执行与细分控制着色器相同的极坐标评估准备工作，但它不会为每个贴图生成细节级别参数，而是会创建多个网格着色器工作组。当这些网格着色器工作组被启动后，它们会执行极坐标评估，并为填充操作的锚定三角形扇形或描边操作的三角形条带构建索引化的顶点缓冲区。为了提高网格着色器的执行效率，每个任务着色器工作组处理的都是包含多达8个链接的链接组合。由于GPU细分着色器基于贴图的方式，以及网格着色器和任务着色器的单指令多线程执行特性，因此极坐标填充和描边在GPU内部的表示方式有着显著差异。3.3.3 共同的处理流程：设置、极坐标评估、光栅化。在GPU渲染路径的过程中，路径中的各个链接会被分配给GPU的并行计算资源（即着色器线程）进行处理，这样就可以并行处理每个链接。每个链接都要经历一个链接设置阶段，在此阶段中，链接会被分类，其变换后的控制点会被收集起来，极坐标评估所需的参数也会被计算出来，同时还会根据某种质量指标来确定处理该链接所需的顶点评估次数。在完成这个初始的链接设置阶段之后，就会进入几何放大阶段。随后，会根据每个链接后续极坐标评估所需的细分程度来启动相应的着色器线程，这些线程会执行极坐标评估，从而计算出每个链接所需的描边或填充顶点几何结构。最终，这些顶点几何结构会形成三角形条带（用于描边）或三角形扇形（用于填充），这些组合好的几何结构会被送入GPU光栅化器，进而转换成碎片，之后这些碎片会被着色，并用于更新帧缓冲区的模板缓冲区和颜色缓冲区。为了实现良好的抗锯齿效果，并遵循路径渲染中“仅混合一次”的原则，对于某条特定路径的渲染过程实际上会进行两次。第一次渲染称为“模板”阶段，其作用是将路径的填充或描边区域渲染到模板缓冲区中，此阶段不会进行任何颜色写入操作。接着是第二次渲染阶段，称为“覆盖”阶段，该阶段会依据第一次渲染生成的模板覆盖情况来进行判断，将模板值重置为中性状态（通常是零），然后对碎片进行着色，并将其与对应的像素颜色进行混合。由于切换当前的着色器程序是一项相对耗时的操作，因此避免程序切换是非常有利的。极坐标填充所需的锚定几何结构和覆盖几何结构都是从相同的路径编码中生成的，而且也使用相同的极坐标填充着色器程序，因此在这“模板”阶段和“覆盖”阶段之间无需更换着色器程序。极坐标描边时的“模板”阶段和“覆盖”阶段同样使用相同的极坐标描边着色器程序。3.4 带链接的极坐标描边在进行极坐标描边时，着色器程序会丢弃所有的隐式闭合链接。如果通过简单的剔除检查能够证明某个链接的几何结构完全位于视图锥体之外，那么这个链接也可能被丢弃。这种检查需要为所有被描边半径扩大的控制点计算出简单的裁剪码，然后验证这些控制点是否都位于至少一个视图锥体裁剪平面之外。如果启用了锐角连接功能，那么在计算扩大幅度时还必须考虑锐角限制。无论出于何种原因丢弃了一个链接，都意味着该链接不会再被进一步处理（也不会为其生成任何几何图形）。之后，剩余的链接会被细分成一系列三角形，从而近似表示出路径的轮廓，这一过程如Kilgard[2020c]所述。单个绑定的GPU程序会依次执行“模板”操作和“覆盖”操作，因此这两个操作之间不会发生程序绑定；其间最少的状态变化为：（1）通过一次低成本的缓冲区绑定来改变程序的运行模式，以及（2）更改图形管线的模板和颜色配置。13.5 带连接的极坐标填充在极坐标填充过程中，着色器程序会忽略所有连接点和端点连接（因为这类连接仅对描边有效）。由于填充用的控制点不会因描边宽度而扩大，因此简单的剔除检查更为简单。而路径描边时，镶嵌过程是将路径分解为一系列四边形（以三角形对的形式输出），而在路径填充中，路径中每个闭合轮廓的镶嵌结果则会形成以锚点为起点的闭合三角形扇形。所谓闭合扇形，是指将扇形的第一个非锚点顶点复制为扇形的最后一个顶点，从而形成围绕整个轮廓的循环结构。如果子路径未被明确闭合，则可通过ImplicitClose连接来实现闭合。所谓的间接绘制命令允许通过一次API调用即可对任意复杂的路径进行模板处理或覆盖操作。在极坐标填充的“模板”步骤中，极坐标计算方式与描边相同，但每个生成曲线轮廓并非以该曲线的起点为基准偏移，而是以轮廓内的重心位置为锚点，从而形成以该点为起点的闭合扇形。在极坐标填充的“覆盖”步骤中，1到7个锚定线段连接起来形成一个具有3到8条边的凸多边形，该多边形能够充分覆盖“模板”步骤生成的几何形状。3.6 极坐标镶嵌的像素空间误差度量图6显示了通过极坐标描边方式镶嵌的立方贝塞尔线段，其最大转角误差度量为4度。作为一种与分辨率无关的保形度量标准，放大图像并不会影响镶嵌效果。但在曲率最低的边界区域放大时，可以看到镶嵌后的线条（橄榄色四边形轮廓）与实际描边边界（青色和品红色曲线）之间存在细微但可观察到的间隙。（为更明显地展示误差，此图像已关闭3.1.1节中提到的半步镶嵌功能。）图7显示了图6中同一线段的最大像素位移误差度量为0.75像素。由于这是一种与分辨率相关的度量标准，放大图像时镶嵌程度会自动增加。在这种度量标准下，镶嵌后的线条与实际描边边界之间不存在可察觉的误差，因为任何位移误差都小于1像素。线条曲率较高的区域（顶部凸起部分）可能存在过度镶嵌的情况，但这是因为需要限制位移误差，以确保曲率较低的区域（线段两端）具有足够的镶嵌密度。最初，极坐标描边方法仅能对最大镶嵌面角给出误差上限（见图6）。这种保形性保证与像素分辨率无关，因此无法确保镶嵌后的边界与实际描边（或填充）后的边界之间的像素位移保持在较小范围内（理想情况下为亚像素级别）。为解决这一问题，Warnock在极坐标描边理论的基础上引入了一种新的误差度量方法，该方法能够在不过度简化的前提下，合理限定极坐标描边（或填充）生成的边界多段线近似值与对应的严格凸且单调的子曲线之间的弗雷歇距离[Bringmann等人，2019]。这些子曲线首尾相连，构成了路径中每段曲线路径的真正曲线描边（或填充）边界。“不过度简化”的含义是，Warnock旨在将最大像素位移误差控制在某个指定的正像素空间阈值db之下，同时他也意识到，一旦误差低于像素级别，过度镶嵌路径几何结构并不会带来相应的质量提升。需要强调的是，我们并非声称能够计算出整个路径及其完整多段线镶嵌结构的弗雷歇距离，而是确保所有严格凸且单调的子曲线之间的弗雷歇距离——这些子曲线通过直线边界段相互连接，共同构成完整的描边（或填充）路径边界——与Warnock对应的多段线近似值之间的差异，都能被一个可配置的最大像素空间位移值所合理限制。为实现这一目标，Warnock的着色器实现方式为每个连接区间独立计算最大转角值，以此作为控制依据。确定了这个最大转角值后，后续的极坐标描边（或填充）镶嵌过程就会按照常规方式进行（即不进行其他修改），具体步数由各连接区间计算出的最大转角值决定。所有与这种像素空间误差度量相关的计算都在用于GPU镶嵌的控制着色器或用于网格着色的任务着色器中完成。3.6.1 测量曲线近似相似度弗雷歇距离是一种衡量两条曲线相似性的指标，它同时考虑了点的位置和顺序。严格来说，度量空间(X, d)中两条曲线A: [0, 1] → X和B: [0, 1] → X之间的弗雷歇距离，是由Alt和Godau[1995]定义的：δF(A,B)=infr,smaxt∈[0,1]d(A(r(t)),B(s(t)))，其中r, s: [0, 1] → [0, 1]是连续的、非递减的满射函数，且具有相同的端点，即r(0) = s(0) = 0且r(1) = s(1) = 1。这一通用定义实际上是对无限维函数的优化形式，对于Warnock的应用而言过于复杂。因此，我们对其应用方式进行了限制，使其更具实用性和可行性。对于Warnock而言，度量空间(X, d)为二维欧几里得像素空间；曲线A是一条二维的、严格凸且单调的曲线，它是某条曲线路径的描边（或填充）边界上的子曲线；曲线B则是通过极坐标描边（或填充）生成的、旨在近似曲线A的多段线边界；而且曲线A和曲线B具有不同的端点以及相同的端点。不同的端点意味着A(0) ≠ A(1)，而相同的端点则意味着A(0) = B(0)且A(1) = B(1)。重要的是，曲线B的所有多段线顶点都位于曲线A上。当某条曲线路径既不是严格凸的也不是单调的时，我们假设将该路径的理想边界分割成多个严格凸且单调的子曲线区间，而极坐标镶嵌机制本身就已经完成了这种分割。随后，每个子曲线都会被一条多段线近似表示，使得该子曲线与其对应的近似多段线具有相同的端点。如果某条连接路径仅由直线段组成（例如方形端头、斜接或倒角连接，或是普通线段），那么该路径的边界可以直接用直线或多段线表示，此时极坐标镶嵌无需进行任何近似处理，也就无需进一步讨论了（因为此时的弗雷歇距离为零，显然小于db值）。虽然弗雷歇距离的通用定义要求对任意重参数化情况进行连续优化，但通过简化假设，我们能够在极坐标镶嵌的背景下对弗雷歇距离做出实用的描述。3.6.2 通过限制切角来约束弗雷歇距离在设计像素空间度量标准时，我们希望开发一种迭代式（非递归式）方法，能够高效地为某个连接区间i计算出“质量控制参数”即最大切角步长阈值qi，该阈值能够合理限制在该区间内，通过极坐标计算过程生成的多段线与基于该区间生成曲线之间的最大像素空间弗雷歇距离，这一限制需同时考虑到给定的qi值以及该连接曲线生成点相对于多段线的偏移量r。在填充操作中，r的值为0，而在描边操作中，r则为描边半径。采用Kilgard[2020c]的符号体系，极坐标计算过程首先确定一个函数t[Ψk,Ψk+1](ψ)，其中[Ψk, Ψk + 1]表示某个特定的切角区间范围[k, k + 1]，该区间内的曲线曲率要么全为正，要么全为负（因为是严格凸曲线），且角度变化幅度小于180°（因为是单调曲线）。在这个区间范围内，存在唯一的t值，我们将其记为tF，该值的对应角度与从pk点到pk+1点之间的弦线角度一致。由于区间[k, k + 1]内的曲线是严格凸且单调的，因此该区间的方向向量ω可表示为：ω=sgn(sin?(Ψk+1?Ψk))(?)intervalorientation(?1or+1)，即方向向量为-1或+1。区间曲线上的任意一点都可以通过一组三元组?θ, t, p?唯一标识，该三元组包含该点的切角θ、参数值t以及位置p，满足条件g(t) = pt，且g′(t)·? ? sin?θt, cos?θt? = 0，这意味着曲线的梯度与切角方向垂直且呈90°夹角。最终，我们关注的是，从?Ψk, tk, pk?到?Ψk + 1, tk + 1, pk + 1?的每一个连接区间k，其通过多段线近似表示的精度如何，这一精度可以通过多段线与该区间曲线之间的弗雷歇距离来衡量。我们的目标是确保路径中所有曲线连接区间的这一弗雷歇距离都小于或等于预先设定的像素距离阈值db。与其考虑整个区间，不如假设我们已经知道了子区间?θa, ta, pa?和?θb, tb, pb?上的两个点a和b，且满足ta < tb，这样就可以形成一个新的子区间[a, b]。我们希望计算从pa点指向pb点的弦线与子区间[a, b]所对应曲线之间的相似度，具体方法是计算这两者之间的弗雷歇距离，如图8所示。图8展示了在路径连接区间k内计算子区间[a, b]的弗雷歇距离dF的几何关系（左侧），以及单独的切角和法向量示意图（右侧）。首先，确定从pa到pb的弦线向外凸出最远的点OF的位置，计算公式如下：Δ=pb?pa(?)chordgradientθF=atan2(Δy,Δx)(?)chordangletF=t[θa,θb](θF)(?)parametrictmatchingthechordanglepF=g(tF)(?)positionoftFn(θF)=??sin?θF,cos?θF?(?)normalvectortothechordangleOF=pF+ωrn(θF)(?)outwardbendingmaximallyoffsetcurveposition 由于边界子曲线是严格凸且单调的，它会“向外凸出”，这是因为方向向量ω的符号与生成子曲线的曲率符号一致。因此，连接区间[a, b]的起始点和结束点的向外凸出位置分别为：Oa=pa+ωrn(θa)Ob=pb+ωrn(θb)二维空间中，点b到由点a和点c构成的直线的最小距离为：d(a,b,c)=‖(b?a)×(c?a)‖‖c?a‖ 根据我们补充文档[Kilgard和Barran 2026a]中的引理1，d(a, b, c)实际上就是从点a到点c的弦线与以a和c为端点的严格凸且单调曲线（即子区间[a, b]的描边或填充边界，从Oa延伸到Ob）之间的精确弗雷歇距离，且该曲线在点b处的最大位移值即为d(a, b, c)。具体而言，点OF就是子区间[a, b]的边界曲线上的这样一个点。既然已经知道从Oa到Ob的弦线与该边界曲线之间的弗雷歇距离，接下来就可以计算：dF=d(Oa,OF,Ob) 如果dF ≤ db，那么目标就达到了；但如果未达到该阈值，Warnock会在任务着色器或控制着色器中启动一个迭代过程，不断寻找合适的qi值，逐步降低像素位移误差，直到dF ≤ db为止，或者达到预设的最大迭代次数为止。在介绍这个迭代过程之前，我们先来看看递归过程会如何处理这种情况。如果计算得到的dF ≤ db，那就说明误差已经控制在允许范围内。但如果dF > db，我们可以将在tF处将生成曲线和偏移曲线分开，然后分别重新计算左半部分子区间[a, F]和右半部分子区间[F, b]的dF值，其中F = ?θF, tF, pF?。之后，我们可以继续递归地处理左右两个子区间，直到所有被递归分割后的子区间的dF值都小于或等于db为止。此时，能够确保满足像素空间误差限制的最大切角步长阈值q，就是所有满足dF ≤ db条件的子区间中，θa与θb之间的最小绝对角度差。如果以这种方式不断递归分割子区间，那么我们该如何根据这些多个子区间来推断整个区间的弗雷歇距离呢？我们补充文档[Kilgard和Barran 2026a]中的引理3证明了：如果一条严格凸且单调的二维曲线在某一点处被分割成两部分（而极坐标镶嵌确实能够做到这一点），那么整条曲线的弗雷歇距离，就等于其各个分割后子曲线对应的弗雷歇距离中的最大值。将这一引理递归应用的话，意味着我们的递归过程最终得到的完整区间的多段线镶嵌结构的弗雷歇距离，将会是其所有组成子区间弗雷歇距离中的最大值。不过，由于这种方法是递归式的，因此在着色器中并不实用——但实际上也没必要这么做。因为每一个区间都是严格凸且单调的，所以那些在分割后仍存在dF > db问题的子区间，实际上都是曲率最低的区域。这些区域必然位于取值范围的极端点上。因此，只要dF > db成立，迭代方法只需不断探索并必要时分割曲率较小的子区间即可。关于内弯尖点的补充说明：在描边时，存在两个子曲线边界N和P，它们分别是当r > 0时相对于g的负向和正向偏移曲线，根据ω的不同，其中一个为外弯，另一个为内弯。如果g是严格凸且单调的，那么外弯也会如此，但当r足够大时，内弯容易出现尖点，从而不再具有严格的凸性或单调性。我们已经将这类内弯尖点视为特殊情况，因为此时面角没有上限[Kilgard 2020b]。当处理这类内弯尖点时，我们忽略像素空间中的位移误差（如图6和图7所示），因为这类误差很可能“隐藏”在原始曲线的描边部分（或连接处、端点处）。容易观察到的位移误差出现在外部偏移曲线上，而该子曲线仍保持严格的凸性和单调性。

3.6.3 迭代方法。由于子区间具有严格的凸性和单调性，我们只需通过迭代方式探索dF较小的左侧或右侧，而非递归地探索两侧，便可限定位移误差。直观上，人们可能认为应该在与dF较大的那一侧进行迭代，因为我们的目标是让dF降至db阈值以下。但实际上，dF较小的那一侧意味着其整体曲率更低。当曲率较高时，每次迭代都能更快地降低dF；而当曲率较低时，每次迭代对dF的降低幅度则相对较小。因此，应选择dF较小的那一侧进行迭代。

Warnock首先将迭代次数j初始化为0，然后根据给定的a0 = ?Ψk, tk, pk?和b0 = ?Ψk + 1, tk + 1, pk + 1?，按照上述方法计算OF和dF。如果dF ≤ db，则无需再迭代，只需1步即可。否则，需在?ΨF, tF, pF?处计算子区间分割后的左侧和右侧的OF及dF值。对于左侧子区间[a, ?ΨF, tF, pF?]，计算OF左、dF左；对于右侧子区间[?ΨF, tF, pF?, b]，则计算OF右、dF右。如果dF左≤db且dF右≤db，则在第j次迭代后结束迭代。若未达到条件，则增加j的值，若dF左 2百万像素）。由于Warnock的GPU镶嵌烘焙格式既可以被普通着色器方法处理，也可以被几何着色器方法处理，因此我们将两种方法中性能较好的那一种记为“GPU tess”，而将采用独立连线包烘焙格式的网格着色方法记为“Mesh shd”。Cairo和Skia无论在何种帧缓冲区配置下都会以相同的方式渲染每种场景，而Warnock和NV_path_rendering的渲染性能则会随着质量等级的不同而有所差异（我们的补充资料中提供了8:8、4:4和16:1三种质量等级下的测试数据）。所有API在测试前都会预先烘焙路径资源，因此计时的是渲染过程而非烘焙过程。表2展示了相关测试结果。低分辨率：<0.25百万像素
中分辨率：0.25–2百万像素
高分辨率：>2百万像素

Warnock与其它图形API的加速比
使用LS时的加速比
使用LCairo 1.16时的加速比
GPU细分：8.18×/40/0、14.4×/40/0、19.7×/38/0
网格着色：11.3×/40/0、19.9×/40/0、26.6×/38/0

Skia 2019版本
GPU细分：6.11×/40/0、9.84×/40/0、12.9×/38/0
网格着色：8.40×/40/0、13.6×/40/0、17.4×/38/0

Direct2D
GPU细分：2.00×/26/1、42.75×/32/8、34.00×/33/5
网格着色：2.76×/32/8、3.79×/35/5、4.58×/34/4

NV_path_rendering
GPU细分：0.30×/3/3、70.31×/0/400、0.37×/2/36
网格着色：0.42×/1/39、0.42×/0/400、0.50×/0/38

在40个SVG场景中，以8:8质量水平测试时，Warnock相对于其他向量图形API的几何平均加速比。数值大于1表示Warnock更快；小于1则表示其他API更快。W/L表示各分辨率下Warnock更快/更慢的场景数量。表2总结了三个分辨率段的几何平均加速比。在所有分辨率段和全部40个测试案例中，Warnock的速度都远快于Cairo和Skia，且在更高分辨率下优势更为明显（例如高分辨率下网格着色的加速比为26.6倍，而Cairo仅为相应值）。与Direct2D相比，根据分辨率不同，Warnock的网格着色方法在40个测试案例中能胜出32–35次，几何平均加速比为2.8–4.6倍，并且随分辨率升高而增加。总体而言，NV_path_rendering的速度仍快于Warnock，其几何平均加速比约为网格着色的2.0–2.4倍，这得益于NV_path_rendering在驱动程序层面经过高度优化的状态管理和实例化路径渲染功能。无论是在4:4、8:8还是16:1的质量水平下，Warnock相比Cairo、Skia和Direct2D的优势，以及NV_path_rendering相比Warnock的优势都保持一致。我们的补充文档[Kilgard和Barran 2026d]提供了所有质量级别下每个场景的详细数据。

结论
Warnock充分利用了GPU的几何放大功能，尤其是GPU细分和网格着色技术，用于路径的填充和描边操作。这一优势源于极坐标描边（以及现在的极坐标填充）能够以一种无需递归的有效方式预判所需的几何扩展。针对极坐标描边和填充缺乏像素级误差限制的问题，Warnock引入了一种仅基于迭代（无递归）的度量方法，以此合理限定位移误差。Warnock通过在GPU上使用统一的路径表示方式，同时支持描边和填充操作，而且只需通过调整缓冲区和程序绑定，即可实现各种变换、描边宽度、端点处理方式、连接样式以及着色效果的变化。实验表明，与NV_path_rendering相比，这种方式大幅降低了存储路径所需的GPU内存容量。Warnock的速度优于Cairo和Skia，与Direct2D相当，但慢于NV_path_rendering；进一步的优化有望缩小这一差距。目前Warnock是基于OpenGL实现的，但该方法也适用于其他现代3D API。我们已通过将Warnock的算法和着色器移植到Vulkan和SPIR-V上并验证其正常运行，但目前尚未完成完整的库实现。虽然不在本次展示的范围之内，但Warnock还具备许多用于GPU加速2D图形的创新功能，比如弧长纹理、多边形形状的绘图工具，以及能更快渲染包含梯度信息的2D有符号距离场[Frisken和Perry 2006]。这些功能都是基于Warnock的极坐标细分理念自然衍生出来的。

致谢
Nick Hammel、Tristan Lorach和David Luebke为这项工作提供了支持。