計(jì)算機(jī)圖形學(xué) 第二章 二維基本圖形的生成與二維區(qū)域的填充ppt課件

1、2020/11/20,1,第二章 二維基本圖形的生成與區(qū)域填空,重點(diǎn)：掌握二維圖元直線(xiàn)、圓、區(qū)域填充、字符的生成算法。 難點(diǎn)：理解二維圖元生成的算法思想并且用C語(yǔ)言進(jìn)行算法的實(shí)現(xiàn)。 課時(shí)安排：授課8學(xué)時(shí)（直線(xiàn)、圓：3學(xué)時(shí)；區(qū)域填充：4學(xué)時(shí)；字符：1學(xué)時(shí)）； 上機(jī)4學(xué)時(shí)（直線(xiàn)、圓：2學(xué)時(shí)；區(qū)域填充：2學(xué)時(shí)）。,2020/11/20,2,第二章 二維基本圖形的生成與區(qū)域填空,圖元生成算法的要求：準(zhǔn)確、亮度均勻、速度快。 前面已經(jīng)知道，矢量顯示（隨機(jī)掃描顯示器）和光柵顯示是兩種完全不同的圖形顯示技術(shù)。,2020/11/20,3,第二章 二維基本圖形的生成與區(qū)域填空,目前，光柵顯示技術(shù)占主要地位。 原

2、因是： 1、光柵顯示可以用顏色或圖案來(lái)填充一個(gè)區(qū)域；2、光柵顯示以象素為單位進(jìn)行讀寫(xiě)和存儲(chǔ)，可以實(shí)現(xiàn)對(duì)物體細(xì)節(jié)的描述；3、圖形的任意部分均可以被移動(dòng)和復(fù)制。,2020/11/20,4,第二章 二維基本圖形的生成與區(qū)域填空,在這一章里，主要介紹在光柵輸出設(shè)備上，根據(jù)物體的坐標(biāo)描述構(gòu)造二維幾何圖形的方法。 在光柵顯示器上，象素是屏幕的最小顯示單位，因此二維圖形的構(gòu)造就是找出最靠近所描述幾何圖形的那些象素，將它們置入規(guī)定的顏色并放入幀緩存。 我們知道，一幅圖是由點(diǎn)、直線(xiàn)、曲線(xiàn)、多邊形填充區(qū)域以及字符串等組成。下面將討論這些基本圖元的生成技術(shù)和算法。,2020/11/20,5,2.1 直線(xiàn)的掃描轉(zhuǎn)換,

3、一、數(shù)學(xué)直線(xiàn) 在數(shù)學(xué)上，理想的直線(xiàn)是一條由無(wú)窮多個(gè)無(wú)限小的連續(xù)的點(diǎn)組成。 數(shù)學(xué)直線(xiàn),2020/11/20,6,2.1 直線(xiàn)的掃描轉(zhuǎn)換,二、光柵平面顯示的直線(xiàn) 但在光柵顯示平面上，我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線(xiàn)的象素點(diǎn)的集合來(lái)表示它。每個(gè)象素具有一定的尺寸，是顯示平面上可被訪(fǎng)問(wèn)的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說(shuō)相鄰像素的坐標(biāo)值是階梯的而不是連續(xù)的。,2020/11/20,7,2.1 直線(xiàn)的掃描轉(zhuǎn)換,光柵直線(xiàn),2020/11/20,8,2.1 直線(xiàn)的掃描轉(zhuǎn)換,三、直線(xiàn)的掃描轉(zhuǎn)換 直線(xiàn)的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線(xiàn)的那些象素的坐標(biāo)值，并將這些象素置成所要求的

4、顏色。 直線(xiàn)的掃描轉(zhuǎn)換 由于一幅圖中可能包含成千上萬(wàn)條直線(xiàn)，所以要求繪制算 法應(yīng)該： 1、最接近數(shù)學(xué)上的直線(xiàn)；,2020/11/20,9,2.1 直線(xiàn)的掃描轉(zhuǎn)換,2、沿著線(xiàn)段分布的象素應(yīng)均勻 不均勻的例子如下圖所示，對(duì)同樣長(zhǎng)的線(xiàn)段，如果進(jìn)行圖中的掃描轉(zhuǎn)換，就會(huì)因?yàn)樾甭实牟煌?，產(chǎn)生的象素個(gè)數(shù)不相等，這樣將導(dǎo)致象素亮度分布不均勻。 3、畫(huà)線(xiàn)速度盡可能的快,2020/11/20,10,2.1.1 生成直線(xiàn)的DDA算法,數(shù)值微分法即DDA法(Digital Differential Analyzer)，是一種基于直線(xiàn)的微分方程來(lái)生成直線(xiàn)的方法 一、直線(xiàn)DDA算法描述： 設(shè)(x1，y1)和(x2，y2)

5、分別為所求直線(xiàn)的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線(xiàn)的微分方程得 = m =直線(xiàn)的斜率 (21),2020/11/20,11,2.1.1 生成直線(xiàn)的DDA算法,可通過(guò)計(jì)算由x方向的增量x引起y的改變來(lái)生成直線(xiàn)：xi+1=xi+x (22) yi+1=yi+y=yi+xm (23) 也可通過(guò)計(jì)算由y方向的增量y引起x的改變來(lái)生成直線(xiàn)：yi+1=yi+y (24) xi+1=xi+x=xi+y/m (25) 式(22)至(25)是遞推的。,2020/11/20,12,2.1.1 生成直線(xiàn)的DDA算法,二、直線(xiàn)DDA算法思想： 選定x2x1和y2y1中較大者作為步進(jìn)方向(假設(shè)x2x1較大)，取該方向上的增量為一個(gè)

