Bresenham画线算法之我见

Bresenham画线算法 一般的教程讲的比较隐晦， 这里有一篇推导过程，用纯数学语言讲的，也比较晦涩... 个人做了一点形象上的理解，核心思想就不说了。 首先算法在判断下一个点的位置时，到底是向右移一格还是向右上移一格是根据斜率是否大于0.5来判断的。 为什么是0.5呢？ 因为向右一格等于dx=1,dy=0，即斜率等于0。而向右上一格等于dx=1,dy=1，即斜率等于1。折中一下就有了0.5这个系数。 接着累加斜率直到超过0.5之后，右上一格再右面的判断就要看是否超过1.5了。 这是因为向右上移了一格，y加了1，而它右面的格子只可能比它高或一样高，不可能比它低。

这样一直到最后，只要向上移一格，判断系数就加1。

 1  dy = y1 - y0;  2  dx = x1 - x0;  3  k = dy / dx;  4  d = 0 ;  5  b = 0.5 ;  6  ix = x0;  7  iy = y0;  8  while (ix <= x1){  9      ++ ix; 10     d  +=  k; 11      if (d  >  b){ 12         ++ iy; 13         ++ b; 14     } 15  }

 

这里面d就是用来累加斜率的，b是判别系数。

以上是我对Bresenham算法的理解，但市面上常见的是没有b这个判别系数的。因为判别系数跟着加1和坐标轴跟着加1是一样的，而坐标轴向上平移1个单位等于d减去1。

这样的好处很显然，少用一个变量。这就是传统的算法。

 1  dy = y1 - y0;  2  dx = x1 - x0;  3  k = dy / dx;  4  d = 0 ;  5  ix = x0;  6  iy = y0;  7  while (ix <= x1){  8      ++ ix;  9     d  +=  k; 10      if (d  >   0.5 ){ 11         ++ iy; 12         -- d; 13     } 14  } 

 

然后是优化上的理解。

先考虑，斜率是否大于0.5，即k-0.5是否大于0。如果是就说明要向上，那么在累加斜率时要再减去1使得坐标轴也跟着向上。否则只加斜率就可以了。

 1  d = k - 0.5  2  while (ix <= x1){  3      ++ ix;  4      if (d > 0 ){  5         ++ iy;  6        d += k - 1 ;  7     } else {  8        d += k;  9     } 10  } 

 

接下来是要去掉浮点数和除法运算。 考虑 d=k-0.5 两边同时放大一倍，等式不变 2*d=2*k-1 同样把dy/dx=k代入 2*d=2*dy/dx-1 2*d*dx=2*dy-dx

因为2和dx都是正数，只要之后的运算都放大2*dx倍，等号、不等号都不会受到影响。最终简化如下：

 1  dy = y1 - y0;  2  dx = x1 - x0;  3  D = 2 * dy - dx;  4  ix = x0;  5  iy = y0;  6  while (ix <= x1){  7      ++ ix;  8      if (D > 0 ){  9         ++ iy; 10        D += 2 * (dy - dx); 11     } else { 12        D += 2 * dy; 13     } 14  }

 

我用D表示放大了的d，实际代码中可以直接用同一个变量d。

最后是一般化

如果k<0，也就是本来往上走的，要往下走。这时仍用以前的思路，就要判断是否k-0.5<0，并且在是的时候坐标轴跟着往下移，然后y每次减1。 考虑让k>0，那么所有判断都不变，只要让y每次减1就可以了。因为判断条件只和斜率有关，和y的走向没有关系。我们完全可以根据同一个斜率，通过+-来改变y的走向，+的话就和斜率同向，-的话就和负斜率同向。而k本身是<0的，现在被我们变了向，那么y的走向再变一次，y的走向就成了我们需要的走向。 而此处是垂直翻转，改变k的符号，只要把dy取绝对值就可以了。

如果|k|>1，所谓的折中系数0.5就没意义了，这时可以把x轴看作y轴，y轴看作x轴，这样斜率又回到了0<|k|<1。只要最后在画线的时候，把x当y，y当x来填充就可以了。

最后考虑反向画线，也就是起点大于终点的情况，那很简单把它们颠倒一下就可以了。

注意，以上|k|>1时xy轴的互换的过程要放在最前面。因为在k>-1时，xy轴的互换会使起点终点关系互换，这时需要后面有检测机制。

pcode xy2yx= abs(y1-y0) > abs(x1-x0);if(xy2yx){    swap(x0,y0);    swap(x1,y1); }if(x0>x1){    swap(x0,x1);    swap(y0,y1); } ydir = y0>y1 ? -1 : 1; dy=abs(y1-y0); dx=x1-x0; d=2*dy-dx; ix=x0; iy=y0;while(ix<=x1){    if(xy2yx){       draw(iy,ix);    }else{       draw(ix,iy);    }    ++ix;    if(d>0){       iy += ydir;       d+=2(dy-dx);    }else{       d+=2*dy;    } }

 

转载于:https://www.cnblogs.com/holybozo/archive/2009/04/26/1444205.html

相关资源：C ，OpenGL实现任意象限的Bresenham画线算法