2基本光栅图形算法

2、基本光栅图形算法数学表示的若干方法1）数学方程2）点集3）边界表示4）关系表示常用的图形对象线段圆多边形字符等一、直线在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。线段理想的是无数多的零面积的点构成。而在实际显示中，在光栅扫描显示器上，线段是由有限多的像素组成的，像素是有面积的。画一条从（x1,y1）到（x2,y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。而且除了水平、垂直和对角线上的线段，其他的线段像素并不一定能准确地落在线段上。最接近数学上的直线:生成的线要直：但实际选择最靠近直线的可寻址点来逼近。理想的绘制绘制线段的要求绘制线段的要求起点和终点要准：在绘制线段的过程中由于受精度的影响，线段的终点与原终点有一个累积误差，导致线段的终点不准。绘制线段的要求粗细要均匀：由于选点不均匀，造成线段粗细不均匀，直观上反映出线段的亮度不均匀。光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。实际绘制线段的笛卡儿斜率截距方程bxmy若其始坐标和终点坐标分别为：),(11yx),(22yx1212xxyym则斜率为11xmyb截距为(1)(2)(3)显示直线的算法可以直线方程（1）、（2）和（3）为基础。1.逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线。偏差判别选择象素点终点判别偏差计算结束否保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。绘制思路由一个点到下一个点的走法是只在X方向或Y方向走一步。OA计算偏差OA‘K1K2设=tg-tg于是有1)=0，点在直线上；2)0，点在直线上方；3)0，点在直线下方。设偏差计算公式为：=tg-tg=FkYXYXXXkAAkAk偏差计算11;0011YYX可以简化为FYXYXkkAAk根据计算出偏差，然后确定下一步的走向。初始：Fk则=0；第一步：如果选择X方向，则;0;11101YXX;0;000YX55*17*0111XYXYFAA0F若选择Y方向，则75*07*1111XYXYFAA所以选择X方向走，则第一步选择（1，0）点处步数走X的偏差走Y的偏差最后选择000（0，0)1-57走X，至（1，0）2-102走Y，至（1，1）3-39走X，至（2，1）4-84走Y，至（2，2）5-111走X，至（3，2）6-66走X，至（4，2）7-111走Y，至（4，3）8-48走X，至（5，3）9-93走Y，至（5，4）10-210走X，至（6，4）11-75走Y，至（6，5）12010走X，至（7，5）起点（0，0）终点（7，5）XA=7YA=5FYXYXkkAAk绘制结果OA偏差递推公式1）时，走X方向一步，即0iF;;;1111AiiiiiiYFFYYXX2）时，走Y方向一步，即0iF;;1111AiiiiiiXFFYYXX偏差递推公式以上讨论的是起点为原点，第一象限的情况，对于其他情况下的绘制直线的偏差计算和偏差判别，推导也很简单。Fi=0Fi01象限3象限X＋1X－1Fi+1=Fi－|YA|Y＋1Y－1Fi+1=Fi＋|XA|2象限4象限Y＋1Y－1Fi+1=Fi－|XA|X－1X＋1Fi+1=Fi＋|YA|终点判别判别终点的方法：设立计数器，计数取X或Y方向的最大增量值（计长方向），在计长方向每走一步，计数器减1，直到计数器值为零为止。绘制直线OA2.DDA(DigitalDifferentialAnalyzer)数字微分该算法是建立在微分方程的基础上。由到的直线段满足的微分方程为：),(AAyx),(BByxABAByydtdyxxdtdx因此有ABAByytyxxtx则有tyyytxxxABAB)()(令),max(1ABAByyxxt有yyyxxxiiii11此递归式的初值为直线的起点，这样，就可以用加法来生成一条直线。),(AAyxVoiddda_line(xa,ya,xb,yb,c){floatdelta_x,delta_y,x,y;intdx,dy,steps,k;dx=xb-xa;dy=yb-ya;if(abs(dx)abs(dy))steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;x=xa;y=ya;putpixel(round(x),round(y),c);for(k=1;k=steps;k++){x+=delta_x;y+=delta_y;putpixel(round(x),round(y),c);}}DDA绘制的直线tOA1/15；6.01591yx算法特点：该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。3.Bresenham算法设直线从起点（x1,y1）到终点（x2,y2）。直线可表示为方程y=mx+b。其中b=y1-m*x1,m=本算法由Bresenham在1965年提出。算法的基本思想：每次迭代在增量最大方向上均走一步，其方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。dxdyxxyy1212xi+1=xi+Dxyi+1=yi+Dy按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限。对于方向在第1a象限内的直线而言，Dx=1，Dy=m。对于方向在第1b象限内的直线而言，取值Dy=1，Dx=1/m。各象限中直线生成时Dx,Dy的取值列在下页表中。象限|dx||dy|?DxDy1a√1m1bX1/m12a√-1m2bX-1/m13a√-1-m3bX-1/m-14a√1-m4bX1/m-1绘制的直线时点的选取riy,riy,1yiyi+1选择哪一个点？(Xi＋1，Yi,r)还是(Xi＋1，Yi+1,r)用Yi+1与Yi,r进行误差计算，误差大于0.5选择上面的点，否则选择下面的点。使用偏差来计算确定那一个点。偏差计算设偏差为5.0)(,11riiiyyx当时，计算的点（实际直线上的点）在中点的上方，取当0时，计算的点（实际直线上的点）在中点的下方，取0)(1ix)(1ix1,,1ririyyririyy,,1整理后，有0)(0)(111,1,,11iriiririiixyxyyxx偏差的递推关系5.0)(,11riiiyyx误差因为myyii1有0)()(0)(1)(0)(5.00)(5.0)1(5.05.0)(,1,1,,11iiiiiriiiriiriiriiixmxxmxxmyyxmyyymyyyx此时，算法中仍有浮点数运算，而且m=dy/dx,并且dx〉0，所以我们引入F=2*dx*F与的符号相同可以用来作为判别式。因此，初始x=x1,y=y1,F1=2dy-dx其递推公式：若Fi0,则xi+1=xi+1,yi+1=yi,Fi+1=Fi+2dy;若Fi=0,则xi+1=xi+1,yi+1=yi+1,Fi+1=Fi+2(dy-dx);总结：算法公式初始条件：F1=2dy-dx当Fi≥0时：yi+1=yi+1,xi+1=xi+1，Fi+1=Fi+2(dy-dx)否则：yi+1=yi,xi+1=xi+1，Fi+1=Fi+2dy第一象限下算法思想如下：此时满足：0≤m≤1且x1x21、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；2、画点(x1,y2);3、dx=x2-x1;dy=y2-y1；计算误差初值P1=2dy-dx;i=1；4、求直线的下一点位置：xi+1=xi+1；ifPi0则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1,yi+1）；4、求下一个误差Pi+1；ifPi0则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1;ifidx+1则转4；否则end算法的完善，所有象限线段的方向可分为八种，从原点出发射向八个区。由线段所在区域位置可决定xi+1和yi+1的变换规律。1a、2a3a、4a1b、4b2b、3b容易证明：当线段处于a区时，以|dx|和|dy|代替前面公式中的dx和dy，当线段处于b区时，将公式中的|dx|和|dy|对换，则上述两公式仍有效。Bresenham算法的优点Bresenham算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenham算法速度很快，并适于用硬件实现。程序代码：由上述算法思想编制的程序如下。这个程序适用于所有8个方向的直线的生成。程序用色彩C画出一条端点为（x1,y1）和（x2,y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断|dx||dy|为分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。代码：voidline(x1,y1,x2,y2,c)intx1,y1,x2,y2,c;{intdx,dy,x,y,p,const1,const2,inc,tmp;dx=x2-x1;dy=y2-y1;if(dx*dy=0)/*准备x或y的单位递变值。*/inc=1;elseinc=-1;if(abs(dx)abs(dy)){if(dx0){tmp=x1;/*将2a,3a象限方向*/x1=x2;/*的直线变换到1a,4a*/x2=tmp;/*象限方向去*/tmp=y1;y1=y2;dx=-dy;dy=-dy;}p=2*dy-dx;const1=2*dy;/*注意此时误差的*/const2=2*(dy-dx);/*变化参数取值.*/x=x1;y=y1;set_pixel(x,y,c);while(xx2){x++;if(p0)p+=const1;else{y+=inc;p+=const2;}set_piexl(x,y,c);}}代码：else{if(dy0){tmp=x1;/*将3b,4b象限方向的*/x1=x2;/*直线变换到2b,1b*/x2=tmp;/*象限方向去.*/tmp=y1;y1=y2;dx=-dy;dy=-dy;}p=2*dx-dy;/*注意此时误差的*/const1=2*dx;/*变化参数取值.*/const2=2*(dx-dy);x=x1;y=y1;set_pixel(x,y,c);while(yy2){y++;if(p0)p+=const1;else{x+=inc;p+=const2;set_pixel(x,y,c);}}}总结前面所介绍的逐点比较法、数值微分法以及Bresenham算法，都是一种单点生成直线的的算法。它们各有优缺点，因此在使用不同的图形输出设备时要选用最适合于该设备的方法，如在绘图仪中多采用逐点比较法，在点迹技术的显示设备中多用DDA法和Bresenham算法。单点生成直线的算法已经没有优化的余地比如bresenham算法，其计算量主要体现在主循环