文档介绍：会计学
1
DDA算法(suàn fǎ)Bresenham算法(suàn fǎ)和画家算法(suàn fǎ)
第一页，共25页。
直线(zhíxiàn)DDA算法描述
设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程(wēi fēn fānɡ chénɡ)得
= m =直线的斜率 (2－1)
可通过计算由x方向的增量△x引起y的改变来生成直线：
xi+1=xi+△x (2－2)
yi+1=yi+△y=yi+△x·m (2－3)
也可通过计算由y方向的增量△y引起x的改变来生成直线：
yi+1=yi+△y (2－4)
xi+1=xi+△x=xi+△y/m (2－5)
式(2－2)至(2－5)是递推的。
第1页/共25页
第二页，共25页。
直线DDA算法(suàn fǎ)思想
1、选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个(yī ɡè)象素单位(△x=1)，
2、利用式(2－1)计算另一个(yī ɡè)方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。
之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。
另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。
第2页/共25页
第三页，共25页。
第3页/共25页
第四页，共25页。
直线DDA算法(suàn fǎ)实现
1、已知直线的两端点坐标：(x1，y1)，(x2，y2) 2、已知画线的颜色：color 3、计算两个(liǎnɡ ɡè)方向的变化量：dx=x2－x1 dy=y2－y1 4、求出两个(liǎnɡ ɡè)方向最大变化量的绝对值： steps=max(|dx|，|dy|) 5、计算两个(liǎnɡ ɡè)方向的增量(考虑了生成方向)： incx=dx/steps inxy=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i<=steps；i++) { draw_pixel(x，y，color)；/*在(x，y)处，以color色画点*/ x=x+incx； y=y+incy； }
第4页/共25页
第五页，共25页。
直线(zhíxiàn)DDA算法特点
该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此(yīncǐ)生成直线的速度较慢。
第5页/共25页
第六页，共25页。
Bresenham算法(suàn fǎ)
由直线的斜率确定选择(xuǎnzé)在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，。
Bresenham算法是计算机图形学典型(diǎnxíng)的直线光栅化算法,可以有效地避免使用浮点运算。
算法原理：
算法特点：
第6页/共25页
第七页，共25页。
Bresenham算法(suàn fǎ)
基本原理
假定直线斜率k在0~1之间。此时，只需考虑x方向每次递增1个单位，决定(juédìng)y方向每次递增0或1。
设
    直线当前点为(xi,y)     直线当前光栅点为(xi,yi)
则  下一个直线