基本圖形元素的生成算法

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

2、y和x=-y。若已知圓弧上一點(x,y),可以得到其關(guān)于四條對稱軸的其它7個點，這種性質(zhì)稱為圓的八對稱性。因此，只要掃描轉(zhuǎ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); },兩種直接離散的方法:,離散點:,離散角度:,開根，三角函數(shù)運算，計算量大，不可取。,利用隱函數(shù)方程:x2+y2=r2(Xi,yi=sqrt(r2-y2))--

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

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

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

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

8、當d＞=0時，P取P2得到一個初步算法： y=r for(x=0;x=0 右下方 y=y+1;},考慮用d的增量1)若d＜0，取P1，再下一個象素的判別式為：        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，再下一個象素的判別式為：        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的初始值(在第一個象

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

12、< 0 對應于 e < -0.25     又因為：e的初值e0為整數(shù)，運算過程中的分量也為整數(shù)，    所以：e < -0.25 等價于 e < 0,程序如下(完全用整數(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算法,一個圓的圓周可以分成四個象限，每個象限所占的圓周稱為四分圓，其第一象限的稱為第一四分圓，以此類推。每一四分圓又分為兩個45°C圓心角所對

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

17、xi,yi)開始，按順時針方向產(chǎ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|,圓于點P(xi,yi)附近光柵網(wǎng)格的相交關(guān)系只有五種。如下圖：假設像素P(xi,yi) 為最佳逼近理想圓弧的點,

18、 下一個像素只可能為正右方像素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到圓的距離, 這時應取D為下一個像素。 而當δHD=0時, 二者均可, 約定取正右方像素H。,對于情形①, 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或D。若2ΔD+2yi-1 0, 則這時應取D為下一個像素。,而對于情形②。 這時, H、 D都在圓內(nèi), 而在這段圓弧上, y是x的單調(diào)遞減函數(shù), 所以只能取H為下一個像素。 又ΔH<0且ΔD<0, 因此, 2ΔD+2y-1=ΔH+ΔD＜0與情形①的判別條件一致。 可見在ΔD<0的情況下, 若2(ΔD+

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

22、=0時, 二者均可取, 約定取右下方像素D。 對于情形③, 由于右下方像素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的符號, 在情形③判斷應取D或V 。 2ΔD-2x

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

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

25、di=0時 選D(xi+1,yi-1),從以上的討論中可知, δHD和δDV可由ΔD推算出來, 因而該算法的關(guān)鍵在于求ΔD。 ΔD可用增量法計算。 若下一個像素為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,若下一個像素為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 若下一個像素為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)時，x i+1 =xi+1 , y i+1 =yi

28、 d i+1=di+2 x i+1 +1,選D(xi+1,yi-1)時，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)時，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;