計(jì)算機(jī)圖形學(xué)直線(xiàn)三種算法

1、計(jì)算機(jī)圖形學(xué)直線(xiàn)三種算法1實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)實(shí)驗(yàn)，進(jìn)一步理解直線(xiàn)段掃描轉(zhuǎn)換的DDA算法、中點(diǎn)畫(huà)線(xiàn)自算法及bresenham算法的基本原理，掌握以上算法生成直線(xiàn)段的基本過(guò)程。通過(guò)編程，掌握在C/C+環(huán)境下完成用DDA算法、中點(diǎn)畫(huà)線(xiàn)算法及bresenham算法對(duì)任意直線(xiàn)段的掃描轉(zhuǎn)換，以及在C/C+環(huán)境下完成用中點(diǎn)畫(huà)圓及橢圓的繪制方法。2.實(shí)驗(yàn)內(nèi)容：閱讀openGL三維程序設(shè)計(jì)(電子書(shū))第二部分第四章，掌握OpenGL基本建模方法，并調(diào)試其中程序。參考教材第6章，編程實(shí)現(xiàn)整數(shù)DDA算法、中點(diǎn)畫(huà)線(xiàn)法和Bresenham畫(huà)線(xiàn)法，繪制直線(xiàn)(直線(xiàn)寬度和線(xiàn)型可自定)。DDA直線(xiàn)生成：算法原理：DDA直線(xiàn)生成算法描

2、述：給定一直線(xiàn)起始點(diǎn)(xO,yO)和終點(diǎn)(x1,y1)。分別計(jì)算dx=x1-x0,dy=y1-y0。計(jì)算直線(xiàn)的斜率k=dy/dx。當(dāng)|k|1時(shí)轉(zhuǎn)向3);當(dāng)|k|=1時(shí)，轉(zhuǎn)向4);當(dāng)x每次增加1時(shí)，y增加k。即(xi,yi)T(xi+1,yi+k)。直到xi增加到x1。并且每次把得到的坐標(biāo)值利用系統(tǒng)函數(shù)掃描顯示出來(lái)。但要注意對(duì)/坐標(biāo)要進(jìn)行int(y+0.5)取整運(yùn)算。結(jié)束。對(duì)y每次增加1時(shí)，x增加1/k,卩(xi,yi)T(xi+1/k,yi+1)。直到y(tǒng)i增加到y(tǒng)1.并且每次把得到的坐標(biāo)值利用系統(tǒng)函數(shù)掃描顯示出來(lái)。但要注意對(duì)fabs(dy)steps=fabs(dx);elsesteps=fa

3、bs(dy);xIncrement=float(dx)/float(steps);NYStartn=0X(n)0.5則卻右上方點(diǎn)p2,否則取正右方點(diǎn)pl。取直線(xiàn)初始點(diǎn)(xO,yO),dx=x1-x0,dy=y1-y0,e=-dx并且將當(dāng)前點(diǎn)掃描并顯示；若e0,則下一點(diǎn)掃描值為(x=x+1,y=y+1)并且e=e+2*dy,轉(zhuǎn)向2)直到x=x1,轉(zhuǎn)向4)；若exEnd)x=xEnd;y=yEnd;xEnd=x0;elsex=x0;y=y0;while(xx+;if(p0)p+=twoDy;elsey+;p+=twoDyMinusDx;glBegin(GL_POINTS);glVertex2i(x

4、,(int)(y+0.5);glEnd();glFlush();voidmyDisplay(void)glClear(GL_COLOR_BUFFER_BIT);glColor3f(0.0,0.0,1.0);lineBres(40,40,150,150);voidmain(intargc,char*argv)glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);glutInitWindowPosition(50,100);glutInitWindowSize(400,400);glutCreateWindow(Hello);

5、init();glutDisplayFunc(myDisplay);glutMainLoop();2.2.4實(shí)驗(yàn)結(jié)果：2.3中點(diǎn)畫(huà)線(xiàn)生成:2.3.1中點(diǎn)畫(huà)線(xiàn)算法原理：算法基本思想：假設(shè)與圓弧最近的點(diǎn)P(x,y)像素點(diǎn)已經(jīng)確定，那么，下一個(gè)像素點(diǎn)只能是其正右方點(diǎn)P1(x+1,y)或者右下方的點(diǎn)P2(x+1,y-1)兩者之一。所以類(lèi)比中點(diǎn)畫(huà)直線(xiàn)發(fā)的思想取這兩個(gè)點(diǎn)的中點(diǎn)M(x+1,y-0.5)帶入圓系方程入圓系方程F(x,y)=xA2+yA2-rA2o顯然如果F(M)0,則說(shuō)明M點(diǎn)位于圓方程之內(nèi)，則應(yīng)取P1為下一像素點(diǎn)。反之應(yīng)該取P2為下一像素點(diǎn)。注：只就圓的八分之一進(jìn)行討論，其它的各點(diǎn)可以利用直線(xiàn)

6、和坐標(biāo)軸進(jìn)行對(duì)稱(chēng)變換得到，只需掃描顯示即可。具體算法如下:輸入圓心位置和圓的半徑作為圓周上的第一點(diǎn)P(0,R)；計(jì)算決策關(guān)鍵參數(shù)的初始值di=dO=1.25-R在每個(gè)初始點(diǎn)(xi,yi)=(0,R),根據(jù)決策參數(shù)判斷下一點(diǎn)的位置，具體如下:如果di0,下一個(gè)像素點(diǎn)的位置(xi+1,yi-1)并且di+1=di+2.0*(xi-yi)+5。將經(jīng)過(guò)判斷后的結(jié)果賦值給新的(xi,yi)，轉(zhuǎn)至3);直到xy為止，轉(zhuǎn)向4);算法結(jié)束，退出執(zhí)行。2.3.1中點(diǎn)畫(huà)線(xiàn)流程圖：2.3.2中點(diǎn)畫(huà)線(xiàn)關(guān)鍵代碼：#include#include#include#includeintx1,y1,x2,y2;voidIni

