gjl_chp04二維填充圖元的生成

1、2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)1第四章 光柵圖形的掃描轉(zhuǎn)換與區(qū)域填充掃描轉(zhuǎn)換矩形掃描轉(zhuǎn)換多邊形區(qū)域填充2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)2掃描轉(zhuǎn)換矩形n問題：?jiǎn)栴}：n矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處理矩形？理矩形？比一般多邊形可簡(jiǎn)化計(jì)算。應(yīng)用非常多，窗口系統(tǒng)。n共享邊界如何處理？共享邊界如何處理？n原則：左閉右開，下閉上開原則：左閉右開，下閉上開屬于誰(shuí)？2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)3掃描轉(zhuǎn)換矩形n方法：方法：void FillRectangle(Rectangle *rect,int color) int x,y; for(y = r

2、ect-ymin;y ymax;y+) for(x = rect-xmin;x xmax;x+) PutPixel(x,y,color);/*end of FillRectangle() */2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)4掃描轉(zhuǎn)換多邊形n多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)5掃描轉(zhuǎn)換多邊形n多邊形的表示方法多邊形的表示方法n頂點(diǎn)表示頂點(diǎn)表示n點(diǎn)陣表示點(diǎn)陣表示n頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。n點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存

3、儲(chǔ)器表示圖形，易于面著色。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)6多邊形的掃描轉(zhuǎn)換n多邊形的掃描轉(zhuǎn)換：多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。n幾種方法：幾種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標(biāo)志法。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)7void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = x

4、min;x e, 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ū)域的連貫性在相鄰兩掃描線上的反映。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)26當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每

5、一奇點(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)的處理2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)27奇點(diǎn)的處理n若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。n若奇點(diǎn)做兩個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)不是偶數(shù)。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)28奇點(diǎn)的處理n多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1 - yi)(yi+1 - yi)0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。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ì)算。否則按一個(gè)交點(diǎn)計(jì)算。n奇點(diǎn)的預(yù)處理：

6、2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)29數(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)陣形式。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)30 即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（Edge Table）和邊的活化鏈表AEL（Active Edge List）兩部分組成。 表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由

7、以下四個(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)步驟2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)31數(shù)據(jù)結(jié)構(gòu)與實(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的值）遞增的順序排列成行。 2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)32數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟與當(dāng)前掃描線相交的邊稱為活性邊（active edge)，把它們按與掃描線交點(diǎn)x坐標(biāo)

8、遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)33例子n已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標(biāo)分別為n（2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2）n建立其邊表和邊的活化鏈表2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)34例子2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)35邊表2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)36y=3Y=8活動(dòng)邊表的例子2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)37算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可

9、按下列步驟進(jìn)行： （1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。 （2）將邊的活化鏈表AEL設(shè)置為空。 （3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。 2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)38算法實(shí)現(xiàn)步驟1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中。遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對(duì)，依此類推。并填色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）x:=x+x。5）y:=y+1。2022-7-6浙江大

10、學(xué)計(jì)算機(jī)圖形學(xué)39掃描線算法n特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。n缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)40掃描線算法問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？如何處理圓、橢圓的掃描線算法？2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)41邊緣填充算法求余運(yùn)算求余運(yùn)算：假定A為一個(gè)正整數(shù)，則M的余定義為A M, 記為 。計(jì)算機(jī)中取A為n位能表示的最大整數(shù)。即，A=0 xFFFFFFFFA=0 xFFFFFFFF由來(lái)由來(lái)：光柵圖形中，如果某區(qū)域已著上值為M的顏色值做偶數(shù)次求余運(yùn)算，該區(qū)域

11、顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐?的顏色。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就為邊緣填充算法。算法基本思想算法基本思想：對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有象素取余。MM2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)421、將當(dāng)前掃描線上的 所有象素著上 顏色；2、求余：for(i = 0;i = m; i+)在當(dāng)前掃描線上， 從橫坐標(biāo)為Xi的交 點(diǎn)向右求余； M算法1（以掃描線為中心的邊緣填充算法）2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)431、將繪圖窗口的背景色置為 ；2、對(duì)多邊形的每一條非水平邊做：從該邊上的每個(gè)象素開始向右求余；M算法2（以邊為中心的邊緣填充算

