1、第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充4.14.1多邊形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換4.24.2區(qū)域填充區(qū)域填充 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。4.1多邊形的掃描轉(zhuǎn)換 多邊形的表示方法多邊形的表示方法頂點(diǎn)表示頂點(diǎn)表示點(diǎn)陣表示點(diǎn)陣表示 頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。多邊形的掃描轉(zhuǎn)換：多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元

2、素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。兩種方法：兩種方法：掃描線算法；邊界標(biāo)志法。 掃描線算法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率算法效率處理對(duì)象：非自交多邊形處理對(duì)象：非自交多邊形 （邊與邊之間除（邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）了頂點(diǎn)外無(wú)其它交點(diǎn)）掃描線算法交點(diǎn)的取整規(guī)則交點(diǎn)的取整規(guī)則 要求：使生成的像素全部位于多邊形之內(nèi)要求：使生成的像素全部位于多邊形之內(nèi)用于線畫圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致用于線畫圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用部分像素位于多邊形之外，從而不可用 假定非水平邊與掃

3、描線假定非水平邊與掃描線y=ey=e相交，交點(diǎn)的橫坐標(biāo)為相交，交點(diǎn)的橫坐標(biāo)為x,x,規(guī)則如下規(guī)則如下掃描線算法規(guī)則1：x x為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間 (a)(a)交點(diǎn)位于左邊之上，向右取整交點(diǎn)位于左邊之上，向右取整 (b)(b)交點(diǎn)位于右邊之上，向左取整交點(diǎn)位于右邊之上，向左取整規(guī)則2 2：邊界上象素的取舍問題，避免填充擴(kuò)大化。解決方法：解決方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間左閉右開掃描線算法規(guī)則3：掃描線與多邊形的頂點(diǎn)相交時(shí)，交點(diǎn)的取舍，保證交點(diǎn)正確配對(duì)。解決方法：解決方法

4、：檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值，兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0，1，2，來決定取0，1，2個(gè)交點(diǎn)。 掃描線算法掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。 開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法 設(shè)多邊形p的頂點(diǎn)pi=(xi,yi),i=0,1, ,n，又設(shè)yi0,yi1,yin是各頂點(diǎn)pi的坐標(biāo)yi的遞減數(shù)

5、列，即yikyik+1,0kn-1這樣，當(dāng)yikyik+1,0kn-1時(shí)，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長(zhǎng)方形區(qū)域被多邊形p的邊分割成若干梯形（三角形可看作其中一底邊長(zhǎng)為零的梯形），它們具有下列性質(zhì)：區(qū)域的連貫性y=yiky=yik+1區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形p的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形p的內(nèi)部；另一類在多邊形p的外部。3）兩類梯形在長(zhǎng)方形區(qū)域yik,yik+1內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形p內(nèi)，另一個(gè)在p外。 y=yik+1y=yik區(qū)域的連貫性根據(jù)這些性質(zhì)

