基本圖形元素的生成算法

1、第五章 基本圖形元素的生成算法,5.1 直線的生成算法5.2 圓的生成算法5.3 橢圓的生成算法5.4 區(qū)域填充算法,5.2.1圓的中點(diǎn)轉(zhuǎn)換算法,本節(jié)我們只考慮中心在原點(diǎn)的圓弧的掃描轉(zhuǎn)換算法，對(duì)于圓心在任意點(diǎn)的圓可通過(guò)平移后再掃描轉(zhuǎn)換，再平移到原來(lái)的位置。,圓的八對(duì)稱性,圓的特征    圓被定義為到給定中心位置(xc,yc)距離為r的點(diǎn)集。圓心位于原點(diǎn)的圓有四條對(duì)稱軸x=0,y=0,x=

2、y和x=-y。若已知圓弧上一點(diǎn)(x,y),可以得到其關(guān)于四條對(duì)稱軸的其它7個(gè)點(diǎn)，這種性質(zhì)稱為圓的八對(duì)稱性。因此，只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集。,顯示圓弧上的八個(gè)對(duì)稱點(diǎn)的算法：void CirclePoints(int x,int y,int color){ putpixel(x,y,color); putpixel (y,x,color);  putpixel (-x,y,color);

3、 putpixel (y,-x,color);  putpixel (x,-y,color); putpixel (-y,x,color);  putpixel (-x,-y,color); putpixel (-y,-x,color); },兩種直接離散的方法:,離散點(diǎn):,離散角度:,開根，三角函數(shù)運(yùn)算，計(jì)算量大，不可取。,利用隱函數(shù)方程:x2+y2=r2(Xi,yi=sqrt(r2-y2))--

4、--------(Xi,yi),取整,利用參數(shù)方程x=rcos(θ) y=rsin(θ),取整（ rcos(θi) ,rsin(θi)),圓弧的正負(fù)劃分性                 F(x,y)=x2+y2-r2

5、60;=0                                圓弧外的點(diǎn)：F(X，Y)＞0 

6、   圓弧內(nèi)的點(diǎn)：F(X，Y)＜0,生成圓弧的中點(diǎn)算法考慮對(duì)象：第二個(gè)八分圓，第一象限的八分之一圓弧.,問(wèn)題：與直線情形類似    圓弧的隱函數(shù):F(X,Y)=X2+Y2-R2=0,     中點(diǎn) M=(xp+1,yp-0.5)    考慮對(duì)象：第二個(gè)八分圓，第一象限的八分之一圓弧

7、       當(dāng)F(M)＜0時(shí)，M在圓內(nèi)，說(shuō)明P1距離圓弧更近，取P1；      當(dāng)F(M)＞=0時(shí)，P取P2,構(gòu)造判別式   d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2 當(dāng)d＜0時(shí)，M在圓內(nèi)，說(shuō)明P1距離圓弧更近，取P1； 

8、當(dāng)d＞=0時(shí)，P取P2得到一個(gè)初步算法： y=r for(x=0;x=0 右下方 y=y+1;},考慮用d的增量1)若d＜0，取P1，再下一個(gè)象素的判別式為：        d1=F(Xp+2,Yp-0.5) = (Xp+2)2+(Yp-0.5)2-R2 = (Xp+1+1)2+(

9、Yp-0.5)2-R2 = (Xp+1 )2 +2(Xp+1 ) +1+(Yp-0.5)2-R2 =d+2Xp+3，      沿正右方向，d的增量為2Xp+3；,2)若d≥0，取P2，再下一個(gè)象素的判別式為：        d2=F(Xp+2,Y

10、p-1.5)=(Xp+1+1)2+(Yp-0.5-1)2-R2= (Xp+1 )2 +2 (Xp+1 ) +1+(Yp-0.5 )2 –2 (Yp-0.5 ) +1 -R2=d+(2Xp+3)+(-2Yp+2)= d+ 2(Xp-Yp)+5      沿右下方向，d的增量為2(Xp-Yp)+5    d的初始值(在第一個(gè)象

11、素(0,R)處),        d0=F(0+1, R-0.5)=1.25-R    算法中有浮點(diǎn)數(shù)，用e=d-0.25代替,所以:初始化運(yùn)算d0 = 1.25–R對(duì)應(yīng)于e0 = 1 - R         判別式 d

