计算机图形学直线三种算法

1、计算机图形学直线三种算法1实验目的：通过实验，进一步理解直线段扫描转换的DDA算法、中点画线自算法及bresenham算法的基本原理，掌握以上算法生成直线段的基本过程。通过编程，掌握在C/C+环境下完成用DDA算法、中点画线算法及bresenham算法对任意直线段的扫描转换，以及在C/C+环境下完成用中点画圆及椭圆的绘制方法。2.实验内容：阅读openGL三维程序设计(电子书)第二部分第四章，掌握OpenGL基本建模方法，并调试其中程序。参考教材第6章，编程实现整数DDA算法、中点画线法和Bresenham画线法，绘制直线(直线宽度和线型可自定)。DDA直线生成：算法原理：DDA直线生成算法描

2、述：给定一直线起始点(xO,yO)和终点(x1,y1)。分别计算dx=x1-x0,dy=y1-y0。计算直线的斜率k=dy/dx。当|k|1时转向3);当|k|=1时，转向4);当x每次增加1时，y增加k。即(xi,yi)T(xi+1,yi+k)。直到xi增加到x1。并且每次把得到的坐标值利用系统函数扫描显示出来。但要注意对/坐标要进行int(y+0.5)取整运算。结束。对y每次增加1时，x增加1/k,卩(xi,yi)T(xi+1/k,yi+1)。直到yi增加到y1.并且每次把得到的坐标值利用系统函数扫描显示出来。但要注意对fabs(dy)steps=fabs(dx);elsesteps=fa

3、bs(dy);xIncrement=float(dx)/float(steps);NYStartn=0X(n)0.5则却右上方点p2,否则取正右方点pl。取直线初始点(xO,yO),dx=x1-x0,dy=y1-y0,e=-dx并且将当前点扫描并显示；若e0,则下一点扫描值为(x=x+1,y=y+1)并且e=e+2*dy,转向2)直到x=x1,转向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实验结果：2.3中点画线生成:2.3.1中点画线算法原理：算法基本思想：假设与圆弧最近的点P(x,y)像素点已经确定，那么，下一个像素点只能是其正右方点P1(x+1,y)或者右下方的点P2(x+1,y-1)两者之一。所以类比中点画直线发的思想取这两个点的中点M(x+1,y-0.5)带入圆系方程入圆系方程F(x,y)=xA2+yA2-rA2o显然如果F(M)0,则说明M点位于圆方程之内，则应取P1为下一像素点。反之应该取P2为下一像素点。注：只就圆的八分之一进行讨论，其它的各点可以利用直线

6、和坐标轴进行对称变换得到，只需扫描显示即可。具体算法如下:输入圆心位置和圆的半径作为圆周上的第一点P(0,R)；计算决策关键参数的初始值di=dO=1.25-R在每个初始点(xi,yi)=(0,R),根据决策参数判断下一点的位置，具体如下:如果di0,下一个像素点的位置(xi+1,yi-1)并且di+1=di+2.0*(xi-yi)+5。将经过判断后的结果赋值给新的(xi,yi)，转至3);直到xy为止，转向4);算法结束，退出执行。2.3.1中点画线流程图：2.3.2中点画线关键代码：#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();/结束绘制glFlush();进行刷新voidCALLBACKDraw(void)/glBegin(GL_POINTS);MidpointLine(x1,y1,x2,y2);/glEnd();/结

9、束绘制/glFlush();/进行刷新voidmain(void)printf(pleaseinputthestartpoint(x1,y1):);scanf(%d,%d,&x1,&y1);printf(pleaseinputthestartpoint(x2,y2):);scanf(%d,%d,&x2,&y2);lnitGL();初始化auxMainLoop(Draw);/进行绘制2.3.3实验结果:2.3.4算法分析与比较：DDA算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢oBresenham画线算法仅仅使用增量整数计算，计算相对DDA较快，中点圆画线同那个Bresenham画线算法一样，中点方法使用整数加减来计算沿圆周的像素位置，计算比DDA复杂但计算速度快！2.3.5总结：在本次实验开始之前，了解vc画图知识不多，所以前期准备工作量很大，加之刚开始接触图形学的知识，应用不是很熟练。经过大致一周的算法研究和相关的准备工作，才使得实验得以完成。印象深刻的是在