6、象素單位(x=1)，然后利用式(21)計(jì)算另一個(gè)方向的增量(y=xm=m)。通過(guò)遞推公式(22)至(25)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線(xiàn)。 之所以取x2x1和y2y1中較大者作為步進(jìn)方向，是考慮沿著線(xiàn)段分布的象素應(yīng)均勻，這在下圖中可看出。,2020/11/20,13,2.1.1 生成直線(xiàn)的DDA算法,另外，算法實(shí)現(xiàn)中還應(yīng)注意直線(xiàn)的生成方向，以決定x及y是取正值還是負(fù)值。,2020/11/20,14,2.1.1 生成直線(xiàn)的DDA算法,三、直線(xiàn)DDA算法實(shí)現(xiàn)： 1、已知直線(xiàn)的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)2、已知畫(huà)線(xiàn)的顏色：colo

7、r3、計(jì)算兩個(gè)方向的變化量：dx=x2x1 dy=y2y14、求出兩個(gè)方向最大變化量的絕對(duì)值： steps=max(|dx|，|dy|),2020/11/20,15,2.1.1 生成直線(xiàn)的DDA算法,5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)： xin=dx/steps yin=dy/steps6、設(shè)置初始象素坐標(biāo)：x=x1,y=y17、用循環(huán)實(shí)現(xiàn)直線(xiàn)的繪制：for(i=1；i=steps；i+) putpixel(x，y，color)；/*在(x，y)處，以color色畫(huà)點(diǎn)*/x=x+xin； y=y+yin；,2020/11/20,16,2.1.1 生成直線(xiàn)的DDA算法,四、直線(xiàn)DDA算法特

8、點(diǎn)： 該算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線(xiàn)的速度較慢。 五、直線(xiàn)DDA算法程序： 下面給出考慮不同斜率、不同方向直線(xiàn)的DDA畫(huà)線(xiàn)算法程序：,2020/11/20,17,2.1.1 生成直線(xiàn)的DDA算法,void DDAline(int x0,int y0,int x1,int y1,int color) int x; float dx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x=x1;x+)putpixel(x，int(y+0.5)，color); /在(x，y)處，以color色畫(huà)點(diǎn)y=y+k;,202

9、0/11/20,18,2.1.2 生成直線(xiàn)的Bresenham算法,從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實(shí)型數(shù)據(jù)的加減運(yùn)算，因此直線(xiàn)的生成速度較慢。 在生成直線(xiàn)的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來(lái)生成直線(xiàn)的方法。 一、直線(xiàn)Bresenham算法描述： 它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個(gè)象素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來(lái)決定是否也要步進(jìn)一個(gè)象素。,2020/11/20,19,2.1.2 生成直線(xiàn)的Bresenham算法,我們首先討論m=y/x，當(dāng)0m1且x1x2時(shí)的Bresenham算法

10、。從DDA直線(xiàn)算法可知這些條件成立時(shí)，公式(2-2)、(2-3)可寫(xiě)成： xi+1=xi+1 (26) yi+1=yi+m (27) 有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。,2020/11/20,20,2.1.2 生成直線(xiàn)的Bresenham算法,二、直線(xiàn)Bresenham算法思想之一 由于顯示直線(xiàn)的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線(xiàn)上第i個(gè)象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線(xiàn)上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)m1），如下圖所示。那么，直線(xiàn)上下一個(gè)象素點(diǎn)的可能位置是(xi+1，yi)或(xi+1，yi

11、+1)。,2020/11/20,21,2.1.2 生成直線(xiàn)的Bresenham算法,2020/11/20,22,2.1.2 生成直線(xiàn)的Bresenham算法,由圖中可以知道，在x=xi+1處，直線(xiàn)上點(diǎn)的y值是y=m(xi+1)+b，該點(diǎn)離象素點(diǎn)(xi+1，yi)和象素點(diǎn)(xi+1，yi+1)的距離分別是d1和d2： d1=y-yi=m(xi+1)+b-yi (28) d2=(yi+1)-y=(yi+1)-m(xi+1)-b (29) 這兩個(gè)距離差是 d1-d2=2m(xi+1)-2yi2b-1 (210),2020/11/20,23,2.1.2 生成直線(xiàn)的Bresenham算法,我們來(lái)分析公式

12、(2-10)：(1)當(dāng)此值為正時(shí)，d1d2，說(shuō)明直線(xiàn)上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi+1)。(2)當(dāng)此值為負(fù)時(shí)，d1d2，說(shuō)明直線(xiàn)上理論點(diǎn)離(xi+1，yi)象素較近，則下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi)。(3)當(dāng)此值為零時(shí)，說(shuō)明直線(xiàn)上理論點(diǎn)離上、下兩個(gè)象素點(diǎn)的距離相等，取哪個(gè)點(diǎn)都行，假設(shè)算法規(guī)定這種情況下取(xi+1，yi+1)作為下一個(gè)象素點(diǎn)。,2020/11/20,24,2.1.2 生成直線(xiàn)的Bresenham算法,因此只要利用(d1-d2)的符號(hào)就可以決定下一個(gè)象素點(diǎn)的選擇。為此，我們進(jìn)一步定義一個(gè)新的判別式： pi=x(d1-d2)=2yxi

13、-2xyi+c (211)式(2-11)中的x=(x2-x1)0，因此pi與(d1-d2)有相同的符號(hào)； 這里y=y2-y1，m=y/x；c=2y+x(2b-1)。 下面對(duì)式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。,2020/11/20,25,2.1.2 生成直線(xiàn)的Bresenham算法,將式(2-11)中的下標(biāo)i改寫(xiě)成i+1，得到： pi+1=2yxi+1-2xyi+1+c (212)將式(2-12)減去(2-11)，并利用xi+1=xi+1，可得： pi+1= pi+2y-2x(yi+1-yi) (213) 再假設(shè)直線(xiàn)的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo)，即滿(mǎn)足： y1=