12、< 0 對(duì)應(yīng)于 e < -0.25     又因?yàn)椋篹的初值e0為整數(shù)，運(yùn)算過(guò)程中的分量也為整數(shù)，    所以：e < -0.25 等價(jià)于 e < 0,程序如下(完全用整數(shù)實(shí)現(xiàn)):    MidpointCircle(r,color)    I

13、nt r, color;    {int x,y,d;     x = 0; y = r; d = 1-r;     putpixcel(x,y,color);     while( x < y)   &

14、#160;  {  if (d <0)        { d += 2*x+3; x++; }       else        { d += 2*(x-y

15、)+5; x++ ; y--; }       putpixcel(x,y,color);      } },5.2.2 圓的Bresenham算法,一個(gè)圓的圓周可以分成四個(gè)象限，每個(gè)象限所占的圓周稱為四分圓，其第一象限的稱為第一四分圓，以此類推。每一四分圓又分為兩個(gè)45°C圓心角所對(duì)

16、的圓周，稱為八分圓，0 °C ~45 °C 的八分圓稱為第一八分圓。因此，如果生成了第一八分圓，整個(gè)圓就可以通過(guò)一系列變換得到。由于圓具有對(duì)稱性, 因而我們只討論圓心在原點(diǎn), 半徑為R的第一個(gè)四分圓, 如圖3.4 所示。 取(0, R)為起點(diǎn), 按順時(shí)針?lè)较蛏蓤A。,,假定圓心在圓點(diǎn)，半徑R,用算法生成第一四分圓上的像素點(diǎn)。且起點(diǎn)為（0，R)，按順時(shí)針?lè)较蛏?，這時(shí)y是x的單調(diào)遞減函數(shù)。從圓周上任意已選的像素P(

17、xi,yi)開始，按順時(shí)針?lè)较虍a(chǎn)生圓周上一新點(diǎn)?？蛇x擇的最佳象素有三個(gè)：,選擇像素點(diǎn)，就是要選擇誤差最小的。這三個(gè)像素點(diǎn)與實(shí)際圓上點(diǎn)之間的誤差可以分別表示為： d(H)=|( xi+1)2+( yi)2-R2| d(D)=|( xi+1)2+( yi-1)2-R2| d(V)=|( xi)2+( yi-1)2-R2|,圓于點(diǎn)P(xi,yi)附近光柵網(wǎng)格的相交關(guān)系只有五種。如下圖：假設(shè)像素P(xi,yi) 為最佳逼近理想圓弧的點(diǎn),

18、 下一個(gè)像素只可能為正右方像素H(xi+1, yi)、 右下方像素D(xi+1, yi-1)或正下方像素V(xi, yi-1)之一, 如圖3.5所示。,H在圓外, D、 V在圓內(nèi); H、 D、 V全在圓內(nèi)。 H、 D在圓外, V在圓內(nèi); H、 D、 V全在圓外; D在圓上, H在圓外, V在圓內(nèi);,令ΔH=(xi+1)2+yi2-R2, ΔD=(xi+1)2+(yi-1)2-R2, ΔV=xi2+(yi-

19、1)2-R2。 下面根據(jù)D(xi+1, yi-1)與圓弧的位置關(guān)系分三種情況討論。,如果ΔD0, 則D到圓的距離小于H到圓的距離, 這時(shí)應(yīng)取D為下一個(gè)像素。 而當(dāng)δHD=0時(shí), 二者均可, 約定取正右方像素H。,對(duì)于情形①, H總在圓外, D在圓內(nèi), 因而有ΔH≥0, ΔD＜0, 所以   δHD=ΔH+ΔD =(xi+1)2+yi2-R2+(xi+1)2+(yi-1)2-R2

20、 =2ΔD+2yi-1  故可根據(jù)2ΔD+2yi-1的符號(hào), 在情形①判斷應(yīng)取H或D。若2ΔD+2yi-1 0, 則這時(shí)應(yīng)取D為下一個(gè)像素。,而對(duì)于情形②。 這時(shí), H、 D都在圓內(nèi), 而在這段圓弧上, y是x的單調(diào)遞減函數(shù), 所以只能取H為下一個(gè)像素。 又ΔH<0且ΔD<0, 因此, 2ΔD+2y-1=ΔH+ΔD＜0與情形①的判別條件一致。 可見在ΔD<0的情況下, 若2(ΔD+

21、yi)-1≤0, 則應(yīng)取H為下一個(gè)像素, 否則應(yīng)取D為下一個(gè)像素。,如果ΔD>0, 這時(shí), 右下方像素D在圓外, 圓弧與候選點(diǎn)的關(guān)系只可能是③和④的情形, 最佳逼近圓弧的像素只可能是D與V二者之一。 為了確定D和V哪個(gè)更接近于圓弧, 令  δDV=|ΔD|-|ΔV| =|(xi+1)2+(yi-1)2-R2|-|xi2+(yi-1)2-R2|,若δDV0, 應(yīng)取正下方像素V。 而當(dāng)δDV