6、，實(shí)際上只需知道該長(zhǎng)方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形p的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于p的內(nèi)外關(guān)系。 設(shè)e為一整數(shù)，yi0eyin。若掃描線y=e與多邊形p的pi-1pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。 現(xiàn)設(shè)xei1,xei2,xei3,xeil 是該掃描線與p的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，稱此序列為交點(diǎn)序列。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)： 掃描線的連貫性掃描線的連貫性1）設(shè)l是偶數(shù)。2）在該掃描線上，只有區(qū)段(xeik,xeik+1）,k=1,3,5,l-1位于多邊形p內(nèi)，其余區(qū)段都在p外。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。 設(shè)

7、d為一整數(shù)，并且d=e-1,并且 yi0dyin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdj3,xdjk 現(xiàn)在來討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形p的邊pr-1pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對(duì)應(yīng)元素xer,xdr滿足下列關(guān)系：xer= xdr + 1/mr (1)其中mr為邊pr-1pr的斜率。 邊的連貫性y=ey=d邊的連貫性于是，可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列，即先運(yùn)用遞推關(guān)系式(1)求得與掃描線y=e和y=d都相交的所有多邊形上的交點(diǎn)xer,再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊pqpq+1上的交點(diǎn)xeq。如果p的頂點(diǎn)的坐標(biāo)是

8、整數(shù)，那么xeq=xq或xeq=xq+1,然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。 y=ey=d邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0kn-1,使得yike, dyik+1成立時(shí)，則由區(qū)域的連貫性可知d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系： 1）兩序列元素的個(gè)數(shù)相等，如上圖所示。 2）點(diǎn)(xeir,e)與(xdjr,d)位于多邊形p的同一邊上，于是 xeir= xdjr + 1/kjr (2)這樣，運(yùn)用遞推關(guān)系式(2)可直接由d的交點(diǎn)序列和e的獲得e的交點(diǎn)序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。當(dāng)掃描線與多邊形p的交點(diǎn)是p的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。

9、以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形p的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡(jiǎn)單地計(jì)為一個(gè)交點(diǎn)或者簡(jiǎn)單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？奇點(diǎn)的處理奇點(diǎn)的處理 若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況a，交點(diǎn)個(gè)數(shù)不是偶數(shù)。 若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況b，交點(diǎn)個(gè)數(shù)不是偶數(shù)。奇點(diǎn)的處理 多邊形p的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1 - yi)(yi+1 - yi)0，則稱頂點(diǎn)pi為極值點(diǎn)；否則稱pi為非極值點(diǎn)。 規(guī)定：奇點(diǎn)是非極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)規(guī)定：奇點(diǎn)是非極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。算

10、，否則按一個(gè)交點(diǎn)計(jì)算。數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdjn ，這一序列由位于掃描線y=d上的多邊形p的頂點(diǎn)組成。 由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形p內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。如何判斷多邊形的一條邊與掃描線是否相交？如何判斷多邊形的一條邊與掃描線是否相交？與當(dāng)前掃描線相交的邊稱為活性邊（active edge)，把它們按與掃描線

11、交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ ael, active edge table)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 如何計(jì)算下一條掃描線與邊的交點(diǎn)。如何計(jì)算下一條掃描線與邊的交點(diǎn)。直線方程：ax+by+c = 0當(dāng)前交點(diǎn)坐標(biāo)：(xi, yi)下一交點(diǎn)坐標(biāo)：(xi+1,yi+1)xi+1= (-byi+1)-c)/a = (-byi+1)-c)/a =xi-b/a=xi+1/mi活動(dòng)邊表中需要存放的信息：x：當(dāng)前掃描線與邊的交點(diǎn)dx-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：

12、邊所交的最高掃描線數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 為了方便邊的活化鏈表的更新，建立另一個(gè)表-邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：x：掃描線與該邊的初始交點(diǎn)dx：x的增量ymax：該邊的最大y值 即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表et（edge table）和邊的活化鏈表ael（active edge list）兩部分組成。 表結(jié)構(gòu)et和ael中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成： ymax 邊的上端點(diǎn)的y坐標(biāo)； x 在et中表示邊的下端點(diǎn)的x坐標(biāo)，在ael中則表示邊與掃描線的交點(diǎn)的坐標(biāo)； x 邊的斜率的倒數(shù)； next 指向下一條邊的指針。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟數(shù)據(jù)結(jié)構(gòu)與

13、實(shí)現(xiàn)步驟邊的分類表et是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按x的值）遞增的順序排列成行。 邊表724p5 p178-1p2 p1620p4 p536-2p3 p4560.5p3 p2(y(ymax, max, x,x, next)x,x, next) 活動(dòng)邊表的例子34-2p3 p456.50.5p3 p2掃描線2aet指針620p4 p5570.5p3 p2掃描線3aet指針(y(ymax, max, x,x, next)x,x, next)36-2p3 p4560.5p3

14、p2掃描線2aet指針620p4 p557.50.5p3 p2掃描線4aet指針620p4 p578-1p2 p1掃描線5aet指針724p5 p178-1p2 p1掃描線6aet指針?biāo)惴▽?shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表et后，掃描線算法可按下列步驟進(jìn)行： （1）取掃描線縱坐標(biāo)y的初始值為et中非空元素的最小序號(hào)。 （2）將邊的活化鏈表ael設(shè)置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表et和邊的活化鏈表都變成空為止。 算法實(shí)現(xiàn)步驟1）如邊分類表et中的第y類元素非空，則將屬于該類的所有邊從et中取出并插入邊的活化鏈表中，ael中的各邊按照x

