一文读懂Bresenham画线算法 bresenham画线算法(0,0)(5,2)

1965年，Bresenham为数字绘图仪开发了一种绘制直线的算法，针对当前主流的光栅扫描显示器同样适用。这里仅讨论斜率在[0,1)区间的情况。

Bresenham算法要点

1. Bresenham算法是一个增量算法，依据xk推导出下个像素xk + 1的坐标。

2. Bresenham算法只使用整数运算，在图形学刚刚起步的年代，计算效率非常重要，整数运算要比浮点、乘除运算快。

从xk得出xk + 1的像素坐标

假设(xk, yk)为已经确定的像素坐标，那么下一个像素坐标为(xk + 1, yk)或(xk + 1, yk + 1)，确定y轴坐标选择哪一个的依据是判断直线和x = xk + 1轴的交点离yk + 1、yk哪个更接近。这里使用du（dupper）表示yk + 1和理想直线交点的偏差，dl（dlower）表示理想直线交点和yk的偏差。

du = yk + 1 ? m(xk + 1) ? b

dl = m(xk + 1) + b ? yk

计算两个值的偏差dl ? du

dl ? du = 2mxk ? 2yk + 2m + 2b ? 1

如果偏差小于0说明交点更接近yk，应该选择yk；如果偏差大于0说明交点更接近yk + 1，应该选择yk + 1；如果偏差等于0说明交点刚好位于中点位置，选择哪一个都可以，这里约定选择yk + 1。

一般画线算法需要提供两个端点(x0,y0)、(x1,y1)，根据直线方程我们很容易计算出m和b，也就是说dl ? du中的变量都是已知量，根据这个偏差的正负我们就可以从起始端点递推出直线上的每一个像素点了，但是由于这个偏差的计算包含了浮点、乘除法（计算m）运算，为了进一步提升计算效率，接下来还需要进行转换使其只需要整数运算。

转换为整数运算

直线光栅化的步骤就是从起始端点(x0,y0)逐步递推计算下一个像素的坐标直到达到末端点(x1,y1)，确定下一个像素的坐标的方法就是判断偏差dl ? du的正负号。接下来的步骤是对这个偏差计算的优化，使其只需要整数运算。

说明：这里约定x1>x0

定义pk = Δx(dl ? du)，上面的公式可变换为

pk = 2Δyxk ? 2Δxyk + 2Δy + Δx(2b ? 1)

因为Δx大于0，因此pk的正负号和dl ? du是一样的，可以使用pk的正负号作为第k步的决策参数来确定下一个像素的坐标。

显然接下来我们需要确定第0步的初始决策参数p0：

还需要确定pk+1怎么由pk来计算：

pk+1 = 2Δyxk+1 ? 2Δxyk+1 + 2Δy + Δx(2b ? 1)

因为这里xk+1表示下一个像素的x坐标，为xk + 1

pk+1 = 2Δyxk + 2Δy ? 2Δxyk+1 + 2Δy + Δx(2b ? 1)

pk+1 = 2Δyxk ? 2Δxyk + 2Δy + Δx(2b ? 1) + 2Δy ? 2Δxyk+1 + 2Δxykpk+1 = pk + 2Δy ? 2Δx(yk+1 ? yk)

其中yk+1表示第k步的下一个像素的y坐标，为yk或yk + 1，根据前面的内容可知它由pk决定

pk ≥ 0 => yk+1 = yk + 1 => pk+1 = pk + 2Δy ? 2Δx

pk < 0 => yk+1 = yk => pk+1 = pk + 2Δy

上面的公式中，Δy和Δx是直线端点x、y轴变化量，是已知且固定不变的，因此2Δx和2Δy都可以一次性计算好，后续的递推运算只需要简单的整数加减运算就可以了。

Bresenham算法总结

根据上面的推导过程，我们就可以得出bresenham画线算法的步骤了：

1. 输入线段的两个端点，确定左端点为起始坐标点(x0,y0)，末端点为(x1,y1);

2. 画第一个点(x0,y0);

3. 计算公式需要用到的常量Δx, 2Δx, 2Δy, 2Δy ? 2Δx，计算第一个决策参数p0 = 2Δy ? Δx;

4. 从k=0开始，针对每个xk，根据pk的值做如下检测：

如果pk>=0，则下一个像素画(xk + 1, yk + 1)，计算pk+1 = pk + 2Δy ? 2Δx

如果pk<0，则下一个像素画(xk + 1, yk)，计算pk+1 = pk + 2Δy

5. 重复步骤4，重复次数x1-x0-1次数。

参考文献

[1] 《计算机图形学》[美]Donald Hearn M. Pauline Baker著（第三版），第3章输出图元，page73;