22、=0時(shí), 二者均可取, 約定取右下方像素D。 對(duì)于情形③, 由于右下方像素D在圓外, 而正下方像素V在圓內(nèi), 所以ΔD≥0, ΔV＜0, 因此 δDV=ΔD+ΔV =(xi+1)2+(yi-1)2-R2+xi2+(yi-1)2-R2 =2ΔD-2xi-1,故可根據(jù)2ΔD-2xi-1的符號(hào), 在情形③判斷應(yīng)取D或V 。 2ΔD-2x

23、i-1 0, 應(yīng)取正下方像素V。 對(duì)于情形④, D和V都在圓外, 應(yīng)取V為下一像素。 由于這時(shí)ΔD＞0且ΔV>0, 因此  2ΔD-2x-1=ΔD+ΔV＞0 可見, 在ΔD＞0的情況下, 若2ΔD-2xi-1<=0, 應(yīng)取D為下一像素, 否則取V作為下一像素。,如果ΔD=0, 這時(shí), 右下方像素D恰好在圓上, 也就是情形⑤, 應(yīng)取D作為下一像素

24、。 綜上所述, 可得計(jì)算下一像素的算法: 當(dāng)ΔD＜0時(shí), 若δHD ≤0, 則取H, 否則取D;當(dāng)ΔD＞0 時(shí), 若δDV ≤0, 則取D, 否則取V; 當(dāng)ΔD＝0時(shí), 取D。,歸納如下： 令di= |( xi+1)2+( yi-1)2-R2|當(dāng)di0 選D(xi+1,yi-1)當(dāng)di>0時(shí) δ’= d(D) - d(V) δ’0 選V (xi,yi-1)當(dāng)

25、di=0時(shí) 選D(xi+1,yi-1),從以上的討論中可知, δHD和δDV可由ΔD推算出來(lái), 因而該算法的關(guān)鍵在于求ΔD。 ΔD可用增量法計(jì)算。 若下一個(gè)像素為H(xi+1, y), 其右下方像素為 D(xi+2, yi-1), 則  Δ′D=((xi+1)+1)2+(yi-1)2-R2 =ΔD+2(xi+1)+1

26、 =ΔD+2x i+1+1 =ΔD+2x′ +1,若下一個(gè)像素為D(xi+1, yi-1), 其右下方像素為 D(xi+2, yi-2), 則  Δ′D=((xi+1)+1)2+((yi-1)-1)2-R2  =ΔD+2(xi+1)-2(yi-1)-2

27、 =ΔD+2x′-2y′-2 若下一個(gè)像素為V(xi, yi-1), 其右下方像素為 D(xi+1, yi-2), 則  Δ′D=(xi+1)2+((yi-1)-1)2-R2 =ΔD-2y′+1,選H(xi+1,yi)時(shí)，x i+1 =xi+1 , y i+1 =yi

28、 d i+1=di+2 x i+1 +1,選D(xi+1,yi-1)時(shí)，x i+1=xi+1, y i+1=yi-1 d i+1=di+2x i+1-2y i+1+2,選V (xi,yi-1)時(shí)，x i+1=xi, y i+1=yi-1, d i+1=di-2y i+1+1,Bresenh

29、am畫圓算法的偽C描述如下:   void Bresenham-Circle(r, color) int r, color; { int x, y, delta, delta1, delta2, direction; x=0; y=r; delta=2*(1-r); while(y>=0) { putpixel(x, y, color); if(delta<

30、;0) { delta1=2*(delta+y)-1; if(delta1<=0) diretion=1;,else direction=2; } else if(delta>0) { delta2=2*(delta-x)-1; if(delta2<=0) direction=2; else direcion=3

31、; } else direction=2; switch(direction) { case 1:x++; delta+=2*x+1; break;,case 2: x++; y--; delta+=2*(x-y+1) break;