計算機(jī)圖形學(xué)圖形生成技術(shù)PPT課件

1、3.1 直線圖形3.2 二次曲線3.3 字 符3.4 區(qū)域填充第第3章章 二維圖形生成技術(shù)二維圖形生成技術(shù)第1頁/共85頁3.1 直線圖形第2頁/共85頁3.1 直線圖形直線圖形 掃描轉(zhuǎn)換直線段就是計算出落在直線段上或充分靠近它的一串象素，并以此象素近似代替原連續(xù)直線段在屏幕上顯示的過程。本節(jié)介紹畫線的三個常用算法：數(shù)值微分法，中點(diǎn)畫線法和Bersenham法。 為了簡化算法，給出兩點(diǎn)假設(shè)： 直線段的寬度為1； 直線段的斜率|k| 1；對于斜率 |k| 1 的直線段的生成方法可對算法做適當(dāng)改變得到。第3頁/共85頁DDA算法算法 DDA是數(shù)值微分法（Digital Differential A

2、nalyzer）的縮寫。設(shè)直線起點(diǎn)（x1,y1），終點(diǎn)（x2,y2），則斜率m（|m| 1） 為： y=mx+b；b = (y2x1 - y1x2)/(x2 - x1) m=dy/ dx； dy=y2-y1；dx=x2-x1； 畫直線算法: 給定直線的兩個端點(diǎn)坐標(biāo)后，求得m和b；然后在x1xx2范圍內(nèi)對x取整數(shù)，利用公式進(jìn)行浮點(diǎn)乘法和加法運(yùn)算，求得y值后再取整數(shù)值，即可得到需要的直線上的像素點(diǎn)。 計算方法的缺點(diǎn)是計算量大。3.1直線圖形直線圖形第4頁/共85頁 直線圖形上的點(diǎn)是由有先后順序的一列像素點(diǎn)構(gòu)成的，相鄰的兩點(diǎn)應(yīng)滿足: m= (yi+1-yi ) / (xi+1-xi ) 于是有： y

3、i+1 = yi + m(xi+1-xi ) 其中(xi,yi)是第i步求得的像素點(diǎn)坐標(biāo)，(xi+1, yi+1)是第i + 1步求得的像素點(diǎn)坐標(biāo)。據(jù)前面的分析，應(yīng)要求：| xi+1-xi | 1 | yi+1-yi | 1并要求較大者為1。即如果|m| 1 ，則要求 | xi+1-xi | 1 | yi+1-yi | 1那么，當(dāng)|m| 1 時，則要求 | xi+1-xi |1 | yi+1-yi |1DDA算法算法第5頁/共85頁于是，畫直線的DDA算法可分兩種情況描述為:a.|m| 1 當(dāng)x2-x1 0時： xi+1 xi 1； yi+1 yi m 當(dāng)x2-x1 0時： xi+1 xi 1

4、； yi+1 yi mb.|m| 1 當(dāng)y2-y1 0時： yi+1 yi 1；xi+1 xi 1/m； 當(dāng)y2-y1 0時： yi+1 yi 1；xi+1 xi 1/m；DDA算法算法第6頁/共85頁象限|dx|dy| ?DxDy1a1m1b1/m12a-1m2b-1/m13a-1-m3b-1/m-14a1-m4b1/m-1DDA算法算法假設(shè)：xi+1 - xi Dxyi+1 - yi Dy Dy = m Dx 則有：xi+1 xi + Dxyi+1 yi +Dy Dy = m Dx第7頁/共85頁DDA算法算法研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個規(guī)律：1、當(dāng)|dx|dy|時 |Dx|=1， |Dy

