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

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

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

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

4、千上萬(wàn)條直線，所以要求繪制算 法應(yīng)該：1、最接近數(shù)學(xué)上的直線；2022-6-2592.1 直線的掃描轉(zhuǎn)換 2、沿著線段分布的象素應(yīng)均勻 不均勻的例子如下圖所示，對(duì)同樣長(zhǎng)的線段，如果進(jìn)行圖中的掃描轉(zhuǎn)換，就會(huì)因?yàn)樾甭实牟煌a(chǎn)生的象素個(gè)數(shù)不相等，這樣將導(dǎo)致象素亮度分布不均勻。3、畫線速度盡可能的快 2022-6-25102.1.1 生成直線的DDA算法 數(shù)值微分法即DDA法(Digital Differential Analyzer)，是一種基于直線的微分方程來(lái)生成直線的方法 一、直線DDA算法描述： 設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得 = m =直

5、線的斜率 (21) 2022-6-25112.1.1 生成直線的DDA算法 可通過(guò)計(jì)算由x方向的增量x引起y的改變來(lái)生成直線：xi+1=xi+x (22) yi+1=yi+y=yi+xm (23) 也可通過(guò)計(jì)算由y方向的增量y引起x的改變來(lái)生成直線：yi+1=yi+y (24) xi+1=xi+x=xi+y/m (25) 式(22)至(25)是遞推的。 2022-6-25122.1.1 生成直線的DDA算法 二、直線DDA算法思想： 選定x2x1和y2y1中較大者作為步進(jìn)方向(假設(shè)x2x1較大)，取該方向上的增量為一個(gè)象素單位(x=1)，然后利用式(21)計(jì)算另一個(gè)方向的增量(y=xm=m)。

6、通過(guò)遞推公式(22)至(25)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。 之所以取x2x1和y2y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。2022-6-25132.1.1 生成直線的DDA算法 另外，算法實(shí)現(xiàn)中還應(yīng)注意直線的生成方向，以決定x及y是取正值還是負(fù)值。 2022-6-25142.1.1 生成直線的DDA算法 三、直線DDA算法實(shí)現(xiàn)： 1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)2、已知畫線的顏色：color3、計(jì)算兩個(gè)方向的變化量：dx=x2x1 dy=y2y14、求出兩個(gè)方向最大變化量的絕對(duì)

7、值： steps=max(|dx|，|dy|)2022-6-25152.1.1 生成直線的DDA算法 5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)： xin=dx/steps yin=dy/steps6、設(shè)置初始象素坐標(biāo)：x=x1,y=y17、用循環(huán)實(shí)現(xiàn)直線的繪制：for(i=1；i=steps；i+) putpixel(x，y，color)；/*在(x，y)處，以color色畫點(diǎn)*/x=x+xin； y=y+yin； 2022-6-25162.1.1 生成直線的DDA算法 四、直線DDA算法特點(diǎn)： 該算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線的速度較慢。五、直線DDA算法程

8、序： 下面給出考慮不同斜率、不同方向直線的DDA畫線算法程序： 2022-6-25172.1.1 生成直線的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色畫點(diǎn)y=y+k; 2022-6-25182.1.2 生成直線的Bresenham算法 從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實(shí)型

9、數(shù)據(jù)的加減運(yùn)算，因此直線的生成速度較慢。 在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來(lái)生成直線的方法。 一、直線Bresenham算法描述： 它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個(gè)象素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來(lái)決定是否也要步進(jìn)一個(gè)象素。2022-6-25192.1.2 生成直線的Bresenham算法 我們首先討論m=y/x，當(dāng)0m1且x1x2時(shí)的Bresenham算法。從DDA直線算法可知這些條件成立時(shí)，公式(2-2)、(2-3)可寫成： xi+1=xi+1 (26) yi+1=yi+m (2

10、7) 有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。2022-6-25202.1.2 生成直線的Bresenham算法 二、直線Bresenham算法思想之一 由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線上第i個(gè)象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)md2，說(shuō)明直線上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi+1)。(2)當(dāng)此值為負(fù)時(shí)，d10，因此pi與(d1-d2)有相同的符號(hào)； 這里y=y2-y1，m=y/x；c=2y+x(2b-1)。 下

