第三章-二維輸出圖元生成技術(shù)

填充圖元生成填充圖元生成通用圖形軟件包中有一種輸出圖元：實心或圖案填充的多邊形區(qū)域：填充圖元。可能有其它種類的填充區(qū)域圖元，但多邊形有線性邊界，更簡潔處理。二維多邊形區(qū)域填充是三維面著色的基礎(chǔ)。光柵系統(tǒng)中有兩種區(qū)域填充(填充圖元生成)方法：掃描轉(zhuǎn)換填充(多邊形掃描填充)：通過確定橫越區(qū)域的掃描線間隔來填充。用來填充多邊形、圓、橢圓和其它簡潔曲線圍成的區(qū)域；(給定多邊形邊界的區(qū)域)區(qū)域填充：從給定的位置，涂描/著色直到滿足指定的邊界條件為止。用于具有困難形態(tài)邊界及交互式涂描系統(tǒng)。(給定點陣表示的區(qū)域)☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符文本屬性多邊形掃描填充多邊形有兩種表示方法：頂點表示：用多邊形的頂點序列來刻畫多邊形。這種表示直觀，幾何意義強，占空間少，易于進行幾何變換，被廣泛應(yīng)用于各種幾何造型系統(tǒng)中。點陣表示：用多邊形內(nèi)部的像素的集合來刻畫多邊形。這種表示雖然失去了很多重要幾何信息（如邊界、頂點等），但它卻是光柵顯示系統(tǒng)顯示時所需的表示形式。多邊形掃描轉(zhuǎn)換：須要將多邊形的頂點表示轉(zhuǎn)換成點陣表示。大多數(shù)圖形學(xué)應(yīng)用接受頂點序列表示多邊形；頂點表示又不能干脆用于顯示。從多邊形的頂點信息動身，求出位于其內(nèi)部的各個像素，并將其顏色值寫入幀緩沖器中相應(yīng)的單元?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性掃描轉(zhuǎn)換基本問題多邊形掃描轉(zhuǎn)換基本處理：對每條橫越多邊形的掃描線，掃描轉(zhuǎn)換算法確定掃描線與多邊形邊的交點位置。一般狀況下，掃描線橫越多邊形的偶數(shù)條邊，有偶數(shù)個交點。將這些點自左至右分對存貯。給每對交點間區(qū)段內(nèi)對應(yīng)的象素點的幀緩沖器位置設(shè)置指定填充顏色。掃描線交點交點交點交點☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性掃描線與頂點相交處理

