解读布尔运算库 VectorBoolean

VectorBoolean 是 Cocoa 上的一个贝塞尔曲线布尔运算库,布尔运算是矢量绘图软件最基本的功能之一,连占据 UI 设计半壁江山的 Sketch 也是使用这个库做布尔运算的。

类说明

FBBezierGraph

这个类作为 NSBezierPath 的替代类,这个类与 NSBezierPath 可以方便的互相转换。

布尔运算时会将 NSBezierPath 转成这个类,做完布尔操作后再转回来。

- (id) initWithBezierPath:(NSBezierPath *)path方法中可以看到从 NSBezierPath 转换成 FBBezierGraph 的过程。

内部成员 _contours 为一个 NSMutableArray ,存储的是 FBBezierContour

FBBezierContour

FBBezierContour 相当于 NSBezierPath 的一个 subpath,一个 NSBezierPath 就是一条完整的线段。可以参考我写的NSBezierPath小记

内部成员 _edges 为一个 NSMutableArray ,存储的是 FBBezierCurve

FBBezierCurve

FBBezierCurve 与 NSBezierPath 的 Element 有点类似,但是不一样,Element 可以是一个点,但是 FBBezierCurve 代表的是曲线的一个线段。

内部成员 data 为一个 FBBezierCurveData,是一个结构体,存储的为贝塞尔曲线的信息(开始点、两个控制点、结束点)。就算是直线,FBBezierCurveData 也把他当成控制点在同一直线上的曲线处理。

上3个类总结

  • FBBezierGraph 包含若干个 FBBezierContour,FBBezierGraph 就相当于多个闭合图形的集合
  • FBBezierContour 包含若干个 FBBezierCurve,相当于一个闭合图(连续的线段构成的)
  • FBBezierCurve 相当于一个线段 (曲线)

FBBezierIntersection

FBBezierIntersection 记录两个 Curve 相交的信息。

location 是相交的点

_parameter1 成员的意思是相交点在线段1上的位置,比如中点,则 parameter1 为0.5;如果为开始点则 parameter1 为 0

_parameter1 成员的意思是相交点线段2上的位置

对应还存有 _curve1 和 _curve2

FBBezierIntersectRange

FBBezierIntersectRange 是记录两个 Curve 覆盖相交的信息。

_parameterRange1 记录的是第一个 Curve 相交部分的范围,比如0-0.5,就是第一个 Curve 开头到一半的位置都有相交

_parameterRange2 记录的是第二个

两个线段有一段是重叠,相交的不是点而是线段重叠,用FBBezierIntersectRange表示

FBEdgeCrossing

FBEdgeCrossing 代表相交点,在判断得到相交点后,存储记录到 FBBezierCurve

主要由 FBBezierIntersection 构成,但是还持有另一个线段的 FBEdgeCrossing 的引用。存在 counterpart 成员中

FBEdgeOverlap

FBEdgeOverlap 代表 Curve 的覆盖相交,即最小单位线段的覆盖相交,主要由 FBBezierIntersectRange 构成。

成员:

1
2
3
FBBezierCurve *_edge1;
FBBezierCurve *_edge2;
FBBezierIntersectRange *_range;

FBEdgeOverlapRun

FBEdgeOverlapRun 的唯一一个成员为 NSMutableArray *_overlaps;,存储的是 FBEdgeOverlap

每次往 FBEdgeOverlapRun 加 FBEdgeOverlap 时,FBEdgeOverlapRun 都检查新加入的是否与 _overlaps 的第一个或者最后一个为连续的,不连续的话则不添加并返回添加失败。

所以 FBEdgeOverlapRun 存储的是连续覆盖相交的 FBEdge 线段

- (BOOL) isComplete指的是是否形成闭合,即 _overlaps 中最后一个与第一个 fits

FBContourOverlap

FBContourOverlap 代表 Contour 的覆盖相交,在判断得到覆盖相交的线段的范围后,存储记录到 FBBezierContour 的 _overlaps 中

FBContourOverlap 的唯一一个成员为 NSMutableArray *_runs;,存储的是 FBEdgeOverlapRun

关于 Overlap 总结

FBEdgeOverlap、FBEdgeOverlapRun、FBContourOverlap的概念容易混淆,这里说明一下。

如果图3个正方形,红色、黑色、蓝色,以黑色为主

上面的1、2、3、4、5都分别代表一个 overlap 线段,是 FBEdgeOverlap 类型

红色与黑色 overlap 的线段为1、2