11、面對(duì)式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。2022-6-25252.1.2 生成直線的Bresenham算法 將式(2-11)中的下標(biāo)i改寫成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è)直線的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo)，即滿足： y1=mx1+b (214)2022-6-25262.1.2 生成直線的Bresenham算法 由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x (215) 這樣，

12、我們可利用誤差判別變量，得到如下算法表示： 初始 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 2022-6-25272.1.2 生成直線的Bresenham算法 從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個(gè)端點(diǎn)坐標(biāo)分量差x和y有關(guān)，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而乘2可利用算術(shù)左移一位來(lái)完成，因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。 三、直線Bresenham算法思想之二 由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取

13、象素點(diǎn)(xi，yir)間會(huì)引起誤差(i)，當(dāng)xi列上已用象素坐標(biāo)(xi，yir)表示直線上的點(diǎn)(xi，yi)，下一直線點(diǎn)B(xi+1，yi+1)，是取象素點(diǎn)C(xi+1，yir )，還是D(xi1，y(i+1)r)呢？2022-6-25282.1.2 生成直線的Bresenham算法 設(shè)A為CD邊的中點(diǎn)，正確的選擇： 若B點(diǎn)在A點(diǎn)上方，選擇D點(diǎn)； 否則，選C點(diǎn)。 用誤差式描述為： (xi+1)=BC-AC=(yi+1-yir)-0.5 (28)2022-6-25292.1.2 生成直線的Bresenham算法 求遞推公式： (xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-

14、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)2022-6-25302.1.2 生成直線的Bresenham算法 初始時(shí)： (xs+1)=BC-AC=m-0.5 (212)2022-6-25312.1.2 生成直線的Bresenham算法 為了運(yùn)算中不含實(shí)型數(shù)，同時(shí)不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。 令方程兩邊同乘2x，即p=2

15、x，則： 初始時(shí)： p = 2y-x (213)遞推式： 當(dāng)p0時(shí)： p=p+2(yx)；y+；x+；否則： p=p+2y；x+； (214)2022-6-25322.1.2 生成直線的Bresenham算法 四、直線Bresenham算法實(shí)現(xiàn) 條件：0m1且x1x2 1、輸入線段的兩個(gè)端點(diǎn)坐標(biāo)和畫線顏色：x1，y1，x2，y2，color；2、設(shè)置象素坐標(biāo)初值：x=x1，y=y1；3、設(shè)置初始誤差判別值：p=2y-x；4、分別計(jì)算：x=x2-x1、y=y2-y1；2022-6-25332.1.2 生成直線的Bresenham算法 5、循環(huán)實(shí)現(xiàn)直線的生成：for(x=x1；x=0) y=y+1

16、；p=p+2(y-x)；else p=p+2y； 2022-6-25342.1.2 生成直線的Bresenham算法 五、直線Bresenham算法完善 現(xiàn)在我們修正(2-16)公式，以適應(yīng)對(duì)任何方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點(diǎn)出發(fā)射向八個(gè)區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。 容易證明：當(dāng)線段處于、區(qū)時(shí)，以|x|和|y|代替前面公式中的x和y，當(dāng)線段處于、區(qū)時(shí)，將公式中的|x|和|y|對(duì)換，則上述兩公式仍有效。2022-6-25352.1.2 生成直線的Bresenham算法 在線段起點(diǎn)區(qū)分線段方向2022-6-25362.1.2

17、 生成直線的Bresenham算法 七、直線Bresenham算法特點(diǎn) 由于程序中不含實(shí)型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫線算法。八、直線Bresenham算法程序 void Bresenhamline (int x1,int y1,int x2,int y2,int color)int x, y, dx, dy, s1, s2, p, temp, interchange, i;x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);if(x2x1)s1=1;elses1=-1;2022-6-25372.1.2 生成直線的Bresenham算法 if(y2y1)s

