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

本期作者

刘孙瑞

移动技术部高级开发工程师

钱爱娟

移动技术部开发工程师

01 背景

随着互联网视频行业的发展，用户对App交互过程中的互动动画和视频中的特效动画，有着越来越高的要求。传统App中大量存在的交互动画，一般采用帧动画的实现形式（每一帧都是一张独立的图片）。帧动画在客户端有着实现简单的优点，但随着应用功能的不断增多，帧动画的缺陷也越来越明显，帧动画由一张张图片组成，资源体积上占用十分大。同时客户端的平台不断增多，设备的屏幕大小也各不相同，要想不同大小屏幕上实现同样效果的动画，需要设计提供不同分辨率大小的资源，这在工程实践上十分不便。与帧动画不同的矢量动画，则解决了这些痛点。矢量动画通过描述图形的绘制行为，来存储图像。这样的存储方式，在资源大小上有着天然的优势，同时矢量动画的绘制可以根据场景的分辨率进行实时的缩放与抗锯齿，较好的解决帧动画在缩放大小时的走样问题。

市面上已有lottie，svga，pag等优秀的矢量动画库，但是在B站业务场景下，并不能完美的解决自身业务痛点。B站拥有着一套自研的渲染引擎 Chronos，目前已支撑了移动端视频播放界面弹幕等视频特效业务，部分视频中的弹幕特效，以及大部分视频中的三连组件。Chronos 拥有对GPU接口的抽象和渲染管线，我们可以在Chronos基础上，完成一个矢量动画绘制模块，解决B站部分场景下特效动画的痛点。

02 从一只画笔说起

想象我们回到幼儿园美术课，在美术课上要画一颗树我们要怎么做。

我们先要将画笔挪到画纸上一个特定位置，先画一个圆，表示树冠部分，再将画笔挪到树冠的下半部分，画一个矩形表示树干。然后再分别对树冠和树干进行上色。

矢量图形的绘制流程和我们画一颗树的过程是相似的，我们需要一些直线和曲线，来描述整个图形的轮廓，然后再根据填充规则对图形每一个部分进行上色。然而GPU并不像我们一样智能，它们并不知道这里要画一个圆，那里要画一个矩形。大多数GPU的接口只能支持画一条线或者画一个三角形。因此我们面临的第一个问题即是如何在计算机上画一条曲线。大学的高数课告诉我们，只要一条曲线和一条线段的误差足够小，我们就可以认为这条线段是可以代替这条曲线的。例如一个圆，我们可以用尽可能多的折线，来代替原有曲线。这里就对应到绘制过程中的重要一步——曲线的折线化。

在折线化过后我们得到的是一个多边形，GPU只认识三角形和直线，所以我们需要将这个多边形进行三角剖分，以拆分成多个三角形。因此，在计算机上绘图，我们需要将图形折线化后的整个轮廓，拆分成很多个三角形来代替。这部分的工作叫做三角剖分。

三角剖分后我们将原始的图形转化成很多个三角形，现在我们可以直接告诉GPU，在某处画一个三角形画什么颜色。到此，整个矢量图的绘制大致完成。这样直接画出来的图形也会有渲染中常见的锯齿问题，我们后文也会讨论如何进行抗锯齿。

图形的描边本身也可以看作是一个图形，我们也会讨论如何从一个图形的轮廓创建一个描边的轮廓。描边也可以支持一些高级的样式，如何画一个虚线的描边，如何画一个渐变色的描边，如何给描边支持一些高光特效等，在后续文章中我们将一一讨论。

以上讨论的是如何绘制一张静态的矢量图，如何让这张图动起来，也是个不小的问题。最简单的方案是将描述静态矢量图中的一部分参数，使用关键帧描述，然后对其进行插值，包括对颜色进行插值，对曲线进行插值等等。这样可以完成，粉色正方形变为蓝紫色的圆再变绿色的四叶草的动画。

矢量动画大致流程如下图，本系列文章将从最基础的几何知识开始讲起，

先从静态矢量图形的描述，然后通过三角剖分，再到绘制一个静态矢量图形。

而后讨论如何实现矢量图形的描边与抗锯齿等进阶功能，支持画出更炫酷的矢量图。

最后讨论如何实现一个动画系统，让静态的图形动起来。

本文中，我们主要讨论两件事，一是静态矢量图形如何描述，二是讲解一些必要的曲线相关的几何基础，为后续文章提前做好数学储备。

03 图形的描述——Path 类

