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

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

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

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

的并集。☆填充圖元生成●掃描轉(zhuǎn)換填充●區(qū)域填充算法

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

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

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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

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

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

?圖像填充●填充圖元屬性●字符表示/輸出●字符屬性+1-1-1+1+1環(huán)繞數(shù)計(jì)算方法叉乘法：將從P點(diǎn)動(dòng)身的射線向量u與穿過射線的每條邊的邊向量e叉乘，假如對(duì)某一特定邊，積u×e的元素z為正，那么，該邊從右到左穿過射線，環(huán)繞數(shù)加1；否則，該邊從左到右穿越射線，環(huán)繞數(shù)減1。向量點(diǎn)積法：建立一個(gè)垂直于u且從P沿u方向看是從右到左指向的向量假如u的元素是(ux,uy)，那么，垂直于u的向量有元素(-uy,ux)。假如垂直向量與邊向量的點(diǎn)積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檢測(cè)

?奇偶效驗(yàn)

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

?環(huán)繞計(jì)算

?邊界填充

?泛濫填充

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