18、2=1;elses2=-1;if(dydx)temp=dx;dx=dy;dy=temp;interchange=1;elseinterchange=0;p=2*dy-dx;2022-6-25382.1.2 生成直線的Bresenham算法 for(i=1;i=0)if(interchange= =0)y=y+s2;elsex=x+s1;p=p-2*dx;if(interchange= =0)x=x+s1; elsey=y+s2;p=p+2*dy; 2022-6-25392.1 直線的生成習(xí)題1.DDA法生成直線的基本原理是什么？2022-6-25402.2 圓的生成 這里僅討論圓心位于坐標(biāo)原點(diǎn)

19、的圓的掃描轉(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，得到 2022-6-25412.2 圓的生成 (217) 我們可以先掃描轉(zhuǎn)換四分之一的圓周。讓自變量x從0到R以單位步長(zhǎng)增加，在每一步時(shí)可解出y，然后調(diào)用畫點(diǎn)函數(shù)即可逐點(diǎn)畫出圓。但這樣做，由于有乘方和平方根運(yùn)算，并且都是浮點(diǎn)運(yùn)算，算法效率不高。而且當(dāng)x接近R值時(shí)(圓心在原點(diǎn))，在圓周上的點(diǎn)（R，0）附近，由于圓

20、的斜率趨于無(wú)窮大，使得圓周上有較大的間隙。2022-6-25422.2 圓的生成 2、極坐標(biāo)法 假設(shè)圓周上一點(diǎn)P（x，y）處的半徑與x軸的夾角為，則圓的極坐標(biāo)方程為 x=Rcos (218) y=Rsin 利用下面將要介紹的圓周上點(diǎn)的對(duì)稱性，那么自變量的取值范圍就是(0，45)。這個(gè)方法涉及三角函數(shù)計(jì)算和乘法運(yùn)算，計(jì)算量較大。因此，也不是一種有效的方法。2022-6-25432.2.1 圓的八分對(duì)稱性 圓心位于原點(diǎn)的圓有四條對(duì)稱軸x=0、y=0、x=y和x=y，見(jiàn)下圖。從而若已知圓弧上一點(diǎn)P(x，y)，就可以得到其關(guān)于四條對(duì)稱軸的七個(gè)對(duì)稱點(diǎn)，這種性質(zhì)稱為八分對(duì)稱性。因此只要能畫出八分之一的圓弧

21、，就可以利用對(duì)稱性的原理得到整個(gè)圓弧。下面的函數(shù)CirclePoints()用來(lái)顯示P(x，y)及其七個(gè)對(duì)稱點(diǎn)。 2022-6-25442.2.1 圓的八分對(duì)稱性 void CirclePoints(x,y,color)int x,y,color;putpixel(x,y,color);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); 2022-6-25452.2.

22、1 圓的八分對(duì)稱性 圓的八分對(duì)稱性 注意：注意： 當(dāng)圓心不在原點(diǎn)時(shí)，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標(biāo)）即可。2022-6-25462.2.1 圓的八分對(duì)稱性 例如 當(dāng) x0=300，y0=200時(shí)，則： putpixel(x0+x，y0+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)；p

23、utpixel(x0-y，y0-x，color)；2022-6-25472.2.2 中點(diǎn)算法生成圓 中點(diǎn)畫圓算法在一個(gè)方向上取單位間隔，在另一個(gè)方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號(hào)來(lái)確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓算法描述 設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在( , )處，順時(shí)針生成八分之一圓，利用對(duì)稱性掃描轉(zhuǎn)換全部圓。 為了應(yīng)用中點(diǎn)畫圓法，我們定義一個(gè)圓函數(shù) F(x，y)=x2+y2-R2 (219)2022-6-25482.2.2 中點(diǎn)算法生成圓 任何點(diǎn)(x，y)的相對(duì)位置可由圓函數(shù)的符號(hào)來(lái)檢測(cè)： 0點(diǎn)

24、(x，y)位于數(shù)學(xué)圓外 2022-6-25492.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)兩者之一。 中點(diǎn)畫線算法2022-6-25502.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)。 2022-6-25512.2.2 中點(diǎn)算法生成圓 二、中點(diǎn)畫圓算法思想 因此，我們用中點(diǎn)M的圓函數(shù)作為決

