直线栅格化算法

1、1、DDA法(数字微分分析法)该方法的基本依据是直线的微分方程，即dy/dx=常数。其本质是用数值方法解微分 方程，通过同时对x和y各增加一个小增量来计算下一步的x,y值，即这是一种增量算法。2、Bresenham 算法该算法构思巧妙，只需根据由直线斜率构成的误差项的符号，就可确定下一列坐标的递 增值。根据直线的斜率，把直线分为8个卦限。下面举斜率在第一卦限的情况为例，其余卦限 的情况类似。该算法的基本思路可描述为：若直线的斜率为l/2Wy/ZxWl,则下一点取(1, 1) 点，若0Ay/Axl/2,则下一点取(1, 0)点。在算法实现时，令起始的误差项为e= 1/2,然后在推断出下一点后，令

2、e=e+Ay/ AxSX),若eNO时,e=e-l.这样只要根据e的符号就可确定下一点的要量,即:若e，0,取(1, 1)点若eVO,取(1, 0)点这种算法不仅速度快、效果好，而且可以理论上证明它是目前同类各种算法中最优的。Bresenliam算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数：3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenliam算法速度很快，并适于用硬件实现。Bresenliam画线算法的思路如卜，：/假设该线段位于第一象限内且斜率大于。小于1,设起点为(xl,yl),终点为(x2,y2)./根据对称性，可推导至全象限内

3、的线段.画起点(xl,yl).准备画下个点。x坐标增1,判断如果达到终点，则完成。否则，由图中可知，下个要画的 点要么为当前点的右邻接点，要么是当前点的右上邻接点.如果线段ax+by+c=O与x=xl+l的交点的y坐标大于M点的y坐标的话，下个点为U(xl+l,yl+l)否则，下个点为B(xl+l,yl+l)画点(U或者B).跳回第2步.结束.这里需要细化的是怎么判断下个要画的点为当前点的右邻接点还是当前点的右上邻接点 设线段方程：ax+by+c=O(xlxx2,yl0时候，即下个点为U.反之，下个点为B.代入 a/b,M Subl = dy/dx-0.5.因为是个循环中都要判断Sub,所以得

4、求出循环下的Sub表达式，我们可以求出Sub的差值的 表达式.卜面求x=xl+2时的Sub,即Sub2如果下下个点是下个点的右上邻接点，则Sub2 = (-c-a(xl+2)/b - (yl+1.5) = -2a/b - 1.5故 Sub 差值 Dsub = Sub2 - Subl = -2a/b -1.5 - (-a/b-0.5) = -a/b -1.代入 a/b 得 Dsub = dy/dx -1;如果下下个点是下个点的右邻接点，Sub2 = (-c-a(xl+2)/b - (yl+0.5) = -2a/b - 0.5故 Sub 差值 Dsub = Sub2 - Subl = -2a/b

5、- 0.5 - (-a/b-0.5) = -a/b,代入 a/b 得 Dsub = dy/dx;于是，我们有了 Sub的处始值Subl = -a/b-0.5 = dy,，dx-0.5,又有了 Sub的差值的表达式Dsub =dy/dx -1 (当 Subl 0)或 dy/dx (当 Subl 0).细化工作完成。于是pcode可以细化如下：/ Pcode for Bresenliain Lme/ Bv SoRoManrx=xl;y=yi;dx = x2xl;dy = y2-yl;Sub = dy/dx-0.5;/赋初值，下个要画的点与中点的差值DiawPixel(x, y)； / 画起点wlu

6、le(x 0) F个要画的点为当前点的右上邻接点Sub += dy/dx -1; 下下个要画的点与中点的差值y+;右上邻接点y需增1else/下个要画的点为当前点的右邻接点Sub += dy/dx;/画下个点DiawPixel(x,y);PS：一般优化：为避免小数转整数以及除法运算，由于Sub只是用来进行正负判断，所以可以令Sub2*dx*Sub = 2dy-dx,则相应的 DSub = 2dy - 2dx 或 2dy.算法描述设：pl=2dy-dx综述上面的推导，第la象限内的直线Bresenliain算法思想如下：1、画起点(xl,yl). dx=x2-xl,dy=y2-yl,i+ 算误差

7、初值pl=2dy-dx;i=l；2、求直线的下一点位置：x(i+l)=x(i+l)：if p(i)0 则 y(i+l)=y(i+l)：否则 y(i+l)=y(i)；3、画点(x(i+l),y(i+l)：4、求下一个误差p(i+l);if p(i)0贝 ijp(i+l)= p(i)+2dy-2dx;否则 p(i+l)=p(i)+2dy：5、i=i+l; ifidx+1 则转 2：否则endBresenliam算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenliam算法速度很快，并适于用硬件实现。

8、三.程序源码：hit BresenliaiiiLme (int xl , int yl , mt x2 , mt y2 , int c)hit dx . dy;hit tx , ty;hit iiicl , iiic2 ;mt d jTag ；int x, y;putpixel (xl , yl , c );if(xl =x2 & yl =y2) /*如果两点重合，结束后面的动作。*/leturn 1 ;iTag = 0 ；dx = abs (x2 - xl );dy = abs (y2 - yl );if ( dx 0?l:-l;/* 确定是增 1 还是减 1*/ty=(y2-yl)0? 1 :-1 ;x = xl ;y = yi ；iiicl = 2 * dv ；iiic2 = 2 * ( dy - dx );d = mcl dx :,wliile (x != x2 )/*循环画点*/if(d0)d += iiicl ;elsey+=ty;d += iiic2 ;if (i