直线扫描转换DDA算法

《直线扫描转换DDA算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机图形学第二章：光栅图形学算法随着光栅显示器的出现，为了在计算机上处理、显示图形，需要发展一套与之相适应的算法：光栅图形学算法光栅图形算法多数属于计算机图形的底层算法，很多图形学的基本概念和思想都在这一章光栅图形学算法的研究内容直线段的扫描转换算法多边形的扫描转换与区域填充算法裁剪算法反走样算法消隐算法一、直线段的扫描转换算法在数学上，直线上的点有无穷多个。但当在计算机光栅显示器屏幕上表示这条直线时需要做一些处理。P1P0P(x,y)111为了在光栅显示器上用这些离散的像素点逼近这条直线，需要知道这些像素点的x，y坐标。求出过P,P的直线段方程：P0(x0

2、,y0)01ykxb(yy)k10(xx)10(xx)10(yy)10xxykxbk(10)(xx)10假设x已知，即从x的起点x0开始P1(x1,y1)，沿x方向前进一个像素（步长=1)，可以计算出相应的y值。P(x,y)000因为像素的坐标是整数，所以y值还要进行取整处理如何把数学上的一个点扫描转换一个屏幕像素点?取整如：p（1.7，0.8）p（1，0）p（1.7，0.8）+0.5p（2.2，1.3）取整p（2.2，1.3）p（2，1）ykxb直线是最基本的图形，一个动画或真实感图形往往需要调用成千上万次画线程序，因此直线算法的好坏与效率

3、将直接影响图形的质量和显示速度。回顾一下刚才的算法：ykxb为了提高效率，把计算量减下来，关键问题就是如何把乘法取消？二、直线绘制的三个著名的常用算法1、数值微分法（DDA）2、中点画线法3、Bresenham算法1、数值微分DDA(DigitalDifferentialAnalyzer)法引进图形学中一个很重要的思想---增量思想ykxbyii4P1(5,3)yi1kxi1b32(x,y)iik(x)1b1i(x,y)i+1i+1P(0,0)kxkb0012345xikxbkiykiyyki1i增量yyki1i这个式子

4、的含义是：当前步的y值等于前一步的y值加上斜率k这样就把原来一个乘法和加法变成了一个加法！用DDA扫描转换连接两点P(0,0)和P(5,3)的直线段。01yy3010yykk6.01i1ixx50104xyint(y+0.5)P(5,3)13000210+0.61120.6+0.61P(0,0)12345031.2+0.6241.8+0.6252.4+0.63给大家留二个思考题（1）DDA画直线算法：x每递增1，y递增斜率k。是否适合任意斜率的直线？yP24k1P13k1xx12i1ik11yyki1iP0012345xk1用D

5、DA方法画连接两点P（0,0）和P（2,5）的直线段01K=5/2=2.5＞1yi+1=yi+k5xyint(y+0.5)43000212.531255012345再比如直线点从（0，0）到（2，100），也只用3个点来表示（1）k1xx?i1iyy?i1i（2）DDA画直线算法是否最优呢？若非，如何改进？