1、Exp - University實 驗 報 告課程名稱 計算機圖形學實驗 實驗項目 直線段的掃描轉換 專業班級 姓 名 Exp 學 號 QQ:289065406 指導教師 成 績 日 期 2 一、實驗目的1、通過實驗，進一步理解直線段掃描轉換的DDA算法、中點bresenham算法以及改進bresenham算法的基本原理；2、 掌握以上算法生成直線段的基本過程；3、 通過編程，會在C/C+環境下完成用DDA算法、中點bresenham算法及bresenham算法對任意直線段的掃描轉換。二、實驗設備及實驗環境1、計算機（每人一臺）2、VC+6.0或其他C/C+語言程序設計環境三、實驗學時2學時四

2、、實驗內容用DDA算法中點bresenham算法及bresenham算法實現任意給定兩點的直線段的繪制（直線寬度和線型可自定）。注：1、實驗報告的內容: 一、實驗目的；二、實驗原理；三、實驗步驟；四、實驗結果；五、討論分析（完成指定的思考題和作業題）；六、改進實驗建議。 2、各專業可在滿足學校對實驗教學基本要求的前提下，根據專業特點自行設計實驗報告的格式，所設計的實驗報告在使用前需交實踐教學管理科備案。五、實驗步驟1、復習有關直線掃描轉換算法的基本原理，明確實驗目的和要求； 2、依據算法思想，繪制程序流程圖；3、設計程序界面，要求操作方便；4、用C/C+語言編寫源程序并調試、執行；5、分析實驗

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

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

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

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

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

8、1, y+1)，當d<0.5時，更接近于 (x+1,y)；當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算法(數值微分法)適用于任意斜率的直線2、中點Bresenham算法以下算法流程僅適用于斜率為0<k<1的直線對于斜率為 k>1的直線，只需交換x、y的地位即可。對于負斜率（包括 -1<k<0和k< -1），只需把對應的正斜率的掃描算法修正為“

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

10、較密集，通過拉伸窗體放大后可清晰看到“粒子”的效果：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(GL_POINTS);for

11、(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函數glPointSize()實現。顯示效果如下（圖片已放大）加粗像素點后，可明顯地看到直線的鋸齒效果：通過在OpenGL窗口上點擊右鍵，會彈出菜單，選擇對應的項可重新選擇算法繪制同一條直線，用不同的顏色標識。菜單效果如下：創建菜單的主要代

12、碼如下：void Menu(void)int MainMenu=glutCreateMenu(ProcessMenu); /創建主菜單glutAddMenuEntry("DDA(數值微分)算法掃描直線",1);glutAddMenuEntry("中點Bresenham算法掃描直線",2);glutAddMenuEntry("改進Bresenham算法掃描直線",3);glutAttachMenu(GLUT_RIGHT_BUTTON);/將主菜單與鼠標右鍵關聯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=-detaY)/y=-x,

14、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)case -10:/斜率

15、不存在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(StrX>EndX)S

16、wap(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(StrY>EndY)Sw

17、ap(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>EndX)Swap(S

18、trX,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(StrX,EndX);Swa

19、p(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,EndX);Swap(S

20、trY,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算法繪制效果 通過菜單切換，可直接得到用改進Bresenham算法繪制同一條直線，繪制

21、效果如下：改進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;else if(sign>

22、;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>EndY)Swap(

23、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,EndX);Swap(StrY

24、,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,EndX);Swap(StrY,

25、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=StrX;int y=St

26、rY;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();y-;e+=2*dx

27、;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鍵可實現該功能，主要通過srand()和rand()函數利用time(0)生成隨機的直線端點坐標進行直線的重新繪制。5、分析討論 DDA直線掃描算法是一個增量算法，原理最為簡單，直觀且易于實現代碼編寫，適用于各種斜率的直