直觀地：掃描線通過一個頂點與多邊形的兩條邊相交，這根掃描線的交點表上要增加兩個點。事實上，須要區(qū)分處理兩種狀況(下圖中)：掃描線y1穿過一個頂點(共享頂點的兩條邊位于掃描線的同側(cè))，它與偶數(shù)條邊相交，沿掃描線y1的相交點正確地分辯出了內(nèi)部像素分布；掃描線y穿過一個頂點(頂點的兩條相交邊位于掃描線的兩側(cè))，與五條多邊形邊相交。因此，必須要作一些額外的處理才能確定正確的內(nèi)部點。交點交點交點交點交點交點交點交點交點掃描線y1掃描線y☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性頂點與掃描線間拓撲關(guān)系通過標識相交邊與掃描線的相對位置關(guān)系而鑒別掃描線間的拓撲差異—頂點兩條邊位于掃描線的同側(cè)/異側(cè)。通過以順時針或逆時針方向搜尋多邊形邊界，并視察從一條邊移到另一條邊時頂點y坐標的相對變更：假如兩條依次連接邊的端點y值單調(diào)增加或削減，那么，對于任何穿過該點的掃描線就必需將該中間頂點計為一個交點；否則，共享頂點表示多邊形邊界上的一個局部極值，這兩條邊與穿過該頂點的掃描線的交點可以添加到相關(guān)表中去。掃描線y+1掃描線y掃描線y-1☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性特殊頂點分別處理將多邊形某些邊縮短，以分別應(yīng)計為1個交點的頂點。以順時針或逆時針方向處理整個多邊形邊界上的非水平邊。在處理每條邊時進行下列檢測：該邊與下一條非水平邊是否有單調(diào)遞增或單調(diào)遞減的端點y值？假如有，可將較低一條邊縮短，以保證對通過連接兩條邊公共頂點的掃描線僅有一個交點生成：當兩條邊的端點y值增加時，當前邊較高端點y值減去1；當端點y值單調(diào)遞減時，緊隨邊較高端點的y坐標值減就去1。掃描線y+1掃描線y掃描線y-1☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性連貫性和增量計算原理在掃描轉(zhuǎn)換及其它圖形算法中常充分利用待顯示場景的各種連貫特性。連貫性可簡潔地看作場景中的一部分的特性以某種方式與場景中的其它部分相關(guān)，這種關(guān)系可用來削減處理。利用沿一條邊從一條掃描線到下一條掃描時斜率為常數(shù)這一連貫性，確定邊交點時可接受增量坐標計算。兩掃描線間y坐標的變更為：yk+1-yk=1掃描線交點的x值xk+1可從前一條掃描線上x交點值xk來確定：xk+1=xk+(1/m)。每個后繼交點的x值都由加斜率的倒數(shù)并取整而計算出來。k條掃描線沿一條邊、相對于最初掃描線交點xk值計算為：xk=x0+(k/m)。掃描線yk+1掃描線yk(xk+1,yk+1)(xk,yk)xk+1=xk+(1/m)☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性連貫性和增量計算方法沿一條邊x方向增量值1/m可用斜率m為兩整數(shù)比的整數(shù)運算來完成：m=△y/△x。沿一條邊對連續(xù)的掃描線的x交點的增量計算可表示為：xk+1=xk+(△x/△y)。用舍入法來取整到最終的交點像素x位置完成交點x坐標的整數(shù)求值：先將計數(shù)器初始化為零，而后每當移向一條新的掃描線計數(shù)器就增加△x值，當計數(shù)器的值大于等于△y時，當前交點x值增加1并將計數(shù)器減去△y值。修改邊相交算法：使增量與△y/2比較：在每一步中計數(shù)器增加2△x值，并將增量與△y比較，當增量大于或等于△y值時，x值增加1，而計數(shù)器值減去2△y。這個過程相當于保持交點x值的整數(shù)和小數(shù)部分，并增加小數(shù)部分直至達到下一個整數(shù)值?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性連貫性和增量計算示例例：假設(shè)一條邊的斜率為m=7/3，在起始掃描線處，將計數(shù)器設(shè)置為零，并增加3，當沿這條邊移到其它三條掃描線時，計數(shù)器依次地設(shè)置值3、6和9。在初始掃描線以上的第三條掃描線上，計數(shù)器值大于7，因而，交點x坐標增加1，并重新將計數(shù)器設(shè)置為值9-7=2，接著以這種方法確定掃描線交點，直止到達邊界的高端點。例：假設(shè)一條邊的斜率為m=7/3，對于這條邊上初始掃描線以上的n條掃描線的計數(shù)器k的值變?yōu)椋?、12；-2(x=x+1，k=12-2×7=-2)、4、10；-4(x=x+1，k=10-2×7=-4)、2、8；-6(x=x+1，k=8-2×7=-6)、0、6和12；-2(x=x+1，k=12-2×7=-2)，在這條邊的初始掃描線以上的第2、4、6、9掃描線上x值得到增加。每條邊所需的額外計算是2△x=△x+△x和2△y=△y+△y。☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性有序邊表有序邊表的作用是解除不必要的求交測試。有序邊表：按邊下端點y坐標對非水平邊進行分類的指針數(shù)組。為每條掃描線建立一個存儲單元或稱“桶”；對多邊形的全部邊按下端點y坐標值進行y桶分類下端點的y坐標值為i的邊歸入第i類同一類中的邊按x值或△x值遞增的依次排列成鏈表。鏈表中的每個節(jié)點包含該邊最大y值、邊下端點x坐標值和邊斜率倒數(shù)(即1/m)。☆填充圖元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性活化邊表活化邊表：由與當前掃描線相交的多邊形邊組成，它記錄多邊形邊沿掃描線的交點序列。對于第k條掃描線，活化邊表可從有序邊表中生成：將y桶中對應(yīng)于當前掃描線以下的類c(c=1,2,…,k-1)的全部邊插入活化邊表，刪除滿足ymax<yk的邊，其它邊的x域依據(jù)xk+1=xk+((yk-yc)/m)確定交點。活化邊表中的每個節(jié)點包含該邊最大y值、與掃描線交點的x坐標值和邊斜率倒數(shù)?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性掃描多邊形填充其它問題一條掃描線上的填充過程包括：求交點；按橫坐標排序；兩兩配對；取整和填充。取整和填充時須要留意幾個主要問題：交點x坐標為小數(shù)，即交點落于掃描線上兩個像素之間：若交點位于多邊形的左邊之上，則取其右端像素，即：int(x+1)；若交點位于多邊形的右邊之上，則取其左端像素，即：int(x)。交點x坐標為整數(shù)，即交點正好落在像素上：若交點位于多邊形左邊上，則它屬于多邊形；否則，它不屬于多邊形。共享邊界的處理：假如多邊形區(qū)域位于它的一條邊界所在直線的右方或上方，則中心落于該邊界上的像素屬于該多邊形區(qū)域，否則不屬于該多邊形區(qū)域。交點x坐標為多邊形頂點時，按特殊交點處理方法處理。水平線在掃描填充算法中不起作用，預(yù)處理時可以去除?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充?基本問題?相交頂點?拓撲處理?分別處理?增量計算?計算方法?計算示例?有序邊表?活化邊表?其它問題●區(qū)域填充算法●填充圖元屬性●字符表示/輸出●字符屬性區(qū)域的表示區(qū)域是指已經(jīng)表示成點陣形式的填充圖形，它是像素的集合。區(qū)域可接受內(nèi)點表示或邊界表示兩種形式：內(nèi)點法：枚舉出給定區(qū)域內(nèi)全部像素。在內(nèi)點表示中，區(qū)域內(nèi)的全部像素著同一顏色，而區(qū)域邊界上的像素著不同的顏色；邊界表示：枚舉出給定區(qū)域全部邊界上像素。在邊界表示中，區(qū)域邊界上的像素著同一顏色，而區(qū)域內(nèi)的像素著不同顏色。區(qū)域的邊界表示法區(qū)域的內(nèi)點表示法☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性區(qū)域填充原理區(qū)域填充：從區(qū)域的一個內(nèi)點（稱為“種子點”）起先，賜予指定的顏色，然后將該顏色擴展到整個區(qū)域。它是對區(qū)域重新著色的過程（變更區(qū)域的顏色或者以圖像填充）。對邊界表示的區(qū)域進行填充為邊界填充；對內(nèi)點表示的區(qū)域進行填充為泛濫填充。區(qū)域的邊界表示法區(qū)域的內(nèi)點表示法區(qū)域的泛濫填充區(qū)域的邊界填充區(qū)域填充算法要求區(qū)域是連通的只有在連通區(qū)域內(nèi)，才有可能將種子點的顏色擴展到區(qū)域內(nèi)的其它點?！斑B通區(qū)域”＋“內(nèi)外點測試”☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性prrrr4連通區(qū)域(4-鄰域)一個象素p(xp,yp)的4連通區(qū)域或4-鄰域N4(p)定義為(圖中標r的象素)：