14、mx1+b (214),2020/11/20,26,2.1.2 生成直線(xiàn)的Bresenham算法,由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x (215) 這樣，我們可利用誤差判別變量，得到如下算法表示： 初始 p1=2y-x (216) 當(dāng)pi0時(shí)： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x) 否則：yi+1=yi,xi+1=xi+1， pi+1=pi+2y,2020/11/20,27,2.1.2 生成直線(xiàn)的Bresenham算法,從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線(xiàn)的兩個(gè)端點(diǎn)坐標(biāo)分量差x和y有關(guān)

15、，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而乘2可利用算術(shù)左移一位來(lái)完成，因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。 三、直線(xiàn)Bresenham算法思想之二 由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取象素點(diǎn)(xi，yir)間會(huì)引起誤差(i)，當(dāng)xi列上已用象素坐標(biāo)(xi，yir)表示直線(xiàn)上的點(diǎn)(xi，yi)，下一直線(xiàn)點(diǎn)B(xi+1，yi+1)，是取象素點(diǎn)C(xi+1，yir )，還是D(xi1，y(i+1)r)呢？,2020/11/20,28,2.1.2 生成直線(xiàn)的Bresenham算法,設(shè)A為CD邊的中點(diǎn)，正確的選擇： 若B點(diǎn)在A(yíng)點(diǎn)上方，選擇D點(diǎn)； 否則，選C點(diǎn)。 用誤差式描述為： (xi+1)=BC

16、-AC=(yi+1-yir)-0.5 (28),2020/11/20,29,2.1.2 生成直線(xiàn)的Bresenham算法,求遞推公式： (xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-y(i+1)r-0.5 (29) 當(dāng)(xi+1)0時(shí)，選D點(diǎn)，y(i+1)r = yir+1 (xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1 (210) 當(dāng)(xi+1)0時(shí)，選C點(diǎn)，y(i+1)r = yir (xi+2)= yi+1+myir-0.5=(xi+1)+m (211),2020/11/20,30,2.1.2 生成直線(xiàn)的Bresenham算法,初始時(shí)： (

17、xs+1)=BC-AC=m-0.5 (212),2020/11/20,31,2.1.2 生成直線(xiàn)的Bresenham算法,為了運(yùn)算中不含實(shí)型數(shù)，同時(shí)不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。 令方程兩邊同乘2x，即p=2x，則： 初始時(shí)： p = 2y-x (213)遞推式： 當(dāng)p0時(shí)： p=p+2(yx)；y+；x+；否則： p=p+2y；x+； (214),2020/11/20,32,2.1.2 生成直線(xiàn)的Bresenham算法,四、直線(xiàn)Bresenham算法實(shí)現(xiàn) 條件：0m1且x1x2 1、輸入線(xiàn)段的兩個(gè)端點(diǎn)坐標(biāo)和畫(huà)線(xiàn)顏色：x1，y1，x2，y2，color；2、設(shè)置象素坐標(biāo)初值：x=

18、x1，y=y1；3、設(shè)置初始誤差判別值：p=2y-x；4、分別計(jì)算：x=x2-x1、y=y2-y1；,2020/11/20,33,2.1.2 生成直線(xiàn)的Bresenham算法,5、循環(huán)實(shí)現(xiàn)直線(xiàn)的生成：for(x=x1；x=0) y=y+1；p=p+2(y-x)；else p=p+2y； ,2020/11/20,34,2.1.2 生成直線(xiàn)的Bresenham算法,五、直線(xiàn)Bresenham算法完善 現(xiàn)在我們修正(2-16)公式，以適應(yīng)對(duì)任何方向及任何斜率線(xiàn)段的繪制。如下圖所示，線(xiàn)段的方向可分為八種，從原點(diǎn)出發(fā)射向八個(gè)區(qū)。由線(xiàn)段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。 容易證明：當(dāng)

19、線(xiàn)段處于、區(qū)時(shí)，以|x|和|y|代替前面公式中的x和y，當(dāng)線(xiàn)段處于、區(qū)時(shí)，將公式中的|x|和|y|對(duì)換，則上述兩公式仍有效。,2020/11/20,35,2.1.2 生成直線(xiàn)的Bresenham算法,在線(xiàn)段起點(diǎn)區(qū)分線(xiàn)段方向,2020/11/20,36,2.1.2 生成直線(xiàn)的Bresenham算法,七、直線(xiàn)Bresenham算法特點(diǎn) 由于程序中不含實(shí)型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫(huà)線(xiàn)算法。 八、直線(xiàn)Bresenham算法程序 void Bresenhamline (int x1,int y1,int x2,int y2,int color)int x, y, dx, dy, s1,

20、s2, p, temp, interchange, i;x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);if(x2x1)s1=1;elses1=-1;,2020/11/20,37,2.1.2 生成直線(xiàn)的Bresenham算法,if(y2y1)s2=1;elses2=-1;if(dydx)temp=dx;dx=dy;dy=temp;interchange=1;elseinterchange=0;p=2*dy-dx;,2020/11/20,38,2.1.2 生成直線(xiàn)的Bresenham算法,for(i=1;i=0)if(interchange= =0)y=y+s2;el

21、sex=x+s1;p=p-2*dx;if(interchange= =0)x=x+s1; elsey=y+s2;p=p+2*dy;,2020/11/20,39,2.1 直線(xiàn)的生成習(xí)題,1.DDA法生成直線(xiàn)的基本原理是什么？,2020/11/20,40,2.2 圓的生成,這里僅討論圓心位于坐標(biāo)原點(diǎn)的圓的掃描轉(zhuǎn)換算法，對(duì)于圓心不在原點(diǎn)的圓，可先用平移變換，將它的圓心平移到原點(diǎn)，然后進(jìn)行掃描轉(zhuǎn)換，最后再平移到原來(lái)的位置。 有幾種較容易的方法可以得到圓的掃描轉(zhuǎn)換，但是效率都不高。例如：直角坐標(biāo)法和極坐標(biāo)法： 1、直角坐標(biāo)法 圓的直角坐標(biāo)方程為 x2+y2=R2若取x作為自變量，解出y，得到,2020/

22、11/20,41,2.2 圓的生成,(217) 我們可以先掃描轉(zhuǎn)換四分之一的圓周。讓自變量x從0到R以單位步長(zhǎng)增加，在每一步時(shí)可解出y，然后調(diào)用畫(huà)點(diǎn)函數(shù)即可逐點(diǎn)畫(huà)出圓。但這樣做，由于有乘方和平方根運(yùn)算，并且都是浮點(diǎn)運(yùn)算，算法效率不高。而且當(dāng)x接近R值時(shí)(圓心在原點(diǎn))，在圓周上的點(diǎn)（R，0）附近，由于圓的斜率趨于無(wú)窮大，使得圓周上有較大的間隙。,2020/11/20,42,2.2 圓的生成,2、極坐標(biāo)法 假設(shè)圓周上一點(diǎn)P（x，y）處的半徑與x軸的夾角為，則圓的極坐標(biāo)方程為 x=Rcos (218) y=Rsin 利用下面將要介紹的圓周上點(diǎn)的對(duì)稱(chēng)性，那么自變量的取值范圍就是(0，45)。這個(gè)方法涉

23、及三角函數(shù)計(jì)算和乘法運(yùn)算，計(jì)算量較大。因此，也不是一種有效的方法。,2020/11/20,43,2.2.1 圓的八分對(duì)稱(chēng)性,圓心位于原點(diǎn)的圓有四條對(duì)稱(chēng)軸x=0、y=0、x=y和x=y，見(jiàn)下圖。從而若已知圓弧上一點(diǎn)P(x，y)，就可以得到其關(guān)于四條對(duì)稱(chēng)軸的七個(gè)對(duì)稱(chēng)點(diǎn)，這種性質(zhì)稱(chēng)為八分對(duì)稱(chēng)性。因此只要能畫(huà)出八分之一的圓弧，就可以利用對(duì)稱(chēng)性的原理得到整個(gè)圓弧。下面的函數(shù)CirclePoints()用來(lái)顯示P(x，y)及其七個(gè)對(duì)稱(chēng)點(diǎn)。,2020/11/20,44,2.2.1 圓的八分對(duì)稱(chēng)性,void CirclePoints(x,y,color)int x,y,color;putpixel(x,y,c

24、olor);putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);,2020/11/20,45,2.2.1 圓的八分對(duì)稱(chēng)性,圓的八分對(duì)稱(chēng)性 注意： 當(dāng)圓心不在原點(diǎn)時(shí)，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標(biāo)）即可。,2020/11/20,46,2.2.1 圓的八分對(duì)稱(chēng)性,例如 當(dāng) x0=300，y0=200時(shí)，則： putpixel(x0+x，y0+

25、y，color)；putpixel(x0+x，y0-y，color)；putpixel(x0-x，y0+y，color)；putpixel(x0-x，y0-y，color)；putpixel(x0+y，y0+x，color)；putpixel(x0+y，y0-x，color)；putpixel(x0-y，y0+x，color)；putpixel(x0-y，y0-x，color)；,2020/11/20,47,2.2.2 中點(diǎn)算法生成圓,中點(diǎn)畫(huà)圓算法在一個(gè)方向上取單位間隔，在另一個(gè)方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號(hào)來(lái)確定象素點(diǎn)的選擇，因此算法效率較高。 一

