直线段的扫描转换_计算机专业_OpenGL实验_Exp(30页).doc

《直线段的扫描转换_计算机专业_OpenGL实验_Exp(30页).doc》由会员分享，可在线阅读，更多相关《直线段的扫描转换_计算机专业_OpenGL实验_Exp(30页).doc（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-直线段的扫描转换_计算机专业_OpenGL实验_Exp注：1、实验报告的内容: 一、实验目的；二、实验原理；三、实验步骤；四、实验结果；五、讨论分析（完成指定的思考题和作业题）；六、改进实验建议。 2、各专业可在满足学校对实验教学基本要求的前提下，根据专业特点自行设计实验报告的格式，所设计的实验报告在使用前需交实践教学管理科备案。五、实验步骤1、复习有关直线扫描转换算法的基本原理，明确实验目的和要求； 2、依据算法思想，绘制程序流程图；3、设计程序界面，要求操作方便；4、用C/C+语言编写源程序并调试、执行；5、分析实验结果6、对程序设计过程中出现的问题进行分析与总结；7、打印源程序或把源程

2、序以文件的形式提交；8、按格式要求完成实验报告。六、实验报告要求：1、各种算法的基本原理；2、各算法的流程图3、实验结果及分析（比较三种算法的特点，界面插图并注明实验条件）4、实验总结（含问题分析及解决方法）七、实验原理1、DDA算法(数值微分法)数值微分法(DDA法，Digital Differential Analyzer)是一种直接从直线的微分方程生成直线的方法。给定直线的两端点P0(x0, y0)和P1(x1, y1)，得到直线的微分方程如下：DDA算法原理：由于直线的一阶导数是连续的，而且对于x和y是成正比的，故此可以通过在当前位置上分别加上二个小增量来求下一点的x，y坐标，如下图所

3、示。则有：其中，=1/max(|x|,|y|)分两种情况讨论如下：（1） max(|x|,|y|)=|x|，即|k|1的情况：（2） max(|x|,|y|)=|y|，此时|k|1：注意：由于在光栅化的过程中不可能绘制半个像素点，因此对求出的xi+1，yi+1的值需要四舍五入。2、中点Bresenham算法给定直线的两个端点坐标，可以得到直线的方程为： 此时直线将平面分成三个区域：对于直线上的点，F(x, y)=0；对于直线上方的点，F(x, y)0；对于直线下方的点，F(x, y)0，如下图所示。图52 直线将平面分为三个区域 基本原理：根据直线的斜率确定或选择变量在x或y方向上每次 递增一

4、个单位，而另一方向的增量为1或0，它取决于实际直线与 相邻像素点的距离，这一距离称为误差项。 如下图所示，假定0k1，x是最大位移方向。算法每次在x方向上 加1，y方向上加0或加1。设当前点是P(xi, yi)，则下一个点在Pu(xi+1, yi+1) 和Pd(xi+1, yi)中选一。以M点表示Pu与Pd的中点，又设Q点是理想直线与 垂线x=xi+1的交点，根据Q点与M点的位置判断选取哪一个点。 图53 Brensemham算法生成直线的原理构造判别式如下：当d0，M在Q点上方，Pd距离Q点近，取Pd点； 若d=0，M与Q点重合，Pu和Pd都合适，约定取Pd。故有：误差项递推：（1） 当d0

5、时，下一个候选点为(xi+1, yi)，再下两个候选点为(xi+2, yi)和(xi+2, yi+1)，他们的中点为 (xi+2, yi+0.5)，故有：此时，d的增量为k。初始值d的计算：但此时算法中仍然包含了浮点数运算，由于这里我们仅使用了判别式d的符号，所以可以用2dx代替d来摆脱小数。用2dx代替d ,令D2dx 则：3、改进Bresenham算法基本原理：假定直线段的0k1，如下图所示，过各行、各列像素中心构造一组虚拟网格线，按直线起点到终点的顺序 计算直线与各垂直网格线的交点，交点与网格线的误差值为d。 当d0.5时，直线更接近于像素点(x+1, y+1)，当d0.5时，更接近于

6、(x+1,y)；当d=0.5时，约定取(x+1, y)。 图5-4 改进的Brensemham算法绘制直线的原理误差项d的初始值为0，每走一步有d=d+k，一旦y方向上走了一步，就要把d减去1。即有：改进1：令e=d0.5改进2：用E=2ex来替换e八、算法流程1、DDA算法(数值微分法)适用于任意斜率的直线2、中点Bresenham算法以下算法流程仅适用于斜率为0k1的直线，只需交换x、y的地位即可。对于负斜率（包括 -1k0和k -1），只需把对应的正斜率的扫描算法修正为“一个坐标递减而另一个坐标递增”即可。而对于水平、垂直、和k=1的直线，无需使用扫描算法，直接绘制即可。3、改进Bres

7、enham算法以下算法流程仅适用于斜率为0k1的直线，只需交换x、y的地位即可。对于负斜率（包括 -1k0和k -1），只需把对应的正斜率的扫描算法修正为“一个坐标递减而另一个坐标递增”即可。而对于水平、垂直、和k=1的直线，无需使用扫描算法，直接绘制即可。九、实验结果及分析 以下实验窗口所显示的直线为随机生成两端点后再绘制，并非通过鼠标点击输入端点。1、DDA扫描算法绘制效果由于描点较密集，通过拉伸窗体放大后可清晰看到“粒子”的效果：DDA算法的核心代码为：void DDALine(int StrX,int StrY,int EndX,int EndY) int dx=EndX-StrX;i

