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

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

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

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

4、千上萬條直線，所以要求繪制算 法應該：1、最接近數(shù)學上的直線；2022-6-2592.1 直線的掃描轉換 2、沿著線段分布的象素應均勻 不均勻的例子如下圖所示，對同樣長的線段，如果進行圖中的掃描轉換，就會因為斜率的不同，產(chǎn)生的象素個數(shù)不相等，這樣將導致象素亮度分布不均勻。3、畫線速度盡可能的快 2022-6-25102.1.1 生成直線的DDA算法 數(shù)值微分法即DDA法(Digital Differential Analyzer)，是一種基于直線的微分方程來生成直線的方法 一、直線DDA算法描述： 設(x1，y1)和(x2，y2)分別為所求直線的起點和終點坐標，由直線的微分方程得 = m =直

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

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

7、值： steps=max(|dx|，|dy|)2022-6-25152.1.1 生成直線的DDA算法 5、計算兩個方向的增量(考慮了生成方向)： xin=dx/steps yin=dy/steps6、設置初始象素坐標：x=x1,y=y17、用循環(huán)實現(xiàn)直線的繪制：for(i=1；i=steps；i+) putpixel(x，y，color)；/*在(x，y)處，以color色畫點*/x=x+xin； y=y+yin； 2022-6-25162.1.1 生成直線的DDA算法 四、直線DDA算法特點： 該算法簡單，實現(xiàn)容易，但由于在循環(huán)中涉及實型數(shù)的運算，因此生成直線的速度較慢。五、直線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色畫點y=y+k; 2022-6-25182.1.2 生成直線的Bresenham算法 從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實型

