图形学2.doc

计算机科学系实验报告 （首页）课程名称 计算机图形学 班 级 08网（1） 实验名称 光栅直线圆弧生成 指导教师 季军杰 姓名 杨志航 学 号 081401229 日 期 2011.11.10 一、实验目的(1) 理解bresenham原理(2) 掌握bresenham算法画直线的方法(3) 掌握bresenham算法画圆的方法二、实验设备与环境操作系统xp微型计算机平台,编程环境:visual c+6.0 三、实验内容、程序清单及运行结果实验原理:1. bresenham算法画直线设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y =mx+b，其中 b=y1-m*x1 ,m=（y2-y1）/(x2-x1)=dy/dx； 此处的讨论直线方向限于1a 象限(图1-3)，当直线光栅化时，x 每次都增加1 个单元，设x 像素为(xi，yi)。下一个像素的列坐标为xi1，行坐标为yi，或者递增1 为yi1，由y 与yi 及yi+1 的距离d1 及d2 的大小而定。计算公式为y=m(xi+1)+ b (1.1)d1 = y - yi (1.2)d2 = yi +1 - y (1.3)如果d1-d20，则yi+1=yi+1，否则yi+1=yi。式(1.1)、(1.2)、(1.3)代入d1-d2，再用dx 乘等式两边，并以Pi=(d1-d2) dx 代入上述等式，得Pi = 2xidy-2yidx+2dy+(2b-1) dx (1.4)d1-d2 是用以判断符号的误差。由于在1a 象限，dx 总大于0，所以Pi 仍旧可以用作判断符号的误差。Pi+1 为Pi+1 = Pi+2dy-2(yi+1-yi) dx (1.5)求误差的初值P1，可将x1、y1 和b 代入式(2.4)中的xi、yi 而得到P1 = 2dy-dx综述上面的推导，第1a 象限内的直线Bresenham 算法思想如下：l 画点(x1, y1)，dx=x2-x1，dy=y2-y1，计算误差初值P1=2dy-dx，i=1；l 求直线的下一点位置 xi+1 = xi + 1 如果Pi0，则yi+1=yi+1，否则yi+1=yi；l 画点(xi+1, yi+1)；l 求下一个误差Pi+1，如果Pi0，则Pi+1=Pi+2dy-2dx，否则Pi+1=Pi+2dy；l i=i+1；如果i0)for(i=0; iSetPixel(xa,ya+i,c);if(dydy; i-)pDC-SetPixel(xa,ya+i,c);/*横线处理*/if(dy=0 & dx!=0)if(dx0)for(i=0; iSetPixel(xa+i,ya,c);if(dxdx; i-)pDC-SetPixel(xa+i,ya,c);/*其他处理坐标域分成八个区域*/if(abs(dx)abs(dy)/*1a*/if(dx0 & dy0) p=2*dy-dx;pDC-SetPixel(x,y,c);while(x0)y+;p=p+2*dy-2*dx;elsep=p+2*dy;pDC-SetPixel(x,y,c);/*4a*/if(dx0 & dySetPixel(x,y,c);while(x0)y-;p=p-2*dy-2*dx;elsep=p-2*dy;pDC-SetPixel(x,y,c);/*2a*/if(dx0) p=-2*dy-dx; pDC-SetPixel(x,y,c);while(xxb)x-;if(p0)p=p-2*dy;elsey+;p=p-2*dy-2*dx;pDC-SetPixel(x,y,c);/*3a*/if(dx0 & dySetPixel(x,y,c);while(xxb)x-;if(p0)p=p+2*dy;elsey-;p=p+2*dy-2*dx;pDC-SetPixel(x,y,c);else/*1b*/if(dy0 & dx0) p=2*dx-dy;pDC-SetPixel(x,y,c);while(y0)x+;p=p+2*dx-2*dy;elsep=p+2*dx;pDC-SetPixel(x,y,c);/*2b*/if(dy0 & dxSetPixel(x,y,c);while(y0)x-;p=p-2*dx-2*dy;elsep=p-2*dx;pDC-SetPixel(x,y,c);/*4b*/if(dy0) p=-2*dx-dy;pDC-SetPixel(x,y,c);while(yyb)y-;if(p0)p=p-2*dx;elsex+;p=p-2*dx-2*dy;pDC-SetPixel(x,y,c);/*3b*/if(dy0 & dxSetPixel(x,y,c);while(yyb)y-;if(p0)p=p+2*dx; elsex-;p=p+2*dx-2*dy;pDC-SetPixel(x,y,c);2. bresenham算法画圆的原理设圆的半径为r。先考虑圆心在(0, 0)，并从x=0、y=r 开始的顺时针方向的1/8 圆周的生成过程。在这种情况下，x 每步增加1，从x=0 开始，到x=y 结束。即有xi+1 = xi + 1 相应的yi+1 则在两种可能中选择： yi+1 =yi 或者yi+1 = yi-1。选择的原则是考察精确值y 是靠近yi 还是靠近yi-1(图1-8)，计算式为y2 = r2-(xi+1)2d1 = yi2-y2 = yi2-r2+(xi+1)2d2 = y2-(yi-1)2 =r2-(xi+1)2-(yi-1)2令pi=d1-d2，并代入d1、d2，则有pi = 2(xi+1)2 + yi2 + (yi-1)2-2r2 (1.6)pi 称为误差。如果pi0 则yi+1=yi，否则yi+1=yi-1。pi 的递归式为pi+1 = pi + 4xi +6+2(yi2+1- yi2) -2(yi+1-yi) (1.7)pi 的初值由式(1.6)代入xi=0，yi=r 而得p1 = 3-2r (1.8)根据上面的推导，圆周生成算法思想如下： 求误差初值，p1=3-2r，i=1，画点(0, r)； 求下一个光栅位置，其中xi+1=xi+1，如果pi0 则yi+1=yi，否则yi+1=yi-1； 画点(xi+1, yi+1)； 计算下一个误差，如果pi0 则pi+1=pi+4xi+6，否则pi+1=pi+4(xi-yi)+10； i=i+1，如果x=y 则结束，否则返回步骤2。关键代码:void CMyView:BresenhamCircle(int xx,int yy,int rr)CDC * pDC=GetDC();int xc=xx,yc=yy,radius=rr,c=RGB(0,0,225);int x=0,y=radius,p=3-2*radius;while(xSetPixel(xc+x,yc+y,c);pDC-SetPixel(xc-x,yc+y,c);pDC-SetPixel(xc+x,yc-y,c);pDC-SetPixel(xc-x,yc-y,c);pDC-SetPixel(xc+y,yc+x,c);pDC-SetPixel(xc-y,yc+x,c);pDC-SetPixel(xc+y,yc-x,c);pDC-SetPixel(xc-y,yc-x,c);if(pSetPixel(xc+x,yc+y,c);pDC-SetPixel(xc-x,yc+y,c);pDC-SetPixel(xc+x,yc-y,c);pDC-SetPixel(xc-x,yc-y,c);pDC-SetPixel(xc+