計(jì)算機(jī)圖形學(xué)第3章二維基本圖(4)

1、3.3.2掃描線種子填充算法掃描線種子填充算法 該算法屬于種子填充算法，它是以掃描線上的區(qū)段為單位進(jìn)行操作。所謂區(qū)段，就是一條掃描線上相連著的若干內(nèi)部象素的集合。一、掃描線種子填充算法思想掃描線種子填充算法的基本思想是：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來(lái)。反復(fù)這個(gè)過(guò)程，直到所保存的各區(qū)段都填充完畢。二、掃描線種子填充算法實(shí)現(xiàn)借助于堆棧，上述算法實(shí)現(xiàn)步驟如下：1、初始化堆棧。2、種子壓入堆棧。3、while（堆棧非空） (1)從堆棧彈出種子象素。(2)如果種子象素尚未填充，則：

2、a.求出種子區(qū)段：xleft、xright;b.填充整個(gè)區(qū)段。c.檢查相鄰的上掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。d.檢查相鄰的下掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。掃描線種子填充算法步驟掃描線種子填充算法步驟(1)種子種子象素象素入棧入棧。(2)棧非空棧非空時(shí)象素時(shí)象素出棧出棧，否則結(jié)束。，否則結(jié)束。(3)對(duì)出棧象素及對(duì)出棧

3、象素及左、右兩邊象素填充左、右兩邊象素填充，直到遇，直到遇邊界邊界XL、XR。(4)在在(XL ，XR) 內(nèi)查相臨的內(nèi)查相臨的上、下兩條掃描線是否為邊界或已填充上、下兩條掃描線是否為邊界或已填充,如不是，則將每區(qū)間的最右邊的象素如不是，則將每區(qū)間的最右邊的象素入棧入棧?；氐交氐?2)。練習(xí)：用掃描線種子填充算法，寫(xiě)出圖中順序進(jìn)棧的種子坐標(biāo)及所需最大?？臻g 順序進(jìn)棧的種子坐標(biāo)為： （1，2）、（2，3）、（2，1）、（4，4）、（2，4） 所需最大棧空間為：2 作業(yè)：用掃描線種子填充算法寫(xiě)出圖中所示的順序進(jìn)棧的種子坐標(biāo)和需要最大的?？臻g？圖中：初始種子坐標(biāo)：（5，1），紅點(diǎn)表示邊界，藍(lán)點(diǎn)表示種子

4、。三、掃描線種子填充算法特點(diǎn)1、該算法考慮了掃描線上象素的相關(guān)性，種子象素不再代表一個(gè)孤立的象素，而是代表一個(gè)尚未填充的區(qū)段。2、進(jìn)棧時(shí)，只將每個(gè)區(qū)段選一個(gè)象素進(jìn)棧（每個(gè)區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問(wèn)題。3、種子出棧時(shí)，則填充整個(gè)區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對(duì)尚未填充象素的登記（象素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆?？臻g，又可以實(shí)施快速填充。 在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個(gè)閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線逐行對(duì)多邊形求交，在交點(diǎn)對(duì)之間填充。邊標(biāo)志填充算法就是在逐行處理時(shí)，利用邊界色作為標(biāo)志來(lái)進(jìn)行填充的。例如某掃描線從左到右

5、掃描時(shí)碰到邊界色，立刻改變標(biāo)志的狀態(tài)，接下來(lái)再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。3.3.3邊標(biāo)志邊標(biāo)志填充算法填充算法 一、邊標(biāo)志填充算法思想掃描線具有連貫性，這種連貫性只有在掃描線與多邊形相交處才會(huì)發(fā)生變化，而每次的變化結(jié)果：無(wú)非是在前景色和背景色之間相互“切換”。邊標(biāo)志填充算法正是基于這一發(fā)現(xiàn)，先在屏幕上生成多邊形輪廓線，然后逐條掃描處理。處理中：逐點(diǎn)讀取象素值，若為邊界色，則對(duì)該象素值進(jìn)行顏色切換。二、邊標(biāo)志填充算法實(shí)現(xiàn) 1、用邊界色畫(huà)出多邊形輪廓線，也就是將多邊形邊界所經(jīng)過(guò)的象素打上邊標(biāo)志。 2、為了縮小范圍，加快填充速度，須找出多邊形的最小包圍盒：xmin、ymin、xmax、ym