5、|=m； 當(dāng)|dx|= -1 & k = 1) y=y1; for(x=x1;x=x2;x+) putpixel(int)x,(int)(y+0.5),color); y+=k; else k=1/k; x=x1; for(y=y1;y0F(x,y)0F(x,y)0假定已經(jīng)求得像素（xi,yi,r），由四舍五入取整原則可知（下圖） 21y,21yyr ,ir ,ii由于P0P1的斜率在0,1之間，故x = xi +1和P0P1的交點(diǎn)的縱坐標(biāo)： 23y,21yyr , ir , i1i在直線x = xi +1 上，區(qū)間內(nèi)存在兩個像素，NE和E。 23y,21yr , ir , iNEM（

6、xi,yi,r）（xi,yi）E（xi+1,yi+1）x=xix=xi+1P0P1第16頁/共85頁中點(diǎn)畫線法中點(diǎn)畫線法 NEM（xi,yi,r）（xi,yi）E（xi+1,yi+1）x=xix=xi+1 根據(jù)取整原則，當(dāng)Q(xi+1,yi+1)在中點(diǎn)M（ xi+1,yi,r+0.5 ）上方時，取像素NE，否則取像素E，即：而“(xi+1,yi+1) 在M上方”等價于“F(M)0di=0第19頁/共85頁void MidpointLine (int x0,int y0,int x1, int y1,int color) int y , x , d1, d2, d, x, y; y = y1 -

7、 y0; x =x1-x0; d= x - 2*y; d1=-2*y ; d2=-2* (y -x ); x=x0; y=y0; putpixel(x, y, color); while (xx1) if (d0，則yi+1=yi+1，否則yi+1=yi。因此算法的關(guān)鍵在于簡便地求出d1-d2的符號。Bresenham畫線法畫線法第25頁/共85頁 d1-d2 =2y-2yi-1=2 (xi+1)-2yi+2b-1 用dx乘等式兩邊，并令Pi=dx(d1-d2)代入上述等式，得：Pi=2xidy-2yidx+2dy+dx(2b-1) (1) d1-d2是我們用以判斷符號的誤差。由于在1a象限，

8、dx總大于0，所以Pi仍舊可以用作判斷符號的誤差。用Pi+1- Pi得： Pi+1 =Pi+2dy-2dx(yi+1-yi) 其中yi+1-yi=0或1；(2) 若Pi0 ，則d1d2， yi+1-yi=1； Pi+1 =Pi+2dy-2dx 若Pi0 ，則d10 then yi+1=yi+1 else yi+1=yi；3、畫點(diǎn)（xi+1, yi+1）；4、求下一個誤差Pi+1： if Pi0 then Pi+1=Pi+2dy-2dx else Pi+1=Pi+2dy；5、i=i+1; if i|dy|為分支，并分別將2a, 3a象限的直線和3b, 4b象限的直線變換到1a, 4a和2b, 1

9、b方向去，以求得程序處理的簡潔。Bresenham畫線法畫線法第29頁/共85頁Bersenham程序程序void line (x1, y1, x2, y2, c)int x1, y1, x2, y2, c; int dx，dy，x，y，p，const1，const2，inc，tmp； dx=x2-x1; dy=y2-y1; if (dx*dy=0) inc=1; else inc=-1; /*準(zhǔn)備x或y的單位遞變值*/ if (abs(dx)abs(dy) if(dx0) /*將2a,3a象限方向的直線變換到1a,4a象限方向去*/ tmp=x1; x1=x2;x2=tmp;tmp=y1;y

10、1=y2; dx=-dx; dy=-dy; p=2*dy-dx; const1=2*dy; const2=2*(dy-dx); /*注意此時誤差的變化參數(shù)取值*/ x=x1; y=y1; set_pixel(x, y, c); 第30頁/共85頁Bersenham程序程序 while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=const2; set_piexl(x, y, c); else /*將3b,4b象限方向的直線變換到2b, 1b象限方向去*/ if (dy0) tmp=x1; x1=x2;x2=tmp;tmp=y1;y1=y2； dx=

11、-dx; dy=-dy; p=2*dx-dy; /*注意此時誤差的變化參數(shù)取值*/ const1=2*dx; const2=2*(dy-dx); x=x1; y=y1; set_pixel (x, y, c); 第31頁/共85頁Bersenham程序程序 while (yy2) y+; if (p0) p+=const1; else x+=inc; p+=const2; set_pixel (x, y, c); 第32頁/共85頁3.2 二次曲線二次曲線第33頁/共85頁3.2 二次曲線二次曲線v 圓弧擬合法 給出圓心坐標(biāo)xc， yc和半徑r，逐點(diǎn)畫出圓的公式有兩種：1、直角坐標(biāo)法：(x-x

12、c)2+(y-yc)2=r2，導(dǎo)出 當(dāng)x-xc從-r到r作加1遞增時，可以求出對應(yīng)的圓周點(diǎn)的y坐標(biāo)。但是這樣求出的圓周上的點(diǎn)是不均勻的；|x-xc|越大，對應(yīng)生成圓周點(diǎn)之間的圓周距離也就越長。2、極坐標(biāo)法： x=xc+rcos y=yc+rsin 從0,360 作加1遞增時，由此式便可求出圓周上均勻分布的360個點(diǎn)的x, y坐標(biāo)。22c)xx(ryyc 第34頁/共85頁3.2.1 圓弧的中點(diǎn)算法 本節(jié)考慮圓的圓心在原點(diǎn)的圓弧的掃描轉(zhuǎn)換算法，對于圓心為任意點(diǎn)的圓可通過平移再掃描轉(zhuǎn)換，再平移到原來的位置。(xc,yc)rv 圓的八對稱性 圓心位于原點(diǎn)的圓有四條對稱軸： x0； y0； xy； x

13、y 如圖若已知圓弧上一點(diǎn)(x,y)，就可以得到其關(guān)于四條對稱軸的七個對稱點(diǎn)，這種性質(zhì)稱為圓的八對稱性。為了求出表示整個圓弧的象素集，只要掃描轉(zhuǎn)換1/8圓弧就可以了。第35頁/共85頁圓弧的中點(diǎn)算法圓弧的中點(diǎn)算法寫出圓弧的隱函數(shù)方程形式：0),(222RyxyxF則圓弧F(x,y)=0具有正負(fù)劃分性，如圖: 圓弧外的點(diǎn)：F(X，Y)0 圓弧內(nèi)的點(diǎn)：F(X，Y)0 圓弧上的點(diǎn)：F(X，Y)=0第36頁/共85頁 討論1b象限內(nèi)的1/8圓弧段，假定計算出象素（xi，yi,r）由四舍五入的取整原則得： 在圓弧段內(nèi)，圓弧上各點(diǎn)的切線斜率k滿足-1,0，豎直線x=xi+1和圓弧的交點(diǎn)的縱坐標(biāo)滿足 P(xi

14、+1,yi,r-0.5)圓弧的中點(diǎn)算法圓弧的中點(diǎn)算法 21y,21yyr , ir , ii 21y,23yyr , ir , i1i第37頁/共85頁)M(Fdi 則變?yōu)椋篜(xi+1,yi,r-0.5)圓弧的中點(diǎn)算法即為生成圓弧的中點(diǎn)判別方法。 0d1y0dyyir , iir , ir ,1i當(dāng)當(dāng)當(dāng)當(dāng) 0d5)yx(2d0d3x2d0dR1)21y(2)21y(1)1x(2)1x(0dR)21y(1)1x(2)1x(0dR)23y(1)1x(2)1x(0dR)21y(1)1x(2)1x(R)21y()2x()21y, 2x(Fdir , iiiiiii2r , i2r , ii2ii22

15、r , ii2ii22r , ii2ii22r , ii2i22r ,1i2ir ,1ii1i 欲判斷M點(diǎn)是在交點(diǎn)上方還下方，只需把M代入F(x,y),并檢查它的符號。判別式：第38頁/共85頁圓弧的中點(diǎn)算法判別式和di+1構(gòu)成了完整的中點(diǎn)算法，這兩個遞推式的初值條件為：x,y的初值：(x0,y0,r)=(0，R) d 的 初 值: d0=F(x0+1, y0,r-0.5) = F(1, R-0.5) = 1+(R-0.5)2-R 2 = 1.25-R 算法中有浮點(diǎn)數(shù)，用e=d-0.25代替，初始化運(yùn)算d0 = 1.25 R 對應(yīng)于 e0= 1- R，判別式 d 0 對應(yīng)于 e -0.25；

16、e的初值e0為整數(shù)，運(yùn)算過程中的分量為整數(shù)，故e始終為整數(shù)所以： e -0.25 等價于 d 0。第39頁/共85頁程序如下（完全用整數(shù)實(shí)現(xiàn)）MidpointCircle(int r, int color) int x,y,d; x = 0; y = r; d = 1-r; putpixel(x,y,color); while( x y) if (d 0) d += 2*x+3; x+; else d += 2*(x-y)+5; x+ ; y-; putpixel(x,y,color); 第40頁/共85頁 考慮圓心在原點(diǎn)，圓弧在第1b象限的1/8圓弧，圓的半徑為R。假定像素點(diǎn)Pi-1是x=x

17、i-1時最靠近圓周的像素點(diǎn)，那么在x=xi-1+1時要得到的最靠近圓周的像素點(diǎn)只可能是：Hi 或Li。因為這一段圓弧曲(xi-1,yi-1)(xi-1+1,yi-1)(xi-1+1,yi-1-1)x=xi-1x=xi線隨x的增加，y單調(diào)減小，且 x 方向改變量大于y方向的改變量。由于x方向改變量為1，y方向的改變量只能在0和1之間， 因此取整后 y 坐標(biāo)的改變量只能是 0 或 1。設(shè)x = xi-1+1時圓周上點(diǎn)的y坐標(biāo)為 y，則必有下列3種關(guān)系之一成立： y yi-1 - 1或yi-1-1 y yi-1。3.2.2 Bresenham圓弧算法圓弧算法第41頁/共85頁(xi-1,yi-1)(

18、xi-1+1,yi-1)(xi-1+1,yi-1-1)x=xi-1x=xi 01yyd0yyd21i2L221iH為x = xi-1+1時圓周上點(diǎn)的y坐標(biāo)為分別與Li和Hi點(diǎn)的y坐標(biāo)平方之差，注意R2 =(xi-1+1)2+y2，則有 21i21i2L21i221iH1y1xRd1xRyd(1). 當(dāng)yi-1-1 y yi-1時，圓弧從Hi或Li兩點(diǎn)間穿過，定義dH,dL兩個量的幾何意義是從圓心到H(或L)距離的平方與到圓周距離的平方之差。如果dH dL，則Li比Hi更接近于實(shí)際的圓。反之，dHdL，則Hi比Li更接近于實(shí)際的圓。故我們把判別變量定義為dH和dL的差，用pi表示：pi = dH

19、-dL = 2(xi-1+1)2+ yi-12 + (yi-1-1)2 - 2R2當(dāng)pi 0時選擇像素點(diǎn)為Hi，否則選擇像素點(diǎn)為Li。3.2.2 Bresenham圓弧算法圓弧算法第42頁/共85頁3.2.2 Bresenham圓弧算法圓弧算法 21i21i2L21i221iH1y1xRd1xRyd總之，無論哪種情況成立，判別規(guī)則都是一致的，即當(dāng)pi 0時選擇的像素點(diǎn)為Hi；否則選擇的像素點(diǎn)為Li 。(xi-1,yi-1)(xi-1+1,yi-1)(xi-1,yi-1 -1)(2). 當(dāng)y 0；(3). 當(dāng)y yi-1時，此時圓弧曲線從Hi和Li兩點(diǎn)上方通過，顯然 的選擇是Hi和Li中y坐標(biāo)為

20、yi-1的點(diǎn)，即Hi。此時上式中定 義的dH 0，dL0 ，故同時有pi 0。pi = dH-dL第43頁/共85頁3.2.2 Bresenham圓弧算法圓弧算法pi = 2(xi-1+1)2+ yi-12 + (yi-1-1)2 - 2R2要決定下一個像素點(diǎn)，就要求出下一步的判別式pi+1。Pi+1 = 2(xi+1)2+ yi2 + (yi-1)2 - 2R2如果Pi0時，取Hi，xi=xi-1+1，yi=yi-1，得Pi+1 = Pi+4xi-1+6如果Pi 0時，取Li，xi=xi-1+1，yi=yi-1-1，得Pi+1 = Pi+4(xi-1- yi-1)+10算法每次從p1開始，以

21、后則按照上式計算下一個判別變量。把點(diǎn)(x0，y0) =(0，R)代人式，可得到 p1=2+R2+(R-1)2-2R2=3-2R第44頁/共85頁根據(jù)上面的推導(dǎo)，圓周生成算法思想為：1 求誤差初值，p1=3-2R；i=1；畫點(diǎn)(0, R)；2 求下一個光柵位置：xi+1=xi+1；if (pi0) 則 yi+1=yi； 否則 yi+1=yi-1；3 畫點(diǎn)（xi+1, yi+1）4 計算下一個誤差： if pi0 則 pi+1=pi+4xi-1+6； 否則 pi+1=pi+4(xi-1-yi-1)+10；5 i=i+1; if x=y則end；否則返2。Bresenham算法思想第45頁/共85頁

22、circle (xc, yc, radius, c) int x, y, p; x=0; y=radius; p=3-2*radius; while (xy) plot_circle_points(xc, yc, x, y, c); if (p0) p=p+4*x+6; else p=p+4*(x-y)+10; y-=1; x+=1; if (x= =y) plot_circle_points(xc, yc, x, y, c);plot_circle_points(xc, yc, x, y, c) set_pixel(xc+x, yc+y, c); set_pixel(xc-x, yc+y,

23、c); set_pixel(xc+x, yc-y, c); set_pixel(xc-x, yc-y, c); set_pixel(xc+y, yc+x, c); set_pixel(xc-y, yc+x, c); set_pixel(xc+y, yc-x, c); set_pixel(xc-y, yc-x, c);Bresenham算法程序第46頁/共85頁3.2.3 圓弧的正負(fù)法v 原 理： 設(shè)圓的方程： F(x,y)=x2 + y2 - R2=0;假設(shè)求得Pi的坐標(biāo)為(xi,yi)：則當(dāng)Pi在圓內(nèi)時， F(xi,yi) 向右- 向圓外 當(dāng)Pi在圓外時， F(xi,yi)0 - 向下- 向

24、圓內(nèi)pipiv 求得Pi點(diǎn)后選擇下一個象素點(diǎn)Pi+1的規(guī)則 當(dāng)F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi； 當(dāng)F(xi,yi) 0 取xi+1 = xi， yi+1 = yi-1； 用于表示圓弧的點(diǎn)均在圓弧附近，且使(xi,yi) 時正時負(fù)，故稱正負(fù)法。 快速計算的關(guān)鍵是F(xi,yi) 的計算，能否采用增量算法？第47頁/共85頁圓弧的正負(fù)法若已知F(xi,yi) ，計算F(xi+1,yi+1) 可分兩種情況：v當(dāng)F(xi,yi)0時 xi+1 = xi+1，yi+1 = yi F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 = (xi+1)

25、2+ yi2 -R2 = F(xi,yi) +2xi +1v當(dāng)F(xi,yi)0時 xi+1 = xi，yi+1 = yi -1 F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1第48頁/共85頁 利用曲線可用折線來逼近，每段折線越短曲線逼近越好，但執(zhí)行時間也越長。 假設(shè)圓弧的起始和終止角分別為ts和te，半徑為R，用折線代替圓弧容許的最大誤差為，如果用n段等長折線來逼近圓弧，則每段圓弧曲線對應(yīng)的圓弧角度為& =（ te - ts ）/n。當(dāng)&充分小時，圓弧和對應(yīng)弦的最大誤差是：e

26、=R1-cos(&/2)=2Rsin2(&/4) (1/8)R&2為了使e= ，把&代人上式后得到： 該式表明半徑越大，要求的誤差越小，則所用的折線段數(shù)也越多。2R2ttnse 3.2.4 圓的內(nèi)接正多邊形逼近法第49頁/共85頁 假設(shè)要畫一個半圓弧，其半徑R = 256個像素點(diǎn)單位，于是圓弧的角度為te-ts = 。若要求誤差不超過兩個像素點(diǎn)單位，即= 2 ，則所需要的折線段數(shù)n為：1342562n 即用13段折線來逼近這個半圓弧。圓的內(nèi)接正多邊形逼近法第50頁/共85頁圓的內(nèi)接正多邊形逼近法v思 想 當(dāng)一個正多邊形的邊數(shù)足夠多時，該多邊形可以和圓無限接近。即

27、 因此，在允許的誤差范圍內(nèi)，可以用正多邊形代替圓。v圓的參數(shù)方程圓邊正內(nèi)接多邊形） (nlimn 0,2tRsintyRcostx 對圓弧來說，參數(shù)t ts , te，而每一折線端點(diǎn)處的參數(shù)為 ti = ts + i&, i = 0, 1, 2, , n因此，各折線段的端點(diǎn)坐標(biāo)為 0,2tRsintyRcostxiii ti&xy第51頁/共85頁 直接利用公式求出折線的端點(diǎn)的計算是很費(fèi)時的，為此我們根據(jù)相鄰折線段的端點(diǎn)間的遞推關(guān)系來遞推地計算折線段的端點(diǎn)： 0,2tRsintyRcostxiii 在這個公式中, 三角函數(shù)值cos &，sin &是常量。于是可以

28、從x0 =Rcos ts和y0 = Rsin ts 開始進(jìn)行逐點(diǎn)遞推計算，并且在遞推計算的過程中每計算一個端點(diǎn)，只需要四次乘法和兩次加法，因而計算速度比較快，但缺點(diǎn)是計算過程中的前面的舍入誤差卻隨著遞推的過程逐步向后傳遞, 使得越靠后的點(diǎn)誤差會越大。圓的內(nèi)接正多邊形逼近法第52頁/共85頁3.2.5 橢圓的掃描轉(zhuǎn)換 對于一個標(biāo)準(zhǔn)橢圓1byax2222 可用如下隱函數(shù)形式的方程表示：F(x,y) = b2x2 + a2y2 - a2b2 = 0v 橢圓的四對稱性 中心點(diǎn)位于原點(diǎn)的橢圓有兩條對稱軸： x0； y0； 如圖若已知橢圓弧上一點(diǎn)(x,y)，就可以得到其關(guān)于兩條對稱軸的三個對稱點(diǎn)，這種性質(zhì)

29、稱為四對稱性。為了求出表示整個圓弧的象素集，需要轉(zhuǎn)換位于第一象限的四分之一橢圓，其它部分可利用四對稱性獲得。（x,y）（-x,y）（-x,-y）（x,-y）yx第53頁/共85頁 在第1象限的1/4橢圓弧當(dāng)x從0變到a時，橢圓弧的變化率是變化的，從0到-1，從-1到-，因此基于變化率為-1的點(diǎn)將第1象限的1/4橢圓弧分成兩部分，確定邊界上的像素點(diǎn)。橢圓弧上任一點(diǎn)(x,y)的法向量為： 第一象限內(nèi)變化率為-1的點(diǎn)應(yīng)滿足：1ya2xb21yyxFxyxF22 ),(),(結(jié)合橢圓方程，求得此Q點(diǎn)的坐標(biāo)是： 222222babbaa,3.2.5 橢圓的掃描轉(zhuǎn)換 當(dāng)0 xxq時，橢圓弧曲線上x方向的變

30、化大于y方向的變化，令x = 1，求解y；當(dāng)xqxa時，則令y =-1，求解x。Q ya2xb2yyxFxyxF22,),(,),( 第54頁/共85頁 當(dāng)0 xxq時，如果當(dāng)前點(diǎn)是P(xi,yi)，下一點(diǎn)(xi+1, yi+1)的選擇方法為：xi+1 = xi+1，取整后的y的改變量是0或1，下一個要選擇的點(diǎn)是H(xi+1,yi)或L(xi+1,yi -1)。根據(jù)H 和L之間中點(diǎn)的函數(shù)值進(jìn)行判別，如果F(xi+1,yi1/2) 0，表明中點(diǎn)位于橢圓內(nèi)部，則點(diǎn)H靠近橢圓，應(yīng)選擇點(diǎn)H；反之則選擇點(diǎn)L。3.2.5 橢圓的掃描轉(zhuǎn)換法向量兩分量相等上半部分下半部分M1M2PP/HLL/H/ 當(dāng)xqxa

31、時，如果當(dāng)前點(diǎn)是P/(xi,yi)，下一點(diǎn)(xi+1, yi+1)的選擇方法為：yi+1= yi1,取整后的x的改變量是0或1,下一個要選擇點(diǎn)是L/(xi, yi1)或H/(xi+1,yi1)。根據(jù)H/和L/之間中點(diǎn)的函數(shù)值進(jìn)行判別,如果F(xi+1/2, yi1) 0，表明中點(diǎn)位于橢圓內(nèi)部，則點(diǎn)H/靠近橢圓，應(yīng)選擇點(diǎn)H/ ；反之則選擇點(diǎn)L/ 。Q第55頁/共85頁基于中點(diǎn)判別規(guī)則，比較容易區(qū)分0 xxq成立否，即： b2 (xp+1) a2 (yp-0.5)其中(xp, yp )為當(dāng)前橢圓弧像素點(diǎn)。而在下一中點(diǎn)，不等式改變方向，則說明橢圓弧從上部分轉(zhuǎn)入下部分。3.2.5 橢圓的掃描轉(zhuǎn)換在上半

32、部分,法向量的y分量大在下半部分,法向量的x分量大法向量兩分量相等上半部分下半部分M1M2PPQ第56頁/共85頁橢圓的中點(diǎn)畫法 與圓弧中點(diǎn)算法類似：確定一個象素后，接著在兩個候選象素的中點(diǎn)計算一個判別式的值，由判別式的符號確定更近的點(diǎn)。圓弧的上部分，(xp,yp)中點(diǎn)(xp+1,yp-0.5)： d1= F(xp+1,yp-0.5) = b2(xp+1)2+a2(yp-0.5)2-a2b2法向量兩分量相等上半部分下半部分M1M2PP/HLL/H/第57頁/共85頁 根據(jù)d1的符號決定下一點(diǎn)是取正右方點(diǎn)，還是右下方點(diǎn)。 若d10，中點(diǎn)在橢圓內(nèi)，取H點(diǎn)，判別式更新為： d1=F(xp+2,yp-

33、0.5)=d1+b2(2xp+3) d1的增量為b2(2xp+3) 若d10，中點(diǎn)在橢圓外，取L點(diǎn)，判別式更新為： d1=F(xp+2,yp-1.5)=d1+b2(2xp+3)+a2(-2yp+2) d1的增量為b2(2xp+3)+a2(-2yp+2)v d1的初始條件 橢圓弧起點(diǎn)為(0，b)，第一個中點(diǎn)為(1，b-0.5) 初始判別式：d10=F(1,b-0.5) = b*b+a*a(-b+0.25)橢圓的中點(diǎn)畫法第58頁/共85頁v 轉(zhuǎn)入橢圓弧下部分，根據(jù)d2的符號決定下一點(diǎn)是正下方或右下方，此時判別式要初始化d2 = F(xp+0.5,yp-1) = b2(xp+0.5)2+a2(yp-

34、1)2-a2b2 若若d2 0，中點(diǎn)在橢圓內(nèi)，取H/點(diǎn)，判別式更新為： d2/ = F(xp+1.5,yp-2) = d2 + b2(2xp+2)+a2(-2yp+3) 若若d20，中點(diǎn)在橢圓外，取L/點(diǎn)，判別式更新為： d2/ = F(xp+0.5,yp-2) = d2 + a2(-2yp+3) 下半部分弧的終止條件為 y = 0橢圓的中點(diǎn)畫法第59頁/共85頁 MidpointEllipse(a,b, color) int a,b,color, int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y

35、,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); 中點(diǎn)畫橢圓的程序第60頁/共85頁3.3 字字 符符第61頁/共85頁 在計算機(jī)圖形學(xué)中，字符可以用不同的方式表達(dá)和生成。常用的方法有點(diǎn)陣式、矢量式和編碼式。3.3 字符的生成字符的生成 點(diǎn)陣式字符將字符表示為一個矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。常用的點(diǎn)陣大小有7 9、 916 、 1624等。

36、矩陣中每個元素是一位二進(jìn)制數(shù)。如圖示，當(dāng)點(diǎn)陣位圖(a) 中為1的位,表示字符筆劃經(jīng)過此位,對應(yīng)到圖 (b) 所示的象素圖案中為字符顏色；為 0 的位表示字符筆劃不經(jīng)過此位置，對應(yīng)此位的象素圖案中字符顏色應(yīng)置為背景色。 點(diǎn)陣式字符第62頁/共85頁a 標(biāo)準(zhǔn)字符b 粗體c 旋轉(zhuǎn)d 斜體粗體字的算法是：當(dāng)字符原型中每個象素被寫入幀緩存寄存器的指定 位置（xi, yi）時，同時被寫入（xi+1, yi）。旋轉(zhuǎn)90的算法是：把字符原型中每個象素的x, y坐標(biāo)彼此交換，并使y 值改變符號后，再寫入幀緩存寄存器的指定位置。斜體字的算法是：從底到頂逐行拷貝字符，每隔n行，左移一單元。3.3 字符的生成字符的生

37、成第63頁/共85頁 在筆式繪圖儀上采用矢量型字符比較合適，矢量式字符具有和圖形相一致的數(shù)據(jù)結(jié)構(gòu)。 矢量式字符 矢量式字符將字符表達(dá)為點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻畫。用矢量式表示字符“B”，由頂點(diǎn)序列a，b，c，d，e，f，e，g，h，i，j，k，j，f，a，l的坐標(biāo)表達(dá)。kjihgedcbalf3.3 字符的生成字符的生成第64頁/共85頁 方向編碼式字符 方向編碼既可用于字符的顯示，也可用于字符的繪圖機(jī)輸出。 方向編碼式字符用有限的若干種方向編碼來表達(dá)一個字符，常用的8個方向的編碼0-7，其中編碼為偶數(shù)的線段的固定長度為1，奇數(shù)的線段的固定長度為 。則一個字

38、符就用一連串方向碼表示。2kjihgedcbalf0 0 0 0 1 2 3 4 4 4 0 0 0 1 2 3 4 4 4 4 0 6 6 6 6 307512463.3 字符的生成字符的生成第65頁/共85頁3.4 區(qū)域填充區(qū)域填充第66頁/共85頁3.4 區(qū)域填充算法區(qū)域填充算法 一個區(qū)域是一組相互連通的像素點(diǎn)集合。區(qū)域的建立和定義通常采用2種方式：內(nèi)部定義區(qū)域：區(qū)域內(nèi)部的所有像素具有同一種顏色值。邊界定義區(qū)域：由多邊形輪廓線定義的內(nèi)部區(qū)域。邊界線上所有 的像素具有特定的顏色值。通常區(qū)域本身部分的 像素點(diǎn)具有不同于邊界上的像素點(diǎn)的值。內(nèi)部定義區(qū)域內(nèi)部定義區(qū)域邊界定義區(qū)域邊界定義區(qū)域v 區(qū)

39、域的定義第67頁/共85頁像素點(diǎn)之間的連通方式可分為如下兩類：3.4 區(qū)域填充算法區(qū)域填充算法v 區(qū)域的連通方式四連通：兩個像素點(diǎn)是上下或左右相連的，則 稱其為四連通的。 即一個像素點(diǎn)最多 與上、下、左和右四個相鄰像素點(diǎn)具 有連通關(guān)系。八連通：兩個像素點(diǎn)是上下或左右相連的，或 者對角線方向相連的，則稱其為八連 通的。即一個像素點(diǎn)最多與上、下、 左和右四個及四個對角點(diǎn)共八個相鄰 像素點(diǎn)具有連通關(guān)系。第68頁/共85頁3.4 區(qū)域填充算法區(qū)域填充算法 區(qū)域填充：給出一個區(qū)域的邊界，要求對邊界范圍內(nèi)的所有象素單元賦予指定的顏色代碼。填色算法分為兩大類： 種子填充（Seed Filling） 掃描線轉(zhuǎn)

40、換填充（Scan-Line Filling）算法v 區(qū)域填充第69頁/共85頁種子填充算法種子填充算法種子填充算法思想： 假設(shè)某點(diǎn)(x , y ) 是已知的，將它作為種子，對相鄰像素進(jìn)行搜索。如果相鄰像素在填充區(qū)域內(nèi)且又沒有改為新顏色值，則作為新的種子繼續(xù)遞歸搜索下去。如果相鄰像素已不在填充區(qū)內(nèi)，則說明已經(jīng)達(dá)到邊界。選取區(qū)域內(nèi)一點(diǎn)為種子種子壓棧彈出種子給種子著新色color2分別判斷（x-1，y）, （x，y -1 ）, （x+1，y）, （x，y +1 ）相鄰像素的顏色邊界顏色color1且相鄰像素的顏色新色color2?作為新種子壓棧棧非空嗎？結(jié) 束非邊界或已填充區(qū)域內(nèi)像素且未填充邊界定義

41、填充算法YNYN選取區(qū)域內(nèi)一點(diǎn)為種子種子壓棧彈出種子給種子著新色color2分別判斷（x-1，y）, （x，y -1 ）, （x+1，y）, （x，y +1 ）相鄰像素的顏色=color1?作為新種子壓棧棧非空嗎？結(jié) 束非區(qū)域內(nèi)像素區(qū)域內(nèi)像素內(nèi)定義填充算法第70頁/共85頁四相鄰種子填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺點(diǎn)？第71頁/共85頁void seed_filling (x, y, fill_color, boundary_color)int x, y, fill_color, bo

42、undary_color; int c; c=inquire_color(x, y); if(c boundary_color) & (c fill_color) putpixel(x, y, fill_color); seed_filling(x+1, y, fill_color, boundary_color); seed_filling(x-1, y, fill_color, boundary_color); seed_filling(x, y+1, fill_color, boundary_color); seed_filling(x, y-1, fill_color, bou

43、ndary_color); 四鄰法種子邊界填色算法描述四鄰法種子邊界填色算法描述第72頁/共85頁void FloodFill4(int x,int y,int fillColor,int oldColor) int c; c=inquire_color(x, y); if (c = oldColor) putpixel(x, y, fillColor); FloodFill4(x+1, y, fillColor, oldColor); FloodFill4(x-1, y, fillColor, oldColor); FloodFill4(x, y+1, fillColor, oldColor

44、); FloodFill4(x, y-1, fillColor, oldColor); 四鄰法種子內(nèi)定義填色算法描述四鄰法種子內(nèi)定義填色算法描述第73頁/共85頁四連通區(qū)域邊界填充算法的填充結(jié)果八連通區(qū)域邊界填充算法的填充結(jié)果區(qū)域連通方式對填充結(jié)果的影響第74頁/共85頁v 缺點(diǎn)缺點(diǎn)： (1) 有些象素會入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。 (2) 遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素 都引起一次遞歸，進(jìn)、出棧，費(fèi)時費(fèi)內(nèi)存。v 改改進(jìn)算法，減少遞歸次數(shù)，提高效率。種子填充算法種子填充算法第75頁/共85頁多邊形掃描轉(zhuǎn)換填充算法 該算法適應(yīng)邊界定義區(qū)域的填充。其基本思想：用水平掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。將這些交點(diǎn)按照 x 坐標(biāo)進(jìn)行分類，將分類后的交點(diǎn)成對取出，作兩個端點(diǎn)，以所需要填的顏色畫水平直線。多邊形掃描完畢，填充完成。 左、右頂點(diǎn)處理 水平邊處理 掃描線與邊的求交方法 活性邊表第76頁/共85頁左、右頂點(diǎn)處理 掃描線與多邊形的每個頂點(diǎn)相交時，會同時產(chǎn)生兩個交點(diǎn)，這是因為一個頂點(diǎn)同屬于多邊形兩條邊的端點(diǎn)。 左頂點(diǎn)2：y1y2y2y3其中y1, y2, y3是三個相鄰的頂點(diǎn)的y坐標(biāo)。對多邊形的所有左、右頂點(diǎn)作如下處理:左、右頂點(diǎn)的入邊（以頂點(diǎn)為終點(diǎn)的邊），即1, 2邊之終點(diǎn)刪去。即：左頂點(diǎn)：入邊（x1