線的生成算法

3.2線的生成算法3.2.1直線的生成算法在數(shù)學(xué)上，直線是沒有寬度的、由無數(shù)個點構(gòu)成的集合。對直線進(jìn)行光柵化就是在顯示器所給定的有限個像素矩陣中，確定最佳逼近于該直線的一組像素。然后按照掃描線順序，對這些像素進(jìn)行寫操作，這就是直線的掃描轉(zhuǎn)換。對于水平線、垂直線和45°線，選擇哪些光柵元素是顯而易見的，而對于其它方向的直線，像素的選擇較為困難。3.2線的生成算法3.2.1直線的生成算法斜率截距直線方程：k表示斜率，b是y軸截距。給定兩個端點P0(x0,y0)和P1(x1,y1)，線段的斜率k和截距b為：從起點到終點，x每次增加(或減少)1，用直線方程計算對應(yīng)的y值，再用SetPixel(x,int(y+0.5),color)輸出該像素。復(fù)雜度：乘法+加法+取整3.2線的生成算法3.2.1直線的生成算法上述方法稱為直線繪制基本算法，缺點：每步都需要一個浮點乘法運(yùn)算和一個四舍五入運(yùn)算，所以效率太低。由于一個圖中可以包含成千上萬條直線，所以要求繪制算法應(yīng)盡可能的快。數(shù)值微分(DDA)法給定兩個端點P0(x0,y0)和P1(x1,y1)，線段的斜率k和截距b為：畫線過程從x的左端點x0開始，向x右端點步進(jìn)，步長=1(個像素)，計算相應(yīng)的y坐標(biāo)：y=kx+b，取像素點(x,round(y))作為當(dāng)前點的坐標(biāo)。計算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx當(dāng)x=1時yi+1=yi+k即：當(dāng)x每遞增1，

y遞增k(即直線斜率)。

圖3-1DDA算法基本原理

復(fù)雜度：加法+取整數(shù)值微分(DDA)法上述采用的增量計算方法稱為數(shù)值微分算法(DigitalDifferentialAnalyzer，簡稱DDA)。數(shù)值微分法的本質(zhì)，是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。圖3-1DDA算法基本原理

voidDDALine(intx0,inty0,intx1,inty1,intcolor)inti； floatdx,dy,length,x,y;if(fabs(x1-x0)>=fabs(y1-y0))length=fabs(x1-x0);elselength=fabs(y1-y0);