6、ax。如下圖所示。邊標(biāo)志填充算法3、逐條掃描線進(jìn)行處理，對(duì)每條掃描線依從左往右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。三、邊標(biāo)志填充算法特點(diǎn) 該算法思想簡(jiǎn)單，實(shí)現(xiàn)容易。既不需要求交點(diǎn)、交點(diǎn)排序、邊的登記，也不需要使用鏈表、堆棧等數(shù)據(jù)結(jié)構(gòu)。四、邊標(biāo)志填充算法程序EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)int i,x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*設(shè)置畫(huà)筆色*/ for(i=0 ;i

7、n;i+)line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*畫(huà)出多邊形的n條邊*/用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y=ymax;y+) flag=-1;for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor)flag=-flag;if(flag=1)putpixel(x,y, newcolor); 五、邊標(biāo)志填充算法錯(cuò)誤處理1、該算法雖然簡(jiǎn)單，但程序運(yùn)行后會(huì)出現(xiàn)局部錯(cuò)誤。從下圖可以發(fā)現(xiàn)，對(duì)于多邊形頂點(diǎn)為局部極值點(diǎn)時(shí)，掃描線與多邊形的相交次數(shù)不再是偶

8、數(shù)，而是奇數(shù)，填充時(shí)會(huì)出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒(méi)有填上色。解決的辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志。2、特別當(dāng)心多邊形邊界的掃描轉(zhuǎn)換。在這里就不能考慮：不同的斜率產(chǎn)生的直線要亮度均勻，如下圖(a)所示。否則當(dāng)掃描線y遇到斜率小于1的邊界線時(shí)，碰到幾個(gè)邊界點(diǎn)，會(huì)引起標(biāo)志的無(wú)序改變，將導(dǎo)致填充的錯(cuò)誤。在邊標(biāo)志填充算法中要注意多邊形邊界的掃描轉(zhuǎn)換解決的辦法：對(duì)于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長(zhǎng)一步，x方向增長(zhǎng)1/m步距，以保證掃描線y遇到斜率小于1的邊界時(shí)，只能遇到一個(gè)點(diǎn)。請(qǐng)看圖

9、(b)。3.3.4 圖案填充圖案填充 前面介紹的區(qū)域填充算法，都是把區(qū)域內(nèi)部的象素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用圖案來(lái)填充平面區(qū)域。這可以將前面的填充算法中寫(xiě)象素的那部分代碼稍加修改來(lái)實(shí)現(xiàn): 在確定了區(qū)域內(nèi)點(diǎn)后，不是馬上對(duì)該象素填色，而是先將該象素映射到圖案位圖的對(duì)應(yīng)位置。根據(jù)圖案該位置的象素值，決定填充顏色。一、圖案填充方式： 1、透明方式:若是以透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)象素，否則，不改變?cè)撓笏氐闹怠?2、不透明方式: 而若是以不透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)象素，否則，用背景色寫(xiě)象素。二、圖案定位法： 1、相對(duì)定

10、位法、相對(duì)定位法:把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊。這樣，當(dāng)被填充的多邊形移動(dòng)時(shí)，圖案也跟著移動(dòng)，看起來(lái)比較自然。對(duì)于多邊形，可取邊界上最左邊的頂點(diǎn)，而對(duì)于圓和橢圓這樣具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)，如取中心與圖案原點(diǎn)對(duì)齊。2、絕對(duì)定位法：、絕對(duì)定位法：把圖案原點(diǎn)與屏幕原點(diǎn)對(duì)齊。該方法可以將整個(gè)屏幕看成被要填充的圖案布滿，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來(lái)，其它區(qū)域?qū)Υ藞D案卻是不透明的，圖案被全部擋住。這種方法比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無(wú)縫連接的效果。但它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其效果是區(qū)域內(nèi)的圖案變。 三、圖案

