計(jì)算機(jī)地圖制圖原理與方法基本圖形生成算法

第三章基本圖形生成算法圖形本章將主要研究在光柵顯示器上的直線(xiàn)、圓、橢圓等的生成算法。內(nèi)存顯存或緩存設(shè)備陣列圖形函數(shù)入口LINE（）等主機(jī)顯卡、其他接口確定象素位置寫(xiě)入顏色等屬性顯示器、打印機(jī)等由驅(qū)動(dòng)程序?qū)懭朐O(shè)備D/A轉(zhuǎn)換顯卡口并行口USB口1整理課件內(nèi)存插槽CPUGPU：生成點(diǎn)陣圖形運(yùn)行圖形程序D/A轉(zhuǎn)換：圖形顯示2整理課件3整理課件基本圖形的生成幾何圖形Ｇ＝｛Ｐi|

Pi最接近圖形的象素

｝基本圖形的生成算法任務(wù)之一就是找出所有的Ｐi.點(diǎn)表示為象素（Pixel），對(duì)應(yīng)于顯存地址單元讀寫(xiě)某一象素是硬件設(shè)備提供的最基本功能一維圖形，由一個(gè)象素寬的直線(xiàn)或曲線(xiàn)表示二維圖形由確定區(qū)域的象素表示線(xiàn)圖元的掃描轉(zhuǎn)換是基本圖形生算法的基礎(chǔ)；4整理課件3.2、直線(xiàn)的生成算法

即是找出逼近直線(xiàn)的一組象素，按掃描線(xiàn)順序，對(duì)這些象素進(jìn)行寫(xiě)操作。3.2.1.數(shù)值微分法（ＤＤＡ）

假定直線(xiàn)的起點(diǎn)、終點(diǎn)分別為：（X0,Y0),(X1,Y1)，且都為整數(shù)。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)柵格交點(diǎn)表示象素點(diǎn)位置5整理課件直線(xiàn)的斜率：k=(Y1-Y0)/(X1-X0)為討論方便，假定|k|<=1直線(xiàn)方程：Ｙ=k*X+B設(shè)Ｘ的增量為Ｄx=１，可得如下Ｙ的增量方程：Yi+1=kXi+1+B=k(Xi+Dx)+B=kXi+B+kDx=Yi+kDx=Yi+k6整理課件畫(huà)直線(xiàn)的DDA算法從起點(diǎn)開(kāi)始朝終點(diǎn)方向畫(huà)點(diǎn)(x,y)在x軸或y軸上走一個(gè)單位長(zhǎng)（沿x軸還是y軸取決于直線(xiàn)的傾斜角）由直線(xiàn)的傾斜程度（斜率或斜率的倒數(shù)）決定另一坐標(biāo)的增量，獲得下一點(diǎn)的座標(biāo)將x或y四舍五入，得(x,y)若(x,y)不是終點(diǎn)則繼續(xù)起點(diǎn)終點(diǎn)未四舍五入前最后選定的點(diǎn)17234560891234567807整理課件voidDDALine(intx0，inty0，intx1，inty1，intcolor){intx；floatdx，dy，y，k；dx=x1-x0；dy=y1-y0；k=dy/dx；y=y0；for(x=x0；x<=x1；x++){SetPixel(x，int(y+0.5)，color);y=y+k;}}

缺點(diǎn)：浮點(diǎn)運(yùn)算、取整－－》廢時(shí)，且不利于硬件實(shí)現(xiàn)。問(wèn)題：為什么｜k｜《１？，若｜k｜>１，上述算法會(huì)出現(xiàn)什么情況？應(yīng)如何處理？8整理課件3.2.2生成直線(xiàn)的中點(diǎn)畫(huà)線(xiàn)算法假定直線(xiàn)斜率k在0~1之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個(gè)象素點(diǎn)有兩種可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點(diǎn)（xp+1,yp+0.5）稱(chēng)為M，Q為理想直線(xiàn)與x=xp+1垂線(xiàn)的交點(diǎn)。當(dāng)M在Q的下方時(shí)，則取P2應(yīng)為下一個(gè)象素點(diǎn)；當(dāng)M在Q的上方時(shí)，則取P1為下一個(gè)象素點(diǎn)。這就是中點(diǎn)畫(huà)線(xiàn)法的基本原理過(guò)點(diǎn)(x0,y0)、(x1,y1)的直線(xiàn)段L的方程式為F(x,y)=ax+by+c=0，欲判斷中點(diǎn)M在Q點(diǎn)的上方還是下方，只要把M代入F（x，y），并判斷它的符號(hào)即可。為此，我們構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c

