动机
圆是连续坐标中的方程,图像则是在格点上取样。把整数横坐标代入平方根公式,是连接两者的一种方法,但仍有几个问题未解答:应该取样哪一段圆弧?怎样把样点反射到其他部分?在坐标轴或对角线上,两次反射落在同一位置时怎样处理?选中一个靠近圆的像素中心,又能否说明描边覆盖了该像素方格的多少面积?
整数直线笔记用一次隐式函数回答了相近的问题。圆的隐式函数是二次式,但相邻位置的差仍可用整数加法更新。我们会从一个指定的中点推导加法公式,不直接挪用直线递推,也不把带分数的量悄悄换成某个熟悉的近似式。
本节规定一个二值边界选点程序。像素中心为 中的点,纵坐标向上增加,圆心 的两个坐标均为整数,半径 是非负整数。证明中的运算均采用数学整数。这些假设使起始轴点和八向对称都能配合格点。分数圆心、有限宽度描边、反锯齿,以及图形 API 的原生规则,都需要另外规定。
定义
定义 2.3.1
(圆的隐式函数与基本八分区)
先使用相对圆心的偏移坐标,定义
负值表示圆内,正值表示圆外。本节使用的基本八分区为 。从精确的轴点 起步。在 的状态,下一步的两个候选点是东点 和东南点 。
两个候选点都把横坐标增加一;第二个还把纵坐标减少一。两者的中点为 。方位名称采用本节纵坐标向上的惯例;若帧缓冲区的行号向下增加,必须一致地转换坐标。
定义 2.3.2
(精确中点判定与闭八分区规则)
存储经放大的中点值
当 时输出当前状态。若 ,立即停止这个八分区。否则, 时选 , 时选 。移动后,只有仍满足 才输出新状态;越过对角线的状态不算另一个八分区样点。
弱不等式把相等情况也写清楚:假如判定值为零,便选较低的候选点。不过,奇数的平方模四余一,所以 。在本模型中不可能等于零。这是关于精确中点相等的结论,不表示其他距离概念下的平手都已排除。
为什么符号与分支是这个方向?在任何非终止判定之前,,因此 ,圆的上半弧具有实数高度
而且 。所以 等价于 ,即 在竖直方向上比 更接近 。当 ,便有 ,较低的候选点在竖直方向上更近。这只确立了两个指定候选点之间的比较;本节没有宣称整体最近像素或最近径向距离定理。
递推式与证明
起始状态的判定为
设旧坐标为 。向东移动后,下一个被测试的中点由 变为 ,所以
向东南移动后,中点变为 ,于是
这些公式使用移动前的坐标。若把已经增加的横坐标代入相同式子,计算的便是另一个多项式。
定理 2.3.3
(精确判定不变量与有限终止)
对整数 ,初始化 、、。在每个非终止输出状态,采用下列其中一个同步更新:
在每个到达的状态,都有 和 。每个输出状态满足 。程序最多移动 次便终止。相邻的输出状态之差为 或 。对 ,结果只有圆心;提前返回是方便的写法,并非必要。
证明
(对两个分支做归纳)
起始恒等式已在上面算出。假设它在旧状态成立,前面的两个多项式差便恰好给出相应新状态的恒等式。以归纳法可证明两个分支都保持恒等式,包括最后一个越界而不再使用判定值的状态。模四的结论可直接由显示的多项式得到,也可由起始余数和两种增量均为四的倍数得到。
起初 。在非终止的输出状态有 ,故 。新横坐标非负,而两种更新都保证 。若新状态仍在基本八分区中,所有输出状态的不等式便再次成立;否则舍弃该状态并停止循环。特别是,不会输出负纵坐标。
为证明终止,令 。起始值是 ;每次东移使它减少一,每次东南移使它减少二。只有 才容许移动。因此最多移动 次,就会到达 ,输出后立即停止;或越界至 ,不予输出。两种位移也给出相邻关系的结论。当 ,起始状态已在对角线上。八项轨道清单全部等于 ,所以局部去重后只得一个中心,而一般循环在任何移动之前就停止。提前返回只是把此情况写得更明确。全部结论得证。
证明透视
不变量证明了什么,又未证明什么
不变量把一个存储整数,对应到下一对候选点之中点的隐式函数值。它并没有把 当成已输出中心的误差:该中心的隐式值是 ,位置与数量都不同。符号比较证明的是两个纵向候选点之间较近的选择。这个比较和有限终止,本身都不会证明全局径向最优、涵盖所有碰到的方格、Hausdorff 距离界或反锯齿公式;那些都需要独立的命题与证明。
最后一个八分区样点为何不需要额外端点
若最后输出的是对角线状态,它本身就是关于 的反射像。若循环因越过对角线而退出,最后输出状态必有 。原因是从正整数间距变成负数,只可能由东南移动从间距一减去二;从间距一向东移动只会到零,仍须输出。因此,越界前最后一对为 ;看来没有输出的相邻点 ,会由反射提供。把越界状态再当作一个八分区样点输出,只会重复它已经拥有的对称轨道。
八向对称与重复写入
对偏移 ,依序形成以下候选清单:
每个偏移都加上 ;在清单内只保留每个位置首次出现的一项。八个目的位置不一定是八个不同像素。当 , 只给四个轴上像素;当 , 只给四个对角线像素;当 ,才有八个不同像素。零半径情况只有一个。
定理 2.3.4
(唯一轨道归属与八连通边界)
各输出代表点的对称轨道互不相交。对 ,若有 个代表点,并令 表示最后代表点位于对角线,否则 ,则不同输出中心的数量为
其并集是八连通的:任意两个选中中心之间,存在一条只经过选中中心的路径,每一步在两个坐标上的变化绝对值都不超过一。
证明
(轨道唯一性与连通性)
轨道中的任何点,都决定唯一的非负有序绝对坐标 。它们正好还原基本八分区代表点。由于 严格增加,代表点不会重复,因此不同代表点不可能拥有共同轨道。起始代表点是唯一在轴上的代表点。对角线代表点最多一个,因为到达后立即停止。轴上计四点,可能的对角线计四点,其余各计八点,即得公式。 的限制很重要:半径零时,轴与对角线代表点重合,公式会给出零,而正确数量是一个中心。
在基本八分区内,相邻代表点是八邻点。反射保持这种关系。在对角线附近,两段反射路径要么共用一个对角线端点,要么端点分别为 和 ;由停止规则可知,后两点仍是八邻点。在坐标轴上,相邻反射路径共用同一轴点。由上方轴点开始顺时针绕行,可依序使用变换后的路径 ,其中每第二条路径反转遍历方向;接合处交替位于对角线与坐标轴。接合这些路径便连接了全部选中中心。这是选中像素图的连通性结论,不是把这幅图等同于连续圆或经过滤波的描边。
八项清单中首次出现的顺序,确立了确定的输出次序,但并非沿角度绕行边界的次序。若应用需要顺时针折线,必须依角度次序接合各八分区路径。若应用涉及计数或 alpha 混合,即使重复的不透明写入看来无害,也必须去除重复位置。
例题
例题 2.3.5
(半径三:每个状态与每条轨道)
取 、。起始判定为 。表中列出对角线状态所存储的判定值,方便核对不变量,但不会使用它作下一步判定。
| 当前 | 输出后动作 | 使用旧坐标的更新 | ||
|---|---|---|---|---|
| 东移 | ||||
| 东南移 | ||||
| 在对角线停止 | 不作下一步判定 |
第二行的中点为 ,其隐式值为 ;乘四后正是存储的 。所以算法把下一个纵坐标降低。相对精确圆,输出同时包含圆内和圆外中心:二值边界选点不等于坚持 。
在各轨道内去重后,三条轨道为
因此 、、。若把圆心移至 ,只须把这十六个中心逐一加上 ;偏移坐标的全部运算与判定均相同。
例题 2.3.6
(半径五:越界就是停止事件)
对 ,输出状态及其存储判定为
首两步向东。下一步向东南,增量为 ,把 从 变为 。最后再向东南移动,到达基本八分区之外的 。它不会作为新代表点输出,因为它已属于 的轨道。共有四个代表点,没有对角线代表点,故有 个不同输出中心。
例题 2.3.7
(最小的半径)
对 ,。先输出轴代表点 ;因 ,向东南移至 ,它已越界,不作输出。最右点是否漏掉了?没有: 早已属于 的轨道。、,个数为 ,即 。对 ,起始状态 在对角线上,循环在任何移动之前停止,八个轨道项合并为唯一的中心 ;提前返回给出同一结果。
完整整数程序
以下程序依照证明的顺序更新:先用旧 计算新判定,再改变坐标。unique_in_order 在最多八对坐标的清单中,只保留每项首次出现的位置。
function raster_circle(C, r):
require C.x and C.y are integers; require integer r >= 0
if r == 0: return [C]
x = 0
y = r
D = 5 - 4*r
output = []
while x <= y:
orbit = [(x,y), (y,x), (-x,y), (-y,x),
(-x,-y), (-y,-x), (x,-y), (y,-x)]
for (u,v) in unique_in_order(orbit):
append (C.x + u, C.y + v) to output
if x == y: break
if D < 0:
D = D + 8*x + 12
x = x + 1
else:
D = D + 8*x - 8*y + 20
x = x + 1
y = y - 1
return output
不需要为全部输出建立哈希集合:唯一轨道归属已获证明,八项局部清单可用常数空间去重。在每次算术运算成本固定的模型下,时间为 ;若逐项输出,辅助空间为 。存储输出则需 空间。数学整数隐藏了比特成本;固定宽度的实现必须确保圆心平移、初始乘积及中间更新均不溢出。本节没有提供机器整数范围认证。
误解与反例
反例模式
分数圆心不保留这个格点构造
半径一、圆心在原点时,算法输出四个轴中心 。若把这些偏移加上 ,所得横坐标是半整数,不是整数像素中心。这些位置不能直接用作整数中心。把圆心取整至格点会改变圆:在整数像素中心 ,真正平移后圆的隐式值是 ;若先把圆心取整到原点,隐式值则是 。
关于分数圆心的八向对称,也不会自动保持整数格点。把 相对 的两个偏移互换,得到的是 ,并非整数中心。某些特殊分数圆心确实保留部分格点对称,但这不足以证明目前的轴点起始及递推适用于任意圆心;必须重新建立模型和推导。
反例模式
选中的边界像素不等于完全覆盖
要定义真正有宽度的描边,可取圆环 ,并采用单位方形盒式滤波。以 为中心的像素方格,在中心附近有一个开邻域位于圆环内;但在其角点 附近,也包含一块正面积区域位于圆环外,因为 ,而且距离函数连续。其覆盖面积严格介于零与一。二值半径一算法会选中该中心并写入完整二值,却没有计算这个分数面积。
零宽度的理想圆周面积为零,所以对它的一般面积指示函数积分,每个像素都只会得到零。要得到可见的反锯齿轮廓,除了滤波器,还须指定宽度或其他重建模型。八向对称与精确整数递推,并没有补上这些定义。
常见错误
(混用不同写法的初值与递推式)
常见的算术捷径,是先把另一个存储量初始化,例如 ,再套用取自别处的递推式。这个值并不是本文在第一个中点处的精确值 。它可能在另行证明的变换下定义出等价的算法,也可能是另一个算法;把不同写法的初值与更新式混用,不能推出等价。应让定义性的不变量始终对应被存储的量。
常见错误
(测当前中心而不是下一个中点)
只测当前输出中心的 ,问的是该中心在圆内还是圆外,并没有比较接下来的两个候选点。以半径三为例, 没有可据以行动的符号,而判定值是 ,正确的一步是向东。把一种符号换成另一种,会混淆两个不同的测试。
习题
快速检查
(追踪半径四。列出每个输出代表点和判定值、每个非终止状态后的移动,以及不同输出中心的数量。)
从 出发,套用更新表。
解答 · 引导解答
代表点为 ,判定依序为 。从第一点向东:。从 向东南:。从 向东:。在 停止,不使用其判定。有 和 ,故输出数量为 。
快速检查
(某输出状态为 、、。直接计算 ,选择下一个状态,并以两种方法计算其判定。说明递推需要哪些旧坐标。)
先代入定义多项式,再与更新结果比较。
解答 · 引导解答
直接代入得 。向东南到达 。旧坐标更新为 。在新状态直接代入得 ,完全一致。若把 用在旧坐标增量中,则会加上 ,得到 ,破坏不变量。
快速检查
(证明整数半径与整数状态不可能发生精确中点相等。若程序把 D < 0 改为 D <= 0,在本规格的精确算术下,输出会否改变?)
考虑 与 模 4 的余数。
解答 · 引导解答
与 均可被四整除,而 模四余一。因此 ,不可能等于零。对这些输入,两种分支条件在精确算术下选出相同状态。但改变输入范围或存储式子后,不能以此为由任意处理零;溢出也会破坏精确算术的论证。
快速检查
(列出半径二的代表点和各自不同的轨道,再把结果平移至 。若实现不加去重,每个代表点都直接写入八项,共有多少次写入?规定的不同中心实际有多少个?)
逐步跟踪递推式;每个代表点的轨道至多有八个点。
解答 · 引导解答
代表点为 的 和 的 。下一状态 已越界,故不输出。首条轨道为 。第二条为 。逐点加上 ,得规定的平移中心:,以及 。直接输出八项会写入十六次;规定集合只有十二个不同中心。
快速检查
(证明对角线代表点最多一个,而且最后代表点的间距 只能为零或一。解释为何附加首个越界状态,会重复已有归属的轨道。)
逐步跟踪差值 。
解答 · 引导解答
对角线代表点使循环立即终止,所以不会再有下一个。若循环因越界退出,前一步的间距是正整数,而更新只减去一或二。要变为负数,只能从一减去二。因此最后输出为 ,越界状态为 ;两者的有序绝对坐标相同,故轨道相同。若在对角线停止,最后间距为零。由终止证明可知,只有这两种停止情况。
快速检查
(半透明来源以预乘 alpha 的 source-over 规则,在透明黑色上混合两次,来源 alpha 为 。计算结果 alpha,并解释即使整数坐标不变,去重为何仍重要。)
反复套用 。
解答 · 引导解答
Source-over 的 alpha 更新为 。第一次写入得 ;第二次得 。更一般地,用归纳法可得重复写入 次后为 。重复输出同一个轴点或对角线中心,可能令半透明轮廓加深或变强。因此去重是输出归属的一部分,不只是存储上的优化。