8、nt 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;/*描点*/ glBegin(GL_POINTS);for(int k=0;k0 & abs(detaY)abs(detaX)/k1k=2;else if(sign0 & abs(detaY)abs(detaX)/0k1k=3;else if(signabs(detaX

9、)/k-1k=-2;else if(sign0 & abs(detaY)abs(detaX)/-1kEndY)Swap(StrX,EndX);Swap(StrY,EndY);for(int y=StrY;yEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX;xEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;xEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;x1if(StrYEndY)Swap(StrX,E

10、ndX);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=0)x+;d+=RightIncre;elsed+=LeftIncre;break;case 3:/0kEndX)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int x=StrX;int y=StrY;int d=dx-2*d

11、y;int UpIncre=2*dx-2*dy;int DownIncre=-2*dy;while(x=EndX) glBegin(GL_POINTS);glVertex2i(x,y);glEnd();x+;if(d0)y+;d+=UpIncre;elsed+=DownIncre;break;case -2:/k-1if(StrY=EndY) glBegin(GL_POINTS);glVertex2i(x,y);glEnd();y-;if(d0)x+;d+=RightIncre;elsed+=LeftIncre;break;case -3:/-1kEndX)Swap(StrX,EndX);Sw

12、ap(StrY,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=0)y-;d+=DownIncre;elsed+=UpIncre;break;return;3、改进Bresenham算法绘制效果 通过菜单切换，可直接得到用改进Bresenham算法绘制同一条直线，绘制效果如下：改进Bresenham算法的核心代码为：void Imp_Bresenham(int StrX,int StrY,

13、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(sign0 & abs(detaY)abs(detaX)/k1k=2;else if(sign0 & abs(detaY)abs(deta

14、X)/0k1k=3;else if(signabs(detaX)/k-1k=-2;else if(sign0 & abs(detaY)abs(detaX)/-1kEndY)Swap(StrX,EndX);Swap(StrY,EndY);for(int y=StrY;yEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX;xEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y=StrY;xEndX)Swap(StrX,EndX);Swap(StrY,EndY);for(int x=StrX,y

15、=StrY;x1if(StrYEndY)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=-dy;int x=StrX;int y=StrY;while(y0)x+;e-=2*dy;break;case 3:/0kEndX)Swap(StrX,EndX);Swap(StrY,EndY);int dx=EndX-StrX;int dy=EndY-StrY;int e=-dx;int x=StrX;int y=StrY;while(x0)y+;e-=2*dx;break;case -2:/k-1if(St

16、rY=EndY)glBegin(GL_POINTS);glVertex2i(x,y);glEnd();y-;e+=2*dx;if(e0)x+;e+=2*dy;break;case -3:/-1kEndX)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(e0)y-;e+=2*dx;break;return;4、直线

17、重绘效果 按R键可实现该功能，主要通过srand()和rand()函数利用time(0)生成随机的直线端点坐标进行直线的重新绘制。5、分析讨论 DDA直线扫描算法是一个增量算法，原理最为简单，直观且易于实现代码编写，适用于各种斜率的直线。但由于带浮点运算，且每一步都必须舍入取整处理，算法效率不高，不利于硬件实现； 中点Bresenham算法原理相对复杂，代码编写相对繁琐，对于不同斜率（共8种情况）的直线需要分别讨论处理。但由于该算法只涉及整数运算，算法效率非常高； 顾名思义，改进Bresenham算法是中点Bresenham的升级版，改变了对误差项的处理方法，算法效率相对于中点Bresenha

18、m有所提高。十、实验总结 通过本次实验，我掌握了3种直线扫描算法的原理及其推导过程，对绘制直线的方法有了深入的了解，为后续的图形生成算法奠定了一定基础。 其实实现DDA算法基本没有任何难度的，关键是Bresenham算法，最初我绘制了斜率为0k1的直线，再通过其他的修改绘制-1k0和k-1的直线，全都绘制失败。最后不得不亲自把各种斜率的Bresenham算法都推导一次，才成功绘制了各种斜率下的Bresenham直线。而之前直接修改0k1的算法之所以绘制失败，是因为书本讲述的方法不够全面，绘制失败也是理所当然的了，所以才说很多时候还是实践见真知。 本次实验的另一个难点就是OpenGL窗口输出文字

19、了。我之所以不在DOS框输出文字是因为我觉得那样很难看，也不够直观，因此我就把DOS框隐藏了。由于我此前已学过在OpenGL窗体输出文字，本来要实现这部分功能也没有什么难度的，把中文、英文和数字都转换为ASCII字符，在OS字库找到字体，再用显示列表输出即可。但是这次要输出斜率k，k是一个double型，而且还可能不存在（直线垂直于x轴）。其实斜率不存在还比较好处理，输出之前做一个斜率判定，不存在就输出“不存在”；关键是double型转换为字符型输出。我最后是利用了C+的ostringstream的类型转换功能，先把double的斜率k压入流，然后再从流里重新读取转换为srting类型的斜率k

20、，最后再通过.c_str()函数把srting类型的k转换为const char*类型，最终实现了在OpenGL窗口上输出直线斜率。-第 29 页Exp - University实 验 报 告课程名称 计算机图形学实验 实验项目 直线段的扫描转换 专业班级 姓 名 Exp 学 号 QQ:289065406 指导教师 成 绩 日 期 2011.11.22 一、实验目的1、通过实验，进一步理解直线段扫描转换的DDA算法、中点bresenham算法以及改进bresenham算法的基本原理；2、 掌握以上算法生成直线段的基本过程；3、 通过编程，会在C/C+环境下完成用DDA算法、中点bresenham算法及bresenham算法对任意直线段的扫描转换。二、实验设备及实验环境1、计算机（每人一台）2、VC+6.0或其他C/C+语言程序设计环境三、实验学时2学时四、实验内容用DDA算法中点bresenham算法及bresenham算法实现任意给定两点的直线段的绘制（直线宽度和线型可自定）。