从轮廓到采样点
多边形轮廓告诉我们形状在哪里结束;光栅化却要判定哪些采样点在形状内。水平线与凸多边形的内部相交,至多得到一个区间;非凸多边形却可能得到多个区间。只连接最左和最右的交点,就会把应属背景的空隙填起来。我们需要一个能找出所有区间的规则,并且在扫描线经过顶点时仍然有效。
这里的多边形是简单多边形:有限条直边组成一条不自交的闭合边界,相邻边只在共同端点相交。假设每条边长非零,且不相邻的边不相交。顶点与采样点的坐标均为精确实数;多边形可以是凹的,也可以有水平边。我们逐点分类,得到的是二元采样遮罩,不是多边形在像素内的面积。下面明确选定的边界规则并不声称符合某个图形 API。
定义 2.6.1
(内部、边界与奇偶采样规则)
Jordan 曲线定理指出,简单闭合多边形曲线把平面分成有界的内部和无界的外部。我们称位于内部或边界的采样点为被覆盖。对不在边界上的点,奇偶规则从右方足够远处的外部开始,沿水平射线每穿过一次边界便切换状态;交叉次数为奇数时,该点在内部。
先测试边界,使单独的多边形成为闭集合;但若两个相邻多边形各自绘制,共边上的采样点可能写入两次。若网格光栅器要求每个采样点恰有一个写入者,便需要另一套一致的归属规则。有限条线段的面积为零,故这些边界规则不改变面积。
扫描线上的事件
设一条非水平边的两端依高度重排为 和 ,其中 。对高度 的扫描线,当且仅当
时,把该边列入事件。线性插值得到事件的水平坐标:
水平边不产生交叉事件,但仍须纳入独立的边界测试。把事件坐标收集成多重集合,保留相等数值及其重数,排序为 。不要删除重复坐标:两个相等事件代表两次切换,在该坐标以外互相抵消。
定理 2.6.2
(半开端点规则下的精确奇偶判定)
对任何简单多边形及实数高度 ,上述事件总数为偶数。对不在边界上的点 ,它在内部当且仅当严格位于 右侧的事件数为奇数。等价地,排序后它属于开区间 之一;这些区间可以为空。如果点在边界上,应在应用此表述前返回“被覆盖”。
证明
(由向上微扰得到奇偶性)
先假设 不等于任何顶点高度。每个交点都位于非水平边的内部,而水平线在该处局部穿过边界,因此在内部与外部之间切换。多边形有界,所以水平线左右两端足够远处都在外部。切换总数必为偶数;从右方数起便得到所述奇偶性。这里用的是定义中的分离性质,无须假设凸性。
现在容许 等于顶点高度,并固定一个不在边界的点 。边界是紧致集,故此点与边界的距离为正。取充分小的 ,使 不等于任何顶点高度,且由 至 的垂直线段不碰边界。两点同在内部或同在外部。对每条非水平边,当正的 充分小时,高度 有交点,当且仅当 ;此时交点横坐标趋向 。水平边不会产生这样的交点。任何极限事件都不可能等于 ,否则 在边界上。因此,充分小的 下, 右方的极限事件数等于高度 的右方交点数。由第一种情况得出奇偶判定。再取足够靠左的 ,可知事件总数为偶数。排序便得到成对开区间的说法;相邻事件相等时,对应区间为空。
证明透视
为何包含一端、排除另一端
把高度 的扫描线看成从上方靠近的扫描线之极限。局部最低顶点有两条边开始,产生两个重合事件;局部最高顶点以上没有边延续,产生零个事件;非极值顶点则恰有一条边延续,产生一个事件。同一极限论证亦处理水平边,而边上的点另作测试。若每条边都把两个端点计入,普通顶点会被计两次,可能把答案翻转。
定理的开区间表述只适用于不在边界的点。事件坐标本身可能是边界点,不能仅凭开区间判断其状态。水平边上的采样点也可能严格位于两个事件之间,但它是边界点,不是内部点。先测边界便能处理两种情况。
反例模式
把每条边的两个端点都计入
命题:只要 就计入该边,这样不会漏掉顶点。取凸五边形 与 。顶点 只是普通的穿过顶点,但它的两条边都被计入,事件为 。内部点 右边就有两个事件,会被判为外部。采用半开规则 时,事件为 , 右边有一个事件,因此是内部点。
完整计算
例题 2.6.3
(U 形多边形)
依次取顶点
在 时,只有四条垂直边与扫描线相交,排序后的事件为 。内部区间为 和 。因此 和 在内部,而 位于开口内的外部。边界点 和 按本规则均被覆盖。
在 时,因为 和 是被包含的下端点,仍得到同样四个事件。不过 在凹槽的水平边上,虽然它右方事件数为偶数,仍因边界测试而被覆盖。在 时,上端点被排除,故没有事件;顶部水平边上的点仍在边界上而被覆盖。这正是不能直接从多边形删除水平边的原因。
例题 2.6.4
(扫描线经过凹口顶点)
依次取顶点
边 至 与边 至 在 时分别给出事件 和 。由 至 的边有 ,事件为 ;由 至 的边,事件为 ;两者在 时活动。底边是水平边,不产生事件。
在 ,事件为 ,所以 与 是内部, 在凹口内。在 ,顶点 是上方轮廓的局部最低点,两条边都被包含,两个事件同为 ,事件表为 。点 右侧有 三个事件,个数为奇数,故在内部; 右侧有一个事件,也在内部;尖端 在边界上,因而被覆盖。于是从 到 的整行都被覆盖。若删去两个相等事件之一, 的个数就变成偶数,被误判为外部。在 ,所有上端点都被排除,没有事件: 和 是边界点,被覆盖; 不在边界上,属于外部。
例题 2.6.5
(夹在下降边与上升边之间的水平边)
依次取顶点
非水平边为: 的 、 的 ,以及 的 。在 ,事件为 ,故 在内部。在 ,边 的上端点被排除,边 的下端点被包含,而由 至 的水平边不产生事件,所以事件为 。“下降边、水平边、上升边”这条链总共只贡献一个事件,与普通顶点相同。
点 右侧有一个事件,在内部。点 右侧没有事件,在外部。点 右侧同样没有事件,单看奇偶性会判为外部;但它在水平边上,边界测试返回被覆盖。预先做边界测试,正是为了这种情况。
反例模式
为何最左与最右交点不足够
在高度 ,U 形的最外事件为 和 。把中间全部填满会错误地覆盖 。错误在于假设所有多边形的水平截面皆连通:凸性可以支持此假设,简单性却不可以。
常见错误
(合并相等的事件)
在局部最低点,两条边从同一坐标开始,事件表中该数值出现两次。为了整齐而删去重复项,凹口例子中的 就变成 ,长度为奇数,最后没有配对。内部点 右侧只剩 两个事件,被误判为外部。必须保留重数:两次相等的切换在 的右侧互相抵消,而 看到的是 。
常见错误
(让奇偶性凌驾于边界测试之上)
奇偶性的表述只对不在边界上的点分类。U 形多边形在 这一行没有事件,所以每个计数都是偶数;但 在由 至 的顶边上,应被覆盖。同样, 的计数为偶数,却在凹槽边上。必须先做边界测试。
明确算法与有理数算术
对每个采样点 :
- 测试该点是否位于任何闭边上;若是,返回被覆盖。
- 对每条满足 的非水平边计算其事件坐标。
- 计算满足 的事件数,保留重复项;当且仅当数目为奇数时返回被覆盖。
命题 2.6.6
(采样测试的正确性)
上述三步程序对采样点 返回“被覆盖”,当且仅当该点属于闭多边形,即在内部或边界上。
证明
(先测边界,再看奇偶)
若采样点在某条边上,第 1 步返回被覆盖,与定义一致。否则第 1 步放行,第 2、3 步恰好算出定理所用的事件多重集合,以及 右侧的事件个数。由定理,奇数表示内部,偶数表示外部。外部点既不在内部也不在边界上,故不被覆盖,结果正确。
若同一行有许多采样点,可先计算并排序一次事件,再同步扫过排好序的采样点和事件。
命题 2.6.7
(单行分类的代价)
固定高度 的一行,多边形有 条边,该行有 个采样点。不计第 1 步的边界测试,计算事件需要 次算术运算,事件排序需要 次比较,采样点排序需要 次比较。两个表都排好序后,只需再做 次比较的一趟同步扫描,就能分类全部 个采样点。
证明
(对两个已排序表做单调扫描)
每条边只需测试一次 ,并至多插值一次,故共 次运算,事件至多 个。把事件与采样点都按递减顺序排序,维护事件表的指针,以及严格大于当前采样点的事件个数 。处理下一个采样点 时,只要当前事件大于 ,就推进指针并把 加一;之后 在内部,当且仅当 为奇数。采样点递减,指针不会回退,所以总共至多移动 步,每个采样点只处理一次。
若采样点已经排好序, 这一项就消失。对每个采样点逐条边做朴素的边界测试,则额外需要 次线段测试。活动边表可以避免每行重新扫描所有边,但其维护与边界处理的代价必须另行计算。
概念视角算法
把边看成带固定增量的扫描
设 为非水平边斜率的倒数。事件公式关于 是仿射的,,所以只要该边在 与 都活动,就有 。边只在半开高度区间 内活动,因此扫描只需维护一张活动边表,它只在顶点高度处改变,每一行对每个事件做一次加法。以由 至 的边为例,, 与 的事件分别为 和 。使用精确有理数时, 是固定的有理数,更新没有误差;若在浮点数中累加已舍入的 ,结果会逐渐偏离插值公式。
若顶点坐标为整数,采样高度为有理数,事件坐标也是有理数。分母调整为正之后,可以交叉相乘比较有理数,避免排序时作舍入选择。点位于从 至 的线段上,当且仅当它与 的二维叉积为零,且两个坐标分别位于端点相应坐标之间。这些精确比较需要无界整数,或已证明足够的整数位宽;固定宽度溢出可改变奇偶结果。浮点相等、几乎重合的交点及 API 特定的并列规则,均需要进一步数值设计。
练习
快速检查
(对 U 形多边形,在先测边界的规则下判定 、 和 。)
先求高度 的事件。
解答 · 答案
高度 的事件为 。第一点在凹槽内,属于外部;第二点在边界上,被覆盖;第三点在 内,属于内部。
快速检查
(三角形顶点为 。列出 和 的扫描线事件,并判定 。)
注意每条边排除哪一个端点。
解答 · 答案
在 ,两条斜边给出 。在 ,两个上端点都被排除,事件表为空;但 是顶点,先前的边界测试会判定其被覆盖。
快速检查
(非水平边由 连至 。求 时的事件,并判定 时该边是否活动。)
用插值公式,其中 、。
解答 · 答案
插值得 。上端点高度 被排除,故该边在此高度不活动。
快速检查
(在 有两个重合事件, 与 之间没有其他事件。采样点从 移到 ,奇偶性会改变吗?能否断定 在外部?)
先数两个采样点之间的切换次数,再想想 是什么点。
解答 · 答案
切换两次不改变奇偶性。事件点本身在多边形边界上,按本规则被覆盖;远离事件处的奇偶性不能判定事件点本身。
快速检查
(解释两个相邻多边形都采用先测边界规则时,为何可能同时覆盖同一个采样点;给出不改变多边形面积而避免重复写入的一种方法。)
考虑共边上的采样点。
解答 · 答案
共边上的采样点属于两个闭边界。整个网格可以用一致的半开归属规则,只把共边分配给其中一个多边形,并一致处理顶点。边界线段的面积为零,因此改变其归属不会改变多边形的几何面积。