Bresenham快速画直线算法

Bresenham算法是DDA算法画线算法的一种改进算法。本质上它也是采取了步进的思想。不过它比DDA算法作了优化，避免了步进时浮点数运算，同时为选取符合直线方程的点提供了一个好思路。首先通过直线的斜率确定了在x方向进行单位步进还是y方向进行单位步进：当斜率k的绝对值$|m|<1$时，在x方向进行单位步进；当斜率k的绝对值$|m|>1$时，在y方向进行单位步进。

下面以$|m|<1$时推导Bresenham算法的数学依据：

请看上图，已知有一直线$y = mx+b，|m|<1$。我们通过斜率确定了x方向为单位步进。当$x = x_k$时，$y = y_k$。那么当x执行一个单位步进时（即$x = x_k+1$时）,y等于$y_k$还是等于$y_k+1$更符合这个直线方程呢？单凭肉眼我们很难得出结论，最好的办法当然是比较$y_k$和$y_k+1$和真实的方程的y值的差是多少（即$y_{real} = m*(x_k+1)+b$），看看哪一个更靠近真实的方程的y值。

算法的具体过程，其实就是在每次画点的时候选取与实际直线的交点y坐标的差最小的那个点。这里假设：
$$
d_{upper} = (y_k + 1) - y_{real} \\
d_{down} = y_{real} - y_k
$$
要确定两像素中哪一个更接近线路径，需测试两个像素偏移的差：
$$
d_{upper} - d_{down} = 2y_k - 2mx_k -2m - 2b + 1
$$
由于$m=\dfrac{\Delta y}{\Delta x}$,我们有：
$$
p_m = \Delta x(d_{upper} - d_{down}) = 2\Delta x y_k - 2\Delta y x_k + \Delta x - 2\Delta y - 2b\Delta x
$$
则：
$$
p_{m+1} = 2\Delta x y_{k+1} - 2\Delta y x_{k+1} + \Delta x - 2\Delta y - 2b\Delta x
$$
相减可得到：
$$
p_{m+1} - p_m = 2\Delta x (y_{k+1} - y_k) - 2\Delta y (x_{k+1} - x_k)
$$
因为$x_{k+1} = x_k + 1$，所以有：
$$
p_{k+1} - p_k = 2\Delta x (y_{k+1} - y_k) - 2\Delta y
$$
其中，$y_{k+1} - y_k$取0还是1，取决于$p_m$的符号。

明白了数学原理，我们很快能确定算法步骤：

1、输入线段的两个端点，并将左端点存储在$(x_{Begin}, y_{Begin})$中；

2、将$(x_{Begin}, y_{Begin})$装入帧缓存，画出第一个点；

3、计算$\Delta x, \Delta y$，并得到决策参数的第一个值：
$$
p_0 = 2\Delta x y_0 - 2\Delta y x_0 + \Delta x - 2\Delta y - 2b\Delta x
$$
因为$y_0 = mx_0 + b = \dfrac{\Delta y}{\Delta x}x_0 + b$,所以代入可得：
$$
p_0 = \Delta x - 2\Delta y
$$
4、从$k=0$开始，在沿线路径的每个$x_k$处，进行下列检测：

如果$p_k < 0$,下一个要绘制的点是$(x_{k+1}, y_{k+1})$，并且：
$$
p_{k+1} = p_k + 2\Delta x - 2\Delta y
$$
否则，下一个要绘制的点是$(x_{k+1}, y_k)$，并且：
$$
p_{k+1} = p_k - 2\Delta y
$$
5、重复步骤4，共$\Delta x - 1$次

上面是完整严谨的数学推导。当然，也可以用直观的递推方式来实现算法。如图所示，我们可以假设在$(x_k, y_k)$时误差为$\varepsilon$,即实际直线上的点为$(x_k, y_k + \varepsilon)$，那么下一个位于直线上的点应该为$(x_k + 1, y_k + \varepsilon + m)$。可以看出，当$\varepsilon + m < 0.5$时，绘制$(x_k + 1, y_k)$点，否则绘制$(x_k + 1, y_k + 1)$点。每次绘制后，$\varepsilon$将更新为新值：

$\varepsilon = \varepsilon + m$, 如果$\varepsilon + m < 0.5$

$\varepsilon = \varepsilon + m - 1$, 其他情况

将上述公式都乘以$\Delta x$, 并将$\varepsilon * \Delta x$用新符号$\xi$表示，可得

$\xi = \xi + \Delta y$, 如果$2*(\xi + \Delta y) < \Delta x$

$\xi = \xi + \Delta y – \Delta x$, 其他情况