25、策變量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)2022-6-25522.2.2 中點(diǎn)算法生成圓 （a）(di0) 中點(diǎn)畫線算法2022-6-25532.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) 2022-6-25542.2.2 中點(diǎn)算法生成圓 （b）(di0) 中點(diǎn)

26、畫線算法 式(224)減去(221)得： di+1=di+2(xi-yi)+5 (225)2022-6-25552.2.2 中點(diǎn)算法生成圓 我們利用遞推迭代計(jì)算這八分之一圓弧上的每個(gè)點(diǎn)，每次迭代需要兩步處理：（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)是 ，所以：2022-6-25562.2.2 中點(diǎn)算法生成圓 (226） 生成圓的初始條件和圓的生成方向 2022-6-25572.2.2 中點(diǎn)算法生成圓 三、中點(diǎn)畫圓

27、算法實(shí)現(xiàn) 1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分對(duì)稱性，用規(guī)定的顏色color畫八個(gè)象素點(diǎn)(x，y)； 若d0y=y-1；d=d+2(x-y)+5；否則d=d+2x+3；x=x+1；2022-6-25582.2.2 中點(diǎn)算法生成圓 四、中點(diǎn)畫圓算法完善 在上述算法中，使用了浮點(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ù)，且在

28、運(yùn)算過(guò)程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e-1/4等價(jià)于e0。因此，可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。要求：寫出用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。2022-6-25592.2.2 中點(diǎn)算法生成圓 五、中點(diǎn)畫圓算法程序 void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;2022-6-25602.2.2 中點(diǎn)算法生成圓 while(x=y)putdot(x0,y0,x,y,color);if(d0)d+=x*2.0+3;elsed+=2.0*(x-

29、y)+5;y-; x+;2022-6-25612.2.2 中點(diǎn)算法生成圓 putdot(x0,y0,x,y,color)putpixel(x0+x,y0+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); 2022-6-25622.2.3 正負(fù)算法生成圓 正負(fù)法是利用

30、平面曲線將平面劃分成正負(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ù)畫圓算法描述 設(shè)要顯示圓的圓心在原點(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；2022-6-25632.2.3 正負(fù)算法生成圓 二、正負(fù)畫圓算法思想 現(xiàn)以下圖的AB弧為例，來(lái)說(shuō)明正負(fù)畫圓法(順時(shí)針生成圓)。2022-6-25642.2.3 正負(fù)算法生成圓 假設(shè)當(dāng)前點(diǎn)為Pi(xi

31、，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。即向右右走一步，從圓內(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ù)，因此稱為正負(fù)法。 下面分兩種情況求出F(xi，yi)的遞推公式：2022-6-25652.2.3 正負(fù)算法生成圓 (1) 當(dāng)F(xi，yi)0時(shí)，向右走，取xi+1=xi+1，yi+1=yi，則 F(xi+1，yi

32、+1)=F(xi+1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1 (2-28)2022-6-25662.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)2022-6-25672.2.3 正負(fù)算法生成圓 初始時(shí)，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(

33、2-30)就構(gòu)成正負(fù)畫圓算法的核心。 給象素坐標(biāo)(x，y)及F賦初始值后，進(jìn)入循環(huán)畫點(diǎn)； 畫點(diǎn)后，根據(jù)F的符號(hào)進(jìn)行F值的遞推和下一個(gè)點(diǎn)的獲取，直到xy為止。 同前面介紹的一樣，利用圓的八分對(duì)稱性，循環(huán)一次，畫八個(gè)點(diǎn)。2022-6-25682.2.3 正負(fù)算法生成圓 三、正負(fù)畫圓算法實(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)，即向左左走一步；2022-6-25692.2.

34、3 正負(fù)算法生成圓 (a) 順時(shí)針生成圓(b) 逆時(shí)針生成圓2022-6-25702.2.3 正負(fù)算法生成圓 四、正負(fù)畫圓算法特點(diǎn) 物理意義清楚，程序中只含整數(shù)運(yùn)算，因此算法速度快。五、正負(fù)畫圓算法程序 / 順時(shí)針生成圓void PNARC(int x0,int y0,int r,int color)int x=0,y=r,f=0;2022-6-25712.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-;2022-6-25722.2 圓的生成習(xí)題 1. 用自己的語(yǔ)言描述中點(diǎn)畫圓

35、算法。2022-6-25732.3 區(qū)域填充 前面介紹的直線和圓都屬于線劃圖，然而，光柵顯示的一個(gè)重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。 區(qū)域填充一般分兩類：多邊形填充和種子填充。 一、多邊形填充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)部還是外部呢？2022-6-25742.3 區(qū)域填充 從測(cè)試點(diǎn)引出一條伸向無(wú)窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，因?yàn)槎噙呅问情]合的，那么： 若射線與多邊形邊界的交點(diǎn)

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

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

