线的生成算法

3.2线的生成算法3.2.1直线的生成算法在数学上，直线是没有宽度的、由无数个点构成的集合。对直线进行光栅化就是在显示器所给定的有限个像素矩阵中，确定最佳逼近于该直线的一组像素。然后按照扫描线顺序，对这些像素进行写操作，这就是直线的扫描转换。对于水平线、垂直线和45°线，选择哪些光栅元素是显而易见的，而对于其它方向的直线，像素的选择较为困难。3.2线的生成算法3.2.1直线的生成算法斜率截距直线方程：k表示斜率，b是y轴截距。给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x,int(y+0.5),color)输出该像素。复杂度：乘法+加法+取整3.2线的生成算法3.2.1直线的生成算法上述方法称为直线绘制基本算法，缺点：每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。数值微分(DDA)法给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：画线过程从x的左端点x0开始，向x右端点步进，步长=1(个像素)，计算相应的y坐标：y=kx+b，取像素点(x,round(y))作为当前点的坐标。计算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx当x=1时yi+1=yi+k即：当x每递增1，

y递增k(即直线斜率)。

图3-1DDA算法基本原理

复杂度：加法+取整数值微分(DDA)法上述采用的增量计算方法称为数值微分算法(DigitalDifferentialAnalyzer，简称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。图3-1DDA算法基本原理

voidDDALine(intx0,inty0,intx1,inty1,intcolor)inti； floatdx,dy,length,x,y;if(fabs(x1-x0)>=fabs(y1-y0))length=fabs(x1-x0);elselength=fabs(y1-y0);

dx=(x1-x0)/length;dy=(y1-y0)/length;i=1;x=x0;y=y0;while(i<=length){SetPixel(int(x+0.5),int(y+0.5),color);x=x+dx;y=y+dy;i++;

xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5图3-2直线段的DDA扫描转换

举例:线段P0(0,0)和P1(5,2)的DDA方法扫描转换DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。Bresenham算法Bresenham算法是1965年提出的，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。

图3-3根据误差量来确定理想的像素点

假设当前直线上的像素坐标为(xi,yi)，那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变，要么递增1，可通过比较d1和d2来决定。

如图3-3所示，对于直线斜率k在0~1之间的情况，从给定线段的左端点P0(x0,y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。yi+1yyixixi+1d2d1根据误差项d的值来决定是否增1的过程如下：设Δy=y1－y0,Δx=x1－x0，则k=Δy/Δx，代入上式，得：

是常量，与像素位置无关。其中yi+1yyixixi+1d2d1则ei的计算仅包括整数运算，其符号与(d1-d2)的符号相同。当ei<0时，直线上理想位置与像素(xi＋1，yi)更接近，应取右方像素；(2)当ei>0时，直线上理想位置与像素(xi＋1，yi＋1)更接近，应取右上方像素；(3)当ei=0时，两个像素与直线上理想位置一样接近，可约定取(xi＋1，yi＋1)。对于第i+1步，误差参数为：此时参数c已经消去，且xi+1=xi+1,得：如果选择右上方像素，即，则：如果选择右方像素，即，则：对于每个整数x，从线段的坐标端点开始，循环的进行误差量的计算。起始像素(x0，y0)的误差参数为：voidBresenham_Line(intx0,inty0,intx1,inty1,intcolor){intdx=x1-x0,dy=y1-y0,e=2*dy-dx;intx=x0,y=y0;for(inti=0;i<=dx;i++){SetPixel(x,y,color);x++;if(e>=0){y++;e=e+2*dy-2*dx;}else{e=e+2*dy;}}}当0<k<1时的Bresenham画线算法程序xye00-110321-331142-552-1图3-4直线段的Bresenham画线法举例:线段P0(0,0)和P1(5,2)的Bresenham画线法思考：k的取值不在0~1之间时，如何处理？X，Y对换当k>1时，x总是增加1，再用Bresenham误差量判别式可以确定y是否增加1。当k<0时，要考虑x或y不是递增1，而是递减1。（不要）3.2.2圆的生成算法为了方便起见，可以只考虑中心在原点、半径为整数的圆：对于中心不在原点的圆，可通过平移变换进行转化。圆上的点关于X轴、Y轴以及45º线对称，只要实现1/8圆的扫描转换就可以利用对称性得到完整的圆。最容易想到的算法如下：根据圆的基本方程，可以沿X轴，x从0到，以单位步长计算对应的y值来得到圆周上每点的位置：该算法每一步均包含浮点乘法和开方运算，且所绘制的像素间间隔不一，随着x的增加，间隔越来越大。3.2.2圆的生成算法一种消除不等间距的方法是使用极坐标来计算沿圆周的点，此时，圆使用参数方程来表示：该算法使用了三角函数和浮点运算，运算速度仍然很慢。与直线绘制算法相似，理想的圆绘制算法也是只需作一些简单的整数和判别运算，常见的有中点画圆法。中点画圆法以从(0，R)到(，)的1/8圆为例，假定当前已确定了圆弧上的一个像素点为，那么，下一个像素只能是右方的或右下方的。中点画圆法构造函数F(x,y)=x2+y2-R2,F(x,y)=0，点在圆上；F(x,y)>0，点在圆外；F(x,y)<0，点在圆内；设M为P1和P2的中点，即M为(xp+1,yp-0.5)若F(M)<0，M在圆内，说明P1点离圆弧更近，则取P1为下一个像素；若F(M)>0，M在圆外，说明P2点离圆弧更近，则取P2为下一个像素；若F(M)=0，M在圆上，P1、P2可任取其一，这里约定取P2。中点画圆法根据上述原理，构造判别式dp=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若dp<0，应则取P1为下一个像素，且判别式变为：dp+1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=dp+2xp+3若dp>=0，应则取P2为下一个像素，且判别式变为：dp+1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=dp+2(xp-yp)+5这里，我们取(0,R)为第一个像素，判别式的初值为：d0=F(1,R-0.5)=1.25-R中点画圆法为了避免浮点数运算，可令e=d-0.25，此时初始化运算d=1.25-R对应于e=1-R，判别式d<0对应于e<-0.25。又由于e的初值为整数，且运算过程中增量也是整数，所以e始终是整数，可以用e<0代替e<-0.25。最后将1/8圆弧做对称处理就能够得到完整的圆。voidCirclePoints(intx,inty,intcolor){SetPixel(x,y,color);SetPixel(y,x,color);SetPixel(-x,y,color);SetPixel(y,-x,color);SetPixel(x,-y,color);SetPixel(-y,x,color);SetPixel(-x,-y,color);SetPixel(-y,-x,color);}根据（x,y）画出另外对称的七个点MidPointCircle(intr,intcolor){ intx=0,y=r;inte=1-r;CirclePoints(x,y,color);//做对称处理