蓝色与黑色 overlap 的线段为3、4、5

  • FBEdgeOverlap 代表 overlap 的线段,这里的1、2、3、4、5都是 overlap 线段
  • FBEdgeOverlapRun 代表连续的 FBEdgeOverlap ,这里有3个,分别是:[1]、[2]、[3、4、5]
  • FBContourOverlap 代表某一 Contour 的所有 overlaprun,这里有两个,分别是 [ [1]、[2] ] 和 [ [3、4、5] ]

FBContourOverlap 存储在 FBBezierContour 中

关键流程

布尔运算算法的基本流程为:

  1. 拆解曲线,判断两个图形的相交点。
  2. 标记相交点,根据布尔运算的类型进行线段筛选。
  3. 遍历所有线段,组合需要的线段,组成新的图形

判断相交

在 FBBezierGraph 中的 - (void) insertCrossingsWithBezierGraph:(FBBezierGraph *)other

遍历两个 FBBezierGraph 的所有的 FBBezierCurve,判断 FBBezierCurve 之间的相交,并把相交的信息写入 FBBezierCurve

FBBezierCurve 中的 - (void) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange withBlock:(FBCurveIntersectionBlock)block

判断链两个 FBBezierCurve 的相交

最关键的方法在 FBBezierCurve 的

static void FBBezierCurveDataIntersectionsWithBezierCurve(FBBezierCurveData me, FBBezierCurveData curve, FBRange *usRange, FBRange *themRange, FBBezierCurve *originalUs, FBBezierCurve *originalThem, FBBezierIntersectRange **intersectRange, NSUInteger depth, FBCurveIntersectionBlock outputBlock, BOOL *stop)

代码非常多,就没看了

判断相交的结果可以通过 FBCurveIntersectionBlock 得到

判断相交例子

蓝色矩形大小为300x50,红色为100x50

以蓝色矩形左下角为原点,执行蓝色矩形 different 红色矩形

相交点判断,log 打印出来的点,的顺序为1,2,3,4

  • FBBezierIntersection1: location = (150, 0), param1 = 0.5, param2 = 0.0,

    param1为 点2 -> 点1 方向,蓝色箭头线段的位置

    param2位 点1 -> 点2 方向,红色箭头线段的位置

  • FBBezierIntersection2:location = (50, 0), param1 = 0.166667, param2 = 1

    param1为 点2 -> 点1 方向,蓝色箭头线段的位置,0.166667x300 = 50,0.166667为相交点在这个线段上的位置

    param2位 点1 -> 点2 方向,红色箭头线段的位置

  • FBBezierIntersection4:location = (50, 50), param1 = 0.833333, param2 = 0

    param1为 点3 -> 点4 方向,蓝色箭头线段的位置,0.833333为相交点在这个线段上的位置

    param2位 点1 -> 点2 方向,红色箭头线段的位置

标记线段

拿作者博客的例子来看,找到3个相交的线段,1、2、3,这三个线段标记为 inside

以矩形为主图形

如果做 union 的操作,那么就是【蓝色矩形 outside 的线段】+【红色圆形 outside 的线段】

如果做 difference 的操作,那么就是 【蓝色矩形 outside 的线段】+【红色圆形 inside 的线段】

只要能正确将线段进行标记、分割,就可以很容易进行布尔操作。

以 difference 操作为例,代码位置为:

- (FBBezierGraph *) differenceWithBezierGraph:(FBBezierGraph *)graph中调用:

1
2
[self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];//标记矩形 outside 的线段
[graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES];//标记圆形 inside 的线段

实际上,代码进行标记的不是线段,而是交点,Bezier 的线段是有方向的,我们假设正方形和圆形都是顺时针方向的

[self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];的意思是标记矩形,标记不在相交区域的线段,出相交区域的交点为 entry,进相交区域的交点为 exit。

对于矩形来说,交点1为 exit,交点2为 entry

[graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES]的意思是标记圆形,标记在相交区域内的线段,进相交区域的交点为 entry,出相交区域的交点为 exit

对于圆形来说,交点1为 entry,交点2为 exit

遍历线段

接下来遍历线段,完成布尔运算

方法为- (FBBezierGraph *) bezierGraphFromIntersections

这里做的操作简化来说就是:

从第一个 entry 的相交点开始,按照 next 的顺序遍历线段,每一段都加到新建的 FBBezierContour 中,直到遇到下一个相交点,切换到 counterpart 相交点上,如果为 entry 则继续添加每一个线段直到下一个相交点,然后又切到 counterpart 相交点,再继续。

上面逻辑,如果遇到的不是 entry 点,则反向操作,按照 previous 的顺序遍历线段,加到新建的 FBBezierContour 中,,,略

处理无相交的情况

参考

VectorBoolean作者的博客:

How to implement boolean operations on bezier paths

请用金钱尽情的践踏我