計算機圖形學（三）_圖元的屬性_10_ 通用掃描填充算法

10 通用掃描填充算法

        要實現區域的掃描線填充必須先肯定填充區邊界與屏幕掃描線的交點位置。然后，將填充色利用于掃描線上位于填充區域內部的每段。掃描線填充算法利用奇偶規則辨認同1內部區域（參見）。最簡單的填充區域是多邊形，由于每掃描線和多邊形的交點可通過求解1對聯立的線性方程來取得，其中掃描線的方程是y = 常數。
        圖4.20給出了多邊形區域的實心填充的掃描線進程。對每條與多邊形相交的掃描線，與邊的交點從左向右排序，且將每對交點之間的像素位置包括這對交點在內，設定為指定色彩。在圖4.20的例子中，與邊界的4個交點像素位置定義了兩組內部像素。這樣，填充色利用于從x=10到x = 14的5個像素和從x = 18到x = 24的7個像素。如果圖案填充利用于多邊形，則沿1條掃描線的每像素色彩由與填充圖案堆疊的位置來肯定。
        但是，多邊形掃描線填充算法并不如圖4.20建議的那樣簡單。每當1條掃描線經過量邊形的1個頂點時，掃描線在該頂點處與多邊形的兩條邊相交。這類情況可能致使在這條掃描線的交點列表上要增加兩個點。圖4.21給出了在頂點處與多邊形相交的兩條掃描線。掃描線y'與偶數條邊相交，而在該掃描線上的兩對交點正確地標識為內部像素段。但是掃描線y與多邊形的5條邊相交。要確認掃描線y的內部像素，必須將頂點處的交點看作為1個點。因此，在處理掃描線時，必須辨別這些情況。
        通過關注相交邊相對掃描線的位置，可以發現圖4.21中掃描線y和掃描線y'間的拓撲差異。對掃描線y，同享1個頂點的兩條相交邊位于掃描線的兩側。但對掃描線y'，兩條相交邊在掃描線的同1側。因此，那些在掃描線兩側有連接邊的頂點應當計為1個邊界交點。可以通過順時針或逆時針方向來搜索多邊形邊界，并視察從1條邊移到另外一條邊時頂點y坐標的相對變化來辨認這個點。假設兩條相鄰邊的3個端點y'值單調遞增或遞減，那末對任何穿過該頂點的掃描線，則必須將該同享(中間)頂點計為1個交點。否則，同享的頂點表示多邊形邊界上的1個局部極值(最大或最小)。這兩條邊與穿過該頂點的掃描線的交點可以添加到相干列表中。
        將頂點交點調劑為1個或兩個的1種實現方法是將多邊形的某些邊縮短，從而分離那些應計為1個交點的頂點。我們可以依照指定的順時針或逆時針方向處理全部多邊形邊界上的非水平邊。在處理每條邊時進行檢測，肯定該邊與下1條非水平邊是不是有單調遞增或單調遞減的端點y值。假設有，可以將較低的1條邊縮短，從而保證對通過公共頂點(連接兩條邊)的掃描線唯一1個交點生
成。圖4.22給出了1條邊的縮短情況。當兩條邊的端點y值遞增時，將當前邊的較高端點y值減去1，如圖4.22(a)所示;當端點y值單調遞減時，如圖4.22(b)所示，就減去緊隨當前邊的1條邊的較高端點y值。

    1般情況下，場景1部份的某些特點會以某種方式與該場景另外一部份的特點相干，且這些相干特點(coherence property)可用于計算機圖形算法中以減少處理。相干方法常常包括沿1條掃描線或在連續的掃描線間利用的增量計算。例如，在肯定填充區邊的交點時，利用沿1條邊從1條掃描線到下1條掃描時斜率為常數這1事實，可以沿任1邊采取增量坐標計算。圖4.23給出了與3角形左面1條邊相交的兩條連續掃描線，這條邊的斜率可以用掃描線交點坐標來表示:

由于兩條掃描線間y坐標的變化很簡單:

上面1條掃描線的x交點值xk+ 1，可以通過前1條掃描線的x交點值xk戈來肯定:

因此，每一個后繼交點的x值都可以通過增加斜率的倒數并取整而計算。

    有關填充算法的最明顯的并行實現方法，是將每條與多邊形區域相交的掃描線分配給1個獨立的處理器。然后分別完成每一個邊交點的計算。掃描線k沿1條具有斜率m的邊，相對最初掃描線的交點x_k值可計算為

在順序填充算法中，沿1條邊x方向的增量值l/m，可以通過調用斜率m為兩整數比的整數運算來完成:

其中，△x和△y是該邊端點x和Y坐標值之間的差。因此，沿1條邊對連續兩條掃描線交點的x增量計算可表示為

        利用這個公式，可以完成交點x坐標的整數求值:先將計數器初始化為零，然后每當移向1條新的掃描線時，計數器就增加△x值，從而完成交點x坐標的整數求值。當計數器的值大于等于△y時，當前交點x值增加1，并將計數器減去△y。這個進程相當于保持交點x值的整數和小數部份，并增加小數部份直至到達下1個整數值。
        作為整數增量的1個例子，假定1條邊的斜率為。m = 7/3。在起始掃描線處，我們將計數器設置為零，增量為3。當沿這條邊移到其他3條掃描線時，計數器順序地設置值3, 6和9。在初始掃描線以上的第3條掃描線上，計數器的值大于7。因此交點x坐標增加1，并重新將計數器設置為值9⑺=2。繼續以這類方法肯定掃描線的交點值，直至到達邊界的最高端點。對負斜率的邊，可以通過一樣的計算而得到交點。
        我們可以不用舍人法以取得整數位置，而是取整到最接近的像素的x值，通過修改邊的相交算法使得增量與△y/2相比較。在每步中計數器增加2△x值，并將增量與△y進行比較，當增量大于或等于△y值時，x值增加1，而計數器值減去2△y。在上面m = 7/3的例子中，對這條邊上初始掃描線以上的幾條掃描線，其計數器值變成6, 12(減少到⑵ ), 4, 10(減少到⑷ ) 2, 8(減少到⑹ ), 0, 6和12(減少到⑵)。在這條邊的初始掃描線以上的第2, 4, 6, 9掃描線上.將增加x的值。每條邊所需的額外計算是2△x = △x + △x和2△y = △y + △y ，這些計算在預處理中完成。
        為了有效地完成多邊形填充，可以首先將多邊形邊界存儲在有序邊表(sorted edge table)中，其中包括有效處理掃描線所需的全部信息。不管是以順時針或逆時針沿邊處理時，我們都可使用桶排序來存儲各條邊，按每條邊的最小y值排序，存儲在相應的掃描線位置。有序邊表中僅存儲非水平線。在處理邊時，可以縮短某些邊以解決頂點相交問題。對某條特定的掃描線，表中的每一個人口包括該邊的最大y值、邊的x交點值(在較低頂點處)和邊斜率的倒數。對每條掃描線，以從左到右的順序對邊進行排序。圖4.24給出了1個多邊形及其相應的有序邊表。
        接下來，從多邊形的底部到頂部處理掃描線。對每條與多邊形邊界相交的掃描線生成1個活化邊表(active edge list )。掃描線的活化邊表包括所有與該掃描線相交的邊，并使用重復相干性計算來得到邊的交點。
         邊的相交計算也可通過將△x和△y值存儲在有序邊表中而得到簡化。另外，為了確保對指定多邊形內部的正確填充，可以利用在(像素編址和對象的幾何要素)節中所討論的斟酌情況。對每條掃描線，對從最左側的x交點值到最右側x交點值之間的每對x交點間的像素段進行填充。而每條多邊形的邊可以在頂部端點y方向上縮短1個單位，這類措施也能保證相鄰多邊形中的像素不會相互覆蓋。