38、數(shù)：該點(diǎn)置為填充色。 (5)否則：該點(diǎn)置為背景色。 逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問(wèn)題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。 2022-6-25792.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ū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。2022-6-25802.3 區(qū)域填充 四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向：上、下、左、右到達(dá)該

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

40、測(cè)條件(1) if(getpixel(x,y)!=邊界色 & getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色) 這兩個(gè)條件任何一個(gè)都可以用來(lái)檢測(cè)象素點(diǎn)(x,y)是不是尚未填充。推薦使用條件(1)進(jìn)行象素點(diǎn)檢測(cè)。2022-6-25842.3.1 邊相關(guān)掃描線多邊形填充算法 邊相關(guān)掃描線填充算法屬于多邊形填充類。它比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。 該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。 一、邊相關(guān)掃描線填充算法描述 掃描線的相關(guān)性掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)

41、，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時(shí)才會(huì)發(fā)生改變。見(jiàn)下圖(a)。2022-6-25852.3.1 邊相關(guān)掃描線多邊形填充算法 邊的相關(guān)性邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對(duì)同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見(jiàn)下圖(b)所示。 2022-6-25862.3.1 邊相關(guān)掃描線多邊形填充算法 (a) 掃描線的相關(guān)性 (b) 邊的相關(guān)性 邊相關(guān)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ET）和活動(dòng)邊表（AET）。2022-6-25872.3.1 邊

42、相關(guān)掃描線多邊形填充算法 1、邊表邊表（ET：Edge Table） 用來(lái)對(duì)除水平邊外的所有邊進(jìn)行登記，來(lái)建立邊的記錄。邊的記錄定義為： 掃描線 y 對(duì)應(yīng)的ET表2022-6-25882.3.1 邊相關(guān)掃描線多邊形填充算法 第一項(xiàng)：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對(duì)于非極值點(diǎn)應(yīng)該ymax=ymax-1。第二項(xiàng)：某邊的最小的y對(duì)應(yīng)的x值。第三項(xiàng)：某邊斜率的倒數(shù):1/m。第四項(xiàng)：指針。用來(lái)指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項(xiàng)置空。 2022-6-25892.3.1 邊相關(guān)掃描線多邊形填充算法 二、邊相關(guān)掃描線填充算法思想1、根據(jù)給出的多邊形頂點(diǎn)坐標(biāo)，建立ET表；

43、 求出頂點(diǎn)坐標(biāo)中最大y值ymax和最小y值ymin。2、初始化AET表指針，使它為空。3、使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。 對(duì)于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：2022-6-25902.3.1 邊相關(guān)掃描線多邊形填充算法 (1) 如果ET表中yj桶非空，則將yj桶中的全部記錄合并合并到AET表中。(2) 對(duì)AET表鏈中的記錄按x的大小從小到大排序排序。(3) 依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對(duì)填充填充，即將每對(duì)xi之間的象素填上所要求的顏色。2022-6-25912.3.1 邊相關(guān)掃描線多邊形填充算法

