002计算机图形学之直线画线算法

我们知道直线方程的斜截式是如下的样子：

代码语言：javascript

复制

y = kx +b

在显示器上显示直线的话，如果使用如上的方程，每描一个点

需要进行一次浮点乘法，一次浮点加法，和取整操作。

DDA算法 digital differential analyzer

对斜截式进行转换成如下：

$y_{k+1}=y_{k}+m$

由此我们可以根据起点依次推算到最后一个点，实现如下：

代码语言：javascript

复制

    inline int round(const float a) { return int(a + 0.5); }
void lineDDA(int x0, int y0, int xEnd, int yEnd)
{

    int dx = xEnd - x0, dy = yEnd - y0, steps, k;
    float xIncrement, yIncrement, x = x0, y = y0;

    if (fabs(dx) &gt; fabs(dy))
      steps = fabs(dx);
    else
      steps = fabs(dy);

    xIncrement = float(dx) / float(steps);
    yIncrement = float(dy) / float(steps);

    //SetPixel(round(x), round(y));
    for (k = 0; k &lt; steps; k++) {
      x += xIncrement;
      y += yIncrement;
      //SetPixel(round(x), round(y));
    }
}</code></pre></div></div><h4 id="ft42v" name="%E4%BC%98%E7%82%B9">优点</h4><p>取消了乘法，计算速度更快。</p><h4 id="dupbe" name="%E7%BC%BA%E7%82%B9">缺点</h4><ol class="ol-level-0"><li>浮点增量连续增加，取证误差会积累</li><li>取整操作和浮点运算仍然十分耗时</li></ol><h2 id="80qs9" name="Bresenham%E7%94%BB%E7%BA%BF%E7%AE%97%E6%B3%95">Bresenham画线算法</h2><p>主要思想是，由于我们在缓存区上画点，全部是整数。那么在画线的时候，当斜率k小于1的时候，下一个点是取（x+1，y+1）还是（x+1，y）取决于点（x+1，y+0.5）是在该直线的上方或者下方，从而将可以通过判断一个参数的的符号来得到下一个点的位置，提高了代码的效率。</p><p>算法可以表达为如下：</p><p>|m|&lt;1 时的Bresenham画线算法</p><ol class="ol-level-0"><li>输入线段的两个端点，并将左端点存储在（x0，y0）中；</li><li>将（x0，y0）装入帧缓存，绘制第一个点；</li><li> 计算常量△x,  △y   2△y 和2△y-2△x，并得到决策参数的第一个值:

p_0 = 2△y - △x
  从k=0开始，如果pk<0,则下一个点是（/x_k+1,yk）,并且
 $p_{k+1} = p_k + 2△y$
 否则，下一个绘制点是(xk+1,yk+1),并且
 $p_{k+1} = p_k+2△y-2△x$
 
重复步骤4，共△x-1次。
考虑到xy平面各种八分和四分区域的对称性，此算法对任意斜率的线段具有通用性。