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

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

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

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

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

5、分別為所求直線的起點和終點坐標，由直線的微分方程得 = m =直線的斜率 (21),2020/11/20,11,2.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)是遞推的。,2020/11/20,12,2.1.1 生成直線的DDA算法,二、直線DDA算法思想： 選定x2x1和y2y1中較大者作為步進方向(假設x2x1較大)，取該方向上的增量為一個

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

7、r3、計算兩個方向的變化量：dx=x2x1 dy=y2y14、求出兩個方向最大變化量的絕對值： steps=max(|dx|，|dy|),2020/11/20,15,2.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；,2020/11/20,16,2.1.1 生成直線的DDA算法,四、直線DDA算法特

8、點： 該算法簡單，實現(xiàn)容易，但由于在循環(huán)中涉及實型數(shù)的運算，因此生成直線的速度較慢。 五、直線DDA算法程序： 下面給出考慮不同斜率、不同方向直線的DDA畫線算法程序：,2020/11/20,17,2.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;,202

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

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

11、+1)。,2020/11/20,21,2.1.2 生成直線的Bresenham算法,2020/11/20,22,2.1.2 生成直線的Bresenham算法,由圖中可以知道，在x=xi+1處，直線上點的y值是y=m(xi+1)+b，該點離象素點(xi+1，yi)和象素點(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) 這兩個距離差是 d1-d2=2m(xi+1)-2yi2b-1 (210),2020/11/20,23,2.1.2 生成直線的Bresenham算法,我們來分析公式

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

13、-2xyi+c (211)式(2-11)中的x=(x2-x1)0，因此pi與(d1-d2)有相同的符號； 這里y=y2-y1，m=y/x；c=2y+x(2b-1)。 下面對式(2-11)作進一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。,2020/11/20,25,2.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=

14、mx1+b (214),2020/11/20,26,2.1.2 生成直線的Bresenham算法,由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x (215) 這樣，我們可利用誤差判別變量，得到如下算法表示： 初始 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,2020/11/20,27,2.1.2 生成直線的Bresenham算法,從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個端點坐標分量差x和y有關

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