44、(4) 如果AET表中某記錄的ymax=yj，則刪除刪除該記錄。(5) 對(duì)于仍留在AET表中的每個(gè)記錄，用xi+1/m代替xi進(jìn)行修改修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。(6) 使yj加加1，以便進(jìn)入下一輪循環(huán)。2022-6-25922.3.1 邊相關(guān)掃描線多邊形填充算法 對(duì)下圖(a)的多邊形利用邊相關(guān)掃描線填充算法進(jìn)行處理：1、首先建立ET表。 注意：在做奇異點(diǎn)處理時(shí)，當(dāng)該邊最大y值對(duì)應(yīng)的頂點(diǎn)為非極值點(diǎn)時(shí)，邊記錄的第一項(xiàng)：ymax=ymax-1。例如：P3P4邊、P3P2邊、P4P5邊，見(jiàn)下圖(b)。2、接著建立AET表。AET表的建立過(guò)程就是有效地進(jìn)行填充的操作，在這個(gè)期

45、間不斷地做以下工作：2022-6-25932.3.1 邊相關(guān)掃描線多邊形填充算法 （1）合并ET表；（2）x遞增排序；（3）實(shí)施填充；（4）刪除ymaxyj的邊；（5）修改邊記錄xi=xi+1/m；（6）yj+1進(jìn)入下一輪循環(huán)。 結(jié)果見(jiàn)下圖(c)。2022-6-25942.3.1 邊相關(guān)掃描線多邊形填充算法 (a) 多邊形 (b) ET表 (c) AET表2022-6-25952.3.1 邊相關(guān)掃描線多邊形填充算法 四、邊相關(guān)掃描線填充算法實(shí)現(xiàn)1、根據(jù)給定的多邊形頂點(diǎn)坐標(biāo)，建立ET 表。2、AET表初始化，每個(gè)桶置空。3、for(y=ymin;y= ymax;y+) 合并當(dāng)前掃描線y的ET表；

46、 將y桶中每個(gè)記錄按x項(xiàng)升序排列； 在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)行填充； 刪除y=ymax的邊記錄； 修改邊記錄x=x+1/m； 2022-6-25962.3.1 邊相關(guān)掃描線多邊形填充算法 五、邊相關(guān)掃描線填充算法特點(diǎn) 該算法充分利用多邊形的邊相關(guān)性和掃描線的相關(guān)性，使用ET表對(duì)多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來(lái)支持填充，大大地減少了求交點(diǎn)的計(jì)算量，有效地提高了填充速度。2022-6-25972.3.2 掃描線種子填充算法 該算法屬于種子填充算法，它是以掃描線上的區(qū)段為單位進(jìn)行操作。所謂區(qū)段，就是一條掃描線上相連著的若干內(nèi)部象素的集合。 一、掃描線種子填充算法思

47、想 掃描線種子填充算法的基本思想是：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來(lái)。反復(fù)這個(gè)過(guò)程，直到所保存的各區(qū)段都填充完畢。2022-6-25982.3.2 掃描線種子填充算法 二、掃描線種子填充算法實(shí)現(xiàn) 借助于堆棧，上述算法實(shí)現(xiàn)步驟如下： 1、初始化堆棧。2、種子壓入堆棧。3、while（堆棧非空） (1)從堆棧彈出種子象素。(2)如果種子象素尚未填充，則： a.求出種子區(qū)段：xleft、xright; b.填充整個(gè)區(qū)段。2022-6-25992.3.2 掃描線種子填充算法 c.檢

48、查相鄰的上掃描線的xleftxxright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。 d.檢查相鄰的下掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。 2022-6-251002.3.2 掃描線種子填充算法 四、掃描線種子填充算法特點(diǎn)1、該算法考慮了掃描線上象素的相關(guān)性，種子象素不再代表一個(gè)孤立的象素，而是代表一個(gè)尚未填充的區(qū)段。2、進(jìn)棧時(shí)，只將每個(gè)區(qū)段選一個(gè)象素進(jìn)棧（每個(gè)區(qū)

