硬核万字长文：我是如何把Skia的体积“缩小”到1/8的？( 四 ) 作者|陈国栋随着移动互联网的

文章图片

文章图片
如上图阴影部分代表多边形的区域，它有内外 2 个顺序相反的多边形组成。按照前文的定义很容易就可以得到多边形的区域，同样也很容易用程序的方式存储这个多边形。
它还是比较简单的，实际运算过程中允许多边形存在父子关系（用来存储含岛多边形），也允许一个多边形的定义存在多个不连通分量，从这个角度多边形是典型的递归定义。
对上面这个多边形进行硬件加速渲染，就需要对它进行三角剖分，如下图红色虚线构成的三角形网格。

文章图片

文章图片
这里有一个问题，类似于圆这样的“多边形”应该如何处理？对于曲线需要先进行离散化，一般在处理的过程中会传递一个忍受值，当离散相邻的两个点之间的距离小于忍受值就不在进行细分了。所以曲线可以看成由许许多多的“短”的线段围成的多边形。
时至今日三角剖分算法已经是计算机图形学中一个成熟的话题了。常见的三角剖分算法比如 “Monotone”、“EarCut” 等等。
其中 Mapbox（一家专注以地图渲染的公司）就开源了一个袖珍精巧的基于“Earcut”的剖分算法。还有一些剖分算法对生成的三角形的形状具有有一定的约束，比如“符合德劳内的三角剖分算法” 。在工业领域当然不希望剖分出来的三角形又长又细。因为这样用做零件加工、存储和运输都十分不方便。
画一条直线
有了前文的理论支持，现在开始面对一些实际的问题吧，比如从画一条直线开始。

文章图片

文章图片
在几何中只需要 2 个端点的坐标就可以描述一条线，从数学的角度看线是没有宽度的。如果我们需要绘制一条有宽度的线就需要把线转化成面（或者是一个矩形）。

文章图片

文章图片
利用给定的线宽并沿着直线的法线方向（一条直线有两个法线方向，互为相反向量）进行偏移。就可以得到一个矩形，对这个矩形进行剖分就可以得到由 2 个三角形组成的三角网格。GPU 可以高效绘制这个网格，用以表示这条有宽度的线。
画一条折线
稍微复杂一些，但是原理和绘制一条直线基本类似。

文章图片

文章图片
如上图所示，最后得到了 4 个三角形的网格，分别是红色、绿色、橙色、紫色四个三角形。在渲染器中，可能还需要指定线的端点和交点的样式。比如圆角端点，交点的长度限制等等。这些都可以用计算几何的方式得到，这里就不做过多的介绍。
贝塞尔曲线
前面我们探讨了一些基础的几何知识。已经可以从面（也就是多边形）和线（甚至是曲线）得到对应的三角形网格。程序可以构建一些简单的多边形（比如矩形，圆形，椭圆等等）然后把这些多边形转化成三角形网格，但是如果想要绘制下图图形则会发现有些难度。
难度体现在如何得到图形的轮廓，也就是如何构建或者优雅的描述这样一个复杂的多边形。就像美术从业人员会用 Photoshop 这类产品做产品的原型设计，大多会用到一个叫“钢笔工具”的绘图功能。它通过使用分段 3 阶贝塞尔曲线来拟合几乎任何图形的外围轮廓。Skia 的 SkPath 类的功能就和“钢笔工具”类似。