一种快速的Bresenham直线生成改进算法.docVIP

一种快速的Bresenham直线生成改进算法 摘 要：直线的生成算法是图形光栅化中最基本的算法，基于经典的Bresenham算法，提出了一种新的直线生成算法，该算法通过直线的第一和第二像素行的像素点数目计算其他各个像素行的像素点数目，利用直线的对称性，每执行一次生成两个像素行。算法中不包含浮点运算和取整运算，且算法的执行次数减少，使得直线的生成速度加快。 关键词：图形光栅化；Bresenham算法；增量；误差项 中图分类号：TP301.6 直线是图形中的基本元素，到目前为止已有很多种直线的生成算法，如数值微分法、中点画线法和Bresenham算法[1]，其中Bresenham算法研究的最多，它的原理是：以各行各列的像素为中心虚拟一组坐标线，按直线上x坐标从小到大的顺序，计算直线与各个坐标线的交点，确定与该交点距离最小的像素。本文在研究了经典的Bresenham算法以及诸多改进算法之后，提出了一种快速的Bresenham直线生成改进算法，既保留了Bresenham算法中无需浮点运算和取整运算的优点，又能使得每次计算生成一个像素行，极大地提高了算法的执行效率。 1 Bresenham算法的基本思想 先考虑直线段位于第一象限、斜率|m|≤1时的扫描转换过程从直线的第一个像素点（x0，y0）开始，以横坐标由大到小的顺序依次寻找与直线最接近的像素点。如图1所示，假设坐标为（xk，yk）为直线的当前像素点，然后在列xk+1上确定扫描线y的值。 Bresenham算法的优点在于使用增量计算，确定所选的像素。相对于其他直线的生成算法而言，它避免了乘除法运算和取整运算，效率较高。但是每次只能判断一个误差项的符号，生成一个像素点。因此，许多专家对Bresenham算法作了一些改进，基本上都是通过直线的斜率求每行的像素点个数[3]，来提高直线的生成速度，但由于引进了浮点运算甚至除法运算，使得整体的改进效率提高不大。 2 快速的Bresenham直线生成改进算法 设像素点P（xp，yp）为当前的像素点，则待选择的像素点可能是点E或点G如图2所示。设F（x，y）为需光栅化的直线函数，点E和点G的中点为M，如果F（M） 0，则点M在该直线的下方，选则点G，如果F（M）≤0，则点M在直线上方，选则点E。Bresenham算法定义了一个判定变量d F（xp+1，yp+1/2），通过d值的正负来选择下一个像素点的坐标[4]。 通过以上分析可以得知，通过Bresenham算法生成的直线除却起始和终止两行像素点外，中间各像素行的像素点个数满足：Q≤e≤Q+1。 确定了像素行的第k个像素点的判定变量的符号，可以推断该行的像素点个数。因为dk d1+2kdy-2dx，如果dk0，下一像素行的像素点个数为Q个，计算一次d值可以找到一个像素行的所有像素点。 本改进算法的关键是求Q的值，本文大胆猜测使用直线的前两行像素点个数求Q的值。通过数学分析证明，若Bresenham算法生成的直线的前两个像素行分别有n和m个像素点，则 可以通过两种情况论证上述结论： 1）如果Bresenham算法生成的直线的第1个像素行的像素点个数为n，则2n-2≤dx/dy0，即 ，其中，d0 2dy-dx为d的初值，是直线第2个像素点的d值，将d0代入 ，得2n-2≤dx/dy 2n； 2）如果Bresenham算法生成的直线的第2个像素行有m个像素点，则m-1≤dx/dym+1，且2n-1≥m+1 dx/dy≥2n-2则Q 2n-2；若2ndx/dy≥m-1则Q m-1；若2n m+1，dn+1 0，而第m+n个像素点的判定变量dm+n≤0，且第m+n+1个像素点的dm+n+1 0，则Q 2n-1。 3 算法及验证 将上述数学思想转化为算法[6]，程序如下。其中变量valuel，valueB是直线和背景的颜色值；函数Linel表示参照value取点共n个像素点；由Bresenham算法生成前两行以及末行像素，新算法生成其他各像素行。 在该算法中，没有除法、取整以及浮点运算，只通过两次减法就求得了n和m，通过一次计算又求得了Q的值，每执行一次就能生成一个像素行，另利用直线的对称性，使得每执行一次就能生成两个像素行。将该算法在计算机上实现，如表1所示，改进算法与Bresenham算法相比效率明显提高。 由算法的原理可知，当待生成直线只有一个像素行时，改进算法与Bresenham算法的生成速度相同，其他情况下，改进算法的执行速度都明显高于经典的Bresenham算法，且生成的像素行数越多，节省的执行时间就越明显。 4 结束语 本文在研究经典Bresenham算法的基础上，提出了一种快速的直线生成算法，利用直线的第一行像素点个数推出其他各像素行的像素点数目，充分利用直线的对称性使得每执行一次能生成两个像