49、段最右邊或最左邊的象素），這樣解決了堆棧溢出的問(wèn)題。3、種子出棧時(shí)，則填充整個(gè)區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對(duì)尚未填充象素的登記（象素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆棧空間，又可以實(shí)施快速填充。2022-6-251012.3.3 邊標(biāo)志填充算法 在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個(gè)閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線逐行對(duì)多邊形求交，在交點(diǎn)對(duì)之間填充。邊標(biāo)志填充算法就是在逐行處理時(shí)，利用邊界色作為標(biāo)志來(lái)進(jìn)行填充的。例如某掃描線從左到右掃描時(shí)碰到邊界色，立刻改變標(biāo)志的狀態(tài)，接下來(lái)再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。 2022-6-251022.3.3 邊

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

51、 邊標(biāo)志填充算法 邊標(biāo)志填充算法3、逐條掃描線進(jìn)行處理，對(duì)每條掃描線依從左往右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。2022-6-251052.3.3 邊標(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)2022-6-251062.3.3 邊標(biāo)志填充算法 int i, x,y,flag,xmin,xmax,y

52、min,ymax;setcolor(boundarycolor); /*設(shè)置畫筆色*/ for(i=0 ;in;i+) line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*畫出多邊形的n條邊*/用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;2022-6-251072.3.3 邊標(biāo)志填充算法 for(y=ymin;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,

53、 newcolor); 2022-6-251082.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í)，掃描線與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時(shí)會(huì)出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒(méi)有填上色。解決的辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志。2022-6-251092.3.3 邊標(biāo)志填充算法 2、特別當(dāng)心多邊形邊界的掃描轉(zhuǎn)換。在這里就不能考慮：不同的斜率產(chǎn)生的直線要亮度均勻，如下圖(a)所示。否則當(dāng)掃描線y遇到斜率小于1的邊

54、界線時(shí)，碰到幾個(gè)邊界點(diǎn)，會(huì)引起標(biāo)志的無(wú)序改變，將導(dǎo)致填充的錯(cuò)誤。 解決的辦法：對(duì)于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長(zhǎng)一步，x方向增長(zhǎng)1/m步距，以保證掃描線y遇到斜率小于1的邊界時(shí)，只能遇到一個(gè)點(diǎn)。請(qǐng)看下圖(b)。2022-6-251102.3.3 邊標(biāo)志填充算法 在邊標(biāo)志填充算法中要注意多邊形邊界的掃描轉(zhuǎn)換2022-6-251112.3.4 圖案填充 前面介紹的區(qū)域填充算法，都是把區(qū)域內(nèi)部的象素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用圖案來(lái)填充平面區(qū)域。這可以將前面的填充算法中寫象素的那部分代碼稍加修改來(lái)實(shí)現(xiàn): 在確定了區(qū)域內(nèi)點(diǎn)后，不是馬上對(duì)該象素填色

55、，而是先將該象素映射到圖案位圖的對(duì)應(yīng)位置。根據(jù)圖案該位置的象素值，決定填充顏色。2022-6-251122.3.4 圖案填充 一、圖案填充方式： 1、透明方式:若是以透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫象素，否則，不改變?cè)撓笏氐闹怠?2、不透明方式: 而若是以不透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫象素，否則，用背景色寫象素。2022-6-251132.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ì)于圓

56、和橢圓這樣具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)，如取中心與圖案原點(diǎn)對(duì)齊。2022-6-251142.3.4 圖案填充 2、絕對(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)的圖案變了。2022-6-251152.3.4 圖案填充 三、圖案填充算法實(shí)現(xiàn) 下面討論在第二種絕對(duì)定位法下用不透明方式對(duì)平面區(qū)域填充圖案： 假設(shè)填充圖

57、案是一個(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)行填充。2022-6-251162.3.4 圖案填充 四、圖案填充算法程序 / 采用不透明方式絕對(duì)定位法填充圖案的程序偽代碼: maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy;int maskcode88=

58、 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;2022-6-251172.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

59、,y, backgroundcolor); /* backgroundcolor為背景色*/ 2022-6-251182.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)的編碼是由它所屬的字符集決定。 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)

60、符號(hào)等可顯示字符。 一個(gè)字符的ASCII碼用一個(gè)字節(jié)（8位）表示，其最高位不用或者作為奇偶校驗(yàn)位。2022-6-251192.4.1 點(diǎ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的矩陣，在此方陣中，每一行稱為“區(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)碼占用兩