當(dāng)d<0時(shí)，M在L(Q點(diǎn))下方，取P2為下一個(gè)象素；

當(dāng)d>0時(shí)，M在L(Q點(diǎn))上方，取P1為下一個(gè)象素；

當(dāng)d=0時(shí)，選P1或P2均可，約定取P1為下一個(gè)象素；9整理課件若當(dāng)前象素處于d>=0情況，則取正右方象素P1(xp+1,yp),要判下一個(gè)象素位置，應(yīng)計(jì)算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量為a。

若d<0時(shí)，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計(jì)算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量為a＋b。畫(huà)線(xiàn)從(x0,y0)開(kāi)始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b，因

F(x0,y0)=0，所以d0=a+0.5b。其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0。voidMidpointLine(intx0，inty0，intx1，inty1，intcolor){inta，b，d1，d2，d，x，y；a=y0-y1；b=x1-x0；d=2*a+b；d1=2*a；d2=2*(a+b)；x=x0；y=y0；while(x<=x1){SetPixel(x，y，color);if(d<0)

{x++；y++；d+=d2;}else

{x++；d+=d1;}}/*while*/}/*midPointLine*/

10整理課件中點(diǎn)畫(huà)線(xiàn)算法示例起點(diǎn)終點(diǎn)初始值：a=-4;b=7;d=2*a+b=-1;d1=2*a=-8;d2=2*(a+b)=61、X0=0,Y0=0,d=-12、X1=1,Y1=1,d=53、X2=2,Y2=1,d=-34、X3=3,Y3=2,d=35、X4=4,Y4=2,d=-56、X5=5,Y5=3,d=17、X6=6,Y6=3,d=-7712345612345678008、X6=7,Y6=4,d=-111整理課件3.2.3生成直線(xiàn)的Bresenham算法xiXi+1YiYi+1CDBA12整理課件原理：假定直線(xiàn)斜率,0<k<1,起點(diǎn)坐標(biāo)為(x,y);下一個(gè)點(diǎn)亮象素可能是：(x+1,y)或(x+1,y+1)。這可通過(guò)d值的大小來(lái)確定:d=d+k,當(dāng)d>1時(shí)d=d-1;當(dāng)d<=0.5取(x+1,y)，否則取(x+1,y+1)。令e=d-0.5,顯然e的初值為-0.5。這樣可用e的符號(hào)來(lái)進(jìn)行判斷。dddd13整理課件voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy；floatk,e;dx=x1-x0；dy=y1-y0；k=dy/dx；x=x0,；y=y0；e=-0.5；for(i=0；i<=dx；i++){Setpixel(x,y,color);x=x+1；e=e+k;if(e≥0){y++；e=e-1;}}}程序如下：14整理課件思考題：如何去除上述程序中的浮點(diǎn)運(yùn)算、乘除法？15整理課件voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){dx=x1-x0,；dy=y1-y0,；e=-dx;x=x0；y=y0;for(i=0;i<=dx;i++){Setpixel(x,y,color);e=e+2*dy;x++;if(e≥0){y++;e=e-2*dx}}}

程序改進(jìn)從速度考慮，還有那些可以改進(jìn)？16整理課件Bresenham畫(huà)線(xiàn)算法示例起點(diǎn)終點(diǎn)初始值：dx=7;dy=4;k=4/7e=-7/141、X0=0,Y0=0,e=1/142、X1=1,Y1=1,e=-5/143、X2=2,Y2=1,e=3/144、X3=3,Y3=2,e=-3/145、X4=4,Y4=2,e=5/146、X5=5,Y5=3,e=-1/147、X6=6,Y6=3,e=7/14712345612345678008、X6=7,Y6=4,e=1/14討論象素點(diǎn)的選取是否有規(guī)律？有何用17整理課件直線(xiàn)生成算法的改進(jìn)

