直線段的掃描轉(zhuǎn)換-計算機專業(yè)-OpenGL實驗-Exp

1、精選優(yōu)質(zhì)文檔-傾情為你奉上Exp - University實 驗 報 告課程名稱 計算機圖形學(xué)實驗 實驗項目 直線段的掃描轉(zhuǎn)換 專業(yè)班級 姓 名 Exp 學(xué) 號 QQ: 指導(dǎo)教師 成 績 日 期 2011.11.22 一、實驗?zāi)康?、通過實驗，進一步理解直線段掃描轉(zhuǎn)換的DDA算法、中點bresenham算法以及改進bresenham算法的基本原理；2、 掌握以上算法生成直線段的基本過程；3、 通過編程，會在C/C+環(huán)境下完成用DDA算法、中點bresenham算法及bresenham算法對任意直線段的掃描轉(zhuǎn)換。二、實驗設(shè)備及實驗環(huán)境1、計算機（每人一臺）2、VC+6.0或其他C/C+語言程序設(shè)

2、計環(huán)境三、實驗學(xué)時2學(xué)時四、實驗內(nèi)容用DDA算法中點bresenham算法及bresenham算法實現(xiàn)任意給定兩點的直線段的繪制（直線寬度和線型可自定）。注：1、實驗報告的內(nèi)容: 一、實驗?zāi)康?；二、實驗原理；三、實驗步驟；四、實驗結(jié)果；五、討論分析（完成指定的思考題和作業(yè)題）；六、改進實驗建議。 2、各專業(yè)可在滿足學(xué)校對實驗教學(xué)基本要求的前提下，根據(jù)專業(yè)特點自行設(shè)計實驗報告的格式，所設(shè)計的實驗報告在使用前需交實踐教學(xué)管理科備案。五、實驗步驟1、復(fù)習(xí)有關(guān)直線掃描轉(zhuǎn)換算法的基本原理，明確實驗?zāi)康暮鸵螅?2、依據(jù)算法思想，繪制程序流程圖；3、設(shè)計程序界面，要求操作方便；4、用C/C+語言編寫源程序

3、并調(diào)試、執(zhí)行；5、分析實驗結(jié)果6、對程序設(shè)計過程中出現(xiàn)的問題進行分析與總結(jié)；7、打印源程序或把源程序以文件的形式提交；8、按格式要求完成實驗報告。六、實驗報告要求：1、各種算法的基本原理；2、各算法的流程圖3、實驗結(jié)果及分析（比較三種算法的特點，界面插圖并注明實驗條件）4、實驗總結(jié)（含問題分析及解決方法）七、實驗原理1、DDA算法(數(shù)值微分法)數(shù)值微分法(DDA法，Digital Differential Analyzer)是一種直接從直線的微分方程生成直線的方法。給定直線的兩端點P0(x0, y0)和P1(x1, y1)，得到直線的微分方程如下：DDA算法原理：由于直線的一階導(dǎo)數(shù)是連續(xù)的，而

4、且對于x和y是成正比的，故此可以通過在當(dāng)前位置上分別加上二個小增量來求下一點的x，y坐標(biāo)，如下圖所示。則有：其中，=1/max(|x|,|y|)分兩種情況討論如下：（1） max(|x|,|y|)=|x|，即|k|1的情況：（2） max(|x|,|y|)=|y|，此時|k|1：注意：由于在光柵化的過程中不可能繪制半個像素點，因此對求出的xi+1，yi+1的值需要四舍五入。2、中點Bresenham算法給定直線的兩個端點坐標(biāo)，可以得到直線的方程為：    此時直線將平面分成三個區(qū)域：對于直線上的點，F(xiàn)(x, y)=0；對于直線上方的點，F(xiàn)(x, y)>0；對

5、于直線下方的點，F(xiàn)(x, y)<0，如下圖所示。圖52 直線將平面分為三個區(qū)域    基本原理：根據(jù)直線的斜率確定或選擇變量在x或y方向上每次 遞增一個單位，而另一方向的增量為1或0，它取決于實際直線與 相鄰像素點的距離，這一距離稱為誤差項。    如下圖所示，假定0k1，x是最大位移方向。算法每次在x方向上 加1，y方向上加0或加1。設(shè)當(dāng)前點是P(xi, yi)，則下一個點在Pu(xi+1, yi+1) 和Pd(xi+1, yi)中選一。以M點表示Pu與Pd的中點，又設(shè)Q點是理想直線與 垂線x=xi+1的交點，根據(jù)Q點與M點的

6、位置判斷選取哪一個點。 圖53 Brensemham算法生成直線的原理構(gòu)造判別式如下：   當(dāng)d<0時，M在Q點下方，Pu距離Q點近，取Pu點；    若d>0，M在Q點上方，Pd距離Q點近，取Pd點；    若d=0，M與Q點重合，Pu和Pd都合適，約定取Pd。故有：誤差項遞推：（1） 當(dāng)d<0時，下一個候選點為(xi+1, yi+1)，再下兩個候選點為(xi+2, yi+1)和(xi+2, yi+2)，他們的中點為(xi+2, yi+1.5)，故有：此時，d的增量為1k。（2） 當(dāng)d

