從輪廓到取樣點
多邊形輪廓告訴我們形狀在哪裏結束;光柵化卻要判定哪些取樣點在形狀內。水平線與凸多邊形的內部相交,至多得到一個區間;非凸多邊形卻可能得到多個區間。只連接最左和最右的交點,就會把應屬背景的空隙填起來。我們需要一個能找出所有區間的規則,並且在掃描線經過頂點時仍然有效。
這裏的多邊形是簡單多邊形:有限條直邊組成一條不自交的閉合邊界,相鄰邊只在共同端點相交。假設每條邊長非零,且不相鄰的邊不相交。頂點與取樣點的座標均為精確實數;多邊形可以是凹的,也可以有水平邊。我們逐點分類,得到的是二元取樣遮罩,不是多邊形在像素內的面積。下面明確選定的邊界規則並不聲稱符合某個圖形 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 形多邊形,在先測邊界的規則下判定 、 和 。)
先求高度 的事件。
解答 · 答案
高度 的事件為 。第一點在凹槽內,屬外部;第二點在邊界上,被覆蓋;第三點在 內,屬內部。
快速檢查
(三角形頂點為 。列出 和 的掃描線事件,並判定 。)
留意每條邊排除哪一個端點。
解答 · 答案
在 ,兩條斜邊給出 。在 ,兩個上端點皆被排除,事件表為空;但 是頂點,先前的邊界測試會判定其被覆蓋。
快速檢查
(非水平邊由 連至 。求 時的事件,並判定 時該邊是否活動。)
用插值公式,其中 、。
解答 · 答案
插值得 。上端點高度 被排除,故該邊在此高度不活動。
快速檢查
(在 有兩個重合事件, 與 之間沒有其他事件。取樣點從 移到 ,奇偶性會改變嗎?可否斷定 在外部?)
先數兩個取樣點之間的切換次數,再想想 是甚麼點。
解答 · 答案
切換兩次不改變奇偶性。事件點本身在多邊形邊界上,依本規則被覆蓋;遠離事件的奇偶性不能判定事件點本身。
快速檢查
(解釋兩個相鄰多邊形都採用先測邊界規則時,為何可同時覆蓋一個取樣點;給出不改變多邊形面積而避免重複寫入的一種方法。)
考慮共邊上的取樣點。
解答 · 答案
共邊上的取樣點屬於兩個閉邊界。整個網格可用一致的半開歸屬規則,只把共邊分配給其中一個多邊形,並一致處理頂點。邊界線段面積為零,因此改變其歸屬不改變多邊形的幾何面積。