2D矢量动画在B站的探索与实践-三角剖分

在前文中，我们拥有了对一个矢量图形的路径描述。在本文中我们会介绍，如何将已有的路径描述 (Path) 转化为，GPU可读取的三角形的顶点数据。整体处理过程如下图所示，路径作为输入，折线化模块首先使用折线近似曲线将其转化为复杂多边形，接着将复杂多边形简单化、简单多边形单调化、单调多边形三角化，最终得到一组三角形作为输出！

上图中相关的概念解释如下（可能与通常的定义略有差异）：

• 简单多边形：边不相交的多边形

• 复杂多边形：除了简单多边形之外的多边形

• 单调多边形：如果一个多边形基于它的  （或  ）坐标值最大和最小的两个顶点可以将它的边分成两个单调边序列，则该多边形称为Y（或X）单调多边形

在上一篇文章中提到，矢量图形是由折线、曲线以及填充规则描述的，我们需要完成的第一步则是化曲为直。

这一部分，主要介绍如何将前文中提到的曲线，包括二次贝塞尔曲线、三次贝塞尔曲线、二次有理贝塞尔曲线，使用多段折线进行拟合！

对于  范围内的二次/三次贝塞尔曲线  ，使用二分法进行逼近拟合。具体地，如下图，当曲线中点  与线段中点  的距离小于给定阈值  时，认为线段  可以近似曲线  。

特别地，对于有拐点的三次贝塞尔曲线，会进一步检查其四分点，将拐点插入数据结构，继续进行二分：

折线化步骤：

1. 使用   （  

   为迭代次数）个二次贝塞尔曲线近似二次有理贝塞尔曲线（参考论文[1]）

2. 对每个二次贝塞尔曲线使用上述二分逼近方法进行折线化

设具有相同控制点  的二次有理贝塞尔曲线  和二次贝塞尔曲线  分别为： 

 其中，  是基函数：

经过简单的求导，即可得到二次贝塞尔曲线  和二次有理贝塞尔曲线  的最大误差  在  时取得：

 得到具有相同控制点的二次贝塞尔曲线与二次有理贝塞尔曲线的最大误差后，便可通过二分法利用二次贝塞尔曲线对原始二次有贝塞尔曲线进行逼近。其中，使用有理De Casteljau算法对二次有理贝塞尔曲线进行二分。具体地，对于原二次有理贝塞尔曲线  ，通过以下方式将其在  处分为两个新的二次有理贝塞尔曲线  和  ：

其中：

第  次迭代的误差  为所有二分区间内近似曲线  与原曲线  误差的最大值，即：

当  时，  ，且收敛是四阶

总体上，使用二次贝塞尔曲线二分逼近二次有理贝塞尔曲线的算法伪代码如下：

1. 对于  ，令  ,  

2. 对于  ，遍历  

得到第  次的近似曲线后，若与原曲线的误差  小于给定阈值，则停止二分！

上述算法的可视化表示如下：

折线化后，我们得到由若干条折线组成的图形路径，即复杂多边形。我们首先需要求出所有交点，将相交的线段从交点处分裂开，把一个复杂的多边形拆分成多个简单的多边形。

求交点的过程中又可以细分为两个子问题：

1. 已知两条线段如何求交点

2. 二维平面内条线段如何求交点

我们接下来将分别进行讨论。

给定两条线段：

  ,所在直线为  

  ,所在直线为  

具体计算步骤如下：

1. 先判断两个线段的包围盒 (bounding box) 是否相交，若不相交，则一定不存在交点；否则，继续执行下一步

2. 计算  在法向量上的投影长度（忽略分母，因为在后续的计算中可以相互抵消）

•   的法向量为  ，  在  法向量上的投影长度为：

•   的法向量为  ，  在  法向量上的投影长度为：

3. 计算  ，表示：

•   ，即  的方向向量  在  的法向量上的投影

•   ，即  的方向向量  在  的法向量上的投影

4. 如果有以下情况，则两个线段不会有交点（只展示  的情况，   时类似）

5. 排除一定没有交点的情况后，添加必要的辅助线，即可求出交点坐标

•   ：

  
  

•   ：

• 交点  的坐标即为：

    

明确目标：给定平面中  个线段的集合  ，计算出所有线段对  的交点。