矢量动画要解决的第一个问题是，如何描述绘制行为。画画的时候，我们需要挪动画笔，因此我们需要MoveTo的绘制动作。我们同样需要画直线，需要LineTo的绘制动作。那么曲线如何描述呢？常用的曲线描述一般采用贝塞尔曲线的方式。贝塞尔曲线的阶数越高，我们可以拥有更多的控制点来描述曲线的变化。常用的二、三阶贝塞尔曲线即可满足大部分业务需求，通过QuadTo和CubicTo来表示这两种曲线的绘制。但是贝塞尔曲线无法描述椭圆、双曲线等圆锥曲线，这需要引入一种新的曲线——有理贝塞尔曲线，有理贝塞尔曲线通过ConicTo来表示。

通过以下五种最基本的绘制动作就可以描述大多数图形：

• MoveTo(p) ：把当前顶点移动到新的位置 p
• LineTo(p) ：把当前顶点移动到新的位置 p，并连接一条线
• QuadTo(p1, p2)：画一条以当前顶点，p1，p2为控制点的二次贝塞尔曲线

二次贝塞尔曲线：3个控制点，曲线方程为：

• CubicTo(p1, p2, p3)：画一条以当前顶点，p1，p2，p3为控制点的三次贝塞尔曲线

三次贝塞尔曲线：4个控制点，曲线方程为：

• ConicTo(p1, p2, w)：画一条以当前顶点，p1（w为其权重），p2为控制点的二次有理贝塞尔曲线

二次有理贝塞尔曲线（标准形式）：3个控制点，曲线方程为：，正实数是与控制点相关的权重，的大小决定了所代表的圆锥曲线的类型：

• 当时，是椭圆
• 当时，是抛物线
• 当时，是双曲线

拥有以上对图形轮廓的描述，加上填充规则，可以描述大多数业务场景下的绘图需求。

描述图形的 Path 类包括以下主要数据成员：

1. 动作数组 vector<DrawVerb> draw_verbs_
2. 顶点数组 vector<glm::vec2> draw_points_
3. 权重数组 vector<float> conic_weights_

上述三类数据的对应关系如下：

1. 填充规则，包括：

• 奇-偶规则：从点往任意方向作一条射线，若与该射线相交的边的数目为奇数，则是图形内部点，否则是外部点；

• 非零缠绕规则：首先使图形的边变为矢量。将环绕数初始化为零。再从点作任意方向的一条射线。当从点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当图形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完图形的所有相关边之后，若环绕数为非零，则为内部点，否则，是外部点。

04 曲线相关知识

Path 类中的绘制动作中包含三种曲线，即二次/三次/二次有理贝塞尔曲线。我们之后的一系列算法需要大量相关知识的支撑。因此，我们在接下来的部分将详细介绍涉及的两大类曲线，即贝塞尔曲线以及有理贝塞尔曲线，包括曲线的定义、重要性质和相关重要算法。当然，我们的介绍重点还是落在涉及到的三种特定曲线上。

 4.1 贝塞尔曲线

次贝塞尔曲线：个控制点，曲线方程为：

基函数

一阶导数为：

可以发现，的一阶导数是由个控制点定义的次贝塞尔曲线

 4.1.1 重要性质

1. 次曲线经过第一个控制点和最后一个控制点

所有基函数非负，且固定的所有基函数的和为1

• 由于，非负性显然
• 基函数是的二项式展开中的系数，即
• 由非负性以及和为1，可以得到任何基函数的值都属于

凸包性：贝塞尔曲线完全位于给定个控制点的凸包中

波折递减性：如果曲线在平面中，则意味着直线与贝塞尔曲线相交的次数不超过与曲线的控制折线（相邻控制点连接的折线）相交的次数

仿射不变性：将仿射变换应用于贝塞尔曲线，等价于将仿射变换应用于其控制点而得到的贝塞尔曲线

曲线与第一条控制折线和最后一条控制折线相切

• 令，则
• 令，则

 4.1.2 De Casteljau 算法

我们经常需要访问曲线上任意一点的坐标，而 De Casteljau 算法是计算贝塞尔曲线上任意参数对应坐标的一般方法，因此接下来我们将简单介绍该方法！

如何在曲线上找到给定参数对应的点？

• 一个简单的方法是将代入每个基函数，计算每个基函数与其对应的控制点的乘积，最后将它们相加。虽然这很直接，但它在数值上不稳定（即，在评估伯恩斯坦多项式的过程中可能会引入数值误差）
• 一种数值稳定的递归算法 De Casteljau 算法——绘制曲线的几何方法，且非常容易实现

基本概念：在线段中选择一个点，使得以的比率划分线段，则

几何解释：为了计算次贝塞尔曲线上的点

为了方便描述算法，我们将原始控制点表示为，其中下标第一位的0表示第0次迭代，第2次迭代则为...