dx=(x1-x0)/length;dy=(y1-y0)/length;i=1;x=x0;y=y0;while(i<=length){SetPixel(int(x+0.5),int(y+0.5),color);x=x+dx;y=y+dy;i++;

xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5圖3-2直線段的DDA掃描轉(zhuǎn)換

舉例:線段P0(0,0)和P1(5,2)的DDA方法掃描轉(zhuǎn)換DDA算法與基本算法相比，減少了浮點乘法，提高了效率。但是x與dx、y與dy用浮點數(shù)表示，每一步要進(jìn)行四舍五入后取整，不利于硬件實現(xiàn)，因而效率仍有待提高。Bresenham算法Bresenham算法是1965年提出的，基本原理是：借助于一個誤差量(直線與當(dāng)前實際繪制像素點的距離)，來確定下一個像素點的位置。算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查誤差量的符號，就可以確定該下一列的像素位置。

圖3-3根據(jù)誤差量來確定理想的像素點

假設(shè)當(dāng)前直線上的像素坐標(biāo)為(xi,yi)，那么下一步需要在列xi+1上確定掃描線y的值。y值要么不變，要么遞增1，可通過比較d1和d2來決定。

如圖3-3所示，對于直線斜率k在0~1之間的情況，從給定線段的左端點P0(x0,y0)開始，逐步處理每個后續(xù)列(x位置)，并在掃描線y值最接近線段的像素上繪出一點。yi+1yyixixi+1d2d1根據(jù)誤差項d的值來決定是否增1的過程如下：設(shè)Δy=y1－y0,Δx=x1－x0，則k=Δy/Δx，代入上式，得：

是常量，與像素位置無關(guān)。其中yi+1yyixixi+1d2d1則ei的計算僅包括整數(shù)運(yùn)算，其符號與(d1-d2)的符號相同。當(dāng)ei<0時，直線上理想位置與像素(xi＋1，yi)更接近，應(yīng)取右方像素；(2)當(dāng)ei>0時，直線上理想位置與像素(xi＋1，yi＋1)更接近，應(yīng)取右上方像素；(3)當(dāng)ei=0時，兩個像素與直線上理想位置一樣接近，可約定取(xi＋1，yi＋1)。對于第i+1步，誤差參數(shù)為：此時參數(shù)c已經(jīng)消去，且xi+1=xi+1,得：如果選擇右上方像素，即，則：如果選擇右方像素，即，則：對于每個整數(shù)x，從線段的坐標(biāo)端點開始，循環(huán)的進(jìn)行誤差量的計算。起始像素(x0，y0)的誤差參數(shù)為：voidBresenham_Line(intx0,inty0,intx1,inty1,intcolor){intdx=x1-x0,dy=y1-y0,e=2*dy-dx;intx=x0,y=y0;for(inti=0;i<=dx;i++){SetPixel(x,y,color);x++;if(e>=0){y++;e=e+2*dy-2*dx;}else{e=e+2*dy;}}}當(dāng)0<k<1時的Bresenham畫線算法程序xye00-110321-331142-552-1圖3-4直線段的Bresenham畫線法舉例:線段P0(0,0)和P1(5,2)的Bresenham畫線法思考：k的取值不在0~1之間時，如何處理？X，Y對換當(dāng)k>1時，x總是增加1，再用Bresenham誤差量判別式可以確定y是否增加1。當(dāng)k<0時，要考慮x或y不是遞增1，而是遞減1。（不要）3.2.2圓的生成算法為了方便起見，可以只考慮中心在原點、半徑為整數(shù)的圓：對于中心不在原點的圓，可通過平移變換進(jìn)行轉(zhuǎn)化。圓上的點關(guān)于X軸、Y軸以及45o線對稱，只要實現(xiàn)1/8圓的掃描轉(zhuǎn)換就可以利用對稱性得到完整的圓。最容易想到的算法如下：根據(jù)圓的基本方程，可以沿X軸，x從0到，以單位步長計算對應(yīng)的y值來得到圓周上每點的位置：該算法每一步均包含浮點乘法和開方運(yùn)算，且所繪制的像素間間隔不一，隨著x的增加，間隔越來越大。3.2.2圓的生成算法一種消除不等間距的方法是使用極坐標(biāo)來計算沿圓周的點，此時，圓使用參數(shù)方程來表示：該算法使用了三角函數(shù)和浮點運(yùn)算，運(yùn)算速度仍然很慢。與直線繪制算法相似，理想的圓繪制算法也是只需作一些簡單的整數(shù)和判別運(yùn)算，常見的有中點畫圓法。中點畫圓法以從(0，R)到(，)的1/8圓為例，假定當(dāng)前已確定了圓弧上的一個像素點為，那么，下一個像素只能是右方的或右下方的。中點畫圓法構(gòu)造函數(shù)F(x,y)=x2+y2-R2,F(x,y)=0，點在圓上；F(x,y)>0，點在圓外；F(x,y)<0，點在圓內(nèi)；設(shè)M為P1和P2的中點，即M為(xp+1,yp-0.5)若F(M)<0，M在圓內(nèi)，說明P1點離圓弧更近，則取P1為下一個像素；若F(M)>0，M在圓外，說明P2點離圓弧更近，則取P2為下一個像素；若F(M)=0，M在圓上，P1、P2可任取其一，這里約定取P2。中點畫圓法根據(jù)上述原理，構(gòu)造判別式dp=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若dp<0，應(yīng)則取P1為下一個像素，且判別式變?yōu)椋篸p+1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=dp+2xp+3若dp>=0，應(yīng)則取P2為下一個像素，且判別式變?yōu)椋篸p+1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=dp+2(xp-yp)+5這里，我們?nèi)?0,R)為第一個像素，判別式的初值為：d0=F(1,R-0.5)=1.25-R中點畫圓法為了避免浮點數(shù)運(yùn)算，可令e=d-0.25，此時初始化運(yùn)算d=1.25-R對應(yīng)于e=1-R，判別式d<0對應(yīng)于e<-0.25。又由于e的初值為整數(shù)，且運(yùn)算過程中增量也是整數(shù)，所以e始終是整數(shù)，可以用e<0代替e<-0.25。最后將1/8圓弧做對稱處理就能夠得到完整的圓。voidCirclePoints(intx,inty,intcolor){SetPixel(x,y,color);SetPixel(y,x,color);SetPixel(-x,y,color);SetPixel(y,-x,color);SetPixel(x,-y,color);SetPixel(-y,x,color);SetPixel(-x,-y,color);SetPixel(-y,-x,color);}根據(jù)（x,y）畫出另外對稱的七個點MidPointCircle(intr,intcolor){ intx=0,y=r;inte=1-r;CirclePoints(x,y,color);//做對稱處理