12、法）2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)44邊緣填充算法n適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備。n優(yōu)點(diǎn)：算法簡(jiǎn)單n缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問多次，輸入/輸出的量比有序邊表算法大得多。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)45n引入柵欄，以減少填充算法訪問象素的次數(shù)。n柵欄：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二半。n基本思想：掃描線與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。n減少了象素重復(fù)訪問數(shù)目，但不徹底。柵欄填充算法2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)461. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象

13、素作一個(gè)邊界標(biāo)志。2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來(lái)指示當(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)志算法2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)47邊界標(biāo)志算法:算法過程void edgemark_fill(polydef, color)多邊形定義 polydef； int color; 對(duì)多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = F

14、ALSE; for (每條與多邊形polydef相交的掃描線y ) for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); 2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)48邊界標(biāo)志算法n用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，n但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。2022-7-6浙江

15、大學(xué)計(jì)算機(jī)圖形學(xué)49邊界標(biāo)志算法n思考：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)50區(qū)域填充算法n區(qū)域區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。n區(qū)域填充區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)51區(qū)域填充n表示方法：表示方法：內(nèi)點(diǎn)表示、邊界表示n內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示n枚舉處區(qū)域內(nèi)部的所有像素n內(nèi)部的所有像素著同一個(gè)顏色n邊界像素著與內(nèi)部像素不同的顏色n邊界表示邊界表示n枚舉出邊界上所有的像素n邊界上的所有像素著同一顏色n內(nèi)部像素著與邊界像素不同的顏色2022

16、-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)52區(qū)域填充區(qū)域填充要求區(qū)域是連通的區(qū)域填充要求區(qū)域是連通的n連通性連通性 4連通、8連通n4 4連通：連通：n8 8連通連通2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)53區(qū)域填充n4 4連通與連通與8 8連通區(qū)域的區(qū)別連通區(qū)域的區(qū)別n連通性：連通性： 4 4連通可看作連通可看作8 8連通區(qū)域，但對(duì)邊界有要求連通區(qū)域，但對(duì)邊界有要求n對(duì)邊界的要求對(duì)邊界的要求2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)54A：適合于內(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)的顏色為

17、new_color，然后逐步將整個(gè)區(qū)域G都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成new_color ； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素在邊界內(nèi)且未置成new_color ，則把該象素入棧。種子填充算法2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)55種子填充算法n例 ： 多 邊 形 由P0P1P2P3P4構(gòu) 成 ，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)n設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示

18、2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)56種子填充算法遞歸算法可實(shí)現(xiàn)如下遞歸算法可實(shí)現(xiàn)如下void FloodFill4(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);

19、/*end of FloodFill4()*/ 2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)57種子填充算法n邊界表示的邊界表示的4 4連通區(qū)域連通區(qū)域void 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,

20、oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/ 2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)58n該算法也可以填充有孔區(qū)域。該算法也可以填充有孔區(qū)域。 n缺點(diǎn)缺點(diǎn)： (1) 有些象素會(huì)入棧多次，降低算法效率； (2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。n改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法種子填充算法2022-7-6浙江大學(xué)計(jì)算機(jī)圖

21、形學(xué)59掃描線算法n掃描線算法掃描線算法n目標(biāo)：減少遞歸層次目標(biāo)：減少遞歸層次n適用于邊界表示的適用于邊界表示的4 4連通區(qū)域連通區(qū)域算法思想算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來(lái)，反復(fù)進(jìn)行這個(gè)過程，直到所保存的個(gè)區(qū)段都填充完畢。2022-7-6浙江大學(xué)計(jì)算機(jī)圖形學(xué)60掃描線填充算法(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)