計算機圖形學(xué)（三）_圖元的屬性_10_ 通用掃描填充算法
來源：程序員人生 發(fā)布時間：2016-11-24 08:40:45 閱讀次數(shù)：3889次
10 通用掃描填充算法
要實現(xiàn)區(qū)域的掃描線填充必須先肯定填充區(qū)邊界與屏幕掃描線的交點位置。然后，將填充色利用于掃描線上位于填充區(qū)域內(nèi)部的每段。掃描線填充算法利用奇偶規(guī)則辨認(rèn)同1內(nèi)部區(qū)域（參見）。最簡單的填充區(qū)域是多邊形，由于每掃描線和多邊形的交點可通過求解1對聯(lián)立的線性方程來取得，其中掃描線的方程是y
= 常數(shù)。
圖4.20給出了多邊形區(qū)域的實心填充的掃描線進程。對每條與多邊形相交的掃描線，與邊的交點從左向右排序，且將每對交點之間的像素位置包括這對交點在內(nèi)，設(shè)定為指定色彩。在圖4.20的例子中，與邊界的4個交點像素位置定義了兩組內(nèi)部像素。這樣，填充色利用于從x=10到x = 14的5個像素和從x
= 18到x = 24的7個像素。如果圖案填充利用于多邊形，則沿1條掃描線的每像素色彩由與填充圖案堆疊的位置來肯定。
但是，多邊形掃描線填充算法并
不如圖4.20建議的那樣簡單。每當(dāng)1條掃描線經(jīng)過量邊形的1個頂點時，掃描線在該頂點處與多邊形的兩條邊相交。
這類情況可能致使在這條掃描線的交點列表上要增加兩個點。圖4.21給出了在頂點處與多邊形相交的兩條掃描線。掃描線
y'與偶數(shù)條邊相交，而在該掃描線上的兩對交點正確地標(biāo)識為內(nèi)部像素段。但是掃描線
y與多邊形的5條邊相交。
要確認(rèn)掃描線y的內(nèi)部像素，必須將頂點處的交點看作為1個點。因此，在處理掃描線時，必須辨別這些情況。
通過關(guān)注相交邊相對掃描線的位置，可以發(fā)現(xiàn)圖4.21中掃描線
y和掃描線
y'間的
拓?fù)洳町?/span>。對掃描線y，同享1個頂點的兩條相交邊位于掃描線的兩側(cè)。但對掃描線y'，兩條相交邊在掃描線的同1側(cè)。因此，那些在掃描線兩側(cè)有連接邊的頂點應(yīng)當(dāng)計為1個邊界交點?？梢酝ㄟ^順時針或逆時針方向來搜索多邊形邊界，并視察從1條邊移到另外一條邊時頂點y坐標(biāo)的相對變化來辨認(rèn)這個點。假設(shè)兩條相鄰邊的3個端點y'值單調(diào)遞增或遞減，那末對任何穿過該頂點的掃描線，則必須將該同享(中間)頂點計為1個交點。否則，同享的頂點表示多邊形邊界上的1個局部極值(最大或最小)。這兩條邊與穿過該頂點的掃描線的交點可以添加到相干列表中。
將頂點交點調(diào)劑為1個或兩個的1種實現(xiàn)方法是將多邊形的某些邊縮短，從而分離那些應(yīng)計為1個交點的頂點。我們可以依照指定的順時針或逆時針方向處理全部多邊形邊界上的非水平邊。在處理每條邊時進行檢測，肯定該邊與下1條非水平邊是不是有單調(diào)遞增或單調(diào)遞減的端點y值。假設(shè)有，可以將較低的1條邊縮短，從而保證對通過公共頂點(連接兩條邊)的掃描線唯一1個交點生
成。圖4.22給出了1條邊的縮短情況。當(dāng)兩條邊的端點y值遞增時，將當(dāng)前邊的較高端點y值減去1，如圖4.22(a)所示;當(dāng)端點y值單調(diào)遞減時，如圖4.22(b)所示，就減去緊隨當(dāng)前邊的1條邊的較高端點y值。
1般情況下，場景1部份的某些特點會以某種方式與該場景另外一部份的特點相干，且這些相干特點(coherence property)可用于計算機圖形算法中以減少處理。相干方法常常包括沿1條掃描線或在連續(xù)的掃描線間利用的增量計算。例如，在肯定填充區(qū)邊的交點時，利用沿1條邊從1條掃描線到下1條掃描時斜率為常數(shù)這1事實，可以沿任1邊采取增量坐標(biāo)計算。圖4.23給出了與3角形左面1條邊相交的兩條連續(xù)掃描線，這條邊的斜率可以用掃描線交點坐標(biāo)來表示:
由于兩條掃描線間y坐標(biāo)的變化很簡單:
上面1條掃描線的x交點值xk+ 1，可以通過前1條掃描線的x交點值xk戈來肯定:
因此，每一個后繼交點的x值都可以通過增加斜率的倒數(shù)并取整而計算。
有關(guān)填充算法的最明顯的并行實現(xiàn)方法，是將每條與多邊形區(qū)域相交的掃描線分配給1個獨立的處理器。然后分別完成每一個邊交點的計算。掃描線k沿1條具有斜率m的邊，相對最初掃描線的交點xk值可計算為
在順序填充算法中，沿1條邊x方向的增量值l/m，可以通過調(diào)用斜率m為兩整數(shù)比的整數(shù)運算來完成:
其中，△x和△y是該邊端點x和Y坐標(biāo)值之間的差。因此，沿1條邊對連續(xù)兩條掃描線交點的x增量計算可表示為
利用這個公式，可以完成交點x坐標(biāo)的整數(shù)求值:先將計數(shù)器初始化為零，然后每當(dāng)移向1條新的掃描線時，計數(shù)器就增加△x值，從而完成交點x坐標(biāo)的整數(shù)求值。當(dāng)計數(shù)器的值大于等于△y時，當(dāng)前交點x值增加1，并將計數(shù)器減去△y。這個進程相當(dāng)于保持交點x值的整數(shù)和小數(shù)部份，并增加小數(shù)部份直至到達下1個整數(shù)值。
作為整數(shù)增量的1個例子，假定1條邊的斜率為。m = 7/3。在起始掃描線處，我們將計數(shù)器設(shè)置為零，增量為3。當(dāng)沿這條邊移到其他3條掃描線時，計數(shù)器順序地設(shè)置值3, 6和9。在初始掃描線以上的第3條掃描線上，計數(shù)器的值大于7。因此交點x坐標(biāo)增加1，并重新將計數(shù)器設(shè)置為值9⑺=2。繼續(xù)以這類方法肯定掃描線的交點值，直至到達邊界的最高端點。對負(fù)斜率的邊，可以通過一樣的計算而得到交點。
我們可以不用舍人法以取得整數(shù)位置，而是取整到最接近的像素的x值，通過修改邊的相交算法使得增量與△y/2相比較。在每步中計數(shù)器增加2△x值，并將增量與△y進行比較，當(dāng)增量大于或等于△y值時，x值增加1，而計數(shù)器值減去2△y。在上面m = 7/3的例子中，對這條邊上初始掃描線以上的幾條掃描線，其計數(shù)器值變成6, 12(減少到⑵ ), 4, 10(減少到⑷ ) 2, 8(減少到⑹ ), 0, 6和12(減少到⑵)。在這條邊的初始掃描線以上的第2, 4, 6, 9掃描線上.將增加x的值。每條邊所需的額外計算是2△x
= △x + △x和2△y = △y + △y ，這些計算在預(yù)處理中完成。
為了有效地完成多邊形填充，可以首先將多邊形邊界存儲在有序邊表(sorted edge table)中，其中包括有效處理掃描線所需的全部信息。不管是以順時針或逆時針沿邊處理時，我們都可使用桶排序來存儲各條邊，按每條邊的最小y值排序，存儲在相應(yīng)的掃描線位置。有序邊表中僅存儲非水平線。在處理邊時，可以縮短某些邊以解決頂點相交問題。對某條特定的掃描線，表中的每一個人口包括該邊的最大y值、邊的x交點值(在較低頂點處)和邊斜率的倒數(shù)。對每條掃描線，以從左到右的順序?qū)呥M行排序。圖4.24給出了1個多邊形及其相應(yīng)的有序邊表。
接下來，從多邊形的底部到頂部處理掃描線。對每條與多邊形邊界相交的掃描線生成1個活化邊表(active edge list )。掃描線的活化邊表包括所有與該掃描線相交的邊，并使用重復(fù)相干性計算來得到邊的交點。
邊的相交計算也可通過將△x和△y值存儲在有序邊表中而得到簡化。另外，為了確保對指定多邊形內(nèi)部的正確填充，可以利用在(像素編址和對象的幾何要素)節(jié)中所討論的斟酌情況。對每條掃描線，對從最左側(cè)的x交點值到最右側(cè)x交點值之間的每對x交點間的像素段進行填充。而每條多邊形的邊可以在頂部端點y方向上縮短1個單位，這類措施也能保證相鄰多邊形中的像素不會相互覆蓋。
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