11、填充算法實(shí)現(xiàn)下面討論在第二種絕對(duì)定位法下用不透明方式對(duì)平面區(qū)域填充圖案：假設(shè)填充圖案是一個(gè)MN的位圖，用MN的數(shù)組存放。M、N一般比需要填充區(qū)域的尺寸小得多（88、1616、3232），所以圖案總是設(shè)計(jì)成周期性的，使之能通過(guò)重復(fù)使用來(lái)構(gòu)成任意尺寸的圖案。當(dāng)確定了區(qū)域內(nèi)點(diǎn)p（x,y）后，則圖案位圖上的對(duì)應(yīng)位置為p（x%M，y%N），其中%為C語(yǔ)言整除取余運(yùn)算符,然后取出圖案位圖該位置的象素進(jìn)行填充。四、圖案填充算法程序/ / 采用不透明方式絕對(duì)定位法填充圖案的程序偽代碼采用不透明方式絕對(duì)定位法填充圖案的程序偽代碼: :maskpixel(int x,int y,int newcolor,int

12、backgroundcolor) maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy;int xx,yy;int maskcode88= 0,0,0,0,1,0,0,0,int maskcode88= 0,0,0,0,1,0,0,0,/ /* *磚縫圖案磚縫圖案* */ / 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,1,0,0,

13、0,0,0,0,0, 1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,11,1,1,1,1,1,1,1;xx=x%8; xx=x%8; / /* *多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)x x映射到圖案坐標(biāo)映射到圖案坐標(biāo)xxxx* */ /yy=y%8; yy=y%8; / /* *多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)y y到圖案坐標(biāo)到圖案坐標(biāo)yyyy* */ /if(maskcodeyyxx)if(maskcodeyyxx)putpixel(x,y, newcolor); /putp

14、ixel(x,y, newcolor); /* * newcolor newcolor 為前景色為前景色* */ /elseelseputpixel(x,y, backgroundcolor); /putpixel(x,y, backgroundcolor); /* * backgroundcolor backgroundcolor為背景色為背景色* */ / 3.4字符的表示與輸出字符的表示與輸出 我們討論的字符是指字母、數(shù)字、漢字、標(biāo)點(diǎn)等符號(hào)。計(jì)算機(jī)中，字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)，對(duì)于一個(gè)字符來(lái)說(shuō)，它所對(duì)應(yīng)的編碼是由它所屬的字符集決定。1、ASCII碼目前，國(guó)際上普遍采用的字符編碼是ASC

15、II碼（American Standard Code for Information Interchange）美國(guó)信息交換標(biāo)準(zhǔn)代碼。它是用七位二進(jìn)制數(shù)進(jìn)行編碼，共能表示128個(gè)字符，其中編碼031表示控制字符（不可顯示），編碼32127表示英文字母、數(shù)字、標(biāo)點(diǎn)符號(hào)等可顯示字符。一個(gè)字符的ASCII碼用一個(gè)字節(jié)（8位）表示，其最高位不用或者作為奇偶校驗(yàn)位。2、國(guó)標(biāo)碼我國(guó)除了采用ASCII碼外，還制定了漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集:中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)信息交換編碼，代號(hào)為“GB231280”。該字符集共收錄常用漢字6763個(gè)，圖形符號(hào)682個(gè)。它規(guī)定所有漢字和圖形符號(hào)組成一個(gè)9494的矩陣，在此方陣

16、中，每一行稱為“區(qū)”，用區(qū)碼來(lái)標(biāo)識(shí)；每一列稱為“位”，用位碼來(lái)標(biāo)識(shí)，一個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼共同標(biāo)識(shí)。區(qū)碼和位碼分別需要7個(gè)二進(jìn)制位，同樣，為了方便，各采用一個(gè)字節(jié)表示。所以在計(jì)算機(jī)中，漢字（符號(hào)）國(guó)標(biāo)碼占用兩個(gè)字節(jié)。3、兩種編碼的區(qū)別那么，給定一個(gè)字節(jié)，如何來(lái)確定它代表的是ASCII碼，還是國(guó)標(biāo)碼的區(qū)碼和位碼呢？通常采用字符中冗余的最高位來(lái)標(biāo)識(shí)：最高位為0時(shí)，表示ASCII碼；最高位為1時(shí)，表示漢字編碼的區(qū)碼（高位字節(jié)）或位碼（低位字節(jié)）。4、機(jī)內(nèi)碼機(jī)內(nèi)碼： 計(jì)算機(jī)內(nèi)表示字符的編碼 1、西文字符西文字符的機(jī)內(nèi)碼就是ASCII碼。2、中文字符國(guó)標(biāo)碼為：2020H+區(qū)位碼的十六進(jìn)制表示機(jī)內(nèi)碼

