動機
幾何線段包含無限多個點,數碼影像中的細線卻只能選出有限個像素中心。在追求計算速度之前,應先說明這些中心應如何選取。對平緩線段,每個水平座標選一個中心是合理的;但把同一做法直接套在陡峭線段上,就可能留下大空隙。把理想高度四捨五入時,也必須處理恰好位於兩行中間的情況。這些都是數學規格的一部分,不能留待程式碰到問題才補上。
上一節用仿射邊函數判斷三角形覆蓋。本節運用相同思想,為兩個端點均為整數像素中心的線段建立完整算法:先把線段轉換為平緩上升的標準形式,再把下一位置的理想高度與兩個候選行的中點比較,最後只用加法更新比較值。這是一種 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 算法;後者還須指定方格邊界的處理政策。選中中心亦不等於算出像素面積積分;反鋸齒需要筆劃足跡與濾波或取樣模型。
反例模式
裁剪端點先取整會改變後面的行
原線段 至 在 選第一行,因理想高度為 。幾何裁剪至 ,精確新端點是 。若先把它取整為 ,再對它與 使用整數端點算法,新線在 的高度是 ,會選第零行。裁剪加上端點取整改變了直線。保留原隱式直線及步進相位而裁掉原輸出,與光柵化一條重新取整的線段,是兩個不同規格。本文只處理實際輸入為整數端點的情況,沒有給出一般有理端點裁剪算法。
常見錯誤
(判定值反號卻沿用原來的不等號)
設判定值改用相反符號 ,卻仍沿用「 便上升」。在第一個例題,首個判定是 ,故 ,線段會上升到 ;但 的理想高度 最接近第 行。隱式函數的符號一旦改變,不等號也必須一併改變。
常見錯誤
(以為平手一律取原座標中較大的行)
平手規則是把標準次座標 往上取整,只有 時它才是較大的原座標。對 到 , 的理想高度為 ,輸出第 行。對 到 ,標準數據為 、、,同一平手給出 ,即第 行,是第 與第 兩行中較小的一行。若規則是「原座標的行一律半向上取整」,這裏會選第 行,得到不同的像素集合。
總結
標準轉換固定了主軸、走訪次序與平手的意義;中點不變量再以整數加法精確算出指定的最近行。端點歸屬、幾何裁剪與經濾波的筆劃覆蓋則各有自己的規則。比較程式影像與本節結果之前,應先把這些選擇寫清楚。
練習
快速檢查
(為甚麼最後輸出的判定值可以忽略?)
想想最後一次判定指的是哪個主座標。
解答 · 答案
它比較的是主座標 的中點,已在指定閉線段之外。此時兩端點均已輸出,不變量也已證明末次座標恰為 。額外判定只會延長光柵線,而不是完成它。
快速檢查
(光柵化 到 。列出全部中心及六次移動前的判定值,並逐點核對帶符號誤差不變量。)
先求 ,再用遞推式;每個中心的 。
解答 · 引導解答
中心為 。初值 ;六次移動前的判定是 。各點 為 ,全部在 。行誤差為 ,最大絕對值 。最後中心就是指定端點,不需第七次移動。
快速檢查
(使用完整標準轉換,光柵化 到 。有沒有平手?交換輸入會否改變像素集合?)
先交換座標,再按主座標排序。
解答 · 引導解答
先交換座標再排序,得到 、,因此 、、,而 。映回原座標的標準輸出為 。如需由 起步,倒轉清單即可。最簡斜率為 ,各理想高度都不是半整數,所以沒有平手。標準化使端點交換不改變像素集合。
快速檢查
(非零斜率約成最簡分數 。證明兩端點之間存在理想高度為半整數的整數主座標,當且僅當 為偶數。據此解釋斜率 為何沒有平手。)
平手即 ( 為整數);先消去分母。
解答 · 引導解答
平手表示 ,即 。若 為奇數,由互質可知 整除 ,則高度 為整數,矛盾。若 為偶數,互質使 必為奇數。取 ,高度為半整數 。由於 是 的正整數倍,此 嚴格在零與 之間。 的分母為奇數,故沒有平手。零斜率可直接處理:全部理想高度皆為零,因此沒有半整數平手。
快速檢查
(把上升判定改成只有 才上升。對 到 列出新中心及新的半開帶符號誤差區間。絕對最近行誤差界是否仍成立?)
時,嚴格測試會留在同一行。
解答 · 引導解答
新中心為 。半整數時選較小行,因此 ,等價於 。絕對誤差仍至多 ,但像素集合不同。證明時也須相應交換兩分支中嚴格與非嚴格不等式。
快速檢查
(折線依次由 經 到 。依走訪方向列出兩段包含端點的輸出,再給一條具體規則,使共同中心只輸出一次,且不遺失兩個外端點。)
先分別光柵化兩段,再決定每段省略哪個端點。
解答 · 引導解答
第一段為 ;第二段按其 的標準平手政策,為 。每段皆省略走訪方向的終點,最後再輸出一次 ,得到 。倒向走訪的線段必須先恢復所需順序,再決定省略哪個端點。轉角重複是歸屬問題,不是最近行證明失效。
快速檢查
(當前標準輸出有 、、、。計算 、下一中心及下一判定。為甚麼以 取代 ,回答的是另一個問題?)
用 與 ,再套用遞推式。
解答 · 引導解答
,。依指定平手規則上升,下一中心為 ,有 、。下一理想高度是 ,恰在一與二之間。錯誤式為 ,比較的是當前主座標 的理想高度與 ,並非 。把它拿來判定下一步便會留在一,違反本節平手規則。