N4(p)={r|d4(p,r)=1}即：任取區(qū)域內(nèi)兩點，在該區(qū)域內(nèi)，通過上、下、左右四個方向的運動，這兩點相互可達。區(qū)域內(nèi)像素距離定義為：城區(qū)距離

d4(p,r)=|xp-xr|+|yp-yr|4連通區(qū)域定義☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性8連通區(qū)域(8-鄰域)一個象素p(xp,yp)的8連通區(qū)域或8-鄰域N8(p)定義為(圖中標r的象素)：

N8(p)={r|d8(p,r)=1}即：任取區(qū)域內(nèi)兩點，通過水平、垂直、兩個對角線八個方向的運動，這兩點相互可達。區(qū)域內(nèi)像素距離定義為：棋盤距離

d8(p,r)=max(|xp-xr|,|yp-yr|)8連通區(qū)域定義prrrrrrrr一個象素p(xp,yp)的8-鄰域N8(p)也是它的4-鄰域N4(p)和它的對角鄰域ND(p)

的并集?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性16連通區(qū)域(16-鄰域)一個象素p(xp,yp)的16連通區(qū)域或16-鄰域N16(p)定義為：

N16(p)=N8(p)∪Nk(p)

即：任取區(qū)域內(nèi)兩點，通過十六個方向的運動相互可達。其中，馬步(或騎士Knight)鄰域Nk(p)定義為：