17、為：8080H+國(guó)標(biāo)碼 即：A0A0H+區(qū)位碼的十六進(jìn)制表示3、舉例“啊”字的區(qū)位碼為1601，轉(zhuǎn)換為十六進(jìn)制表示應(yīng)為1001H（區(qū)碼16轉(zhuǎn)為10H，位碼01轉(zhuǎn)為01H）。于是，“啊”字的機(jī)內(nèi)碼為：A0A0H+1001H=B0A1H4、附加說(shuō)明除了機(jī)內(nèi)碼外，還有一個(gè)概念，即漢字輸入碼。漢字輸入碼是為了方便人工輸入漢字而設(shè)計(jì)的人機(jī)界面編碼。用戶將漢字輸入碼輸入到計(jì)算機(jī)中，然后通過(guò)漢字系統(tǒng)將其轉(zhuǎn)為機(jī)內(nèi)碼。 為了在顯示器等輸出設(shè)備上輸出字符，必須要有每個(gè)字符的圖形信息，這些信息保存在系統(tǒng)的字庫(kù)中。字符的圖形表示方法有兩種：點(diǎn)陣表示和矢量表示。3.4.1點(diǎn)陣字符點(diǎn)陣字符 就目前來(lái)說(shuō)，用得最多的是點(diǎn)陣字

18、符。在字符的點(diǎn)陣表示中，每個(gè)字符由一個(gè)位圖（字符掩模）來(lái)表示，對(duì)于西文字符的掩模矩陣一般不小于57，而定義漢字的掩模矩陣一般不小于1616。一個(gè)字符的點(diǎn)陣數(shù)越多，字符越清晰、美觀。一、點(diǎn)陣字符的存儲(chǔ)點(diǎn)陣字符是由位圖表示，保存字符就是保存位圖。即點(diǎn)陣字符的存儲(chǔ)就是按行或按列進(jìn)行編碼。如下圖(a)，每行右邊的二進(jìn)制或十六制的代碼就是對(duì)該行的編碼。 二、點(diǎn)陣字符的顯示從給定的字符編碼到在屏幕上將它顯示出來(lái)要經(jīng)歷兩個(gè)步驟：1從字庫(kù)中將它的位置找到。2將該位置上的位圖讀到二維數(shù)組中進(jìn)行顯示，見(jiàn)圖(b)。矢量字符由于其占空間少、美觀、變換方便等優(yōu)點(diǎn)得到越來(lái)越廣泛的應(yīng)用，特別在排版軟件、工程繪圖軟件中，它幾乎完全取代了傳統(tǒng)的點(diǎn)陣字符。在字符的矢量表示方法中，保存的是字符的筆畫(huà)信息而不是整個(gè)位圖。一、字符坐標(biāo)系 字符處于局部坐標(biāo)系中，見(jiàn)圖(a)。對(duì)一個(gè)字符來(lái)說(shuō)，它由構(gòu)成它的筆畫(huà)組成，而每一筆畫(huà)又由其兩端點(diǎn)坐標(biāo)和端點(diǎn)間是否連線的標(biāo)志確定。例如，漢字“士”有三畫(huà)，六個(gè)端點(diǎn)，可以按圖(b)的結(jié)構(gòu)保存該漢字。3.4.2矢量字符矢量字符 二、矢量字符的變換點(diǎn)陣字符的表示是位圖，點(diǎn)陣字符的變換是圖像變換，當(dāng)將點(diǎn)陣字符旋轉(zhuǎn)或者放大時(shí)，會(huì)發(fā)現(xiàn)顯示結(jié)果粗糙而難看；而用來(lái)表示矢量字符的是端點(diǎn)坐標(biāo)，對(duì)矢量字符的變換就是對(duì)這些端點(diǎn)進(jìn)行變換，是圖形的幾何變換，它可以對(duì)矢量字符進(jìn)行任意變換而不影響顯示結(jié)果。此外，點(diǎn)陣字