計算機地圖制圖原理與方法基本圖形生成算法

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

Pi最接近圖形的象素

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

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

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

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)柵格交點表示象素點位置5整理課件直線的斜率：k=(Y1-Y0)/(X1-X0)為討論方便，假定|k|<=1直線方程：Ｙ=k*X+B設(shè)Ｘ的增量為Ｄx=１，可得如下Ｙ的增量方程：Yi+1=kXi+1+B=k(Xi+Dx)+B=kXi+B+kDx=Yi+kDx=Yi+k6整理課件畫直線的DDA算法從起點開始朝終點方向畫點(x,y)在x軸或y軸上走一個單位長（沿x軸還是y軸取決于直線的傾斜角）由直線的傾斜程度（斜率或斜率的倒數(shù)）決定另一坐標的增量，獲得下一點的座標將x或y四舍五入，得(x,y)若(x,y)不是終點則繼續(xù)起點終點未四舍五入前最后選定的點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;}}

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

當d<0時，M在L(Q點)下方，取P2為下一個象素；

當d>0時，M在L(Q點)上方，取P1為下一個象素；

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

若d<0時，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量為a＋b。畫線從(x0,y0)開始，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整理課件中點畫線算法示例起點終點初始值：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生成直線的Bresenham算法xiXi+1YiYi+1CDBA12整理課件原理：假定直線斜率,0<k<1,起點坐標為(x,y);下一個點亮象素可能是：(x+1,y)或(x+1,y+1)。這可通過d值的大小來確定:d=d+k,當d>1時d=d-1;當d<=0.5取(x+1,y)，否則取(x+1,y+1)。令e=d-0.5,顯然e的初值為-0.5。這樣可用e的符號來進行判斷。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整理課件思考題：如何去除上述程序中的浮點運算、乘除法？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}}}

程序改進從速度考慮，還有那些可以改進？16整理課件Bresenham畫線算法示例起點終點初始值：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討論象素點的選取是否有規(guī)律？有何用17整理課件直線生成算法的改進

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

圓形根據(jù)圓的對稱性將其擴展到四個象限即可獲得整圓

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

即是找出逼近圓的一組象素，按掃描線順序，對這些象素進行寫操作。

下面僅以圓心在原點的圓為例，討論圓的生成算法。1.圓弧掃描算法X2+Y2=R221整理課件Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當X取整數(shù)時，Y須圓整。缺點：浮點運算，開方，圓整，不均勻。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

值后，即可以增量方式獲得圓周上的坐標，然后取整可得象素坐標。但要采用浮點運算、乘法運算。23整理課件3.中點法利用圓的對稱性，只須討論1/8圓。MP1P2P（Xp，Yp）P為當前點亮象素，那么，下一個點亮的象素可能是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間的中點，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為下一個象素，那么再下一個象素的判別式為：

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為下一個象素，那么再下一個象素的判別式為：

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--;}}}該程序如何改進，提高效率？28整理課件Bresenham畫圓算法討論、圓的中點算法與Bresenham算法是否一致？29整理課件橢圓的生成算法F(x,y)=b2x2+a2y2-a2b2=0橢圓的對稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點作為分界點。橢圓上一點處的法向： N(x,y)=(F)'xi+(F)'yj =2b2xi+2a2yj30整理課件在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量兩分量相等M1M2在當前中點處，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即： b2(Xp+1)<a2(Yp-0.5),而在下一中點，不等式改變方向，則說明橢圓弧從上部分轉(zhuǎn)入下部分31整理課件橢圓的中點畫法與圓弧中點算法類似：確定一個象素后，接著在兩個候選象素的中點計算一個判別式的值，由判別式的符號確定更近的點先討論橢圓弧的上部分 設(shè)(Xp，Yp)已確定，則下一待選像素的中點是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b232整理課件根據(jù)d1的符號來決定下一像素是取正右方的那個，還是右上方的那個。 若d1＜0，中點在橢圓內(nèi)，取正右方象素，判別式更新為： d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量為b2(2Xp+3)當d1≥0，中點在橢圓外，取右下方象素，更新判別式： d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量為b2(2Xp+3)+a2(-2Yp+2)33