DDA算法Bresenham算法和画家算法

1、DDA算法Bresenham算法和画家算法直线DDA算法描绘设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得 = m =直线的斜率 (21)可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x (22)yi+1=yi+y=yi+xm (23)也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y (24)xi+1=xi+x=xi+y/m (25)式(22)至(25)是递推的。直线DDA算法思想1、选定x2x1和y2y1中较大者作为步进方向(假设x2x1较大)，取该方向上的增量为一个象素单位(x=1)，2、利用式(21)计算另一个

2、方向的增量(y=xm=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，那么得到扫描转换后的直线。之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在以以下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。直线DDA算法实现1、直线的两端点坐标：(x1，y1)，(x2，y2)2、画线的颜色：color3、计算两个方向的变化量：dx=x2x1 dy=y2y14、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)： incx

3、=dx/steps inxy=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i=steps；i+) draw_pixel(x，y，color)；/*在(x，y)处，以color色画点*/x=x+incx； y=y+incy； 直线DDA算法特点 该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。Bresenham算法由直线的斜率确定选择在x方向或y方向上每次递增减1个单位，另一变量的递增减量为0或1，它取决于实际直线与最近光栅网格点的间隔 ，这个间隔 的最大误差为。 Bresenham算法是计算机图形学典型的直线光

4、栅化算法,可以有效地防止使用浮点运算。算法原理： 算法特点：Bresenham算法根本原理假定直线斜率k在01之间。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。 设 直线当前点为(xi,y) 直线当前光栅点为(xi,yi)那么下一个直线的点应为(xi+1,y+k) 下一个直线的光栅点为右光栅点(xi+1,yi)y方向递增量0 或为右上光栅点(xi+1,yi+1)y方向递增量1 记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)yi，且 0d1 当：下一个象素应取右光栅点(xi+1,yi) 当：下一个象素应取右上光栅点(xi+1,yi+1)Bresenham算法假

5、设直线的起端点在整数点上，误差项d的初值：d00，x坐标每增加1，d的值相应递增直线的斜率值k，即：dd + k。一旦d1，就把它减去1，保证d的相对性，且在0-1之间。Bresenham算法Bresenham算法令，关于d的判别式和初值可简化成： e的初值，增量亦为k; e0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)； e=0时，可任取上、下光栅点显示。Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e的符号决定y方向每次递增 0 或 1。 e0，y方向递增1 x方向每次递增1个单位，e = e + k因为e是相对量，所以当e0时，说明

6、e的计值将进入下一个参考点上升一个光栅点，此时须：e = e - 1Bresenham算法 通过(0,0)的所求直线的斜率大于，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；假设斜率小于，那么反之；当斜率等于，没有确定的选择标准，本算法选择(1,1) 1)Bresenham算法的施行Rogers 版Bresenham算法x=x1y=y1dx = x2 x1dy = y2 y1/初始化误差eError =dy/dx-0.5/begin the main loopfor i=1 to dx WritePixel (x, y, value) i

7、f (Error 0) then /判断斜率是否大于 y=y+1 Error = Error -1 end if x=x+1 Error = Error +dy/dxnext ifinish 1)Bresenham算法的施行Rogers 版Bresenham算法2)整数Bresenham算法 上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和防止除法可以加快算法的速度。 由于上述Bresenham算法中只用到误差项初值的符号因此只需作如下的简单变换： NError = 2*Error*dx即可得到整数算法，这使本算法便于硬件固件实现。Bresenham算

8、法x=x1y=y1dx = x2 x1dy = y2 y1/initialize e to compensate for a nonzero interceptNError =2*dy-dx /Error =dy/dx-0.5; NError = 2*Error*dx /begin the main loopfor i=1 to dx WritePixel (x, y) if (NError =0) then y=y+1 NError = NError 2*dx /Error = Error -1 end if x=x+1 NError = NError +2*dy /Error = Erro