26、、中點(diǎn)畫(huà)圓算法描述 設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在( , )處，順時(shí)針生成八分之一圓，利用對(duì)稱(chēng)性?huà)呙柁D(zhuǎn)換全部圓。 為了應(yīng)用中點(diǎn)畫(huà)圓法，我們定義一個(gè)圓函數(shù) F(x，y)=x2+y2-R2 (219),2020/11/20,48,2.2.2 中點(diǎn)算法生成圓,任何點(diǎn)(x，y)的相對(duì)位置可由圓函數(shù)的符號(hào)來(lái)檢測(cè)： 0點(diǎn)(x，y)位于數(shù)學(xué)圓外,2020/11/20,49,2.2.2 中點(diǎn)算法生成圓,如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時(shí)針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)

27、兩者之一。 中點(diǎn)畫(huà)線(xiàn)算法,2020/11/20,50,2.2.2 中點(diǎn)算法生成圓,假設(shè)M是E和SE的中點(diǎn)，則： 1、當(dāng)F(M)0時(shí)，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；3、當(dāng)F(M)=0時(shí)，在E點(diǎn)與SE點(diǎn)之中隨便取一個(gè)即可，我們約定取SE點(diǎn)。,2020/11/20,51,2.2.2 中點(diǎn)算法生成圓,二、中點(diǎn)畫(huà)圓算法思想 因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時(shí)用增量法來(lái)迭代計(jì)算下一個(gè)中點(diǎn)M的決策變量di+1。 (221) 下面分兩種情況來(lái)討論在迭代計(jì)算中決策變量di+1的推導(dǎo)。 1、見(jiàn)圖（a），若di0，則選擇E點(diǎn)，接著下一個(gè)中點(diǎn)就是 ，這時(shí)新的決策變量為： (222)