16、-AC=(yi+1-yir)-0.5 (28),2020/11/20,29,2.1.2 生成直線的Bresenham算法,求遞推公式： (xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-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),2020/11/20,30,2.1.2 生成直線的Bresenham算法,初始時： (

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

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

19、線段處于、區(qū)時，以|x|和|y|代替前面公式中的x和y，當線段處于、區(qū)時，將公式中的|x|和|y|對換，則上述兩公式仍有效。,2020/11/20,35,2.1.2 生成直線的Bresenham算法,在線段起點區(qū)分線段方向,2020/11/20,36,2.1.2 生成直線的Bresenham算法,七、直線Bresenham算法特點 由于程序中不含實型數(shù)運算，因此速度快、效率高，是一種有效的畫線算法。 八、直線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 生成直線的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 生成直線的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 直線的生成習題,1.DDA法生成直線的基本原理是什么？,2020/11/20,40,2.2 圓的生成,這里僅討論圓心位于坐標原點的圓的掃描轉(zhuǎn)換算法，對于圓心不在原點的圓，可先用平移變換，將它的圓心平移到原點，然后進行掃描轉(zhuǎn)換，最后再平移到原來的位置。 有幾種較容易的方法可以得到圓的掃描轉(zhuǎn)換，但是效率都不高。例如：直角坐標法和極坐標法： 1、直角坐標法 圓的直角坐標方程為 x2+y2=R2若取x作為自變量，解出y，得到,2020/

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

23、及三角函數(shù)計算和乘法運算，計算量較大。因此，也不是一種有效的方法。,2020/11/20,43,2.2.1 圓的八分對稱性,圓心位于原點的圓有四條對稱軸x=0、y=0、x=y和x=y，見下圖。從而若已知圓弧上一點P(x，y)，就可以得到其關于四條對稱軸的七個對稱點，這種性質(zhì)稱為八分對稱性。因此只要能畫出八分之一的圓弧，就可以利用對稱性的原理得到整個圓弧。下面的函數(shù)CirclePoints()用來顯示P(x，y)及其七個對稱點。,2020/11/20,44,2.2.1 圓的八分對稱性,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 圓的八分對稱性,圓的八分對稱性 注意： 當圓心不在原點時，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標）即可。,2020/11/20,46,2.2.1 圓的八分對稱性,例如 當 x0=300，y0=200時，則： 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 中點算法生成圓,中點畫圓算法在一個方向上取單位間隔，在另一個方向的取值由兩種可能取值的中點離圓的遠近而定。實際處理中，用決策變量的符號來確定象素點的選擇，因此算法效率較高。 一

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

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

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

29、步處理：（1）用前一次迭代算出的決策變量的符號來決定本次選擇的點。（2）對本次選擇的點，重新遞推計算得出新的決策變量的值。 剩下的問題是計算初始決策變量d0，如下圖所示。對于初始點(0，R)，順時針生成八分之一圓，下一個中點M的坐標是 ，所以：,2020/11/20,56,2.2.2 中點算法生成圓,(226） 生成圓的初始條件和圓的生成方向,2020/11/20,57,2.2.2 中點算法生成圓,三、中點畫圓算法實現(xiàn) 1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分對稱性，用規(guī)定的顏色color畫八個象素點(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 中點算法生成圓,四、中點畫圓算法完善 在上述算法中，使用了浮點數(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ù)，且在運算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e-1/4等價于e0。因此，可以寫出完全用整數(shù)實現(xiàn)的中點畫圓算法。要求：寫出用整數(shù)實現(xiàn)的中點畫圓算法程序，并上機調(diào)試，觀看運行結(jié)果

31、。,2020/11/20,59,2.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;,2020/11/20,60,2.2.2 中點算法生成圓,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 中點算法生成圓,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 正負算法生成圓,正負法是利用平面曲線將平面劃分成正負區(qū)域，對當前點產(chǎn)生的圓函數(shù)進行符號判別，利用負反饋調(diào)整以決定下一個點的產(chǎn)生來直接生成圓弧。 一、正負畫圓算法描述 設要顯示圓

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

34、即向右走一步，從圓內(nèi)走向圓外。對應圖(a)中的從Pi到Pi+1。2、當F(xi，yi)0時：取xi+1= xi，yi+1= yi-1。即向下走一步，從圓外走向圓內(nèi)。對應圖(b)中的從Pi到Pi+1。 由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負，因此稱為正負法。 下面分兩種情況求出F(xi，yi)的遞推公式：,2020/11/20,65,2.2.3 正負算法生成圓,(1) 當F(xi，yi)0時，向右走，取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 正負算法生成圓,(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),2020/11/20,67,2.2.3 正負算法生成圓,初始時，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(2-30)就構(gòu)成正負畫圓算法的核心。 給象素坐標(x，y)及F賦初始值后，進入循環(huán)畫點； 畫點后，根據(jù)F的符號進

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

37、 正負算法生成圓,四、正負畫圓算法特點 物理意義清楚，程序中只含整數(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 正負算法生成圓,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 圓的生成習題,1. 用自己的語言描述中點畫圓算法。,2020/11/20,73,2.3 區(qū)域填充,前面介紹的直線和圓都

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

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

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

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

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

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

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

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

46、、掃描線種子填充算法特點 1、該算法考慮了掃描線上象素的相關性，種子象素不再代表一個孤立的象素，而是代表一個尚未填充的區(qū)段。 2、進棧時，只將每個區(qū)段選一個象素進棧（每個區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問題。 3、種子出棧時，則填充整個區(qū)段。 4、這樣有機的結(jié)合：一邊對尚未填充象素的登記（象素進棧），一邊進行填充（象素出棧），既可以節(jié)省堆棧空間，又可以實施快速填充。,2020/11/20,101,2.3.3 邊標志填充算法,在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個閉合區(qū)域，填充是逐行進行的，即用掃描線逐行對多邊形求交，在交點對之間填充。邊標志填充算法就是在逐

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

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

49、dgeMarkFill(int p2,int n,int boundarycolor,int newcolor),2020/11/20,106,2.3.3 邊標志填充算法,int i, x,y,flag,xmin,xmax,ymin,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;,2020/11/20,107,2.3.3 邊標志填充算法,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 邊標志填充算法,五、邊標志填充算法錯誤處理 1、該算法雖然簡單，但程序運行后會出現(xiàn)局部錯誤。從下圖可以發(fā)現(xiàn)，對于多邊形頂點為局部極值點時，掃描線與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時會出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應該填充的區(qū)段卻沒有填上色。解決的辦法：判斷多邊形頂

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

52、轉(zhuǎn)換,2020/11/20,111,2.3.4 圖案填充,前面介紹的區(qū)域填充算法，都是把區(qū)域內(nèi)部的象素全部置成同一種顏色。但在實際應用中，有時需要用圖案來填充平面區(qū)域。這可以將前面的填充算法中寫象素的那部分代碼稍加修改來實現(xiàn): 在確定了區(qū)域內(nèi)點后，不是馬上對該象素填色，而是先將該象素映射到圖案位圖的對應位置。根據(jù)圖案該位置的象素值，決定填充顏色。,2020/11/20,112,2.3.4 圖案填充,一、圖案填充方式： 1、透明方式:若是以透明方式填充圖案，則當圖案位圖的對應位置為1時，用前景色寫象素，否則，不改變該象素的值。 2、不透明方式: 而若是以不透明方式填充圖案，則當圖案位圖的對應位置

53、為1時，用前景色寫象素，否則，用背景色寫象素。,2020/11/20,113,2.3.4 圖案填充,二、圖案定位法： 1、相對定位法:把圖案原點與填充區(qū)域邊界或內(nèi)部的某點對齊。這樣，當被填充的多邊形移動時，圖案也跟著移動，看起來比較自然。 對于多邊形，可取邊界上最左邊的頂點，而對于圓和橢圓這樣具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點，如取中心與圖案原點對齊。,2020/11/20,114,2.3.4 圖案填充,2、絕對定位法：把圖案原點與屏幕原點對齊。該方法可以將整個屏幕看成被要填充的圖案布滿，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來，其它區(qū)域?qū)Υ藞D案卻是不透明的，圖案被全部擋住。 這種

54、方法比較簡單，并且在相鄰區(qū)域用同一圖案填充時，可以達到無縫連接的效果。但它有一個潛在的毛病，即當區(qū)域移動時，圖案不會跟著移動。其效果是區(qū)域內(nèi)的圖案變了。,2020/11/20,115,2.3.4 圖案填充,三、圖案填充算法實現(xiàn) 下面討論在第二種絕對定位法下用不透明方式對平面區(qū)域填充圖案： 假設填充圖案是一個MN的位圖，用MN的數(shù)組存放。M、N一般比需要填充區(qū)域的尺寸小得多（88、1616、3232），所以圖案總是設計成周期性的，使之能通過重復使用來構(gòu)成任意尺寸的圖案。當確定了區(qū)域內(nèi)點p（x,y）后，則圖案位圖上的對應位置為p（x%M，y%N），其中%為C語言整除取余運算符,然后取出圖案位圖該位

55、置的象素進行填充。,2020/11/20,116,2.3.4 圖案填充,四、圖案填充算法程序 / 采用不透明方式絕對定位法填充圖案的程序偽代碼: 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)點坐標x映射到圖案坐標xx*/yy=y%8; /*多邊形區(qū)域內(nèi)點坐標y到圖案坐標yy*/if(maskcodeyyxx)putpixel(x,y, newcolor); /* newcolor 為前景色*/elseputpixel(x,y, backgroundcolor); /* backgroundcolor為背景色*/,2020/11/20,118,2.4.1 點陣字符,我們討論的字符是指字母、數(shù)字、漢字、標點等符號。計算機中，字符由一個數(shù)字編碼唯一標識，對于一個字符來說，它所對應的編碼是由它所屬的字符集決

57、定。 1、ASCII碼 目前，國際上普遍采用的字符編碼是ASCII碼（American Standard Code for Information Interchange）美國信息交換標準代碼。它是用七位二進制數(shù)進行編碼，共能表示128個字符，其中編碼031表示控制字符（不可顯示），編碼32127表示英文字母、數(shù)字、標點符號等可顯示字符。 一個字符的ASCII碼用一個字節(jié)（8位）表示，其最高位不用或者作為奇偶校驗位。,2020/11/20,119,2.4.1 點陣字符,2、國標碼 我國除了采用ASCII碼外，還制定了漢字編碼的國家標準字符集:中華人民共和國國家標準信息交換編碼，代號為“GB23

58、1280”。該字符集共收錄常用漢字6763個，圖形符號682個。 它規(guī)定所有漢字和圖形符號組成一個9494的矩陣，在此方陣中，每一行稱為“區(qū)”，用區(qū)碼來標識；每一列稱為“位”，用位碼來標識，一個符號由一個區(qū)碼和一個位碼共同標識。 區(qū)碼和位碼分別需要7個二進制位，同樣，為了方便，各采用一個字節(jié)表示。所以在計算機中，漢字（符號）國標碼占用兩個字節(jié)。,2020/11/20,120,2.4.1 點陣字符,3、兩種編碼的區(qū)別 那么，給定一個字節(jié)，如何來確定它代表的是ASCII碼，還是國標碼的區(qū)碼和位碼呢？通常采用字符中冗余的最高位來標識： 最高位為0時，表示ASCII碼；最高位為1時，表示漢字編碼的區(qū)碼（高位字節(jié)）或位碼（低位字節(jié)）。 4、機內(nèi)碼 機內(nèi)碼： 計算機內(nèi)表示字符的編碼 1、西文字符 西文字符的機內(nèi)碼就是ASCII碼。2、中文字符國標碼為：2020H+區(qū)位碼的十六進制表示機內(nèi)碼為：8080H+國標碼 即：A0A0H+區(qū)位碼的十六進制表示,2020/11/20,121,2.4.1 點陣字符,3、舉例“啊”字的區(qū)位碼為1601，轉(zhuǎn)換為十六進制表示應為1001H（區(qū)碼16轉(zhuǎn)為10H，位碼01轉(zhuǎn)為01H）。于是，“啊”