如何利用上述算法實(shí)現(xiàn)任意直線(xiàn)的繪制？18整理課件關(guān)于線(xiàn)型線(xiàn)寬的說(shuō)明實(shí)線(xiàn)就是將選到所有的點(diǎn)都畫(huà)出來(lái)虛線(xiàn)就是在所選的點(diǎn)中選相鄰的幾個(gè)畫(huà)，然后接著相鄰的幾個(gè)不畫(huà)點(diǎn)線(xiàn)就是在所選的點(diǎn)中，每隔幾個(gè)就畫(huà)一個(gè)線(xiàn)寬只對(duì)實(shí)線(xiàn)有效，實(shí)際上就是根據(jù)其傾斜角然后選定是在選中的點(diǎn)的(x+-width/2,y)或者(x,y+-width/2)也畫(huà)出來(lái)，相當(dāng)于一把近似垂直于直線(xiàn)的刷子19整理課件關(guān)于多邊形和圓形的作圖多邊形確定多邊形的頂點(diǎn)用直線(xiàn)順序連接起來(lái)

圓形根據(jù)圓的對(duì)稱(chēng)性將其擴(kuò)展到四個(gè)象限即可獲得整圓

20整理課件二、圓的生成算法

即是找出逼近圓的一組象素，按掃描線(xiàn)順序，對(duì)這些象素進(jìn)行寫(xiě)操作。

下面僅以圓心在原點(diǎn)的圓為例，討論圓的生成算法。1.圓弧掃描算法X2+Y2=R221整理課件Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時(shí)，Y須圓整。缺點(diǎn)：浮點(diǎn)運(yùn)算，開(kāi)方，圓整，不均勻。2.角度DDA法x=x0+Rcosy=y0+Rsin22整理課件dx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)d

yn+1=yn+(xn-x0)d

顯然，確定x,y的初值及d

值后，即可以增量方式獲得圓周上的坐標(biāo)，然后取整可得象素坐標(biāo)。但要采用浮點(diǎn)運(yùn)算、乘法運(yùn)算。23整理課件3.中點(diǎn)法利用圓的對(duì)稱(chēng)性，只須討論1/8圓。MP1P2P（Xp，Yp）P為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。24整理課件

構(gòu)造一函數(shù)：F（X，Y）=X2+Y2-R2F（X，Y）=0（X，Y）在圓上；F（X，Y）<0（X，Y）在圓內(nèi)；F（X，Y）>0（X，Y）在圓外。M為P1、P2間的中點(diǎn)，M=(Xp+1,Yp-0.5)有如下結(jié)論：F（M）<0取P1F（M）>=0取P2為此，可采用如下判別式：

25整理課件d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,則P1為下一個(gè)象素，那么再下一個(gè)象素的判別式為：

d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d的增量為2xp+3.26整理課件若d>=0,則P2為下一個(gè)象素，那么再下一個(gè)象素的判別式為：

d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+2(xp-yp)+5即d的增量為2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R27整理課件MidpointCircle(intr){intx,y;floatd;x=0;y=r;d=1.25-r;while(x<y){setpixel(x,y); if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}該程序如何改進(jìn)，提高效率？28整理課件Bresenham畫(huà)圓算法討論、圓的中點(diǎn)算法與Bresenham算法是否一致？29整理課件橢圓的生成算法F(x,y)=b2x2+a2y2-a2b2=0橢圓的對(duì)稱(chēng)性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線(xiàn)斜率為-1的點(diǎn)作為分界點(diǎn)。橢圓上一點(diǎn)處的法向： N(x,y)=(F)'xi+(F)'yj =2b2xi+2a2yj30整理課件在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量?jī)煞至肯嗟萂1M2在當(dāng)前中點(diǎn)處，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即： b2(Xp+1)<a2(Yp-0.5),而在下一中點(diǎn)，不等式改變方向，則說(shuō)明橢圓弧從上部分轉(zhuǎn)入下部分31整理課件橢圓的中點(diǎn)畫(huà)法與圓弧中點(diǎn)算法類(lèi)似：確定一個(gè)象素后，接著在兩個(gè)候選象素的中點(diǎn)計(jì)算一個(gè)判別式的值，由判別式的符號(hào)確定更近的點(diǎn)先討論橢圓弧的上部分 設(shè)(Xp，Yp)已確定，則下一待選像素的中點(diǎn)是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b232整理課件根據(jù)d1的符號(hào)來(lái)決定下一像素是取正右方的那個(gè)，還是右上方的那個(gè)。 若d1＜0，中點(diǎn)在橢圓內(nèi)，取正右方象素，判別式更新為： d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量為b2(2Xp+3)當(dāng)d1≥0，中點(diǎn)在橢圓外，取右下方象素，更新判別式： d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量為b2(2Xp+3)+a2(-2Yp+2)33