9、r +dy/dxnext ifinish Bresenham算法3)一般Bresenham算法 要使上面的Bresenham算法适用于一般直线，只需对以下2点作出改造：a、当直线的斜率|k|1时，改成y的增量总是1，再用Bresenham误差判别式确定x变量是否需要增加1；b、x或y的增量可能是“+1或“-1，视直线所在的象限决定。画家算法一、画家算法的根本思想：先将画面中的物体按其间隔 观察点的远近进展排序，结果存放在一张线形表中。距观察点远者称其优先级高，放在表头，距观察点近者称其优先级低，放在表尾，这张表称为深度优先级表。然后按照从表头到表尾的顺序逐个绘制物体。由于距观察者近的物体在表尾

10、最后画出，它覆盖了远处的物体，最终在屏幕上产生了正确的遮挡关系。画家算法看起来非常简单，但关键是如何对画面中各种不同情况下的多边形按深度排序，建立深度优先表。假设视点在z轴正向无穷远处，视线方向沿着z轴负向看过去。假设z值大，离观察点近；而z值小，离观察点远。画家算法二、多边形优先级的考虑1、首先对一个简单的画面，如图a所示可以直接建立一个确定的深度优先表，排序可以一次完成，不会有任何的歧义。例如，多边形可按其最大或最小值排序，都可以很容易地把它们按深度大小分开。2、但是，当画面略微复杂一点，如图b所示，却无法按简单的z向排序建立确定的深度优先表，以确定每一个多边形的优先级。例如，假设按最小z

11、坐标值zmin对P、Q排序，那么在深度优先表中，P应排在Q之前，如按此顺序将P、Q写入帧缓冲器，那么Q将局部地遮挡P。但实际上是P局部地遮挡Q。假设按最大z坐标值zmax对P、Q排序，同样也不能得到正确的消隐结果。画家算法三、穿插覆盖和循环覆盖多边形的优先级考虑对更复杂的情况，如以下图，出现的困难更多。图a、b均有穿插覆盖或循环遮挡的情况。如在图a中，P在Q的前面，Q在R的前面，而R反过来又在P的前面。在图b中，P在Q的前面，而Q又在P的前面。对它们均无法直接建立确定的深度优先表。画家算法四、解决深度优先级冲突的排序算法假定视点在Z轴正向无穷远处，那么该算法表达如下：1、计算多边形最小深度值z

12、min，并以此值的优先级进展排序，建立初步的深度优先表。表中第一个元素是对应有最小zmin值的多边形，标记为P，优先级最高。表中第二个多边形标记为Q。2、考察P和Q之间的关系：1假设P上离视点最近的顶点Pzmax比Q上离视点最远的顶点Qzmin还远， QzminPzmax那么P不遮挡Q，将P写入帧缓冲区，见图示。画家算法2假设QzminPzmax，那么P不但有遮挡Q的可能，而且还可能局部地遮挡表上Q之后的任一满足 Rzmin Pzmax的多边形R。我们把所有这种有可能被P所遮挡的多边形的全体记为Q。为了进一步确定P是否真正遮挡Q中的多边形，做以下逐步的测试，假设对Q中每个Q，都能通过以下问题中

13、任一个，那么P不会遮挡Q，因此可将P写入帧缓冲区中去。画家算法所提出的问题是：P和Q的外接最小包围盒在X方向不相交吗？P和Q的外接最小包围盒在Y方向不相交吗？P是否全部位于Q所在平面的背离视点的一侧。以以下图a能通过这一测试。Q是否全部位于P所在平面的靠近视点的一侧。以以下图b能通过这一测试。P和Q在显示屏幕上的投影是否可以别离。假设Q和P不能通过以上测试，就不能把P写到帧缓冲区中去，那么交换P和Q，并将Q作上记号，形成新的优先级表。画家算法3对重新排列的表重复2中步骤，对于图c，经重新排列后，就能把Q写入帧缓冲区中去了。多边形重叠判断画家算法4执行3以后，假设Q的位置需再次交换，那么说明存在穿插覆盖的情况，见以以下图所示，这时可将P沿Q所在平面分割成两局部P1和P2，从表中去掉原多边形P，而将P的这