28、,2020/11/20,52,2.2.2 中點(diǎn)算法生成圓,（a）(di0) 中點(diǎn)畫(huà)線(xiàn)算法,2020/11/20,53,2.2.2 中點(diǎn)算法生成圓,式(222)減去(221)得： di+1=di+2xi+3 (223) 2、見(jiàn)圖（b），若di0，則選擇SE點(diǎn)，接著下一個(gè)中點(diǎn)就是 ，這時(shí)新的決策變量為： (224),2020/11/20,54,2.2.2 中點(diǎn)算法生成圓,（b）(di0) 中點(diǎn)畫(huà)線(xiàn)算法 式(224)減去(221)得： di+1=di+2(xi-yi)+5 (225),2020/11/20,55,2.2.2 中點(diǎn)算法生成圓,我們利用遞推迭代計(jì)算這八分之一圓弧上的每個(gè)點(diǎn)，每次迭代需要兩

29、步處理：（1）用前一次迭代算出的決策變量的符號(hào)來(lái)決定本次選擇的點(diǎn)。（2）對(duì)本次選擇的點(diǎn)，重新遞推計(jì)算得出新的決策變量的值。 剩下的問(wèn)題是計(jì)算初始決策變量d0，如下圖所示。對(duì)于初始點(diǎn)(0，R)，順時(shí)針生成八分之一圓，下一個(gè)中點(diǎn)M的坐標(biāo)是 ，所以：,2020/11/20,56,2.2.2 中點(diǎn)算法生成圓,(226） 生成圓的初始條件和圓的生成方向,2020/11/20,57,2.2.2 中點(diǎn)算法生成圓,三、中點(diǎn)畫(huà)圓算法實(shí)現(xiàn) 1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分對(duì)稱(chēng)性，用規(guī)定的顏色color畫(huà)八個(gè)象素點(diǎn)(x，y)； 若

30、d0y=y-1；d=d+2(x-y)+5；否則d=d+2x+3；x=x+1；,2020/11/20,58,2.2.2 中點(diǎn)算法生成圓,四、中點(diǎn)畫(huà)圓算法完善 在上述算法中，使用了浮點(diǎn)數(shù)來(lái)表示決策變量d。為了簡(jiǎn)化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d0=5/4-r對(duì)應(yīng)于e0=1-r。決策變量d0對(duì)應(yīng)于e-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過(guò)程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e-1/4等價(jià)于e0。因此，可以寫(xiě)出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫(huà)圓算法。要求：寫(xiě)出用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫(huà)圓算法程序，并上機(jī)調(diào)試，觀(guān)看運(yùn)行結(jié)果

31、。,2020/11/20,59,2.2.2 中點(diǎn)算法生成圓,五、中點(diǎn)畫(huà)圓算法程序 void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;,2020/11/20,60,2.2.2 中點(diǎn)算法生成圓,while(x=y)putdot(x0,y0,x,y,color);if(d0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;,2020/11/20,61,2.2.2 中點(diǎn)算法生成圓,putdot(x0,y0,x,y,color)putpixel(x0+x,y0+

32、y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,color);putpixel(x0-y,y0+x,color);putpixel(x0-y,y0-x,color);,2020/11/20,62,2.2.3 正負(fù)算法生成圓,正負(fù)法是利用平面曲線(xiàn)將平面劃分成正負(fù)區(qū)域，對(duì)當(dāng)前點(diǎn)產(chǎn)生的圓函數(shù)進(jìn)行符號(hào)判別，利用負(fù)反饋調(diào)整以決定下一個(gè)點(diǎn)的產(chǎn)生來(lái)直接生成圓弧。 一、正負(fù)畫(huà)圓算法描述 設(shè)要顯示圓

33、的圓心在原點(diǎn)(0，0)，半徑為R，初始點(diǎn)的坐標(biāo)為(0，R)，順時(shí)針生成八分之一圓，令：F(x，y)=x2+y2-R2 則圓的方程為： F(x，y)=0 (2-27) 當(dāng)點(diǎn)(x，y)在圓內(nèi)時(shí)，則F(x，y)0；當(dāng)點(diǎn)(x，y)在圓上時(shí)，則F(x，y)=0；,2020/11/20,63,2.2.3 正負(fù)算法生成圓,二、正負(fù)畫(huà)圓算法思想 現(xiàn)以下圖的AB弧為例，來(lái)說(shuō)明正負(fù)畫(huà)圓法(順時(shí)針生成圓)。,2020/11/20,64,2.2.3 正負(fù)算法生成圓,假設(shè)當(dāng)前點(diǎn)為Pi(xi，yi)，取下一個(gè)點(diǎn)Pi+1(xi+1，yi+1)的原則是： 1、當(dāng)F(xi，yi)0時(shí)：取xi+1= xi+1，yi+1= yi。

34、即向右走一步，從圓內(nèi)走向圓外。對(duì)應(yīng)圖(a)中的從Pi到Pi+1。2、當(dāng)F(xi，yi)0時(shí)：取xi+1= xi，yi+1= yi-1。即向下走一步，從圓外走向圓內(nèi)。對(duì)應(yīng)圖(b)中的從Pi到Pi+1。 由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負(fù)，因此稱(chēng)為正負(fù)法。 下面分兩種情況求出F(xi，yi)的遞推公式：,2020/11/20,65,2.2.3 正負(fù)算法生成圓,(1) 當(dāng)F(xi，yi)0時(shí)，向右走，取xi+1=xi+1，yi+1=yi，則 F(xi+1，yi+1)=F(xi+1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1

35、 (2-28),2020/11/20,66,2.2.3 正負(fù)算法生成圓,(2) 當(dāng)F(xi，yi)0時(shí)，向下走，取xi+1=xi，yi+1=yi-1，則 F(xi+1，yi+1)=F(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1 (2-29),2020/11/20,67,2.2.3 正負(fù)算法生成圓,初始時(shí)，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(2-30)就構(gòu)成正負(fù)畫(huà)圓算法的核心。 給象素坐標(biāo)(x，y)及F賦初始值后，進(jìn)入循環(huán)畫(huà)點(diǎn)； 畫(huà)點(diǎn)后，根據(jù)F的符號(hào)進(jìn)

36、行F值的遞推和下一個(gè)點(diǎn)的獲取，直到xy為止。 同前面介紹的一樣，利用圓的八分對(duì)稱(chēng)性，循環(huán)一次，畫(huà)八個(gè)點(diǎn)。,2020/11/20,68,2.2.3 正負(fù)算法生成圓,三、正負(fù)畫(huà)圓算法實(shí)現(xiàn) 注意：初值不同、圓的生成方向不同時(shí)，當(dāng)前點(diǎn)和下一個(gè)點(diǎn)的獲取原則是不同的，見(jiàn)下圖。 例如，初始點(diǎn)(R，0)，逆時(shí)針生成圓，從圖（b）可知： 若當(dāng)前點(diǎn)Pi在圓內(nèi)，則下一點(diǎn)Pi+1(xi，yi+1)，即向上走一步；若當(dāng)前點(diǎn)Pi在圓外，則下一點(diǎn)Pi+1(xi-1，yi)，即向左走一步；,2020/11/20,69,2.2.3 正負(fù)算法生成圓,(a) 順時(shí)針生成圓(b) 逆時(shí)針生成圓,2020/11/20,70,2.2.3

37、 正負(fù)算法生成圓,四、正負(fù)畫(huà)圓算法特點(diǎn) 物理意義清楚，程序中只含整數(shù)運(yùn)算，因此算法速度快。 五、正負(fù)畫(huà)圓算法程序 / 順時(shí)針生成圓void PNARC(int x0,int y0,int r,int color)int x=0,y=r,f=0;,2020/11/20,71,2.2.3 正負(fù)算法生成圓,while(x=y)putdot(x0,y0,x,y,color);if(f=0)f=f+2*x+1;x+;elsef=f-2*y+1;y-;,2020/11/20,72,2.2 圓的生成習(xí)題,1. 用自己的語(yǔ)言描述中點(diǎn)畫(huà)圓算法。,2020/11/20,73,2.3 區(qū)域填充,前面介紹的直線(xiàn)和圓都

38、屬于線(xiàn)劃圖，然而，光柵顯示的一個(gè)重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。 區(qū)域填充一般分兩類(lèi)：多邊形填充和種子填充。 一、多邊形填充 1、填充條件 多邊形的頂點(diǎn)序列(Pi，i=0，1，n)、填充色。 2、多邊形內(nèi)點(diǎn)的判別準(zhǔn)則 對(duì)多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。在順序給定多邊形頂點(diǎn)坐標(biāo)的情況下，如何判明一個(gè)象素點(diǎn)是處于多邊形的內(nèi)部還是外部呢？,2020/11/20,74,2.3 區(qū)域填充,從測(cè)試點(diǎn)引出一條伸向無(wú)窮遠(yuǎn)處的射線(xiàn)(假設(shè)是水平向右的射線(xiàn))，因?yàn)槎噙呅问情]合的，那么： 若射線(xiàn)與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，則該點(diǎn)為內(nèi)點(diǎn)(例：圖中測(cè)試點(diǎn)4引出的射線(xiàn))

39、；反之，交點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，則該點(diǎn)為外點(diǎn)。(例：測(cè)試點(diǎn)2引出的射線(xiàn))。,2020/11/20,75,2.3 區(qū)域填充,多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn),2020/11/20,76,2.3 區(qū)域填充,3、奇異點(diǎn)的處理 上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線(xiàn)正好通過(guò)多邊形頂點(diǎn)時(shí)，要特別注意。例如，圖中過(guò)頂點(diǎn)的射線(xiàn)1、射線(xiàn)6，它們與多邊形的交點(diǎn)個(gè)數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實(shí)際上卻是外點(diǎn)。 而圖中過(guò)頂點(diǎn)的射線(xiàn)3、射線(xiàn)5，對(duì)于判別準(zhǔn)則的使用又是正確的。,2020/11/20,77,2.3 區(qū)域填充,綜合以上情況，我們將多邊形的頂點(diǎn)分為兩大類(lèi)： (1) 局部極值點(diǎn)：如圖中的點(diǎn)P1、

40、P2、P4和P6。對(duì)于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線(xiàn)和離開(kāi)該點(diǎn)的邊線(xiàn)位于過(guò)該點(diǎn)掃描線(xiàn)的同一側(cè)。(2)非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對(duì)于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線(xiàn)和離開(kāi)該點(diǎn)的邊線(xiàn)位于過(guò)該點(diǎn)掃描線(xiàn)的兩側(cè)。 處理奇異點(diǎn)規(guī)則： （1）對(duì)于局部極值點(diǎn)，應(yīng)看成兩個(gè)點(diǎn)； （2）對(duì)于非極值點(diǎn)，應(yīng)看成一個(gè)點(diǎn)。,2020/11/20,78,2.3 區(qū)域填充,4、逐點(diǎn)判別算法步驟： (1)求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。 (2)對(duì)包圍盒中的每個(gè)象素引水平射線(xiàn)進(jìn)行測(cè)試。 (3)求出該射線(xiàn)與多邊形每條邊的有效交點(diǎn)個(gè)數(shù)。 (4)如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。

41、(5)否則：該點(diǎn)置為背景色。 逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問(wèn)題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。,2020/11/20,79,2.3 區(qū)域填充,二、種子填充 種子填充是將區(qū)域內(nèi)的一點(diǎn)(種子)賦予給定的顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過(guò)程。 1、填充條件 區(qū)域內(nèi)一點(diǎn)的坐標(biāo)即種子坐標(biāo)、邊界色、填充色。 2、連通方式 區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。,2020/11/20,80,2.3 區(qū)域填充,四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向：上、下、左、右到達(dá)該區(qū)域內(nèi)部

42、的任意象素。 八連通：區(qū)域內(nèi)部從一個(gè)象素到達(dá)另一個(gè)象素的移動(dòng)路徑，除了上、下、左、右四個(gè)方向外，還允許沿著對(duì)角線(xiàn)方向。,2020/11/20,81,2.3 區(qū)域填充,注意： （1） 八連通區(qū)域中，既然區(qū)域內(nèi)的兩個(gè)象素可以通過(guò)對(duì)角線(xiàn)相通，那么，區(qū)域邊界上的象素則不能通過(guò)對(duì)角線(xiàn)相連，否則填充就會(huì)溢出到區(qū)域外，因此，八連通區(qū)域的邊界線(xiàn)必須是四連通的，見(jiàn)下圖(a)； （2）而四連通區(qū)域，其邊界象素是四連通和八連通的都可以，見(jiàn)下圖(b)。,2020/11/20,82,2.3 區(qū)域填充,(a) 八連通區(qū)域四連通邊界(b) 四連通區(qū)域八連通(或四連通)邊界,2020/11/20,83,2.3 區(qū)域填充,3、

43、內(nèi)點(diǎn)(x,y)的檢測(cè)條件 (1) if(getpixel(x,y)!=邊界色 y= ymax;y+) 合并當(dāng)前掃描線(xiàn)y的ET表； 將y桶中每個(gè)記錄按x項(xiàng)升序排列； 在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)行填充； 刪除y=ymax的邊記錄； 修改邊記錄x=x+1/m； ,2020/11/20,96,2.3.1 邊相關(guān)掃描線(xiàn)多邊形填充算法,五、邊相關(guān)掃描線(xiàn)填充算法特點(diǎn) 該算法充分利用多邊形的邊相關(guān)性和掃描線(xiàn)的相關(guān)性，使用ET表對(duì)多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來(lái)支持填充，大大地減少了求交點(diǎn)的計(jì)算量，有效地提高了填充速度。,2020/11/20,97,2.3.2 掃描線(xiàn)種子填充算

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

