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

本期作者

刘孙瑞

哔哩哔哩高级开发工程师

钱爱娟

哔哩哔哩开发工程师

三角剖分

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

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

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

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

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

 折线化

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

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

二次/三次贝塞尔曲线

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

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

二次有理贝塞尔曲线

折线化步骤：

1. 使用   （  

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

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

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

 其中，  是基函数：

重新参数化   ，令  ，（其中  ），  ，代入计算则有： 

代入可求出：  

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

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

其中：

具体计算过程见上一章中有理De Casteljau算法部分的介绍！

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

当  时，  ，且收敛是四阶

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

1. 对于  ，令  ,  

2. 对于  ，遍历  

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

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

 复杂多边形的简单化

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

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

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

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

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

线段交点快速计算

给定两条线段：

  ,所在直线为  

  ,所在直线为  

具体计算步骤如下：

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

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

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

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

3. 计算  ，表示：

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

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

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

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

•   ：

  
  

•   ：

• 交点  的坐标即为：

    

Bentley-Ottmann算法

Bentley-Ottmann算法[2]，是一种以  时间复杂度，计算出  条线段的所有  个交点的方法！

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

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

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

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

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

注意：本文中使用的扫描线算法均为水平扫描线，即从左向右扫描！

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

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

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

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

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

如果扫描线到达线段的过渡点，则Y-结构中Active 线段的顺序会发生变化！

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

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

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

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

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

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

由于  和  不再是  上的邻居，测试它们是否在  右侧相交。若相交，我们将从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-单调链。

同样我们可以按照类似的方式定义y-单调链或者任意方向的单调链。

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

类似地，可以定义y-单调多边形。

有一类单调多边形比较特殊，如果单调多边形的一条单调链是一条直线，另一条是一个普通的单调链，我们将这种单调多边形称之为单调山（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加入链表尾部

插入Left_side类型边的过程类似！

下图示例中的单调多边形包含三个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）。我们只要将汇合顶点与分裂顶点消除掉，那么得到的多边形可以保证是单调的！

定理的证明可参考链接[3]。

与求交点的算法（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的区别）

例如，当扫描线  在  时，  的Left_mPoly = mPoly_blue，Right_mPoly = mPoly_purple

当扫描线  在顶点  时，我们需要考虑经过  的哪些边由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 线段）；

b. 如果  是一个汇合顶点 (leftward cusp)，即没有线段的top point是这个点（下图中的  ），我们把当前汇合顶点的Left_mPoly和Right_mPoly设置为彼此的Partner。这里之所以要设置Partner，是因为汇合顶点需要与后面的一个顶点新建一条边  ，来消除这个汇合顶点，而边  的Left_mPoly和Right_mPoly正是汇合顶点  的Left_mPoly和Right_mPoly。

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

• 在移动扫描线之前   ：

• 有蓝色的单调多边形mPoly_blue，其中包含 一个L_mountain单调山（包含边  ，都以Left_Side类型加入单调多边形）

• 有紫色的单调多边形mPoly_purple，其中包含 一个R_mountain单调山（包含边  ，以Right_Side类型加入单调多边形）

• 在移动扫描线之后  ，枚举以  作为bottom point的所有边：

• 对于边  ，我们需要将  作为Right_Side类型加入  的Left_mPoly（即蓝色的单调多边形mPoly_blue）。但是，mPoly_blue的尾部是一个L_mountain类型的单调山blue1，只能包含Left_Side类型的边。因此，我们需要将当前顶点  与mPoly_blue的最后一个顶点  连接一条对角线  ，将  以Left_Side类型加入blue1以完成blue1的构建。并且再创建一个R_mountain类型的单调山blue2，插入单调多边形mPoly_blue的尾部，最后将  以Right_Side类型加入blue2

• 对于边  ，我们需要将   作为Left_Side类型加入  的Right_mPoly（即紫色的单调多边形mPoly_purple）。但是，mPoly_purple的尾部是一个R_mountain类型的单调山purple1，只能包含Right_Side类型的边。因此，我们需要将当前顶点  与mPoly_purple的最后一个顶点  连接一条对角线  ，将  以Right_Side类型加入purple1以完成purple1的构建。并且再创建一个L_mountain类型的单调山purple2，插入单调多边形mPoly_purple的尾部，最后将  以Left_Side类型加入purple2