7、>0時，下一個候選點為(xi+1, yi)，再下兩個候選點為(xi+2, yi)和(xi+2, yi+1)，他們的中點為 (xi+2, yi+0.5)，故有：此時，d的增量為k。 初始值d的計算：但此時算法中仍然包含了浮點數(shù)運算，由于這里我們僅使用了判別式d的符號，所以可以用2dx代替d來擺脫小數(shù)。用2dx代替d ,令D2dx 則：3、改進Bresenham算法基本原理：假定直線段的0k1，如下圖所示，過各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線起點到終點的順序 計算直線與各垂直網(wǎng)格線的交點，交點與網(wǎng)格線的誤差值為d。    當(dāng)d>0.5時

8、，直線更接近于像素點(x+1, y+1)，當(dāng)d<0.5時，更接近于 (x+1,y)；當(dāng)d=0.5時，約定取(x+1, y)。 圖5-4 改進的Brensemham算法繪制直線的原理誤差項d的初始值為0，每走一步有d=d+k，一旦y方向上走了一步，就要把d減去1。即有：改進1：令e=d0.5改進2：用E=2ex來替換e八、算法流程1、DDA算法(數(shù)值微分法)適用于任意斜率的直線2、中點Bresenham算法以下算法流程僅適用于斜率為0<k<1的直線對于斜率為 k>1的直線，只需交換x、y的地位即可。對于負斜率（包括 -1<k<0和k< -1），只需把對應(yīng)

9、的正斜率的掃描算法修正為“一個坐標(biāo)遞減而另一個坐標(biāo)遞增”即可。而對于水平、垂直、和k=±1的直線，無需使用掃描算法，直接繪制即可。3、改進Bresenham算法以下算法流程僅適用于斜率為0<k<1的直線對于斜率為 k>1的直線，只需交換x、y的地位即可。對于負斜率（包括 -1<k<0和k< -1），只需把對應(yīng)的正斜率的掃描算法修正為“一個坐標(biāo)遞減而另一個坐標(biāo)遞增”即可。而對于水平、垂直、和k=±1的直線，無需使用掃描算法，直接繪制即可。九、實驗結(jié)果及分析 以下實驗窗口所顯示的直線為隨機生成兩端點后再繪制，并非通過鼠標(biāo)點擊輸入端點。1、DD

10、A掃描算法繪制效果由于描點較密集，通過拉伸窗體放大后可清晰看到“粒子”的效果：DDA算法的核心代碼為：void DDALine(int StrX,int StrY,int EndX,int EndY) int dx=EndX-StrX;int dy=EndY-StrY;double x=(double)StrX;double y=(double)StrY;int epsl=max(abs(dx),abs(dy);double xIncre=(double)dx/(double)epsl;double yIncre=(double)dy/(double)epsl;/*描點*/ glBegin(G

11、L_POINTS);for(int k=0;k<=epsl;k+) /原形:putpixel(int)(x+0.5),(int)(y+0.5),color);glVertex2i(int)(x+0.5),(int)(y+0.5);x+=xIncre;y+=yIncre;glEnd();return;通過按B鍵可改變繪制的像素點的半徑，從而改變線粗。這部分功能主要利用OpenGL函數(shù)glPointSize()實現(xiàn)。顯示效果如下（圖片已放大）加粗像素點后，可明顯地看到直線的鋸齒效果：通過在OpenGL窗口上點擊右鍵，會彈出菜單，選擇對應(yīng)的項可重新選擇算法繪制同一條直線，用不同的顏色標(biāo)識。菜單

12、效果如下：創(chuàng)建菜單的主要代碼如下：void Menu(void)int MainMenu=glutCreateMenu(ProcessMenu); /創(chuàng)建主菜單glutAddMenuEntry("DDA(數(shù)值微分)算法掃描直線",1);glutAddMenuEntry("中點Bresenham算法掃描直線",2);glutAddMenuEntry("改進Bresenham算法掃描直線",3);glutAttachMenu(GLUT_RIGHT_BUTTON);/將主菜單與鼠標(biāo)右鍵關(guān)聯(lián)return;2、中點Bresenham算法繪制效果