7、tGL(void)auxInitDisplayMode(AUX_SINGLE|AUX_RGBA);auxInitPosition(0,0,640,480);auxInitWindow(FirstAuxOpenGLDemo);glClearColor(0.6,0.6,0.6,0.0);glClear(GL_COLOR_BUFFER_BIT);voidMidpointLine(intx1,inty1,intx2,inty2)inti,x,y;floatdx,dy,d,k;dx=x2-x1;dy=y2-y1;k=dy/dx;if(k=1)d=0.5-k;x=x1;y=y1;glVertex2i(x1

8、,y1);for(i=1;i=dx;i+)glBegin(GL_POINTS);glVertex2i(x,y);x+;if(d1)d=1-0.5*k;x=x1;y=y1;glVertex2i(x1,y1);for(i=1;i=dy;i+)glBegin(GL_POINTS);glVertex2i(x,y);y+;if(d0)x+;d=d+1;elsed=d-k+1;Sleep(10);glEnd();/結(jié)束繪制glFlush();進(jìn)行刷新voidCALLBACKDraw(void)/glBegin(GL_POINTS);MidpointLine(x1,y1,x2,y2);/glEnd();/結(jié)

9、束繪制/glFlush();/進(jìn)行刷新voidmain(void)printf(pleaseinputthestartpoint(x1,y1):);scanf(%d,%d,&x1,&y1);printf(pleaseinputthestartpoint(x2,y2):);scanf(%d,%d,&x2,&y2);lnitGL();初始化auxMainLoop(Draw);/進(jìn)行繪制2.3.3實(shí)驗(yàn)結(jié)果:2.3.4算法分析與比較：DDA算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線(xiàn)的速度較慢oBresenham畫(huà)線(xiàn)算法僅僅使用增量整數(shù)計(jì)算，計(jì)算相對(duì)DDA較快，中點(diǎn)圓畫(huà)線(xiàn)同那個(gè)Bresenham畫(huà)線(xiàn)算法一樣，中點(diǎn)方法使用整數(shù)加減來(lái)計(jì)算沿圓周的像素位置，計(jì)算比DDA復(fù)雜但計(jì)算速度快！2.3.5總結(jié)：在本次實(shí)驗(yàn)開(kāi)始之前，了解vc畫(huà)圖知識(shí)不多，所以前期準(zhǔn)備工作量很大，加之剛開(kāi)始接觸圖形學(xué)的知識(shí)，應(yīng)用不是很熟練。經(jīng)過(guò)大致一周的算法研究和相關(guān)的準(zhǔn)備工作，才使得實(shí)驗(yàn)得以完成。印象深刻的是在