贵州大学计算机图形学实验报告直线生成算法.docx

1、贵州大学计算机图形学实验报告直线生成算法贵州大学计算机图形学实验报告学院：计算机科学与信息学院 专业：软件工程 班级：102班姓名学号实验组实验时间指导教师成绩实验项目名称实验一 直线生成算法实验目的通过本实验，了解并掌握在光栅显示系统中直线的生成和显示算法，熟悉相关开发平台。为后继实验打下基础。实验要求1、 能够使用DDA数值微分法绘制直线。2、 能够使用中点画线算法绘制直线。3、 能够使用Bresenham画线算法绘制直线。实验原理一、DDA数值微分法画直线已知直线段L的起点为P0（x0,y0）,终点为P1（x1,y1）直线的斜率K则为：K=(y1-y0)/(x1-x0).直线的方程为：y

2、 = kx+b.则对于|k|1来说，y每增加1个步长，x增加1/k。分析如下所示：|k|1的推导过程Xi+1 = yi+1/k b/k = yi/k - b/k +y/ky = 1Xi+1 = Xi+1/kDDA算法的分析：复杂度：加法+取整优点：避免了y=kx+b 方程中的浮点乘法,比直接用点斜式画线快。缺点：需浮点数加法及取整运算,不利于硬件实现。二、中点划线法假设直线的起点、终点分别为：（X0,Y0),(X1,Y1)，直线方程: F(x,y)=ax+by+c=0，其中: a=y0-y1，b=(x1-x0)，c=x0y1-x1y0。如F(x,y)=0, 则(x,y) 在直线上如F(x,y)

3、0, 则(x,y)在直线上方对于|k|=1假设已确定当前象素点P（Xp ,Yp ）,然后确定下一个象素点，即T 或B之一。M为T，B中点，Q为理想直线与栅格线的交点。若M在Q的下方，选T，否则选B。使用直线的正负划分性来判断M和Q的位置关系.构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d=0，M在L(Q点)上方，取右方B为下一个象素；当d=0，选T或B均可，约定取B为下一个象素判断了M的位置之后则可以依次的画出各个点，从而得到一条直线。对于|k|1d=F(M)=F(xp+0.5,yp+1)=a(xp+0.5)+b(yp+1)+c当d=0，M在

4、L(Q点)下方，取右上方T为下一个象素；当d0，M在L(Q点)上方，取右方B为下一个象素；当d=0，选T或B均可，约定取B为下一个象素中点划线算法的分析：优点：用整数加法代替了DDA数值微分法中的浮点数加法及取整运算,大大提高了算法的效率。缺点：在计算d的符号时，需要做4个加法和2个乘法改进：因为d是x和y的线性函数，因此可采用增量计算。通过计算可得对于|k|=0，M在L上方，增量d1为a；当d1的情况d的初值为0.5a+b，当d=0，M在L下方，增量d1为b；当d=0时，取当前像素(xi,yi)的右上方像素(xi+1,yi+1)，e减小1，而当e= -1 & k = 1) / |k|=0 i

5、nt x; float y; y = y0; for (x = x0; x 0 int y; float x; x = x0; for (y = y0; y = -1 & k = 0) d = 2 * a + b; d1 = 2 * a; d2 = 2 * (a + b); while (x x1) if (d 0) x+; y+; d += d2; else x+; d += d1; g.drawLine(x, y, x, y); else d = 2 * a - b; d1 = 2 * a; d2 = 2 * (a - b); while (x x1) if (d = 0) d = a +

6、 2 * b; d1 = 2 * b; d2 = 2 * (a + b); while (y y1) if (d 0) y+; d += d1; else x+; y+; d += d2; g.drawLine(x, y, x, y); else d = -a + 2 * b; d1 = 2 * b; d2 = 2 * (-a + b); while (y y1) if (d = -1 & k =0) for (int i = 0; i = 0) y+; e = e - 1; else for (int i = 0; i = 0) y-; e = e - 1; else if(k=0) for

7、 (int i = 0; i = 0) x+; e = e - 1; else for (int i = 0; i = 0) x-; e = e - 1; System.out.println(Bresenham划线算法 k = + k); 实验结果在java中原点位于左上点，水平向右为X轴正方向，垂直向下为Y轴正方向。用三种算法划线的过程中采用了不同的颜色加以区分：DDA算法（黄色），中点划线算法（绿色），Bresenham算法（蓝色）。运行程序后，分别显示如下：DDA算法：斜率显示：中点划线算法斜率显示：Bresenham算法斜率显示：实验总结本次试验我收获很大，掌握了三种划线算法的基本原理，并成功编出了测试程序，我觉得试验是将书本知识与实践结合的最佳途径，编写程序的过程也不是很顺利，过程中存在很多BUG，通过调试得到了解决，但是还遗留一些问题没有解决，在我的代码中，要运行算法画直线，必须先将其他的两种算法的代码注释，才能显示，否则后一中算法的颜色就会覆盖前一种算法的颜色，因为我画的六条直线在三种算法中都是相同的斜率。此次试验中存在的不足我会查阅相关资料并改正，争取得到更好的完善。指导教师意见签名： 年 月 日注：可根据教学需要对以上栏目进行增减。表格内容可根据内容扩充。