45、如果種子象素尚未填充，則： a.求出種子區(qū)段：xleft、xright; b.填充整個(gè)區(qū)段。,2020/11/20,99,2.3.2 掃描線(xiàn)種子填充算法,c.檢查相鄰的上掃描線(xiàn)的xleftxxright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話(huà)，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。 d.檢查相鄰的下掃描線(xiàn)的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話(huà)，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。 ,2020/11/20,100,2.3.2 掃描線(xiàn)種子填充算法,四

46、、掃描線(xiàn)種子填充算法特點(diǎn) 1、該算法考慮了掃描線(xiàn)上象素的相關(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í)施快速填充。,2020/11/20,101,2.3.3 邊標(biāo)志填充算法,在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個(gè)閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線(xiàn)逐行對(duì)多邊形求交，在交點(diǎn)對(duì)之間填充。邊標(biāo)志填充算法就是在逐

47、行處理時(shí)，利用邊界色作為標(biāo)志來(lái)進(jìn)行填充的。例如某掃描線(xiàn)從左到右掃描時(shí)碰到邊界色，立刻改變標(biāo)志的狀態(tài)，接下來(lái)再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。,2020/11/20,102,2.3.3 邊標(biāo)志填充算法,一、邊標(biāo)志填充算法思想 掃描線(xiàn)具有連貫性，這種連貫性只有在掃描線(xiàn)與多邊形相交處才會(huì)發(fā)生變化，而每次的變化結(jié)果：無(wú)非是在前景色和背景色之間相互“切換”。 邊標(biāo)志填充算法正是基于這一發(fā)現(xiàn)，先在屏幕上生成多邊形輪廓線(xiàn)，然后逐條掃描處理。處理中：逐點(diǎn)讀取象素值，若為邊界色，則對(duì)該象素值進(jìn)行顏色切換。,2020/11/20,103,2.3.3 邊標(biāo)志填充算法,二、邊標(biāo)志填充算法實(shí)現(xiàn) 1、用邊界色畫(huà)出多邊