算法的核心是扫描线 (Sweep Line) 方法，假设使用水平扫描线  ，  从所有线段的左侧开始，从左向右移动，对于扫描线所处的任何位置，可以将线段分成以下三组：

1. Dead 线段：这些线段完全位于扫描线  的左侧

2. Active 线段：这些线段与扫描线  相交

3. Sleeping 线段：这些线段完全位于扫描线  的右侧

算法执行过程中主要维护两个数据结构：

1. X-结构：保存过渡点 (Transition points)，按照  坐标从小到大排序（若  坐标相同，则按照  坐标从大到小排序），过渡点包括：

• 线段的端点：算法开始前已知

• 线段的交点：扫描期间被发现，并插入到X-结构

1. Y-结构：保存Active 线段，按照与扫描线  交点的  坐标从大到小排序

在给出算法细节之前，需要一些定义。令  和  是两个Active 线段，它们与扫描线  的交点分别是  和  （假设  在  下方）。如果不存在不同于   和  的Active 线段，它与  的交点  和  之间，则我们认为线段  和  是  上的邻居。在下图中，我们称  是  在  上的前驱 (Predecessor)，  是  在  上的后继 (Successor)。

初始化：X-结构中存放  个线段  的所有端点（即  个过渡点），并按照  坐标从小到大排序（若  坐标相同，则按照  坐标从大到小排序）

扫描过程：扫描线  依次处理X-结构中的过渡点，  从一个过渡点移动到下一个过渡点时，有以下三种可能的情况：

1. 扫描线遇到线段的左端点，例如  ：

• 由于  变为Active状态，则将其插入Y-结构（依旧保持Y-结构的有序性）

• 在Y-结构中搜索扫描线  上线段  的前驱  和后继  。为简单起见，这里假设  和  都存在。由于  和  （  和  ）现在是  上的邻居，我们测试  和  （  和  ）是否在  右侧相交。若相交，则将交点插入X-结构中（依旧保持X-结构的有序性）

2. 扫描线遇到线段的右端点，例如  ：

• 在Y-结构中搜索扫描线  上线段  的前驱  和后继  ，同样假设  都存在

• 由于  变为Dead状态，则将其从Y-结构中删除

• 测试  和  是否在  右侧相交，若相交，则将交点插入X-结构（依旧保持X-结构的有序性）

3. 扫描线遇到两个线段的交点，例如  和  （假设在交点之前，  在扫描线上处于  下方）：

• 在Y-结构中搜索扫描线  上线段  的前驱  和  的后继  （假设  和  都存在）

• 改变  和  在Y-结构中的顺序（保持Y-结构的有序性）

• 测试  和  （  和  ）是否在  右侧相交，若相交，则将交点插入X-结构（依旧保持X-结构的有序性）

可以发现，在扫描过程中，我们保持以下三个不变性：

1. 对于扫描线  所处的任何位置，Y-结构都包含所有Active 线段，且根据它们与  交点的   坐标从大到小进行排序

2. 对于扫描线  所处的任何位置，X-结构（  坐标从小到大排序）都包含：

• Sleeping 线段的所有端点

• 在  右侧的所有Active 线段的端点

•   上相邻的Active 线段在  右侧的所有交点

3. 对于扫描线  所处的任何位置，所有Dead 线段的交点都已经被找到

复杂多边形简单化后，我们得到若干个简单多边形。接着，我们需要将每个简单多边形转化为若干个单调多边形，方便后续的三角化操作！

在进行此部分讨论前，我们先定义一些概念： 

x-单调链 (x-monotone chains)：一个多边形的链，对于垂直于x轴的任意一条线，只有一条线段与之相交，那么这条链称为x-单调链。