Nk(p)={r|dk(p,r)=1}馬步距離是國際象棋棋盤上馬從一格運動到另一格所需步數(shù)計算，也是網(wǎng)格上兩點間最短k-通路的長度。16連通區(qū)域定義prrrrrrrrrrrrrrrr☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性連通區(qū)域定義問題由定義知：4連通區(qū)域也可以看作是8連通區(qū)域。但它作為4連通區(qū)域和8連通區(qū)域的邊界是不同的(4連通比8連通約束緊)：像素作為4連通區(qū)域，其邊界只要是８連通就可以了；像素作為8連通區(qū)域，其邊界必需是４連通區(qū)域。否則，8連通區(qū)域的邊界將失效：即欠約束。8連通區(qū)域能用來填充更困難的圖形。起始點起始點4連通區(qū)域邊界4連通區(qū)域邊界8連通區(qū)域邊界8連通區(qū)域邊界區(qū)域定義無邊界☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性內(nèi)外點測試方法奇偶規(guī)則或非零環(huán)繞數(shù)規(guī)則用來鑒別區(qū)域內(nèi)部對于標準多邊形和其它簡潔形態(tài)，非零環(huán)繞數(shù)規(guī)則和奇偶規(guī)則給出相同的結(jié)果，但對于困難形態(tài)，兩種方法會產(chǎn)生不同的內(nèi)部和外部區(qū)域。非零環(huán)繞數(shù)規(guī)則比奇偶規(guī)則更通用。AGCBDFEAGCBDFE奇偶規(guī)則非零環(huán)繞規(guī)則外部外部外部☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性奇偶內(nèi)外點測試方法奇偶規(guī)則（射線法）從任何位置p到對象坐標范圍以外遠距離畫始終線(射線)，并統(tǒng)計沿該射線與區(qū)域各邊的交點數(shù)目。假如與這條射線相交的多邊形邊數(shù)為奇數(shù)，則p是內(nèi)部點；否則，p是外部點。為了得到精確的邊數(shù)，必需確認所畫線不與任何多邊形頂點相交。pp☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性非零環(huán)繞數(shù)內(nèi)外點測試環(huán)繞數(shù)統(tǒng)計多邊形邊以逆時針方向環(huán)繞某一特定點的次數(shù)，這個數(shù)稱為環(huán)繞數(shù)，二維物體的內(nèi)部點被定義為具有環(huán)繞數(shù)為非零值。非零環(huán)繞數(shù)規(guī)則將環(huán)繞數(shù)初始化為零，再假想從隨意位置P畫一射線(不與多邊形任何頂點相交)。當從P點沿射線方向移動時，對在每個方向上穿過射線的邊計數(shù)：當多邊形從右到左穿過射線時，環(huán)繞數(shù)加1；當多邊形從左到右穿過射線時，環(huán)繞數(shù)減1；全部穿過的邊都計數(shù)后的環(huán)繞數(shù)值確定P的相對位置?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性+1-1-1+1+1環(huán)繞數(shù)計算方法叉乘法：將從P點動身的射線向量u與穿過射線的每條邊的邊向量e叉乘，假如對某一特定邊，積u×e的元素z為正，那么，該邊從右到左穿過射線，環(huán)繞數(shù)加1；否則，該邊從左到右穿越射線，環(huán)繞數(shù)減1。向量點積法：建立一個垂直于u且從P沿u方向看是從右到左指向的向量假如u的元素是(ux,uy)，那么，垂直于u的向量有元素(-uy,ux)。假如垂直向量與邊向量的點積v?e為正，那么，該邊從右向左穿越射線，環(huán)繞數(shù)加1；否則，該邊從左至右穿越射線，環(huán)繞數(shù)則減1。PuABe=VB-VA，u×v=0u×e>0，環(huán)繞數(shù)加1；v?e>0，環(huán)繞數(shù)加1。v☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

?原理和基礎(chǔ)?四連通?八連通?十六連通?連通問題?I/O檢測

?奇偶效驗

?環(huán)繞規(guī)則

