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

具体内部原理并不复杂，实现的难度并不大，这里就不过度对其实现原理加以概述。

文章图片

文章图片
上图简单的描述了用分段贝塞尔曲线来拟合椭圆并三角化成 Mesh 的整个流程。
最后做个科普贝塞尔曲线不是贝塞尔发明的，贝塞尔曲线也不是唯一可以用来做拟合的工控曲线。机械加工有时候要求零件表面曲率平滑，也就是曲线二阶导数平滑那么贝塞尔曲线就无能为力了。但是在图形这个分支下贝塞尔曲线和贝塞尔曲面倒大放异彩。
建模构形
尽管通过塞尔曲线有着非常好的拟合的特性。但是在构建复杂多边形轮廓的时候，完全通过贝塞尔曲线来拟合还是不够方便。
如果把贝塞尔曲线构建的面所围成的区域看成一个集合，如果可以像数学集合一样进行 “并交叉” 运算，就可以更加方便的操作二维空间。在图形学中把这类操作看成多边形的“布尔”运算，操作的过程可以当做多二维多边形的建模或者叫构形。

文章图片

文章图片
多边形减法

文章图片

文章图片
多边形加法
就如上图所示，如果直接构建左侧的多边形会有一些困难。但是利用多边形的布尔运算就比较容易了。
多边形堆叠
一个复杂多边形的数据定义出现了一部分区域和另一部分区域重叠，这个时候问题就开始变的异常复杂了。

文章图片

文章图片
不仅仅在多边形定义的过程中会出现多边形区域重叠。回想一下绘制折线的过程需要对折线中的子线段进行法线平移，相当于扩大了线段描述的区域。那么扩大了区域的同时难免会出现多边形区域重叠。而渲染器在执行渲染前需要对多边形进行堆叠的剔除。
布尔运算
在详细描述如果解决多边形堆叠问题前，先来了解一下多边形布尔运算。Skia 中存在对 SkPath 的 OP 操作就是对这个算法的实现。剔除多边形堆叠就可以简化成对多边形“自己”和“自己”求并集。
这是一个古老的数学问题。不仅在图形学中存在，在材料科学等领域都有广泛的使用场景。数学家们为了找到这个问题的完美解，历时长达 50 年，直到 1990 年 Vatti bala 发表的博士毕业论文《A Generic Solution to Polygon Clipping》才标志着这一问题被解决。
值得一提的是中国前计算几何协会的会长、浙江大学前数学系的主任、中国计算几何的泰斗梁友栋教授早在 Vatti 这篇论文发表的 10 年之前给出了一个存在约束条件的解，也就是著名的Liang-Barskey算法。
直到 2009 年时隔 20 年后 Francisco Mart?′nez 发表了《A new algorithm for computing Boolean operations on polygons》貌似给出了一个更快的解决方案。此外从行业的经验来看， Boost 库中的多边形运算的子库被认为是错误的实现。
由于《A Generic Solution to Polygon Clipping》这篇文章，后续这类算法和衍生算法被简称为 GPC 。
GPC 通用多边形裁剪
得到 GPC 的过程非常坎坷，但是算法本身却十分容易描述。如下简要的描述下算法的整个过程。为了简单，采用下图 2 个凸多边形的并集运算作为样例。
算法的关键在于求出边的“交点”和“交点的进出性” 。“交点”相对比较容易理解，姑且不表。“进出性”可以用来表达交点和对应多边形的关系。比如下图交点 “C0” 如果从多边形 B 的 B0 点出发，那么“C0”点对于多边形 A 来说是“外部”进入到“内部” ，相对应的“C0”点就是多边形 B 的出点。“进出性”对后续的多边形裁剪有着非常重要的意义。