• 同时我们发现  是一个汇合顶点，并且  的    ，因此需要将  的Left_mPoly与Right_mPoly设置为彼此的Partner。后续，在扫描线  扫到  时，会新建边  ，我们将  加入mPoly_purple时，发现mPoly_purple有Parnter。我们也会将  加入其Partner（即mPoly_blue)

填充规则传递

此算法执行完成过后，我们就将一个简单多边形，拆分成多个单调多边形（每个单调多边形包含一个或多个单调山）。但是这里还有一个问题需要解决。上文中我们只讨论了多边形的拆分，其实是并没有考虑这个拆分好的多边形是否应该被填充？单调化算法过程中也有一个问题，没有详细说明在新建单调多边形时winding值是如何计算的？

我们其实可以发现 winding number 的一个性质，每个单调多边形的 winding值（简记为  ）其实是，其左侧多边形的winding值加上作为两个单调多边形分界线的线段的winding值。

因此，在我们创建单调多边形时，新多边形的winding值定义为：

  

  为新多边形的第一条边，左侧多边形为    的Left_mPoly。

我们使用如下示例进行解释，对于按照图中箭头指示的五角星的绘制顺序，使用单调化算法可以得到以下结果：

• Poly1的第一条边为  ，winding number值为  

• Poly2的第一条边为  ，winding number值为  

• Poly3的第一条边为  ，winding number值为  

• Poly4的第一条边为  ，winding number值为  

• Poly5的第一条边为  ，winding number值为  

• Poly6的第一条边为  ，winding number值为  

得到每个单调多边形的winding值后，按照填充规则判断该单调多边形是否需要被填充：

• 若为非零缠绕规则：  则填充；否则不填充

• 若为奇-偶规则：  为奇数则填充；否则不填充

  
  

  
  

对于上述示例设置不同的填充规则可以得到以下不同的结果：

注意：我们只对需要填充的单调多边形进行下一节的三角剖分操作！

 单调多边形的三角剖分

至此，我们得到了原始图形的单调多边形划分，其中每个单调多边形包含一个或多个单调山。最后，我们只需要对每个单调山进行三角化，即可提交给GPU进行绘制。

对于不同类型的单调山，依次遍历相邻三个顶点  ，利用向量的叉乘判断内角的凹凸性：  ，  ，由   到  （逆时针）的夹角为  

• 若  ，则  ，即  ，b在a的逆时针方向，内角是凸的

• 若  ，则  ，即  ，b在a的顺时针方向，内角是凹的

若当前计算出的内角为凸，则直接剖出三角形  ；否则，继续处理紧接着的三个相邻顶点。该过程一直持续到单调多边形只剩下三个顶点！

更直观地，单调多边形的三角剖分过程演示如下（以kRight单调山为例，kLeft类型同理）：

小结

本章中我们讨论了矢量动画绘制中最关键的步骤之一 —— 三角剖分。下一章中，我们将根据生产环境中的一些特效场景（如路径如何绘制描边，如何绘制沿路径的渐变等）展开，讨论如何在三角剖分的基础上，针对不同的需求做相应的拓展，敬请期待！

参考文献

[1] Floater M. High-order approximation of conic sections by quadratic splines[J]. Computer Aided Geometric Design, 1995, 12(6): 617-637.

[2] Smid M. Computing intersections in a set of line segments: the Bentley-Ottmann algorithm[J]. 2003.

[3] https://tildesites.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/fall21/Lectures/L9-polygontriangulation/cg-polygontriangulation.pdf

[4] Computational Geoemtry: Algorithms & Applications.

[5] https://skia.org/docs/

以上是今天的分享内容，如果你有什么想法或疑问，欢迎大家在留言区与我们互动，如果喜欢本期内容的话，欢迎点个“在看”吧！

往期精彩指路

• 2D矢量动画在B站的探索与实践-矢量图形的描述

• 二次元超分常见瑕疵及处理

• 视频基础知识