动机
几何线段包含无限多个点,数字图像中的细线却只能选出有限个像素中心。在追求计算速度之前,应先说明这些中心应如何选取。对平缓线段,每个水平坐标选一个中心是合理的;但把同一做法直接套在陡峭线段上,就可能留下大空隙。把理想高度四舍五入时,也必须处理恰好位于两行中间的情况。这些都是数学规格的一部分,不能留待程序碰到问题才补上。
上一节用仿射边函数判断三角形覆盖。本节运用相同思想,为两个端点均为整数像素中心的线段建立完整算法:先把线段转换为平缓上升的标准形式,再把下一位置的理想高度与两个候选行的中点比较,最后只用加法更新比较值。这是一种 Bresenham 式中点直线算法。推导比背诵递推式更重要,因为它说明不等号的方向、整数状态所代表的量,以及换到另一八分区时应作哪些转换。
图像采用笛卡儿(Descartes)坐标,第二坐标向上增加,整数点为像素中心。若帧缓冲的行号向下增加,可以先转换坐标,或从头到尾使用另一套一致约定。本文包含两个端点,并以精确整数算术证明;固定字长溢出则属另外的实现问题。本文不声称这个规则等于任何图形 API 原生直线图元的覆盖规则。
定义
定义 2.2.1
(标准主坐标与次坐标)
设相异端点 、 属于 。若 ,把两端点的坐标交换,记作 ;否则使用 ,相等时亦不交换。重新排列端点,使 ,并定义
于是 、。令 、,线段便由 连至 ,在整数主坐标 的理想高度为 。
交换坐标处理陡峭程度;端点排序处理沿主轴向左或向下的输入方向;符号 处理负次斜率。次坐标对平缓线段是原行号,对陡峭线段则是原水平坐标。每一步都有逆运算。因此只需在 证明一次,再把选出的中心映回原坐标。若原端点重合,应在计算斜率之前直接返回该中心。
定义 2.2.2
(最近行与指定的平手规则)
对每个 ,选取整数次坐标
它是距离 最近的整数;恰好在两整数中间时选较大者。撤销坐标交换之前,实际中心为 。“较大”是指 ,不一定是原图像的行号。
次斜率为负时,增加 会减少 ,所以平手时可能选取原坐标中较小的次坐标。完整坐标转换与平手规则共同决定结果。本文先依主坐标排序端点,因此交换输入的两端点,仍会得到相同的输出序列。若调用者需要依原输入方向遍历,可以把标准序列倒转;像素集合不变。
定理 / 命题
在已输出中心 ,下一步的候选者为 及 。定义整数判定值
因为 ,其符号正好比较下一位置的理想高度与两行中点。当 时选上升候选,当 时留在同一行。
定理 2.2.3
(精确中点递推与最近行误差界)
设整数 、。从 、、 开始,输出 。每次判定后,令 增加一,并使用
其中三列依次是旧判定值、新次坐标与新判定值。输出主坐标 后停止。每次输出皆满足 ,以及
首尾中心恰为 及 。相邻中心差值只能是 或 ,包括斜率零与一。
上述界限是半开区间。恰好半整数时,选定行高于理想高度半个单位,因此带符号行误差可以等于 ,却不能等于 。把判定改成严格大于零,就得到另一个平手向下的算法。两种判定在精确平手时选中不同像素,覆盖结果必须可重现时便不能互换。
概念视角几何
把判定看成直线的侧别测试
在标准坐标中,支撑直线是 的零点集。于是 ,即 是 在下一列两个候选像素的中点处取值的两倍。 表示该中点在直线上或直线下方,直线从它上方经过,上升的像素更近; 则相反。
证明思路
证明
(对判定值做归纳)
在当前输出令 。同时证明下列不变量:
初始时 、,两式成立。若 ,便有 。保持 而增加 ,使 变成 。由 又有 ,故误差区间保持不变。新的判定式为 ,正是算法所用更新。
若 ,则 。增加 及 后,。另一方面, 且 ,故 。新的判定为 ,亦与递推一致。归纳证明了每次输出的不变量,过程没有使用浮点近似。
把误差界除以 ,得到 ,等价于 。所以每次确实选到规定的最近行,而只比较两个候选并没有漏掉更好的整数。在 时, 是 的整数倍,且在 内,只能等于零,因此 。两种步幅直接证明相邻性。撤销交换、符号改变及平移不会改变距离与相邻关系,所以结论适用于所有八分区。
证明透视
存储的是下一位置的中点测试
带符号量 描述已输出中心的误差; 则描述下一位置与半行边界的关系。混淆这两个时刻,是常见的索引偏移原因:先移至下一位置却仍沿用旧公式,就会比较错误的中点。递推式使两种意义一直一致。乘二消去半整数,再乘 消去有理斜率,因此全部比较都可以用整数完成。
定理 2.2.4
(到闭线段的距离)
在相同假设下,每个选定中心到闭线段的欧氏距离,至多为 。
证明
(到支撑直线的距离)
标准坐标中的支撑直线为 ,故 到它的垂直距离是
这也是到闭线段的距离,而不仅是到无限直线的距离。算法单调且以 结束,所以 、。垂足沿支撑直线的参数为 ,介于零与一,因此垂足在线段上。本定理约束的是所选中心,没有声称涵盖线段穿过的每个像素方格,也没有声称阶梯形结果与经滤波的有限宽度笔划具有相同外观。
例题详解
例题 2.2.5
(逐步追踪一个有理斜率)
取 、。不需交换、倒转或反射:、、。理想次高度为 ,初始判定 。下表列出 ,以及当前中心输出后将使用的判定值。
| 输出中心 | 下一步 | |||||
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 同行 | |||
| 1 | 0 | 3 | 上升 | |||
| 2 | 1 | 同行 | ||||
| 3 | 1 | 2 | 上升 | |||
| 4 | 2 | 同行 | ||||
| 5 | 2 | 1 | 上升 | |||
| 6 | 3 | 同行 | ||||
| 7 | 3 | 0 | 不再使用 | 停止 |
最大行误差为 ,分别在 及 以相反符号出现。相应垂直距离为 ,小于界 。表内皆为精确值,不必反复更新浮点高度再四舍五入。
例题 2.2.6
(恰好半整数与端点倒转)
从 到 ,选出的次坐标为 。当 ,理想高度为 ;当 ,为 ,两次都在标准坐标中向上取整。四次移动前的判定值是 。即使交换输入端点,算法也先恢复相同标准起点 ,故输出不变。
考虑另一种实现:直接从先给出的端点起步,平手时把次坐标往目的地方向移动。若从 开始,第一个半整数便选 ;本文在 的标准结果却是 。另一算法可以是合理的有向约定,但它不具输入倒转不变性。只说“选最近行”而不指定平手与排序,不能唯一决定像素集合。
例题 2.2.7
(陡峭线段的原水平坐标递减)
取 、。因 ,交换坐标后得到 、。此时 、、,标准次坐标为 。用 映回,得到
每个原图像行各有一个中心。若仍只沿原水平坐标迭代,最多选出三个中心,无法形成这条六中心相邻路径。因此选择主轴关乎结果是否正确,不只是速度上的优化。
完整整数程序与边界情况
以下伪代码使用数学整数,依标准主轴方向返回。亦可逐个输出中心,只保留固定数目的整数状态变量。
function raster_line(P, Q):
if P == Q: return [P]
steep = abs(Q.y - P.y) > abs(Q.x - P.x)
if steep:
(u0, v0) = (P.y, P.x)
(u1, v1) = (Q.y, Q.x)
else:
(u0, v0) = (P.x, P.y)
(u1, v1) = (Q.x, Q.y)
if u0 > u1: exchange (u0, v0) with (u1, v1)
a = u1 - u0
s = 1 if v1 >= v0 else -1
b = s * (v1 - v0)
k = 0
D = 2*b - a
output = []
for t = 0, 1, ..., a:
u = u0 + t
v = v0 + s*k
append (v, u) if steep else (u, v) to output
if t == a: break
if D >= 0:
k = k + 1
D = D + 2*(b-a)
else:
D = D + 2*b
return output
共执行 次输出迭代。若每次算术的成本视为常数,时间为 ;逐个输出时,额外状态空间为 ,存储整份清单则需 。任意大整数另有比特运算成本;固定字长则必须容纳坐标差、两倍量及中间加法。采用整数不代表自然免于溢出。
水平线段有 ,所以不会移动次坐标;垂直线段交换后就是水平线。对角线有 ,每一步都上升。例如倒转水平输入 会依标准顺序输出 ;输入 会输出 。重合端点只输出一个中心。这些情况都不用除以零、虚构容差或另设斜率公式。
单独线段包含两端点很自然。折线却会让相邻两段都输出共同顶点。若是直接覆写同一像素,可能无害;混合或计数则可能改变结果。可采半开线段约定,省略遍历方向的终点,再为最后一段另定规则。“终点”应依所需折线方向决定,不可自动当作标准主轴方向的末端。这是应用层的归属选择,不改变已证明的最近行计算。
常见错误
反例模式
最近行不等于涵盖所有碰到的像素
由 到 ,选定中心为 。线段上的 严格位于以 为中心、边长一、边界在半整数位置的方格内。线段在该格内具有正长度,中心却未被选中。因此本算法不是涵盖所有相交像素方格的 supercover 算法;后者还须指定方格边界的处理政策。选中中心亦不等于算出像素面积积分;反锯齿需要笔划足迹与滤波或采样模型。
反例模式
裁剪端点先取整会改变后面的行
原线段 至 在 选第一行,因理想高度为 。几何裁剪至 ,精确新端点是 。若先把它取整为 ,再对它与 使用整数端点算法,新线在 的高度是 ,会选第零行。裁剪加上端点取整改变了直线。保留原隐式直线及步进相位而裁掉原输出,与光栅化一条重新取整的线段,是两个不同规格。本文只处理实际输入为整数端点的情况,没有给出一般有理端点裁剪算法。
常见错误
(判定值反号却沿用原来的不等号)
设判定值改用相反符号 ,却仍沿用“ 就上升”。在第一个例题中,首个判定是 ,故 ,线段会上升到 ;但 的理想高度 最接近第 行。隐式函数的符号一旦改变,不等号也必须随之改变。
常见错误
(以为平手一律取原坐标中较大的行)
平手规则是把标准次坐标 向上取整,只有 时它才是较大的原坐标。对 到 , 处的理想高度为 ,输出第 行。对 到 ,标准数据为 、、,同一平手给出 ,即第 行,是第 与第 两行中较小的一行。若规则是“原坐标的行一律四舍五入向上取”,这里会选第 行,得到不同的像素集合。
总结
标准转换固定了主轴、遍历次序与平手的意义;中点不变量再以整数加法精确算出指定的最近行。端点归属、几何裁剪与经滤波的笔划覆盖则各有自己的规则。比较程序图像与本节结果之前,应先把这些选择写清楚。
练习
快速检查
(为什么最后输出的判定值可以忽略?)
想想最后一次判定指的是哪个主坐标。
解答 · 答案
它比较的是主坐标 的中点,已在指定闭线段之外。此时两端点均已输出,不变量也已证明末次坐标恰为 。额外判定只会延长光栅线,而不是完成它。
快速检查
(光栅化 到 。列出全部中心及六次移动前的判定值,并逐点核对带符号误差不变量。)
先求 ,再用递推式;每个中心的 。
解答 · 引导解答
中心为 。初值 ;六次移动前的判定是 。各点 为 ,全部在 。行误差为 ,最大绝对值 。最后中心就是指定端点,不需第七次移动。
快速检查
(使用完整标准转换,光栅化 到 。有没有平手?交换输入会否改变像素集合?)
先交换坐标,再按主坐标排序。
解答 · 引导解答
先交换坐标再排序,得到 、,因此 、、,而 。映回原坐标的标准输出为 。如需由 起步,倒转清单即可。最简斜率为 ,各理想高度都不是半整数,所以没有平手。标准化使端点交换不改变像素集合。
快速检查
(非零斜率约成最简分数 。证明两端点之间存在理想高度为半整数的整数主坐标,当且仅当 为偶数。据此解释斜率 为何没有平手。)
平手即 ( 为整数);先消去分母。
解答 · 引导解答
平手表示 ,即 。若 为奇数,由互素可知 整除 ,则高度 为整数,矛盾。若 为偶数,互素使 必为奇数。取 ,高度为半整数 。由于 是 的正整数倍,此 严格在零与 之间。 的分母为奇数,故没有平手。零斜率可直接处理:全部理想高度皆为零,因此没有半整数平手。
快速检查
(把上升判定改成只有 才上升。对 到 列出新中心及新的半开带符号误差区间。绝对最近行误差界是否仍成立?)
时,严格测试会留在同一行。
解答 · 引导解答
新中心为 。半整数时选较小行,因此 ,等价于 。绝对误差仍至多 ,但像素集合不同。证明时也须相应交换两分支中严格与非严格不等式。
快速检查
(折线依次由 经 到 。依遍历方向列出两段包含端点的输出,再给一条具体规则,使共同中心只输出一次,且不遗失两个外端点。)
先分别光栅化两段,再决定每段省略哪个端点。
解答 · 引导解答
第一段为 ;第二段按其 的标准平手规则,为 。每段皆省略遍历方向的终点,最后再输出一次 ,得到 。倒向遍历的线段必须先恢复所需顺序,再决定省略哪个端点。转角重复是归属问题,不是最近行证明失效。
快速检查
(当前标准输出有 、、、。计算 、下一中心及下一判定。为什么以 取代 ,回答的是另一个问题?)
用 与 ,再套用递推式。
解答 · 引导解答
,。依指定平手规则上升,下一中心为 ,有 、。下一理想高度是 ,恰在一与二之间。错误式为 ,比较的是当前主坐标 的理想高度与 ,并非 。把它拿来判定下一步便会留在一,违反本节平手规则。