動機
圓是連續座標中的方程,圖像則是在格點上取樣。把整數橫座標代入平方根公式,是連接兩者的一種方法,但仍有幾個問題未解答:應該取樣哪一段圓弧?怎樣把樣點反射到其他部分?在座標軸或對角線上,兩次反射落在同一位置時怎樣處理?選中一個靠近圓的像素中心,又能否說明描邊覆蓋了該像素方格的多少面積?
整數直線筆記用一次隱式函數回答了相近的問題。圓的隱式函數是二次式,但相鄰位置的差仍可用整數加法更新。我們會從一個指定的中點推導加法公式,不直接挪用直線遞推,也不把帶分數的量悄悄換成某個熟悉的近似式。
本節規定一個二值邊界選點程序。像素中心為 中的點,縱座標向上增加,圓心 的兩個座標均為整數,半徑 是非負整數。證明中的運算均採用數學整數。這些假設使起始軸點和八向對稱都能配合格點。分數圓心、有限寬度描邊、反鋸齒,以及圖形 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,在本規格的精確算術下,輸出會否改變?)
考慮 與 對四的餘數。
解答 · 引導解答
與 均可被四整除,而 模四餘一。因此 ,不可能等於零。對這些輸入,兩種分支條件在精確算術下選出相同狀態。但改變輸入範圍或儲存式子後,不能以此為由任意處理零;溢位也會破壞精確算術的論證。
快速檢查
(列出半徑二的代表點和各自不同的軌道,再把結果平移至 。若實作不加去重,每個代表點都直接寫入八項,共有多少次寫入?規定的不同中心實際有多少個?)
逐步追蹤遞推式;每個代表點的軌道至多有八個點。
解答 · 引導解答
代表點為 的 和 的 。下一狀態 已越界,故不輸出。首條軌道為 。第二條為 。逐點加上 ,得規定的平移中心:,以及 。直接輸出八項會寫入十六次;規定集合只有十二個不同中心。
快速檢查
(證明對角線代表點最多一個,而且最後代表點的間距 只能為零或一。解釋為何附加首個越界狀態,會重複已有歸屬的軌道。)
逐步追蹤差值 。
解答 · 引導解答
對角線代表點使循環立即終止,所以不會再有下一個。若循環因越界退出,前一步的間距是正整數,而更新只減去一或二。要變為負數,只能從一減去二。因此最後輸出為 ,越界狀態為 ;兩者的有序絕對座標相同,故軌道相同。若在對角線停止,最後間距為零。由終止證明可知,只有這兩種停止情況。
快速檢查
(半透明來源以預乘 alpha 的 source-over 規則,在透明黑色上混合兩次,來源 alpha 為 。計算結果 alpha,並解釋即使整數座標不變,去重為何仍重要。)
反覆套用 。
解答 · 引導解答
Source-over 的 alpha 更新為 。第一次寫入得 ;第二次得 。更一般地,用歸納法可得重複寫入 次後為 。重複輸出同一個軸點或對角線中心,可能令半透明輪廓加深或變強。因此去重是輸出歸屬的一部分,不只是儲存上的優化。