图形学课程设计.doc

河南理工大学计算机科学与技术学院课程设计报告2009 2010学年第二学期课程名称 计算机图形学 设计题目 计算机图形学基本算法 演示系统设计 学生姓名 郭俊萍 学 号 320909010202 专业班级 计本09-2 指导教师 徐 文 鹏 2010 年 6 月 29 日15目 录目 录目 录I第1章设计内容与要求11.1总体目标和要求11.2内容与要求1第2章 总体设计32.1 Bresenham算法画直线32.2用Bresenham算法画圆32.3用梁友栋-Barsky算法进行线段裁剪4第3章 详细设计53.1 Bresenham算法画直线53.2 Bresenham算法画圆53.3用梁友栋-Barsky算法进行线段裁剪6第4章 功能实现74.1 Bresenham算法画直线74.2用Bresenham算法画圆94.3梁友栋-Barsky裁剪算法10第5章 总结14参考文献15第1章 基础知识第1章 设计内容与要求1.1 总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1) 巩固和实践计算机图形学课程中的理论和算法；2) 学习表现计算机图形学算法的技巧；3) 培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：Viusal C+ 6.0，VC2005或其他你认为比较熟悉的环境。1.2 内容与要求实验分为五项内容。1. 直线的生成内容：用Bresenham算法画直线要求：1) 将像素网格表现出来，建立网格坐标系2) 用橡皮筋的形式输入参数3) 鼠标移动时，显示鼠标当前位置4) 显示判别式的计算过程和下一点的选择策略5) 记录生成点的坐标，建议用表的形式6) 图形生成过程可以重复进行2. 圆弧的生成内容：用Bresenham算法画圆要求：1) 将像素网格表现出来，建立网格坐标系2) 用橡皮筋的形式输入参数3) 鼠标移动时，显示鼠标当前位置4) 显示判别式的计算过程和下一点的选择策略5) 记录生成点的坐标，建议用表的形式6) 图形生成过程可以重复进行3. 线段裁剪内容：用梁友栋-Barsky算法进行线段裁剪要求：1) 将像素网格表现出来，建立网格坐标系2) 用橡皮筋的形式输入剪裁线段3) 对于线段裁剪，线段被窗口的四条边裁剪的过程要显示出来第2章 总体设计第2章 总体设计2.1 Bresenham算法画直线2.1.1直线Bresenham算法描述Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。2.1.2直线Bresenham算法基本原理过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。2.2用Bresenham算法画圆2.2.1圆Bresenham算法描述假设圆的圆心位于坐标原点（如果圆心不在原点，可以通过坐标平移使其与原点重合），半径为R。以原点为圆心的圆C有四条对称轴：x=0,y=0,x=y和x=-y。若已知圆弧上一点P1C（x, y），利用其对称性便可以得到关于四条对称轴的其它7个点，即：P2C（x,y）， P3C（x, y），P4C（x,y），P5C（y，x），P6C（y，x），P7C（y，x），P8C（y，x）。这种性质称为八对称性。因此，只要扫描转换八分之一圆弧，就可以通过圆弧的八对称性得到整个圆。2.2.2圆Bresenham算法基本原理计算误差值Pi，以圆心为平面坐标轴原点，以Y轴正半轴向第一象限变化作基准x与y的变化关系，每点的偏移量以误差值Pi为计算基量，Pi0则yi+1yi，否则yi+1yi+1，算出y的变化量（从Y正半轴开始到1/8弧x变化快于y变化，所以x变化量为1）。Pi的递归式，当Pi小于0，Pi+1Pi+4xi+6，否则PiPi+1+4（xi+yi）+10。每画一点后根据中心对称原理在4个坐标轴同时向8个方向画点。直至到1/8弧相交（此时X等于Y）。2.3用梁友栋-Barsky算法进行线段裁剪2.3.1梁友栋-Barsky算法特点梁友栋-Barsky算法只能应用于矩形窗口的情形。通常梁友栋-Barsky算法比CohenSutherland算法效率更高，因为需要计算的交点数目减少了。更新参数u1、u2仅仅需要一次除法；线段与窗口边界的交点仅计算一次，就计算出u1、u2最后的值。相比之下，即使一条线段完全落在裁剪窗口之外，CohenSutherland算法也要对它反复求交点，而且每次求交计算都需要做乘除法。2.3.2梁友栋-Barsky算法实现1、初始化线段交点的参数：u1=0，u2=1；2、计算出各个裁剪边界的p、q值；3、根据p、q来判断：是舍弃线段还是改变交点的参数。（1） 当p0时，参数r用于更新u2。（u2=minu2，rk）（3）如果更新了u1或u2后，使u1u2，则舍弃该线段。（4）当p=0且q|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。1、画点(x1, y2); dx=x2-x1; dy=y2-y1；计算误差初值P1=2dy-dx; i=1；2、求直线的下一点位置：xi+1=xi+1；if Pi0 则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1, yi-1）；4、求下一个误差Pi+1；if Pi0 则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1; if i=y为止。误差量由(x,y)=x2+y2-R2给出。 先找递推关系，若当前d=F(x+1,y-0.5)0，则y须减1，则下一d值为d=F(x+2,y-1.5)=(x+2)2+(y-1.5)2-R2=(x+1)2+(x-0.5)2-R2+2x+3-2y+2=d+2x-2y+5，若当前d=F(x+1,y-0.5)0即d0.25，这和d0等价，所以d取初值1-R。3.3用梁友栋-Barsky算法进行线段裁剪设窗口为下列方程所确定：x=XL x=XR (记XLxXR的区域为x)y=YB y=YT (记YByYT的区域为y)则平面上任意线段P1P2在窗口内的部分为：P1P2xy 设通过P1P2的直线与窗口左、右、上、下边界的交点分别为L、R、B、T，则P1P2可见部分亦可表为：P1P2LRBT 当直线垂直时：xp1=xp2且XLxp1XR时，P1P2LRBT 等价于求P1P2BT；当直线平行时：yp1=yp2且YByp1YT时，P1P2LRBT 等价于求P1P2LR；当直线既不垂直又不平行时：xp1！= xp2且yp1！= yp2 L、R、B、T都是确定的P1P2的斜率k=( yp2-yp1)/ ( xp2-xp1)为非零或非奇异值。xB= xp1 +(YB- yp1)/k； xT= xp1 +(YT- yp1)/k；且 xB 0； xT xB，当k=0) inc=1; else inc=-1; if(abs(dx)abs(dy) if(dx0)tmp=x0;x0=x1;x1=tmp; tmp=y0;y0=y1;y1=tmp; dx=-dx;dy=-dy;d=2*dy-dx;d1=2*dy;d2=2*(dy-dx);x=x0;y=y0;putpixel(x,y);while(xx1) x+; if(d0) d+=d1; else y+=inc; d+=d2; putpixel(x,y); else if(dy0) tmp=x0;x0=x1;x1=tmp; tmp=y0;y0=y1;y1=tmp; dx=-dx;dy=-dy; d=2*dx-dy; d1=2*dx; d2=2*(dx-dy); x=x0; y=y0; putpixel(x,y); while(yy1) y+; if(d0) d+=d1; else x+=inc; d+=d2; putpixel(x,y); 4.2用Bresenham算法画圆核心代码：void plotC(int x,int y,int xc,int yc) putpixel(xc+x,yc+y); putpixel(xc+x,yc-y); putpixel(xc-x,yc+y); putpixel(xc-x,yc-y); putpixel(xc+y,yc+x); putpixel(xc+y,yc-x); putpixel(xc-y,yc+x); putpixel(xc-y,yc-x);void Bresenham_Circle(int xc,int yc,int r)/Bresenham函数画圆 int x,y,d; y=r; d=3-2*r; x=0; while(x=y) plotC(x,y,xc,yc); if(d0) d+=4*x+6; else d+=4*(x-y)+10; y=y-1; x=x+1; 4.3梁友栋-Barsky裁剪算法剪裁前：剪裁后：核心代码：int clipTest(float p,float q,float *u1,float *u2) /裁剪算法int retVal;retVal=1; /*retVal为标志变量，0：表示舍弃；1：表示可见。float r;if(p*u2)retVal=0;accept=false;else if(r*u1) *u1=r; /*u1取进入点的最大参数值else if(p0.0) r=q/p;if(r*u1) retVal=0;accept=false;else if(r*u2)*u2=r; /*u2取离开 点的最小参数值else if(q0.0) /*p=0，且q0。平行于边界，而且在界外的线retVal=0;accept=false;return retVal;void clipLine(int xwmin,int ywmin,int xwmax,int ywmax,int *x1,int *y1,int *x2,int *y2) /裁剪float u1=0.0,u2=1.0,dx=*x2-*x1,dy;if(clipTest(-dx,*x1-xwmin,&u1,&u2)if(clipTest(dx,xwmax-*x1,&u1,&u2) dy=*y2-*y1;if(clipTest(-dy,*y1-ywmin,&u1,&u2)if(clipTest(dy,ywmax-*y1,&u1,&u2)if(u20.0)*x1=*x1+u1*dx; /通过u1求得裁剪后的p1端点*y1=*y1+u1*dy;void keyboard(unsigned char key,int x,int y)/键盘事件，按键盘C键进行裁剪switch(key)case c:clipLine(rect.xmin ,rect.ymin ,rect.xmax ,rect.ymax ,&x0,&y01,&x2,&y2);glutPostRedisplay();break;default:break;第5章 总结第5章 总结这次的图形学课程设计让我收获不小，到真正自己动手做的时候才会发现不足之处。在做设计的期间，又温习了原来所学的知识，可以吧知识系统的归纳。任何知识和理论都要归结于实践。在做设计期间，多亏了同学的帮助和老师的细心指导。自己不懂的代码和原理可以有同学参考。这次设计做得时间太短，大家都要帮着复习考试，没有全身心的投入，很多地方都没有深入的考虑，这也是这次设计的不足之处。我要感谢辅导老师徐文鹏对我的教育培养，您细心指导我的学习与研究，在此，我要向您深深地鞠上一躬。还要感谢在我身边帮助过我的同学们，感谢你们热情的付出！你们兢兢业业，