?環(huán)繞計算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性邊界填充算法邊界填充算法：從區(qū)域的一個內(nèi)點起先，按指定顏色由內(nèi)向外繪點直到邊界。邊界填充程序接受輸入內(nèi)部種子點(x,y)的坐標、填充顏色和邊界（包括內(nèi)邊界和外邊界）顏色。從種子點(x,y)起先，檢測相鄰位置以確定是否為邊界顏色？倘如不是，就用填充顏色涂色，并依據(jù)區(qū)域連通性檢測其相鄰位置。這個過程遞歸地進行到檢測完區(qū)域邊界顏色范圍內(nèi)的全部像素為止。遞歸邊界填充算法：假如邊界是以單一顏色指定的，則填充算法可按連通性逐個像素地向外處理，直到遇到邊界顏色。掃描線邊界填充算法：通過沿掃描線填充水平像素段來代替處理4連通或8-連通相鄰點?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性遞歸邊界填充算法假如有些內(nèi)部像素已給以填充顏色顯示，則遞歸式的邊界填充算法或許不能正確地填充區(qū)域。這是因為算法按邊界顏色和填充顏色來檢測下一個像素，遇到一個具有填充顏色的像素就導(dǎo)致該遞歸分支終止，從而留下一些尚未填充的內(nèi)部像素。為了避開這種狀況，可在應(yīng)用邊界填充程序前先變更那些初始顏色為填充顏色的內(nèi)部像素的顏色。假如邊界是以單一顏色指定的，則填充算法可按連通性逐個像素地向外處理，直到遇到邊界顏色。程序給出了填充4連通區(qū)域的遞歸方法：區(qū)域顏色在參數(shù)fill中指定；邊界顏色用參數(shù)boundary指定。缺陷：須要較大的存儲相鄰點的?？臻g?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性掃描線邊界填充算法為削減存儲相鄰點的棧空間，可通過沿掃描線填充水平像素段來代替處理4連通或8-連通相鄰點。這樣，僅將每個水平像素段的起始位置放進棧，而不需將全部當前位置四周未處理相鄰位置放進棧。填充過程：從種子點起先，首先填該像素所在掃描行的連續(xù)像素段；將相鄰掃描線上各段的起始位置進棧，這些水平段分別被用區(qū)域邊界顏色顯示的像素包圍；從棧頂逐步取出起先點(先進后出)，填充該水平段像素；并重復(fù)上述過程。123456123456圖中示出了運用這種方法對4連通填充區(qū)域填充像素區(qū)段：沿每條掃描線，從左向右將每個水平段最左邊像素位置放進棧?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性泛濫填充算法泛濫填充算法：假如不是邊界，而是區(qū)域內(nèi)部用單一顏色定義的區(qū)域填充。通過替換指定的內(nèi)部顏色來對這個區(qū)域涂色(填充)。從指定的內(nèi)部點(x,y)起先，用所希望的填充顏色賦給全部當前設(shè)置為給定內(nèi)部顏色的像素。假如所要涂色的區(qū)域內(nèi)部具有多種顏色：重設(shè)置像素值，使全部內(nèi)部點具有相同顏色；運用連通定義，逐步連通各像素位置；直到全部內(nèi)部點均被涂色。也可通過掃描線填充來削減對堆棧的存儲要求。僅存儲具有原象素顏色的那些像素段的起先位置，修改后的泛濫填充算法的步驟與邊界填充相同：從每個區(qū)間的第一個位置起先，替代像素值直到遇到原象素顏色以外的值?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性圖像填充區(qū)域在實際應(yīng)用中，填充圖元有兩大類四種填充方式：勻整著色區(qū)域前面所講的圖元填充方式。圖像填充區(qū)域位圖不透亮方式；位圖透亮方式；像素圖填充方式。位圖是二值圖像，有兩種方式：透亮方式：以位圖(前景色)覆蓋區(qū)域內(nèi)的部分像素，而讓其它像素顏色不變；不透亮方式：以位圖(前景色+背景色)覆蓋區(qū)域內(nèi)的全部像素；像素圖是多值圖像，只有不透亮方式?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性圖像區(qū)域填充原理圖像填充區(qū)域可通過對前述圖元填充算法中顯示像素的那部分代碼稍作修改來實現(xiàn)：在確定區(qū)域內(nèi)的某一像素后，首先查詢它對應(yīng)的位圖或像素圖中的單元，再以該單元的值依據(jù)填充方式顯示該像素。當按位圖不透亮方式填充時，若對應(yīng)位圖單元為1，仍以前景色顯示該圖像；若為零，用背景色顯示該像素(反轉(zhuǎn))。當按位圖透亮方式填充時，若對應(yīng)的位圖單元為1，仍以前景色顯示該圖像；若為零，不變更屏幕上該像素的顏色(不作任何處理)當按像素圖方式填充時，以像素對應(yīng)的像素圖單元的顏色值顯示該像素?！钐畛鋱D元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性圖像填充的效果處理通常，用來填充區(qū)域的圖像較小，不足以填充整個區(qū)域。進行圖像區(qū)域填充時，使圖像在水平和垂直方向周期性排列，直到所定義的區(qū)域全被不重迭的圖像所覆蓋。假定每個圖像的尺寸是M×N，存放在數(shù)組pattern[M][N]中，通過周期性排列構(gòu)成圖像空間。區(qū)域定義影響圖像填充區(qū)域效果的主要因素是區(qū)域與圖像間的位置關(guān)系，即：區(qū)域中各像素與圖像各單元間的映射關(guān)系。圖像空間與區(qū)域關(guān)系的不同會產(chǎn)生不同的效果!圖像空間☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性整體坐標下的映射關(guān)系圖像空間對應(yīng)區(qū)域整體坐標系：掃描轉(zhuǎn)換獲得的區(qū)域內(nèi)像素就是圖像空間中的對應(yīng)點。若pattern是一像素圖，則用來顯示像素(x,y)的顏色為：pattern[x%M][y%N]。在這種映射方式下，當區(qū)域運動(平移、旋轉(zhuǎn)等)時，填充其內(nèi)部的圖像并不跟隨。這種效果適用于動畫中漫游圖像的狀況。區(qū)域定義圖像空間(x,y)(x,y)☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性確定坐標YX局部坐標下的映射關(guān)系圖像空間對應(yīng)區(qū)域局部坐標系：掃描轉(zhuǎn)換時獲得的區(qū)域內(nèi)像素必需轉(zhuǎn)換到區(qū)域的局部坐標系，才能對應(yīng)于圖像空間中的點。若pattern是一像素圖，像素(x,y)的必需首先轉(zhuǎn)換到區(qū)域局部坐標下的點(x’,y’)，顯示顏色值為：pattern[x’%M][y’%N]。這種映射方式下，當區(qū)域運動(平移、旋轉(zhuǎn)等)時，填充其內(nèi)部的圖像也會作同樣運動。這種效果適用于圖像作為表面屬性的狀況。區(qū)域定義圖像空間(x,y)(x’,y’)☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法?原理和基礎(chǔ)?邊界填充?遞歸填充?掃描填充?泛濫填充?圖像填充?填充原理?填充映射?整體映射?局部映射■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性相對坐標YXY’X’掃描填充與區(qū)域填充轉(zhuǎn)換多邊形掃描轉(zhuǎn)換和區(qū)域填充是光柵圖形中兩類典型的面著色問題。兩類問題在確定條件下可以相互轉(zhuǎn)換：當已知頂點表示的多邊形內(nèi)一點作為種子點，并用掃描轉(zhuǎn)換直線段的算法將多邊形的邊界表示成8連通區(qū)域后，多邊形掃描轉(zhuǎn)換問題便可轉(zhuǎn)化為區(qū)域填充問題；反過來，若已知給定區(qū)域是多邊形區(qū)域，并且通過確定的方法求出它的頂點坐標，則區(qū)域填充問題便可轉(zhuǎn)化為多邊形掃描轉(zhuǎn)換問題。求出區(qū)域邊界表示的頂點邊界轉(zhuǎn)化為8連通像素表示☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法■兩種方法轉(zhuǎn)換■兩種方法區(qū)分●填充圖元屬性●字符表示/輸出●字符屬性掃描填充與區(qū)域填充區(qū)分基本思想不同多邊形掃描轉(zhuǎn)換是指將多邊形的頂點表示轉(zhuǎn)化為點陣表示；區(qū)域填充只變更區(qū)域的填充顏色，不變更區(qū)域表示方法。對邊界的要求不同多邊形掃描轉(zhuǎn)換的掃描算法只要求一條掃描線與多邊形邊界的交點個數(shù)為偶數(shù)，多邊形的邊界可以不封閉；在區(qū)域填充算法中，為了防止遞歸填充時跨越區(qū)域的邊界，要求：4連通區(qū)域的邊界是封閉的8連通區(qū)域，8連通區(qū)域的邊界為封閉的4連通區(qū)域?；诘臈l