13、 通過菜單切換，可直接得到用中點Bresenham算法繪制同一條直線，繪制效果如下：中點Bresenham算法的核心代碼為：void Mid_Bresenham(int StrX,int StrY,int EndX,int EndY) int k;int detaX=EndX-StrX;int detaY=EndY-StrY;int sign=detaX*detaY;if(StrX=EndX)/直線垂直于x軸，斜率不存在k=-10;else if(StrY=EndY)/直線垂直于y軸，斜率k=0k=0;else if(detaX=detaY)/y=x,k=1k=1;else if(detaX=

14、-detaY)/y=-x,k=-1k=-1;else if(sign>0 && abs(detaY)>abs(detaX)/k>1k=2;else if(sign>0 && abs(detaY)<abs(detaX)/0<k<1k=3;else if(sign<0 && abs(detaY)>abs(detaX)/k<-1k=-2;else if(sign<0 && abs(detaY)<abs(detaX)/-1<k<0k=-3;switch(k

15、)case -10:/斜率不存在if(StrY>EndY)Swap(StrX,EndX);Swap(StrY,EndY);for(int y=StrY;y<=EndY;y+)glBegin(GL_POINTS);glVertex2i(StrX,y);glEnd();break;case 0:/k=0if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX;x<=EndX;x+)glBegin(GL_POINTS);glVertex2i(x,StrY);glEnd();break;case 1:/k=1if(S

16、trX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;x<=EndX;x+,y+)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();break;case -1:/k=-1if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;x<=EndX;x+,y-)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();break;case 2:/k>1if(St

17、rY>EndY)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int x=StrX;int y=StrY;int d=2*dx-dy;int LeftIncre=2*dx;int RightIncre=2*dx-2*dy;while(y<=EndY) glBegin(GL_POINTS);glVertex2i(x,y);glEnd();y+;if(d>=0)x+;d+=RightIncre;elsed+=LeftIncre;break;case 3:/0<k<1if(StrX&g

18、t;EndX)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int x=StrX;int y=StrY;int d=dx-2*dy;int UpIncre=2*dx-2*dy;int DownIncre=-2*dy;while(x<=EndX) glBegin(GL_POINTS);glVertex2i(x,y);glEnd();x+;if(d<0)y+;d+=UpIncre;elsed+=DownIncre;break;case -2:/k<-1if(StrY<EndY)Swap(S

19、trX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int x=StrX;int y=StrY;int d=-2*dx;int LeftIncre=-2*dx;int RightIncre=-2*dy-2*dx;while(y>=EndY) glBegin(GL_POINTS);glVertex2i(x,y);glEnd();y-;if(d<0)x+;d+=RightIncre;elsed+=LeftIncre;break;case -3:/-1<k<0if(StrX>EndX)Swap(StrX

20、,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int x=StrX;int y=StrY;int d=-dx-2*dy;int UpIncre=-2*dy;int DownIncre=-2*dx-2*dy;while(x<=EndX) glBegin(GL_POINTS);glVertex2i(x,y);glEnd(); x+;if(d>=0)y-;d+=DownIncre;elsed+=UpIncre;break;return;3、改進Bresenham算法繪制效果 通過菜單切換，可直接得到用改進Bresenha

21、m算法繪制同一條直線，繪制效果如下：改進Bresenham算法的核心代碼為：void Imp_Bresenham(int StrX,int StrY,int EndX,int EndY) int k;int detaX=EndX-StrX;int detaY=EndY-StrY;int sign=detaX*detaY;if(StrX=EndX)/直線垂直于x軸，斜率不存在k=-10;else if(StrY=EndY)/直線垂直于y軸，斜率k=0k=0;else if(detaX=detaY)/y=x,k=1k=1;else if(detaX=-detaY)/y=-x,k=-1k=-1;el

22、se if(sign>0 && abs(detaY)>abs(detaX)/k>1k=2;else if(sign>0 && abs(detaY)<abs(detaX)/0<k<1k=3;else if(sign<0 && abs(detaY)>abs(detaX)/k<-1k=-2;else if(sign<0 && abs(detaY)<abs(detaX)/-1<k<0k=-3;switch(k)case -10:/斜率不存在if(StrY&

23、gt;EndY)Swap(StrX,EndX);Swap(StrY,EndY);for(int y=StrY;y<=EndY;y+)glBegin(GL_POINTS);glVertex2i(StrX,y);glEnd();break;case 0:/k=0if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX;x<=EndX;x+)glBegin(GL_POINTS);glVertex2i(x,StrY);glEnd();break;case 1:/k=1if(StrX>EndX)Swap(StrX,En

24、dX);Swap(StrY,EndY);for(int x=StrX,y=StrY;x<=EndX;x+,y+)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();break;case -1:/k=-1if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;x<=EndX;x+,y-)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();break;case 2:/k>1if(StrY>EndY)Swap(StrX,End

25、X);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=-dy;int x=StrX;int y=StrY;while(y<=EndY)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();y+;e+=2*dx;if(e>0)x+;e-=2*dy;break;case 3:/0<k<1if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=-dx;int x=

26、StrX;int y=StrY;while(x<=EndX)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();x+;e+=2*dy;if(e>0)y+;e-=2*dx;break;case -2:/k<-1if(StrY<EndY)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=dy;int x=StrX;int y=StrY;while(y>=EndY)glBegin(GL_POINTS);glVertex2i(x,y);glEnd

27、();y-;e+=2*dx;if(e>0)x+;e+=2*dy;break;case -3:/-1<k<0if(StrX>EndX)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=dx;int x=StrX;int y=StrY;while(x<=EndX)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();x+;e+=2*dy;if(e<0)y-;e+=2*dx;break;return;4、直線重繪效果 按R鍵可實現(xiàn)該功能，主要通過srand()和rand()函數(shù)利用time(0)生成隨機的直線端點坐標(biāo)進行直線的重新繪制。5、分析討論 DDA直線掃描算法是一個增量算法，原理最為簡單，直觀且易于實現(xiàn)代碼編寫，適用于各種斜率的直線。但由于帶