1. 首先将个控制点连接形成一条折线
2. 利用上述公式，计算出折线中每条线段上的点，使得点分该线段的比率为。这样，我们将得到个点，定义了一条由条线段组成的新折线
3. 将该过程应用于这条新的折线，得到第二条由个点和条线段组成的折线
4. 重复这个过程次产生单个点

计算方法：如下图所示

1. 首先，将所有给定的控制点排列成一列，即图中最左边的一列
2. 对于每对相邻的控制点，画一个东南向箭头和一个东北向箭头，并在两个相邻箭头的交点处写下一个新点

例如，如果两个相邻点是和，则新点是。东南/东北箭头表示将/乘以它的尾部点/，新点即为求和：

1. 从初始列第 0 列，我们计算第 1 列；从第 1 列我们得到第 2 列，依此类推。最终，在 n 次应用之后，我们将到达一个点，这就是曲线上的点！

上述计算可以递归表示为：

De Casteljau 算法的正确性证明^[1]

 4.1.3 曲线细分

在之后的算法中（例如折线化、描边等），我们经常需要将原始贝塞尔曲线拆分成多个同阶的贝塞尔曲线以进行下一步操作。因此，介绍曲线的细分算法是十分必要的！

细分 (Subdividing)：将给定的贝塞尔曲线在某个对应的处分裂成两条曲线，每条曲线仍然是一条贝塞尔曲线

• 因为生成的贝塞尔曲线必须有自己的新控制点，所以原始控制点集被丢弃
• 分裂后的每段都是原始次贝塞尔曲线的子集，因此新生成的贝塞尔曲线必须是次

明确目标：给定一组个控制点和一个在范围内的参数，要找到两组个控制点和，使得：

• 由定义的贝塞尔曲线是原始贝塞尔曲线在的部分
• 由 定义的贝塞尔曲线是原始贝塞尔曲线在的部分

下图说明了这些点的选择：

• 左边的折线由点组成（蓝色折线）
• 右边的折线由点组成（粉色折线）

回想一下 De Casteljau 算法的三角计算方案：

• 对于给定的，计算需要次迭代
• 在计算过程中，可以收集每列上的第一个和最后一个点
• 第一个点的集合给出了与定义在上的原始曲线片段相对应的细分
• 最后一个点的集合给出了与定义在上的原始曲线片段相对应的细分

因此，在下图的三角形方案中，箭头方向的上边缘和箭头相反方向的下边缘分别提供了第一段和第二段曲线的控制点

细分算法的正确性证明^[2]

 4.2 有理贝塞尔曲线

 4.2.1 有理曲线

使用多项式的参数表示不够强大，这是因为很多曲线（例如，椭圆和双曲线）无法通过这种方式表示。克服这个缺点的一种方法是使用齐次坐标。例如：

• 空间曲线用四个函数而不是三个表示：
• 平面曲线用三个函数而不是两个表示：

其中是某个闭区间中的参数，将上述曲线转换为它们的常规形式：

• 空间曲线：
• 平面曲线：

显然，如果，即为常函数，齐次形式将简化为多项式形式。

为了区分，我们将：

• 齐次形式的参数曲线称为有理曲线 (rational curve)
• 多项式形式的曲线称为多项式曲线 (polynomial curve)

次有理贝塞尔曲线：个控制点，每个控制点都与一个非负的权重相关联 ，曲线方程为：

基函数

贝塞尔曲线到有理贝塞尔曲线的推导过程^[3]

 4.2.2 重要性质

1. 次曲线经过第一个控制点和最后一个控制点
2. 凸包性：有理贝塞尔曲线完全位于给定个控制点的凸包中
3. 波折递减性：如果曲线在平面中，则意味着直线与有理贝塞尔曲线相交的次数不超过与曲线的控制折线（相邻控制点连接的折线）相交的次数
4. 射影不变性：将射影变换应用于有理贝塞尔曲线，等价于将射影变换应用于其控制点而得到的有理贝塞尔曲线
5. 修改控制点的权重会将曲线推离或拉向控制点（具体证明^[4]）

 4.2.3 圆锥曲线的表示

Path 类中引入二次有理贝塞尔曲线的目的是为了描述圆锥曲线，因此，接下来我们将使用部分篇幅来介绍二次有理贝塞尔曲线如何表示圆锥曲线！

所有的圆锥曲线都可以表示为以下形式，其中、、不同时为 0：

由三个非共线控制点、和定义的2次贝塞尔曲线是抛物线的一段，我们希望扩展这个概念来定义椭圆和双曲线段！

假设经过、并分别在、 处与、相切的二次曲线由上述的2次隐式方程表示，其中六个系数是未知数。如果不为 0，我们可以将整个等式除以，得到如下方程：

那么，我们实际上只有五个未知数！（如果为零，我们还是有五个未知数）

