直線段的掃描轉(zhuǎn)換計(jì)算機(jī)專業(yè)OpenGL實(shí)驗(yàn)Exp

1、Exp - University實(shí) 驗(yàn) 報(bào) 告課程名稱 計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目 直線段的掃描轉(zhuǎn)換 專業(yè)班級(jí) 姓 名 Exp 學(xué) 號(hào) QQ:289065406 指導(dǎo)教師 成 績(jī) 日 期 2 一、實(shí)驗(yàn)?zāi)康?、通過實(shí)驗(yàn)，進(jìn)一步理解直線段掃描轉(zhuǎn)換的DDA算法、中點(diǎn)bresenham算法以及改進(jìn)bresenham算法的基本原理；2、 掌握以上算法生成直線段的基本過程；3、 通過編程，會(huì)在C/C+環(huán)境下完成用DDA算法、中點(diǎn)bresenham算法及bresenham算法對(duì)任意直線段的掃描轉(zhuǎn)換。二、實(shí)驗(yàn)設(shè)備及實(shí)驗(yàn)環(huán)境1、計(jì)算機(jī)（每人一臺(tái)）2、VC+6.0或其他C/C+語(yǔ)言程序設(shè)計(jì)環(huán)境三、實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)四

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

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

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

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

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

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

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

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

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;/*描點(diǎn)*/ 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鍵可改變繪制的像素點(diǎn)的半徑，從而改變線粗。這部分功能主要利用OpenGL函數(shù)glPointSize()實(shí)現(xiàn)。顯示效果如下（圖片已放大）加粗像素點(diǎn)后，可明顯地看到直線的鋸齒效果：通過在OpenGL窗口上點(diǎn)擊右鍵，會(huì)彈出菜單，選擇對(duì)應(yīng)的項(xiàng)可重新選擇算法繪制同一條直線，用不同的顏色標(biāo)識(shí)。菜單效果如下：創(chuàng)建菜單的主要代

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

13、用中點(diǎn)Bresenham算法繪制同一條直線，繪制效果如下：中點(diǎn)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、改進(jìn)Bresenham算法繪制效果 通過菜單切換，可直接得到用改進(jìn)Bresenham算法繪制同一條直線，繪制

21、效果如下：改進(jìn)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鍵可實(shí)現(xiàn)該功能，主要通過srand()和rand()函數(shù)利用time(0)生成隨機(jī)的直線端點(diǎn)坐標(biāo)進(jìn)行直線的重新繪制。5、分析討論 DDA直線掃描算法是一個(gè)增量算法，原理最為簡(jiǎn)單，直觀且易于實(shí)現(xiàn)代碼編寫，適用于各種斜率的直