48、形輪廓線(xiàn)，也就是將多邊形邊界所經(jīng)過(guò)的象素打上邊標(biāo)志。 2、為了縮小范圍，加快填充速度，須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。如下圖所示。,2020/11/20,104,2.3.3 邊標(biāo)志填充算法,邊標(biāo)志填充算法 3、逐條掃描線(xiàn)進(jìn)行處理，對(duì)每條掃描線(xiàn)依從左往右的順序，逐個(gè)訪(fǎng)問(wèn)該掃描線(xiàn)上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。,2020/11/20,105,2.3.3 邊標(biāo)志填充算法,三、邊標(biāo)志填充算法特點(diǎn) 該算法思想簡(jiǎn)單，實(shí)現(xiàn)容易。既不需要求交點(diǎn)、交點(diǎn)排序、邊的登記，也不需要使用鏈表、堆棧等數(shù)據(jù)結(jié)構(gòu)。 四、邊標(biāo)志填充算法程序 E

49、dgeMarkFill(int p2,int n,int boundarycolor,int newcolor),2020/11/20,106,2.3.3 邊標(biāo)志填充算法,int i, x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*設(shè)置畫(huà)筆色*/ for(i=0 ;in;i+) line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*畫(huà)出多邊形的n條邊*/用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;,2020/11/20,107,2.3.3 邊標(biāo)志填充算法,for(y=y

50、min;y=ymax;y+) flag=-1; for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor) flag=(-1) *flag;if(flag=1)putpixel(x,y, newcolor); ,2020/11/20,108,2.3.3 邊標(biāo)志填充算法,五、邊標(biāo)志填充算法錯(cuò)誤處理 1、該算法雖然簡(jiǎn)單，但程序運(yùn)行后會(huì)出現(xiàn)局部錯(cuò)誤。從下圖可以發(fā)現(xiàn)，對(duì)于多邊形頂點(diǎn)為局部極值點(diǎn)時(shí)，掃描線(xiàn)與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時(shí)會(huì)出現(xiàn)“抽絲”現(xiàn)象。即某掃描線(xiàn)上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒(méi)有填上色。解決的辦法：判斷多邊形頂