方程的梯度为：

点处的切线与梯度相互垂直，又梯度的斜率为，所以处的切线斜率为

因此我们可以得到以下四个方程：

1. 曲线通过：
2. 与处的圆锥曲线相切：
3. 曲线通过：
4. 与处的圆锥曲线相切：

现在，我们得到了四个方程，每个方程关于未知数、、、和都是线性的。如果我们能找到一个更多的条件来产生一个线性方程，我们将有5个具有5个未知数的线性方程。求解这个线性方程组会产生所有5个系数，且二次曲线是唯一确定的。

非常自然的想法是添加一个点。将该点的坐标代入方程将得到一个类似于控制点和的方程。但是，这个点在哪里？

• 这个点应该在三个控制点的三角形内，这样才能保持凸包性质
• 这个点的位置也应该是“规则的”，这样我们就可以很容易地改变这个点来产生另一个圆锥曲线
• 一种方法是让该点位于连接 和 中点的线段上。这样，在这条线段上移动该点会产生不同的圆锥曲线

注意到：

• 如果所选点从的中点向移动，则它帮助定义的圆锥曲线向控制点移动
• 如果该点远离，它帮助定义的曲线也会远离
• 因此，这个观察使我们推测这个移动点的位置可以通过分配给控制点的权重来控制

由于我们只需要一个点，它受控制点的权重影响，因此我们可以使用具有三个控制点、、的二次有理贝塞尔曲线，权重分别为 1、和 1，分配给控制点的权重将控制额外点的位置。二次有理贝塞尔曲线的方程为：

下面，为方便讨论，我们将和放轴的相对两侧，以 的中点为坐标原点。

使用此设置，我们有。设 的中点为，有理贝塞尔曲线在处与线段相交，如下图所示：

计算时的有：，表示和是同一个点，则有：

若，则二次有理贝塞尔曲线变为二次贝塞尔曲线，即抛物线。在这种情况下，点是线段的中点。那么。这条有理贝塞尔曲线何时是椭圆或双曲线？

这就要用到射影几何中的一个定理。如下图，从给定圆锥曲线外部的点绘制两条在和处与曲线相交的切线，以及满足在处与弦相交且交圆锥曲线于和的任意一条割线，其中在三角形内。若：

• 曲线是椭圆，这些点的顺序是、、、
• 曲线是双曲线，则点位于曲线的另一个分支上！

定理表明以下关系成立：

又，则有：

• 若曲线是椭圆，则有，即
• 若曲线是双曲线，则有，即

回到二次有理贝塞尔曲线，我们有，，，，，则有：

• 若曲线是椭圆，则有，即
• 若曲线是双曲线，则有，即

至此，我们得到了如何用二次有理贝塞尔曲线来表示不同类型的圆锥曲线！

 4.2.4 二次有理贝塞尔曲线的标准形式

我们可能会疑惑二次有理贝塞尔曲线和上述的形式有没有什么区别，或者说是否是等价的？答案是肯定的，我们只需要重新参数化操作就可以得到二次有理贝塞尔曲线的标准形式（后一种 表示方式）！

有理重新参数化的一般形式为：

• 时，则有
• 时，则有

则有：，

使用替换，替换，代入一般形式，解出

即二次有理贝塞尔曲线的一般形式可以转化为等价的标准形式：

 4.2.5 有理 De Casteljau 算法

次有理贝塞尔曲线的有理 De Casteljau 算法具体可以参考论文^[5]，其递归表示为：

我们主要关注二次有理贝塞尔曲线（权重为 1、、1）的有理 De Casteljau 算法：

• 权重的更新方式为：

• 控制点的更新方式为：

 4.2.6 曲线细分

有理贝塞尔曲线的细分方式和贝塞尔曲线的细分方式相同，即在得到有理 De Casteljau 算法的三角计算之后，取最上侧和最下侧的控制点以及对应的权重。下面，给出在处对曲线进行细分的具体步骤：

1. 计算权重：

1. 计算控制点：

1. 由控制点、、确定的曲线，是原曲线的部分

  4. 由控制点、、确定的曲线，是原曲线的部分

05 小结

到此为止，我们主要介绍了静态矢量图形的描述，以及贝塞尔曲线相关的几何基础知识。下一章中，我们将讨论如何将Path折线化，然后进行三角剖分，敬请期待！

参考链接：

[1] https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau-correct.html

[2] https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/b-sub-correct.html

[3] https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/NURBS-def.html

[4] https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/NURBS-mod-weight.html#In-Depth-Discussion

[5] Šír, Zbyněk, and Bert Jüttler. "On de Casteljau-type algorithms for rational Bézier curves." Journal of Computational and Applied Mathematics 288 (2015): 244-250

---