x-单调多边形 (x-monotone polygon）：如果一个多边形是简单多边形，且由两条x-单调链组成，那么我们称这个多边形为为x-单调多边形。

有一类单调多边形比较特殊，如果单调多边形的一条单调链是一条直线，另一条是一个普通的单调链，我们将这种单调多边形称之为单调山（monotone mountain）。

x-单调山 (x-monotone mountain）：由一条直线以及一条x-单调链组成。按照x-单调链处于扫描线前进方向的左右可以分为两种：

• 如果x-单调链在右，我们称之为R_mountain类型的单调山（后文简称R_mountain）

• 如果x-单调链在左，我们称之为L_mountain类型的单调山（后文简称L_mountain）

最后，我们对简单多边形中的顶点进行分类，以方便后续算法的描述：

相关定义

为了更清晰地描述算法过程，我们首先给出一些必要的符号定义和解释。

线段的左右侧单调多边形：一条线段  的和Left_mPoly和Right_mPoly很好理解，直观地，在扫描线的前进方向上位于线段左侧的单调多边形即为Left_mPoly，右侧的即为Right_mPoly。

顶点的左右侧单调多边形：一个顶点  的Left_mPoly和Right_mPoly稍微复杂一点。简单来说，我们用  表示以顶点  为右端点的所有线段（按照与扫描线交点的  坐标从大到小排序），  表示  在扫描线  上的前驱，  表示  在扫描线  上的后继，那么：

• 若  存在，则顶点  的Left_mPoly表示线段  的Left_mPoly；否则若  存在，则顶点  的Left_mPoly表示线段e_lel的Right_mPoly；否则，顶点  的Left_mPoly不存在

• 若  存在，则顶点  的Right_mPoly表示线段  的Right_mPoly；否则若  存在，则顶点  的Right_mPoly表示线段  的Left_mPoly；否则，顶点  的Right_mPoly不存在

单调山中保存的边类型：我们定义两种不同的边类型，每个特定类型的单调山只保存单个类型的边组成的x-单调链，另外的一条直线不作保存，具体地：

• R_mountain只包含Right_side类型的边组成的x-单调链

• L_mountain只包含Left_side类型的边组成的x-单调链

当向R_mountain中添加Left_side类型的边时，意味着找到了另外的一条直线，我们只需添加一条对角线即可完成当前R_mountain的构建，大致过程如下所示（L_mountain类似）：

单调多边形的插边规则：单调多边形的数据结构具有以下性质：

• 一个x-单调多边形，可以由一个或者多个x-单调山组成（链表形式存储）

• 两种类型的x-单调山交替排列

• 包含的每个x-单调山只保存x-单调链，而不保存另一条直线

当向单调多边形  中插入一条Right_side类型的边  时，可能有以下几种情况：

1. 若  中不包含x-单调山，则使用  创建一个新的R_mountain加入链表

2. 若  链表尾部的x-单调山  是：

• R_mountain类型：直接向  中插入  

• L_mountain类型：则连接  的右端点与  的x-单调链的最右侧端点（记作边  ），将其直接插入  ，并使用  创建一个新的R_mountain加入链表尾部

下图示例中的单调多边形包含三个x-单调山，分别为：

• L_mountain1：包含Left_side类型的边  

• R_mountain1：包含Right_side类型的边  

• L_mountain2：包含Left_side类型的边  
  

边的winding值定义：首先定义一条边的起始点start point和结束点end point，直观的解释为，先绘制的顶点为起始点，后绘制的顶点则为结束点。那么，如果一条边的起始点到结束点的x坐标单调增（x相等时，y单调减），则其winding值（简记为  ）定义为+1；否则定义为-1，

边包含的顶点类型：一条边  包含两个顶点  、  ，我们定义  坐标较小（  相等时，  较大）的顶点为top point，另一个则为bottom point，如上图所示。

具体过程

我们首先要思考一个问题，一个简单多边形为什么不是单调的？这里抽象的解释一下，不单调的原因是因为，简单多边形中可能存在汇合顶点（leftward cusp）与分裂顶点（rightward cusp）。我们只要将汇合顶点与分裂顶点消除掉，那么得到的多边形可以保证是单调的！

与求交点的算法（Bentley-Ottmann算法）类似，这里仍使用扫描线 (Sweep Line) 思路。我们仍然要维护扫描线的基本元素，Dead 线段，Active 线段，Sleeping 线段。

在后文中，为了更直观地描述扫描过程，我们将以下图作为示例展开讨论 。图中对多边形进行了命名，后文中同一多边形与此图命名相同。图中为一个简单多边形被单调化后的结果，其被拆分成三个单调多边形，每个单调多边形又由多个单调山组成。

算法过程中维护的其他数据有所变化：

(1) X-结构：保存过渡点，按照  坐标从小到大排序（若  坐标相同，则按照  坐标从大到小排序），过渡点包括：

• 线段的端点：在多边形简单化的过程中已经求得的，所有线段的端点

(2) Y-结构：保存每个Active 线段的Left_mPoly（左边的单调多边形）和Right_mPoly（右边的单调多边形）

如上图，扫描线  在点  时：

  

初始化：X-结构中存放个  个线段  的所有端点（即  个过渡点），并按照  坐标从小到大排序（若  坐标相同，则按照  坐标从大到小排序）

扫描过程：扫描线  依次处理X-结构中的过渡点  ，  从一个过渡点移动到下一个过渡点时，处理如下：

我们首先需要找到顶点  的Left_mPoly与Right_mPoly（注意顶点与边的Left_mPoly和Right_mPoly的区别）

当扫描线  在顶点  时，我们需要考虑经过  的哪些边由Active 线段 变为 Dead 线段，哪些边由Sleeping 线段变为Active 线段：

(1) Sleeping 线段变为 Active 线段时，  是这些线段的top point，我们做如下处理：

a. 先判断  是不是一个分裂顶点 (rightward cusp)，即没有线段的bottom point是这个点。如果是分裂顶点则先执行以下处理，不是则直接执行步骤 b。

<i>. 如果  （下图中的  ），我们新建一条   与   最后一个顶点的边   。以  的最后一个顶点再新建一个单调多边形。然后将  加入其两侧的单调多边形中。

我们以下图为例详细解释一下执行过程，扫描线从之前的   移动到当前的   时：

• 在移动扫描线之前   ：

• 有一个以  为顶点的单调多边形，其中没有加入任何边。

• 在移动扫描线之后  ：

• 发现  不作为任何线段的bottom point，是一个分裂顶点，我们创建边  。再创建一个以  为顶点的单调多边形，现在有两个以  为顶点的单调多边形，一个粉色一个蓝色。我们把  以Right_Side类型加入粉色的单调多边形，以Left_Side类型加入蓝色的单调多边形。

<ii>. 如果  （下图中的  ），我们需要将当前的   与Left_mPoly的最后一个顶点相连生成新的对角线  。且  将以Right_Side类型加入Left_mPoly，以Left_Side类型加入Right_mPoly。

下图为例详细解释一下执行过程，扫描线从之前的   移动到当前的   时：

• 在移动扫描线之前   ：

• 有蓝色的单调多边形 mPoly_blue，其中包含三个单调山（blue1, blue2, blue3）, blue1为L_mountain, blu2为R_mountain，blue3为L_mountain

• 有紫色的单调多边形 mPoly_purple，其中包含两个单调山（purple1, purple2）, purple1为R_mountain, purple2为L_mountain

• 有橙色的单调多边形mPoly_orange ，其中包含一个单调山（orange1）, orange1为R_mountain

• 在移动扫描线之后  ：

• 发现  不作为任何线段的bottom point，是一个分裂顶点，我们创建边  。将  以Right_Side类型加入mPoly_orange，以Left_Side类型加入mPoly_blue

b. 枚举所有以  作为top point的线段  ，将其变为Active 线段，并计算  下方的一个点引出的一条射线的winding值 (winding number 如何快速计算，我们在后文中在讨论)。如果  ，说明线段  下方有一个以  作为起始点的单调多边形，我们创建此单调多边形，并且更新  的Left_mPoly与Right_mPoly

我们以下图为例详细解释一下执行过程，扫描线从之前的   移动到当前的   时：

• 在移动扫描线之前   ：

• 有蓝色的单调多边形mPoly_blue，暂不包含任何单调山

• 在移动扫描线之后  ：

• 枚举所有以   作为top point的线段   和  ，   的下方的   ，我们创建以  为顶点的单调多边形mPoly_purple，  的下方的   ，不创建单调多边形

(2) Active 线段变为 Dead 线段 时，  一定是这些线段的bottom point，我们做如下处理：

a. 枚举  作为bottom point的所有边  ，将其以Right_Side类型加入  的Left_mPoly，以Left_Side类型加入  的Right_mPoly。而后将  从Active 线段中移除（即变为Dead 线段）；