51、點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線(xiàn)碰上它則不改變標(biāo)志。,2020/11/20,109,2.3.3 邊標(biāo)志填充算法,2、特別當(dāng)心多邊形邊界的掃描轉(zhuǎn)換。在這里就不能考慮：不同的斜率產(chǎn)生的直線(xiàn)要亮度均勻，如下圖(a)所示。否則當(dāng)掃描線(xiàn)y遇到斜率小于1的邊界線(xiàn)時(shí)，碰到幾個(gè)邊界點(diǎn)，會(huì)引起標(biāo)志的無(wú)序改變，將導(dǎo)致填充的錯(cuò)誤。 解決的辦法：對(duì)于不同斜率的邊界，都要使用斜率大于1的直線(xiàn)掃描轉(zhuǎn)換方法：每次y方向增長(zhǎng)一步，x方向增長(zhǎng)1/m步距，以保證掃描線(xiàn)y遇到斜率小于1的邊界時(shí)，只能遇到一個(gè)點(diǎn)。請(qǐng)看下圖(b)。,2020/11/20,110,2.3.3 邊標(biāo)志填充算法,在邊標(biāo)志填充算法中要注意多邊形邊界的掃描

52、轉(zhuǎn)換,2020/11/20,111,2.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ù)圖案該位置的象素值，決定填充顏色。,2020/11/20,112,2.3.4 圖案填充,一、圖案填充方式： 1、透明方式:若是以透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)象素，否則，不改變?cè)撓笏氐闹怠?2、不透明方式: 而若是以不透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置

53、為1時(shí)，用前景色寫(xiě)象素，否則，用背景色寫(xiě)象素。,2020/11/20,113,2.3.4 圖案填充,二、圖案定位法： 1、相對(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ì)齊。,2020/11/20,114,2.3.4 圖案填充,2、絕對(duì)定位法：把圖案原點(diǎn)與屏幕原點(diǎn)對(duì)齊。該方法可以將整個(gè)屏幕看成被要填充的圖案布滿(mǎn)，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來(lái)，其它區(qū)域?qū)Υ藞D案卻是不透明的，圖案被全部擋住。 這種

54、方法比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無(wú)縫連接的效果。但它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其效果是區(qū)域內(nèi)的圖案變了。,2020/11/20,115,2.3.4 圖案填充,三、圖案填充算法實(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)算符,然后取出圖案位圖該位

55、置的象素進(jìn)行填充。,2020/11/20,116,2.3.4 圖案填充,四、圖案填充算法程序 / 采用不透明方式絕對(duì)定位法填充圖案的程序偽代碼: maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy;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, 1,1,1,1,1,1,1,1, 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,1;,2

56、020/11/20,117,2.3.4 圖案填充,xx=x%8; /*多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)x映射到圖案坐標(biāo)xx*/yy=y%8; /*多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)y到圖案坐標(biāo)yy*/if(maskcodeyyxx)putpixel(x,y, newcolor); /* newcolor 為前景色*/elseputpixel(x,y, backgroundcolor); /* backgroundcolor為背景色*/,2020/11/20,118,2.4.1 點(diǎn)陣字符,我們討論的字符是指字母、數(shù)字、漢字、標(biāo)點(diǎn)等符號(hào)。計(jì)算機(jī)中，字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)，對(duì)于一個(gè)字符來(lái)說(shuō)，它所對(duì)應(yīng)的編碼是由它所屬的字符集決

57、定。 1、ASCII碼 目前，國(guó)際上普遍采用的字符編碼是ASCII碼（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)位。,2020/11/20,119,2.4.1 點(diǎn)陣字符,2、國(guó)標(biāo)碼 我國(guó)除了采用ASCII碼外，還制定了漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集:中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)信息交換編碼，代號(hào)為“GB23

58、1280”。該字符集共收錄常用漢字6763個(gè)，圖形符號(hào)682個(gè)。 它規(guī)定所有漢字和圖形符號(hào)組成一個(gè)9494的矩陣，在此方陣中，每一行稱(chēng)為“區(qū)”，用區(qū)碼來(lái)標(biāo)識(shí)；每一列稱(chēng)為“位”，用位碼來(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é)。,2020/11/20,120,2.4.1 點(diǎn)陣字符,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)碼為：8080H+國(guó)標(biāo)碼 即：A0A0H+區(qū)位碼的十六進(jìn)制表示,2020/11/20,121,2.4.1 點(diǎn)陣字符,3、舉例“啊”字的區(qū)位碼為1601，轉(zhuǎn)換為十六進(jìn)制表示應(yīng)為1001H（區(qū)碼16轉(zhuǎn)為10H，位碼01轉(zhuǎn)為01H）。于是，“啊”