Bresenham’s algorithm( 布兰森汉姆算法)画直线

简介

• 1967年，IBM的J.Bresenham提出了Bresenham算法。
• Bresenham算法是在一些约定条件下的最佳逼近。
• Bresenham算法通过前一个像素点提供的信息来判定后一个像素点的位置。
• DDA算法虽也可绘制直线，但该算法中存在类型转换以及除法运算，当需要画大量的直线时，速度慢。而Bresenham算法则只涉及加法和乘法，且乘法是乘2操作，相当于移位，减少了画直线所需的时间。
  

符号说明（Notations）

• 直线从（x₀，y₀）开始，到（x₁，y₁)结束。
• 设
• 假设斜率|m| ≤1。
• 从x = x₀开始，每次对x轴的值增加1。
• 令第i个像素点的坐标为（x_i，y_i）
• 则下一个像素点的坐标只能为（x_i + 1，y_i）或（x_i + 1，y_i + 1）

判别标准（Criteria）

• 当选择下一个要画的点时，选择距离下面交点更近的一个像素点。
  
• 两个候选像素点到交点的距离分别为：
  
  显然： 如果d_lower - d_upper > 0，则取交点上方的点作为下一个点；如果d_lower - d_upper < 0，则取交点下面的点作为下一个点；如果d_lower - d_upper = 0，则可任选一点。

判别条件的计算（Computation of Criteria）

• 由于m（斜率）的计算是除法运算，为了节约运算时间，我们需要去掉除法运算。不妨把代入上式，再两边同时除以△x。由前面判别条件可以知道，我们所关注的只是d_lower - d_upper 的符号（正负），而△x的符号肯定为正的，因此，可以作如下处理：
  
  其中：
  
  对于p_i，我们可以得出如下结论：
  • 如果p_i > 0，则选择（x_i + 1，y_i + 1）作为下一点；
  • 如果p_i < 0，则选择（x_i + 1，y_i）作为下一点；
  • 如果p_i = 0，则随机选一个。

简化计算，递归求P_i

• 首先，对于p₀，我们有：
  
• 易知：
  
• 如果p_i ≤ 0，根据上面结论，选择（x_i + 1，y_i）作为下一点，则此时y_i+1 - y_i = 0，因此：
• 如果p_i ≤ 0，根据上面结论，选择（x_i + 1，y_i+1）作为下一点，则此时y_i+1 - y_i = 1，因此：
• 通过上面所述，知道了p₀以及p_i和p_i+1的关系，则可以画直线了。

Bresenham总结

1. 画出（x₀，y₀）
2. 计算△x，△y，2△y，2△y - 2△x，p₀ = 2△y - △x
3. 如果p_i ≤ 0，画出（x_i+1，y_i+1） = （x_i + 1，y_i），同时计算p_i+1 = p_i + 2△y
4. 如果p_i ＞ 0，画出（x_i+1，y_i+1） = （x_i + 1，y_i + 1），同时计算p_i+1 = p_i + 2△y - 2△x
5. 重复第3步和第4步，直到画完直线。

• 例如：画出直线(3,4)-(8,7)