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

文章图片

文章图片
如上图所示，多边形 A（A0,A1,A2,A3,A4）和多边形 B（B0,B1,B2,B3）。首先计算出所有的边的交点，并计算出交点相对多边形的进出性。然后随机选取一个交点沿多边形一边进行“行进”直到遇到下一个交点。交点代表着分叉口，通过“进出性”来选取对应的路线。递归整个过程，直到全部的交点都被处理掉。

文章图片

文章图片
如上图所示， “C0”作为起点开始处理，直到遇到下一个交点“C1” 。考虑到“C1”的“进出性”和当前是求多边形的“并集” ，故选取“C1-B2”这条路线，直到所有的交点全部被处理。就能够得到新的多边形（C0,A0,A1,A2,A3,C1,B2,B3,B0），这个多边形就是剔除了堆叠后的并集。

文章图片

文章图片
最后要解决的是如何快速求解多边形边的交点？尤其当多边形异常复杂的情况下。这个可以通过线扫描配合优先队列的方式来完成。此类算法在诸多论文中都有详细的描述，不做详细研究。
上图只是描述了一个最简单的情况，真实的情况下一般是下面这样：

文章图片

文章图片
请自行脑补......
抗锯齿
抗锯齿本来和几何没有什么关系，比如游戏中常用的抗锯齿技术：
SSAA：拉大画幅后再线性插值缩小画幅的方式来抗锯齿
MSAA：硬件提供的多重采样后再 resolve 的抗锯齿技术
FXAA: 通过后处理的算法来来抗锯齿算法
这些抗锯齿算法在游戏这类全画幅处理中起到了很好的效果，但是在矢量渲染器中就不太合适，由于矢量描述多边形拥有明确的边界。算法只需要处理多边形的边界，像素的过渡中过滤高频跳变就可以达到完美的抗锯齿。所以可以在边界进行低通滤波，也可以通过其他技法来模拟这一过程。这里采用轮廓区域拓展 + 径向渐变的方法来间接模拟低通滤波。就拿绘制斜线的例子来说：

文章图片

文章图片
上图前三个步骤和前文的描述没有任何区别。在最后一步对轮廓进行了一次扩展，上图所描述的多边形简单，如果对任意复杂度的多边形执行这个过程就非常复杂了。这个过程叫“Polygon Offsetting”具体实现可以参考《Polygon Offsetting by Computing Winding Numbers》Paper no. DETC2005-85513 pp. 565-575 这篇论文中描述。
在正确进行了外轮廓的拓展后，多边形原本的区域被称为“实部” ，扩展出来的部分被称为“虚部” 。“实部”依旧按照正常的渲染方式进行，此外从“实部”径向渐变过渡到“虚部”的边缘就可以模拟出抗锯齿的效果。
总结
如前文所述，从分段贝塞尔曲线到二维构形，从多边形堆叠到通用多边形并交差。已经具备了完善的二维建模的能力，也配备了操作二维图形的手术刀。配合三角剖分算法可以完成和 GPU 的对接。
硬件加速的必要性
在计算机显卡还没有普及的年代， UI 依赖的矢量渲染器都是通过 CPU 来实现， CPU 通过线扫描为主的一系列算法来完成像素染色。此后 GPU 得到了广为普及，由于 GPU 的设计天然不适合来进行矢量渲染。故在早期尝试使用 GPU 来加速矢量渲染的尝试中大多得到的都是负优化。