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

《贵州大学计算机图形学实验报告----直线生成算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、K则为：K=(y1-y0)/(x1-x0).直线的方程为：y=kx+b.则对于

3、k

4、<=1来说，x每增加1个步长，y增加k(直线的斜率)。对于

5、k

6、>1来说，y每增加1个步长，x增加1/k。分析如下所示：

7、k

8、<=1的推导过程yi+1=kxi+1+b=k(xi+Δx)+b=kxi+b+kΔxyi+1=yi+kΔxΔx=1yi+1=yi+k

9、k

10、>1的推导过程Xi+1=yi+1/k–b/k=yi/k-b/k+Δy/kΔy=1Xi+1=Xi+1/kDDA算法的分析：复杂度：加法+取整优点：避免了y=kx

11、+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)<0,则(x,y)在直线下方如F(x,y)>0,则(x,y)在直线上方对于

12、k

13、<=1xPi=(xi,yi)MQP1p2y假设已确定当前象素点P（Xp,Yp）,然后确定下一个象素点，即

14、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点)下方，取右上方T为下一个象素；当d>=0，M在L(Q点)上方，取右方B为下一个象素；当d=0，选T或B均可，约定取B为下一个象素判断了M的位置之后则可以依次的画出各个点，从而得到一条直线。对于

15、k

16、>1d=F(M)=F(xp+0.5,yp+1)=a(xp+0.5

17、)+b(yp+1)+c当d>=0，M在L(Q点)下方，取右上方T为下一个象素；当d<0，M在L(Q点)上方，取右方B为下一个象素；当d=0，选T或B均可，约定取B为下一个象素中点划线算法的分析：优点：用整数加法代替了DDA数值微分法中的浮点数加法及取整运算,大大提高了算法的效率。缺点：在计算d的符号时，需要做4个加法和2个乘法改进：因为d是x和y的线性函数，因此可采用增量计算。通过计算可得对于

18、k

19、<=1的情况d的初值为a+0.5b，当d>=0，M在L上方，增量d1为a；当d<0，M在L下方，增量d2为a+

20、b。对于

21、k

22、>1的情况d的初值为0.5a+b，当d>=0，M在L下方，增量d1为b；当d<0，M在L上方，增量d2为a+b。三、Bresenham划线算法该算法是计算机图形学领域中使用最为广泛的直线扫描转换算法，该划线算法类似与中点划线算法，也是由误差项符号决定下一个像素右边点还是右上点。基本原理：过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的优点在于增量计算，使得对于每一列只要检查一个误差项的符号，就可以确定该列

23、所求的像素。根据直线的斜率来确定变量在x或y方向递增一个单位。另一个方向y或x的增量为0或1，它取决于实际直线与最接近网格点位置的距离。这一距离称为误差。由以上原理，为方便计算，令e=d-0.5,e的初值为-0.5，增量为k。当e>=0时，取当前像素(xi,yi)的右上方像素(xi+1,yi+1)，e减小1，而当e<0时，更接近于右方像素(xi+1,yi)。Bresenham算法的分析：优点：高效，巧妙地采用了e=d-0.5,e的初值为-0.5来简化运算，把e和0.5的比较转化成了e和0的比较，使得每次画点

24、只需考虑误差项增量的符号即可。实验环境硬件平台：PC机软件：Windows平台，eclipse编程语言：java实验步骤1.掌握三种划线算法的基本原理；2.依据划线算法，在eclipse下编写源程序并进行调试；3.对运行过程中的错误进行修改；4.对运行结果进行分析与总结；5.书写实验报告。实验内容在java中没有画点的函数，可以借用划线的函数来完成，java中的划线函数需要传线段的起点和终点两个点做参数来画线，我