9、數(shù)據(jù)的加減運算，因此直線的生成速度較慢。 在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來生成直線的方法。 一、直線Bresenham算法描述： 它也是采用遞推步進的辦法，令每次最大變化方向的坐標步進一個象素，同時另一個方向的坐標依據(jù)誤差判別式的符號來決定是否也要步進一個象素。2022-6-25192.1.2 生成直線的Bresenham算法 我們首先討論m=y/x，當0m1且x1x2時的Bresenham算法。從DDA直線算法可知這些條件成立時，公式(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算法思想之一 由于顯示直線的象素點只能取整數(shù)值坐標，可以假設直線上第i個象素點坐標為(xi，yi)，它是直線上點(xi，yi)的最佳近似，并且xi=xi(假設md2，說明直線上理論點離(xi+1，yi+1)象素較近，下一個象素點應取(xi+1，yi+1)。(2)當此值為負時，d10，因此pi與(d1-d2)有相同的符號； 這里y=y2-y1，m=y/x；c=2y+x(2b-1)。 下

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

12、我們可利用誤差判別變量，得到如下算法表示： 初始 p1=2y-x (216) 當pi0時： 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、直線的兩個端點坐標分量差x和y有關，運算中只含有整數(shù)相加和乘2運算，而乘2可利用算術左移一位來完成，因此這個算法速度快并易于硬件實現(xiàn)。 三、直線Bresenham算法思想之二 由于象素坐標的整數(shù)性，數(shù)學點(xi，yi)與所取

13、象素點(xi，yir)間會引起誤差(i)，當xi列上已用象素坐標(xi，yir)表示直線上的點(xi，yi)，下一直線點B(xi+1，yi+1)，是取象素點C(xi+1，yir )，還是D(xi1，y(i+1)r)呢？2022-6-25282.1.2 生成直線的Bresenham算法 設A為CD邊的中點，正確的選擇： 若B點在A點上方，選擇D點； 否則，選C點。 用誤差式描述為： (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) 當(xi+1)0時，選D點，y(i+1)r = yir+1 (xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1 (210) 當(xi+1)0時，選C點，y(i+1)r = yir (xi+2)= yi+1+myir-0.5=(xi+1)+m (211)2022-6-25302.1.2 生成直線的Bresenham算法 初始時： (xs+1)=BC-AC=m-0.5 (212)2022-6-25312.1.2 生成直線的Bresenham算法 為了運算中不含實型數(shù)，同時不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。 令方程兩邊同乘2x，即p=2

15、x，則： 初始時： p = 2y-x (213)遞推式： 當p0時： p=p+2(yx)；y+；x+；否則： p=p+2y；x+； (214)2022-6-25322.1.2 生成直線的Bresenham算法 四、直線Bresenham算法實現(xiàn) 條件：0m1且x1x2 1、輸入線段的兩個端點坐標和畫線顏色：x1，y1，x2，y2，color；2、設置象素坐標初值：x=x1，y=y1；3、設置初始誤差判別值：p=2y-x；4、分別計算：x=x2-x1、y=y2-y1；2022-6-25332.1.2 生成直線的Bresenham算法 5、循環(huán)實現(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)公式，以適應對任何方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點出發(fā)射向八個區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。 容易證明：當線段處于、區(qū)時，以|x|和|y|代替前面公式中的x和y，當線段處于、區(qū)時，將公式中的|x|和|y|對換，則上述兩公式仍有效。2022-6-25352.1.2 生成直線的Bresenham算法 在線段起點區(qū)分線段方向2022-6-25362.1.2

17、 生成直線的Bresenham算法 七、直線Bresenham算法特點 由于程序中不含實型數(shù)運算，因此速度快、效率高，是一種有效的畫線算法。八、直線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 直線的生成習題1.DDA法生成直線的基本原理是什么？2022-6-25402.2 圓的生成 這里僅討論圓心位于坐標原點

19、的圓的掃描轉換算法，對于圓心不在原點的圓，可先用平移變換，將它的圓心平移到原點，然后進行掃描轉換，最后再平移到原來的位置。 有幾種較容易的方法可以得到圓的掃描轉換，但是效率都不高。例如：直角坐標法和極坐標法： 1、直角坐標法 圓的直角坐標方程為 x2+y2=R2若取x作為自變量，解出y，得到 2022-6-25412.2 圓的生成 (217) 我們可以先掃描轉換四分之一的圓周。讓自變量x從0到R以單位步長增加，在每一步時可解出y，然后調用畫點函數(shù)即可逐點畫出圓。但這樣做，由于有乘方和平方根運算，并且都是浮點運算，算法效率不高。而且當x接近R值時(圓心在原點)，在圓周上的點（R，0）附近，由于圓

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

21、，就可以利用對稱性的原理得到整個圓弧。下面的函數(shù)CirclePoints()用來顯示P(x，y)及其七個對稱點。 2022-6-25442.2.1 圓的八分對稱性 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 圓的八分對稱性 圓的八分對稱性 注意：注意： 當圓心不在原點時，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標）即可。2022-6-25462.2.1 圓的八分對稱性 例如 當 x0=300，y0=200時，則： 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 中點算法生成圓 中點畫圓算法在一個方向上取單位間隔，在另一個方向的取值由兩種可能取值的中點離圓的遠近而定。實際處理中，用決策變量的符號來確定象素點的選擇，因此算法效率較高。一、中點畫圓算法描述 設要顯示圓的圓心在原點(0，0)，半徑為R，起點在(0，R)處，終點在( , )處，順時針生成八分之一圓，利用對稱性掃描轉換全部圓。 為了應用中點畫圓法，我們定義一個圓函數(shù) F(x，y)=x2+y2-R2 (219)2022-6-25482.2.2 中點算法生成圓 任何點(x，y)的相對位置可由圓函數(shù)的符號來檢測： 0點

24、(x，y)位于數(shù)學圓外 2022-6-25492.2.2 中點算法生成圓 如下圖所示，圖中有兩條圓弧A和B，假定當前取點為Pi(xi，yi)，如果順時針生成圓，那么下一點只能取正右方的點E(xi+1，yi)或右下方的點SE(xi+1，yi-1)兩者之一。 中點畫線算法2022-6-25502.2.2 中點算法生成圓 假設M是E和SE的中點，則： 1、當F(M)0時，M在圓外(圓弧B)，表明SE點離圓更近，應取SE點；3、當F(M)=0時，在E點與SE點之中隨便取一個即可，我們約定取SE點。 2022-6-25512.2.2 中點算法生成圓 二、中點畫圓算法思想 因此，我們用中點M的圓函數(shù)作為決

25、策變量di，同時用增量法來迭代計算下一個中點M的決策變量di+1。 (221) 下面分兩種情況來討論在迭代計算中決策變量di+1的推導。 1、見圖（a），若di0，則選擇E點，接著下一個中點就是 ，這時新的決策變量為： (222)2022-6-25522.2.2 中點算法生成圓 （a）(di0) 中點畫線算法2022-6-25532.2.2 中點算法生成圓 式(222)減去(221)得： di+1=di+2xi+3 (223) 2、見圖（b），若di0，則選擇SE點，接著下一個中點就是 ，這時新的決策變量為： (224) 2022-6-25542.2.2 中點算法生成圓 （b）(di0) 中點

26、畫線算法 式(224)減去(221)得： di+1=di+2(xi-yi)+5 (225)2022-6-25552.2.2 中點算法生成圓 我們利用遞推迭代計算這八分之一圓弧上的每個點，每次迭代需要兩步處理：（1）用前一次迭代算出的決策變量的符號來決定本次選擇的點。（2）對本次選擇的點，重新遞推計算得出新的決策變量的值。 剩下的問題是計算初始決策變量d0，如下圖所示。對于初始點(0，R)，順時針生成八分之一圓，下一個中點M的坐標是 ，所以：2022-6-25562.2.2 中點算法生成圓 (226） 生成圓的初始條件和圓的生成方向 2022-6-25572.2.2 中點算法生成圓 三、中點畫圓

27、算法實現(xiàn) 1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分對稱性，用規(guī)定的顏色color畫八個象素點(x，y)； 若d0y=y-1；d=d+2(x-y)+5；否則d=d+2x+3；x=x+1；2022-6-25582.2.2 中點算法生成圓 四、中點畫圓算法完善 在上述算法中，使用了浮點數(shù)來表示決策變量d。為了簡化算法，擺脫浮點數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d0=5/4-r對應于e0=1-r。決策變量d0對應于e-1/4。算法中其它與d有關的式子可把d直接換成e。又由于e的初值為整數(shù)，且在

28、運算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e-1/4等價于e0。因此，可以寫出完全用整數(shù)實現(xiàn)的中點畫圓算法。要求：寫出用整數(shù)實現(xiàn)的中點畫圓算法程序，并上機調試，觀看運行結果。2022-6-25592.2.2 中點算法生成圓 五、中點畫圓算法程序 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 中點算法生成圓 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 中點算法生成圓 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 正負算法生成圓 正負法是利用

30、平面曲線將平面劃分成正負區(qū)域，對當前點產(chǎn)生的圓函數(shù)進行符號判別，利用負反饋調整以決定下一個點的產(chǎn)生來直接生成圓弧。 一、正負畫圓算法描述 設要顯示圓的圓心在原點(0，0)，半徑為R，初始點的坐標為(0，R)，順時針生成八分之一圓，令：F(x，y)=x2+y2-R2 則圓的方程為： F(x，y)=0 (2-27) 當點(x，y)在圓內時，則F(x，y)0；當點(x，y)在圓上時，則F(x，y)=0；2022-6-25632.2.3 正負算法生成圓 二、正負畫圓算法思想 現(xiàn)以下圖的AB弧為例，來說明正負畫圓法(順時針生成圓)。2022-6-25642.2.3 正負算法生成圓 假設當前點為Pi(xi

31、，yi)，取下一個點Pi+1(xi+1，yi+1)的原則是： 1、當F(xi，yi)0時：取xi+1= xi+1，yi+1= yi。即向右右走一步，從圓內走向圓外。對應圖(a)中的從Pi到Pi+1。2、當F(xi，yi)0時：取xi+1= xi，yi+1= yi-1。即向下下走一步，從圓外走向圓內。對應圖(b)中的從Pi到Pi+1。 由于向圓內或向圓外走取決于F(xi，yi)的正負，因此稱為正負法。 下面分兩種情況求出F(xi，yi)的遞推公式：2022-6-25652.2.3 正負算法生成圓 (1) 當F(xi，yi)0時，向右走，取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 正負算法生成圓 (2) 當F(xi，yi)0時，向下走，取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 正負算法生成圓 初始時，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(

33、2-30)就構成正負畫圓算法的核心。 給象素坐標(x，y)及F賦初始值后，進入循環(huán)畫點； 畫點后，根據(jù)F的符號進行F值的遞推和下一個點的獲取，直到xy為止。 同前面介紹的一樣，利用圓的八分對稱性，循環(huán)一次，畫八個點。2022-6-25682.2.3 正負算法生成圓 三、正負畫圓算法實現(xiàn) 注意：初值不同、圓的生成方向不同時，當前點和下一個點的獲取原則是不同的，見下圖。 例如，初始點(R，0)，逆時針生成圓，從圖（b）可知： 若當前點Pi在圓內，則下一點Pi+1(xi，yi+1)，即向上上走一步；若當前點Pi在圓外，則下一點Pi+1(xi-1，yi)，即向左左走一步；2022-6-25692.2.

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

35、算法。2022-6-25732.3 區(qū)域填充 前面介紹的直線和圓都屬于線劃圖，然而，光柵顯示的一個重要特點是能進行面著色，區(qū)域填充就是在一個閉合區(qū)域內填充某種顏色或圖案。 區(qū)域填充一般分兩類：多邊形填充和種子填充。 一、多邊形填充1、填充條件 多邊形的頂點序列(Pi，i=0，1，n)、填充色。 2、多邊形內點的判別準則 對多邊形進行填充，關鍵是找出多邊形內的象素。在順序給定多邊形頂點坐標的情況下，如何判明一個象素點是處于多邊形的內部還是外部呢？2022-6-25742.3 區(qū)域填充 從測試點引出一條伸向無窮遠處的射線(假設是水平向右的射線)，因為多邊形是閉合的，那么： 若射線與多邊形邊界的交點

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

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

38、數(shù)：該點置為填充色。 (5)否則：該點置為背景色。 逐點判別算法雖然簡單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對每個象素進行多次求交運算，求交時要做大量的乘除運算，從而影響了填充速度。 2022-6-25792.3 區(qū)域填充 二、種子填充 種子填充是將區(qū)域內的一點(種子)賦予給定的顏色，然后將這種顏色擴展到整個區(qū)域內的過程。 1、填充條件 區(qū)域內一點的坐標即種子坐標、邊界色、填充色。 2、連通方式 區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。2022-6-25802.3 區(qū)域填充 四連通：從區(qū)域內一點出發(fā)，可通過四個方向：上、下、左、右到達該

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

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

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

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

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

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

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

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

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

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

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

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

51、 邊標志填充算法 邊標志填充算法3、逐條掃描線進行處理，對每條掃描線依從左往右的順序，逐個訪問該掃描線上的象素。每遇到邊界象素，標志取反。然后，按照標志是否為真，決定象素是否為填充色。2022-6-251052.3.3 邊標志填充算法 三、邊標志填充算法特點 該算法思想簡單，實現(xiàn)容易。既不需要求交點、交點排序、邊的登記，也不需要使用鏈表、堆棧等數(shù)據(jù)結構。四、邊標志填充算法程序 EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)2022-6-251062.3.3 邊標志填充算法 int i, x,y,flag,xmin,xmax,y

52、min,ymax;setcolor(boundarycolor); /*設置畫筆色*/ for(i=0 ;in;i+) line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*畫出多邊形的n條邊*/用求極值的算法，從多邊形頂點數(shù)組p中，求出xmin,xmax,ymin,ymax;2022-6-251072.3.3 邊標志填充算法 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 邊標志填充算法 五、邊標志填充算法錯誤處理1、該算法雖然簡單，但程序運行后會出現(xiàn)局部錯誤。從下圖可以發(fā)現(xiàn)，對于多邊形頂點為局部極值點時，掃描線與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時會出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應該填充的區(qū)段卻沒有填上色。解決的辦法：判斷多邊形頂點的性質，如果是局部極值點，那么掃描線碰上它則不改變標志。2022-6-251092.3.3 邊標志填充算法 2、特別當心多邊形邊界的掃描轉換。在這里就不能考慮：不同的斜率產(chǎn)生的直線要亮度均勻，如下圖(a)所示。否則當掃描線y遇到斜率小于1的邊

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

55、，而是先將該象素映射到圖案位圖的對應位置。根據(jù)圖案該位置的象素值，決定填充顏色。2022-6-251122.3.4 圖案填充 一、圖案填充方式： 1、透明方式:若是以透明方式填充圖案，則當圖案位圖的對應位置為1時，用前景色寫象素，否則，不改變該象素的值。 2、不透明方式: 而若是以不透明方式填充圖案，則當圖案位圖的對應位置為1時，用前景色寫象素，否則，用背景色寫象素。2022-6-251132.3.4 圖案填充 二、圖案定位法： 1、相對定位法:把圖案原點與填充區(qū)域邊界或內部的某點對齊。這樣，當被填充的多邊形移動時，圖案也跟著移動，看起來比較自然。 對于多邊形，可取邊界上最左邊的頂點，而對于圓

56、和橢圓這樣具有光滑邊界的區(qū)域，則最好取區(qū)域內部某一點，如取中心與圖案原點對齊。2022-6-251142.3.4 圖案填充 2、絕對定位法：把圖案原點與屏幕原點對齊。該方法可以將整個屏幕看成被要填充的圖案布滿，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來，其它區(qū)域對此圖案卻是不透明的，圖案被全部擋住。 這種方法比較簡單，并且在相鄰區(qū)域用同一圖案填充時，可以達到無縫連接的效果。但它有一個潛在的毛病，即當區(qū)域移動時，圖案不會跟著移動。其效果是區(qū)域內的圖案變了。2022-6-251152.3.4 圖案填充 三、圖案填充算法實現(xiàn) 下面討論在第二種絕對定位法下用不透明方式對平面區(qū)域填充圖案： 假設填充圖

57、案是一個MN的位圖，用MN的數(shù)組存放。M、N一般比需要填充區(qū)域的尺寸小得多（88、1616、3232），所以圖案總是設計成周期性的，使之能通過重復使用來構成任意尺寸的圖案。當確定了區(qū)域內點p（x,y）后，則圖案位圖上的對應位置為p（x%M，y%N），其中%為C語言整除取余運算符,然后取出圖案位圖該位置的象素進行填充。2022-6-251162.3.4 圖案填充 四、圖案填充算法程序 / 采用不透明方式絕對定位法填充圖案的程序偽代碼: 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ū)域內點坐標x映射到圖案坐標xx*/yy=y%8; /*多邊形區(qū)域內點坐標y到圖案坐標yy*/if(maskcodeyyxx)putpixel(x,y, newcolor); /* newcolor 為前景色*/elseputpixel(x

59、,y, backgroundcolor); /* backgroundcolor為背景色*/ 2022-6-251182.4.1 點陣字符 我們討論的字符是指字母、數(shù)字、漢字、標點等符號。計算機中，字符由一個數(shù)字編碼唯一標識，對于一個字符來說，它所對應的編碼是由它所屬的字符集決定。 1、ASCII碼 目前，國際上普遍采用的字符編碼是ASCII碼（American Standard Code for Information Interchange）美國信息交換標準代碼。它是用七位二進制數(shù)進行編碼，共能表示128個字符，其中編碼031表示控制字符（不可顯示），編碼32127表示英文字母、數(shù)字、標點

60、符號等可顯示字符。 一個字符的ASCII碼用一個字節(jié)（8位）表示，其最高位不用或者作為奇偶校驗位。2022-6-251192.4.1 點陣字符 2、國標碼 我國除了采用ASCII碼外，還制定了漢字編碼的國家標準字符集:中華人民共和國國家標準信息交換編碼，代號為“GB231280”。該字符集共收錄常用漢字6763個，圖形符號682個。 它規(guī)定所有漢字和圖形符號組成一個9494的矩陣，在此方陣中，每一行稱為“區(qū)”，用區(qū)碼來標識；每一列稱為“位”，用位碼來標識，一個符號由一個區(qū)碼和一個位碼共同標識。 區(qū)碼和位碼分別需要7個二進制位，同樣，為了方便，各采用一個字節(jié)表示。所以在計算機中，漢字（符號）國標碼占用兩