DDA算法Bresenham算法和画家算法.ppt

《DDA算法Bresenham算法和画家算法.ppt》由会员分享，可在线阅读，更多相关《DDA算法Bresenham算法和画家算法.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、直线直线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)计算另一个方向的增量(y=x

2、m=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=d

3、x/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，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。 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 当d0.5：下一个象素应取右光栅点(xi+1,yi) 当d0.5：下一个象素应取右上光

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

6、递增1 x方向每次递增1个单位，e = e + k因为e是相对量，所以当e0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e - 1Bresenham算法 通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；如果斜率小于0.5，则反之；当斜率等于0.5，没有确定的选择标准，本算法选择(1,1) 1)Bresenham算法的实施Rogers 版Bresenham算法x=x1y=y1dx = x2 x1dy = y2 y1/初始化误差eError =dy/dx-0.5/begin t

7、he main loopfor i=1 to dx WritePixel (x, y, value) if (Error 0) then /判断斜率是否大于0.5 y=y+1 Error = Error -1 end if x=x+1 Error = Error +dy/dxnext ifinish 1)Bresenham算法的实施Rogers 版Bresenham算法2)整数Bresenham算法 上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。 由于上述Bresenham算法中只用到误差项（初值Error =dy/dx-

8、0.5）的符号因此只需作如下的简单变换： NError = 2*Error*dx即可得到整数算法，这使本算法便于硬件（固件）实现。Bresenham算法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 = NEr

9、ror 2*dx /Error = Error -1 end if x=x+1 NError = NError +2*dy /Error = Error +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）所示可以直接建立一个确定的深度优先表，排序可以一次完成，不会有任何的歧义。例

11、如，多边形可按其最大或最小值排序，都可以很容易地把它们按深度大小分开。2、但是，当画面略微复杂一点，如图（b）所示，却无法按简单的z向排序建立确定的深度优先表，以确定每一个多边形的优先级。例如，若按最小z坐标值（zmin）对P、Q排序，则在深度优先表中，P应排在Q之前，如按此顺序将P、Q写入帧缓冲器，则Q将部分地遮挡P。但实际上是P部分地遮挡Q。如果按最大z坐标值（zmax）对P、Q排序，同样也不能得到正确的消隐结果。画家算法三、交叉覆盖和循环覆盖多边形的优先级考虑三、交叉覆盖和循环覆盖多边形的优先级考虑对更复杂的情况，如图所示，出现的困难更多。图（a）、（b）均有交叉覆盖或循环遮挡的情况。如

12、在图（a）中，P在Q的前面，Q在R的前面，而R反过来又在P的前面。在图（b）中，P在Q的前面，而Q又在P的前面。对它们均无法直接建立确定的深度优先表。画家算法四、解决深度优先级冲突的排序算法四、解决深度优先级冲突的排序算法假定视点在Z轴正向无穷远处，则该算法叙述如下：1、计算多边形最小深度值zmin，并以此值的优先级进行排序，建立初步的深度优先表。表中第一个元素是对应有最小zmin值的多边形，标记为P，优先级最高。表中第二个多边形标记为Q。2、考察P和Q之间的关系：（1）若P上离视点最近的顶点Pzmax比Q上离视点最远的顶点Qzmin还远， QzminPzmax则P不遮挡Q，将P写入帧缓冲区，

13、见图示。画家算法（2）若QzminPzmax，那么P不但有遮挡Q的可能，而且还可能部分地遮挡表上Q之后的任一满足 Rzmin Pzmax的多边形R。我们把所有这种有可能被P所遮挡的多边形的全体记为Q。为了进一步确定P是否真正遮挡Q中的多边形，做以下逐步的测试，如果对Q中每个Q，都能通过以下问题中任一个，那么P不会遮挡Q，因而可将P写入帧缓冲区中去。画家算法所提出的问题是：P和Q的外接最小包围盒在X方向不相交吗？P和Q的外接最小包围盒在Y方向不相交吗？P是否全部位于Q所在平面的背离视点的一侧。下图（a）能通过这一测试。Q是否全部位于P所在平面的靠近视点的一侧。下图（b）能通过这一测试。P和Q在显

14、示屏幕上的投影是否可以分离。若Q和P不能通过以上测试，就不能把P写到帧缓冲区中去，则交换P和Q，并将Q作上记号，形成新的优先级表。画家算法（3）对重新排列的表重复（2）中步骤，对于图（c），经重新排列后，就能把Q写入帧缓冲区中去了。多边形重叠判断画家算法（4）执行（3）以后，若Q的位置需再次交换，则表明存在交叉覆盖的情况，见下图所示，这时可将P沿Q所在平面分割成两部分P1和P2，从表中去掉原多边形P，而将P的这两个新的部分插入原表中的适当位置，使其仍保持按zmin排序的性质。对新形成的表，重新执行（2）。画家算法1、画家算法同时在物体空间和图像空间中进行处理，即：在物体空间中排序以确定优先级；而显示结果在算法运行之际就要不断地写入图像空间的帧缓冲区中。2、该算法利用几何关系来判断可见性，而不是像在z缓冲器算法中那样，逐个像素地进行比较。因此，它利用了多边形深度的相关性，可见性判别是根据整个多边形来进行的。五、画家算法特点：五、画家算法特点：