線的生成算法

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

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

圖3-1DDA算法基本原理

復(fù)雜度：加法+取整數(shù)值微分(DDA)法上述采用的增量計(jì)算方法稱為數(shù)值微分算法(DigitalDifferentialAnalyzer，簡(jiǎn)稱DDA)。數(shù)值微分法的本質(zhì)，是用數(shù)值方法解微分方程，通過(guò)同時(shí)對(duì)x和y各增加一個(gè)小增量，計(jì)算下一步的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算法與基本算法相比，減少了浮點(diǎn)乘法，提高了效率。但是x與dx、y與dy用浮點(diǎn)數(shù)表示，每一步要進(jìn)行四舍五入后取整，不利于硬件實(shí)現(xiàn)，因而效率仍有待提高。Bresenham算法Bresenham算法是1965年提出的，基本原理是：借助于一個(gè)誤差量(直線與當(dāng)前實(shí)際繪制像素點(diǎn)的距離)，來(lái)確定下一個(gè)像素點(diǎn)的位置。算法的巧妙之處在于采用增量計(jì)算，使得對(duì)于每一列，只要檢查誤差量的符號(hào)，就可以確定該下一列的像素位置。

圖3-3根據(jù)誤差量來(lái)確定理想的像素點(diǎn)

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

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

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