講二維圖形生成算法.ppt

第三講 二維圖形生成算法,二維圖形生成算法,二維圖形生成算法 線段的掃描變換 基本增量算法 中點(diǎn)線算法 Bresenham畫線算法 圓與橢圓的掃描變換,線段的掃描變換,線段的掃描變換,象素，中心位于均衡柵格上的離散圓點(diǎn) 。 直線掃描變換算法就是獲得一系列象素的坐標(biāo)，使這些象素落在所要近似的理想直線上或位于該直線的附近。原則上講，象素序列應(yīng)盡可能逼近理想的直線，而且盡可能直一些。,基本增量算法,直線方程：y=mx+b ，0m1， m= y/ x= y ； x=1，xi+1=xi+ 1，yi+1=yi+m,基本增量算法,增量算法的定義：每一步都是根據(jù)前一步進(jìn)行增量計(jì)算。這種算法通常被稱作數(shù)值微分(DDA)算法。DDA(Digital Differential Analyzer algorithm)是用數(shù)值方法解決微分方程的一種手段 。 請(qǐng)注意如果m1，則x的步進(jìn)會(huì)使y的步進(jìn)超過1，此時(shí)，如果采用上述算法將會(huì)使得點(diǎn)亮的象素個(gè)數(shù)太少，畫出來的線沒有很好的模擬理想直線，例如：從(0,2)點(diǎn)到(2,100)點(diǎn)畫線，則會(huì)只點(diǎn)亮3個(gè)點(diǎn)來表示，光柵點(diǎn)太稀了。解決辦法是顛倒x與y的位置，給y以單位增量，而x的增量為x=y/m=1/m，即取x軸和y軸中變化最快的軸作為參考軸以保證直線被光柵化后有足夠多的象素。,基本增量算法的實(shí)現(xiàn),#include/*加入c圖形庫*/ #include/*數(shù)學(xué)庫*/ #include/*鍵盤控制*/ void Line(int x0,int y0,int x1,int y1,int value) /*從坐標(biāo)(x0,y0)到(x1,y1)畫顏色為value的直線*/ int x; float dx,dy,m,y; dx=x1-x0; dy=y1-y0; m=dy/dx;/*取得斜率*/ y=y0; for(x=x0;x=x1;x+) putpixel(x,(int)(y+0.5),value);/*找到距理想直線最近的點(diǎn)，putpixel為畫點(diǎn)函數(shù)*/ y=y+m; /*計(jì)算下一步的y值，增幅為m*/ ,基本增量算法,考慮基本增量算法是否是最優(yōu)的！ 1.運(yùn)算符的快速性 采用增量思想的DDA算法,每計(jì)算一個(gè)象素，只需計(jì)算一個(gè)加法。加法已經(jīng)是最快的算法了（加減乘除開方三角函數(shù)等） 2.參數(shù)運(yùn)算的快速性 DDA算法的計(jì)算中含有浮點(diǎn)數(shù)運(yùn)算。把浮點(diǎn)運(yùn)算的加法變成整數(shù)加法，因?yàn)檎麛?shù)的加法比浮點(diǎn)的加法要快很多,中點(diǎn)線算法,直線方程：F(x,y)=0 F(x,y)= x dy+B dx -y dx 中點(diǎn)M=(x+1,y+1/2) d=F(M） d 下一點(diǎn)中點(diǎn)取法取決于本次點(diǎn)亮點(diǎn)是E還是NE,中點(diǎn)線算法,中點(diǎn)線算法的目的在于改進(jìn)DDA算法，使得只采用整形變量參加運(yùn)算。 假設(shè)當(dāng)前為old點(diǎn)，下一點(diǎn)為new點(diǎn)，則有： dold=a(xp1)+b(yp1/2)c 如果選擇的是E，M在x方向增加一個(gè)步長(zhǎng)，那么： dnew=F(xp2，yp1/2)=a(xp2)b(yp1/2)c dnew=dolda 用E表示選擇E后加入到d的增量，則E=a=dy。 如果選擇的是NE，那么M在x方向和y方向上均需增加一個(gè)步長(zhǎng)，那么： dnew=F(xp2，yp3/2)=a(xp2)b(yp3/2)c dnew=doldab 用NE表示選擇NE后加入到d的增量，則 NE=ab=dydx。,增量初始值的計(jì)算,因?yàn)榈谝粋€(gè)象素是端點(diǎn)(x0，y0)，可直接計(jì)算d的初始值dstart，以此決定是選E還是NE。第一個(gè)中點(diǎn)在(x01，y0 1/2)處，有： dstart=F(x01，y01/2)=a(x01)b(y01/2)c =ax0by0cab/2 =F(x0，y0)ab/2 由于(x0，y0)在線上，因此F(x0，y0)=0；故 dstart=ab/2=dydx/2。,對(duì)DDA的改進(jìn),為消除分?jǐn)?shù)部分，將F乘上2重新定義F：F(x，y)=2(axbyc)，使每個(gè)常量和判斷變量均乘上2，但這并不影響判斷變量d的符號(hào)，因此仍可作為中點(diǎn)檢測(cè)的標(biāo)準(zhǔn)。 最終結(jié)果：每一步dnew值的計(jì)算只需做簡(jiǎn)單的加法，無需耗時(shí)的乘法。,中點(diǎn)線算法舉例,中點(diǎn)線算法,改進(jìn)：中點(diǎn)算法進(jìn)一步把效率提高到每步只做一個(gè)整數(shù)加法，如果再想在算法的效率上作文章已經(jīng)是不可能了。但是DDA和中點(diǎn)算法嚴(yán)格依賴直線方程，不能再推廣。而下面講述的Bresenham畫線算法不但能解決直線的光柵化，還能解決圓弧、拋物線甚至自由曲線的光柵化問題，使算法的覆蓋域擴(kuò)大。,Bresenham算法,01時(shí)，只保留d的小數(shù)部分作為d的新值，x=x+1, y則根據(jù)d 0.5來決定點(diǎn)亮(x+1,y)還是 (x+1,y+1)。,?,Bresenham算法,令e=d0.5。 則當(dāng)e0時(shí)，下一象素的y坐標(biāo)增加1，而當(dāng)e0時(shí)，下一象素的y坐標(biāo)不變。e的初值為0.5。 從而利用e代替d，來判斷下一點(diǎn)的取舍,圓的掃描變換,利用對(duì)稱性可以加速畫圓過程; 只需計(jì)算45弧段,通過對(duì)稱變換可完成整圓.,圓的掃描變換(中點(diǎn)算法）,思路:當(dāng)前顯示點(diǎn)P=(Xp,Yp),取第二八分圓 圓方程為x2+y2=R2 ,因此令:F(x,y)=x2+y2 -R2 中間點(diǎn)M=(Xp+1,Yp-(1/2) 令: d=F(M) 判斷: d=0 中點(diǎn)在圓上; 點(diǎn)亮可取E 或 SE d0 中點(diǎn)在圓外;點(diǎn)亮可取SE,橢圓的掃描變換（中點(diǎn)算法）,思路: 方程為: F(X,Y)=b2x2+a2y2-a2b2=0 由于對(duì)稱性,只考慮第一象限中的橢圓生成 把此象限內(nèi)的弧段分成兩段,以法向量中兩分量相等處為分界線,既斜率為-1處. 上部中點(diǎn)為(xp+1,yp-(1/2),亮點(diǎn)選擇有E和SE,取y的中值. 下部中點(diǎn)為(xp+(1/2),yp-1),亮點(diǎn)選擇有S和SE,取x的中值. 判斷何時(shí)從上部轉(zhuǎn)入下部的條件: 法向量的兩個(gè)分量是否相等. 起始點(diǎn):(0,b); 終止點(diǎn):(a,0),曲線DDA算法,y=f (x) x; 可按步長(zhǎng)逐點(diǎn)畫出這條曲線 例如對(duì)于圓周上任意一點(diǎn)的坐標(biāo)方程為： x=RcosA+ x0 y=RsinA+y0 可有: dx=-(y-y0)dA