15、值（當(dāng)x值相等時(shí)，按x值）遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表ael非空，則將ael中的邊兩兩依次配對(duì)，即1，2邊為一對(duì)，3，4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。3）將邊的活化鏈表ael中滿足y=ymax的邊刪去。4）將邊的活化鏈表ael剩下的每一條邊的x域累加x，即x:=x+x。5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y:=y+1。掃描線算法 特點(diǎn)：算法效率較高。 缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。掃描線算法問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能

16、處理邊自交的多邊形？1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。邊界標(biāo)志算法邊界標(biāo)志算法:算法過程void edgemark_fill(polydef, color)多邊形定義 polydef； int color; 對(duì)多邊形polydef 每條

17、邊進(jìn)行直線掃描轉(zhuǎn)換； inside = false; for (每條與多邊形polydef相交的掃描線y ) for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= false) drawpixel (x, y, color); else drawpixel (x, y, background); 邊界標(biāo)志算法 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。邊界標(biāo)志算法 思考

18、：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？4.1多邊形掃描轉(zhuǎn)換4.2區(qū)域填充4.2區(qū)域填充算法 區(qū)域區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。 區(qū)域填充區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的4.2區(qū)域填充 表示方法：表示方法：內(nèi)點(diǎn)表示、邊界表示 內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色 邊界表示邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色4.2區(qū)域填充區(qū)域填充要求區(qū)域是連通的區(qū)域填充要求區(qū)域是連通的 連通性連通性 4連通、8連通

19、 4 4連通：連通： 8 8連通連通4.2區(qū)域填充 4 4連通與連通與8 8連通區(qū)域的區(qū)別連通區(qū)域的區(qū)別連通性：連通性： 4 4連通可看作連通可看作8 8連通區(qū)域，但對(duì)邊界有要連通區(qū)域，但對(duì)邊界有要求求對(duì)邊界的要求對(duì)邊界的要求適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)g為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為g的原色。現(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域g進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個(gè)區(qū)域g都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成多邊形色； （3）按上、下、左、右的順序檢

20、查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。種子填充算法種子填充算法 例 ： 多 邊 形 由 p0p1p2p3p4構(gòu) 成 ，p0(1,5)p1(5,5)p2(7,3)p3(7,1)p4(1,1) 設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示 s12 3 49 8 7 6 511 12 13 1410(2 10 8 13)(3 7 13 10 8 13)(4 6 14 7 13 10 8 13)(5 6 14 7 13 10 8 13)種子填充算法遞歸算法可實(shí)現(xiàn)如下遞歸算法可實(shí)現(xiàn)如下void flo

21、odfill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y) = oldcolor) putpixel(x,y,newcolor); floodfill4(x,y+1,oldcolor,newcolor); floodfill4(x,y-1,oldcolor,newcolor); floodfill4(x-1,y,oldcolor,newcolor); floodfill4(x+1,y,oldcolor,newcolor); /*end of floodfill4()*/ 種子填充算法邊界表示的邊界表示的4 4連通區(qū)域連通區(qū)域v

22、oid boundaryfill4(int x,int y,int boundarycolor,int newcolor)int color;color = getpixel(x,y);if(color != boundarycolor) & (color != newcolor)putpixel(x,y,newcolor);boundaryfill4(x,y+1,oldcolor,newcolor);boundaryfill4(x,y-1,oldcolor,newcolor);boundaryfill4(x-1,y,oldcolor,newcolor);boundaryfill4(x+1,y,oldcolor,newcolor);/*end of boundaryfill4()*/ 該算法也可以填充有孔區(qū)域。該算法也可以填充有孔區(qū)域。 缺點(diǎn)缺點(diǎn)：(1) 有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。 改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法種子填充算法掃描線算法 掃描線算法掃描線算法目標(biāo)：減少遞歸層次目標(biāo)：減少遞歸層次適用于邊界表示的適用于邊界表示的4 4連通區(qū)域連通區(qū)域算法思想算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相