DDA算法Bresenham算法和画家算法

会计学1DDA算法Bresenham算法和画家算法直线DDA算法描述设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得=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页直线DDA算法思想1、选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，2、利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。第2页/共25页第3页/共25页直线DDA算法实现1、已知直线的两端点坐标：(x1，y1)，(x2，y2)

2、已知画线的颜色：color

3、计算两个方向的变化量：dx=x2－x1

dy=y2－y1

4、求出两个方向最大变化量的绝对值：

steps=max(|dx|，|dy|)

5、计算两个方向的增量(考虑了生成方向)：

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页直线DDA算法特点该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。第5页/共25页Bresenham算法由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。

Bresenham算法是计算机图形学典型的直线光栅化算法,可以有效地避免使用浮点运算。算法原理：

算法特点：第6页/共25页Bresenham算法基本原理假定直线斜率k在0~1之间。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。设

直线当前点为(xi,y)

直线当前光栅点为(xi,yi)则

下一个直线的点应为(xi+1,y+k)

下一个直线的光栅点为右光栅点(xi+1,yi)（y方向递增量0）

或为右上光栅点(xi+1,yi+1)（y方向递增量1）第7页/共25页

记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)–yi，且

0≤d≤1

当d<0.5：下一个象素应取右光栅点(xi+1,yi)

当d≥0.5：下一个象素应取右上光栅点(xi+1,yi+1)Bresenham算法第8页/共25页如果直线的（起）端点在整数点上，误差项d的初值：d0＝0，

x坐标每增加1，d的值相应递增直线的斜率值k，即：d＝d+k。

一旦d≥1，就把它减去1，保证d的相对性，且在0-1之间。Bresenham算法第9页/共25页Bresenham算法令e=d-0.5，关于d的判别式和初值可简化成：

e的初值e0=-0.5，增量亦为k;

e<0时，取当前象素(xi,yi)的右方象素(xi+1,yi)；

e>0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)；

e=0时，可任取上、下光栅点显示。Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e的符号决定y方向每次递增0或1。

e<0，y方向不递增

e>0，y方向递增1

x方向每次递增1个单位，e=e+k因为e是相对量，所以当e>0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e=e-1第10页/共25页Bresenham算法

通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；

如果斜率小于0.5，则反之；

当斜率等于0.5，没有确定的选择标准，本算法选择(1,1)1)Bresenham算法的实施——Rogers版第11页/共25页Bresenham算法x=x1

y=y1

dx=x2–x1

dy=y2–y1

//初始化误差e

Error=dy/dx-0.5

//beginthemainloop

fori=1todx

WritePixel(x,y,value)

if(Error≥0)then//判断斜率是否大于0.5

y=y+1

Error=Error-1

endif

x=x+1

Error=Error+dy/dx

nexti

finish1)Bresenham算法的实施——Rogers版第12页/共25页Bresenham算法2)整数Bresenham算法

上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。由于上述Bresenham算法中只用到误差项（初值Error=dy/dx-0.5）的符号因此只需作如下的简单变换：

NError=2*Error*dx即可得到整数算法，这使本算法便于硬件（固件）实现。第13页/共25页Bresenham算法x=x1

y=y1

dx=x2–x1

dy=y2–y1

//initializeetocompensateforanonzerointercept

NError=2*dy-dx

//Error=dy/dx-0.5;NError=2*Error*dx

//beginthemainloop

fori=1todx

WritePixel(x,y)

if(NError>=0)then

y=y+1

NError=NError–2*dx

//Error=Error-1

endif

x=x+1

NError=NError+2*dy

//Error=Error+dy/dx

nexti

finish第14页/共25页Bresenham算法3)一般Bresenham算法

要使上面的Bresenham算法适用于一般直线，只需对以下2点作出改造：

a、当直线的斜率|k|>1时，改成y的增量总是1，再用Bresenham误差判别式确定x变量是否需要增加1；

b、x或y的增量可能是“+1”或“-1”，视直线所在的象限决定。第15页/共25页画家算法一、画家算法的基本思想：先将画面中的物体按其距离观察点的远近进行排序，结果存放在一张线形表中。距观察点远者称其优先级高，放在表头，距观察点近者称其优先级低，放在表尾，这张表称为深度优先级表。然后按照从表头到表尾的顺序逐个绘制物体。由于距观察者近的物体在表尾最后画出，它覆盖了远处的物体，最终在屏幕上产生了正确的遮挡关系。画家算法看起来十分简单，但关键是如何对画面中各种不同情况下的多边形按深度排序，建立深度优先表。假设视点在z轴正向无穷远处，视线方向沿着z轴负向看过去。如果z值大，离观察点近；而z值小，离观察点远。第16页/共25页画家算法二、多边形优先级的考虑1、首先对一个简单的画面，如图（a）所示可以直接建立一个确定的深度优先表，排序可以一次完成，不会有任何的歧义。例如，多边形可按其最大或最小值排序，都可以很容易地把它们按深度大小分开。2、但是，当画面略微复杂一点，如图（b）所示，却无法按简单的z向排序建立确定的深度优先表，以确定每一个多边形的优先级。例如，若按最小z坐标值（zmin）对P、Q排序，则在深度优先表中，P应排在Q之前，如按此顺序将P、Q写入帧缓冲器，则Q将部分地遮挡P。但实际上是P部分地遮挡Q。如果按最大z坐标值（zmax）对P、Q排序，同样也不能得到正确的消隐结果。第17页/共25页画家算法三、交叉覆盖和循环覆盖多边形的优先级考虑对更复杂的情况，如图所示，出现的困难更多。图（a）、（b）均有交叉覆盖或循环遮挡的情况。如在图（a）中，P在Q的前面，Q在R的前面，而R反过来又在P的前面。在图（b）中，P在Q的前面，而Q又在P的前面。对它们均无法直接建立确定的深度优先表。第18页/共25页画家算法四、解决深度优先级冲突的排序算法假定视点在Z轴正向无穷远处，则该算法叙述如下：

1、计算多边形最小深度值zmin，并以此值的优先级进行排序，建立初步的深度优先表。表中第一个元素是对应有最小zmin值的多边形，标记为P，优先级最高。表中第二个多边形标记为Q。

2、考察P和Q之间的关系：（1）若P上离视点最近的顶点Pzmax比Q上离视点最远的顶点Qzmin还远，Qzmin≥Pzmax则P不遮挡Q，将P写入帧缓冲区，见图示。第19页/共25页画家算法（2）若Qzmin＜Pzmax，那么P不但有遮挡Q的可能，而且还可能部分地遮挡表上Q之后的任一满足Rzmin＜Pzmax的多边形R。我们把所有这种有可能被P所遮挡的多边形的全体记为{Q}。为了进一步确定P是否真正遮挡{Q}中的多边形，做以下逐步的测试，如果对{Q}中每个Q，都能通过以下问题中任一个，那么P不会遮挡{Q}，因而可将P写入帧缓冲区中去。第20页/共25页画家算法所提出的问题是：①P和Q的外接最小包围盒在X方向不相交吗？

②P和Q的外接最小包围盒在Y方向不相交吗？

③