Introduction

计算机图形学课上介绍了一个由两点所决定的直线的算法——Bresenham 算法 ；

这个算法用到了快速的整数加法，减法和位元移位，是计算机图形里面描绘直线的较为快速的算法。

首先来介绍一下，绘制直线的基本方法:

假设我们需要由(x0, y0)这一点，绘画一直线至右下角的另一点(x1, y1)，x,y分别代表其水平及垂直坐标，并且x1 - x0 > y1 - y0。

因为像素点需要的x及y皆为整数，但并非每一点x所对应的y皆为整数，因此没有必要去计算每一点x所对应之y值。反之由于此线的斜率介乎于1至0之间，因此我们只需要找出当x到达那一个数值时，会使y上升1，若x尚未到此值，则y不变。至于如何找出相关的x值，则需依靠斜率。斜率之计算方法为 $m=(y_{1}-y_{0})/(x_{1}-x_{0})$ 。由于此值不变，故可于运算前预先计算，减少运算次数。

Problem

但这里遇到了一个问题，由于计算机图形学对速度要求较高，而上面提到的算法中用到了大量的浮点运算；而且，经过大量的浮点运算，误差会被大量积累。因此为了避免这种情况发生，应该将浮点运算转换为整数运算。

因此就引入了这种算法：Bresenham's line algorithm

首先来看这张图：

由此可见，每次xi增加时，yi都有两个选择：y(i+1) =yi or y(i+1) =yi + 1；因此我们需要比较d1和d2的大小：
- y = m(xi + 1) + b
- d1 = y - yi
- d2 = yi + 1 - y
- If d1-d2 > 0，then y(i+1)=yi + 1，else yi+1 = yi
根据上面的式子和m = dy/dx (dy = y1 - y0；dx = x1 - x0)，我们可以计算得：
- d1-d2= 2y - 2yi - 1= 2dy/dxxi + 2dy/dx + 2b - 2yi - 1*
关键点来了，为了避免浮点数运算，我们在两边乘以dx；假设 dx*(d1-d2) = Pi:
- Pi = 2xidy - 2yidx + 2dy + (2b-1)dx
- 同理：P(i+1) = 2x(i+1)dy - 2y(i+1)dx + 2dy + (2b-1)dx

这时，当Pi > 0，下一个y取 yi + 1，否则还是yi；

因此我们可以得到一个增量函数：P(i+1) = Pi+2dy-2(y(i+1)-yi)dx;
既然是增量函数：我们要求起始P0：
- 由上面的式子，P0 = 2x0dy - 2y0dx + 2dy + (2b-1)dx；
- 两边除以dx，得到 P0/dx = 2x0m - 2y0 + 2m + (2b-1)；
- 结合: 2x0m - 2y0 + 2b = 0，得到P0 = 2mdx - dx = 2dy - dx ；

以上就是，我们对此算法的推导，通过整数运算，移位等，根据Pi的正负，即可快速描绘出直线；

Pseudocode

function line(x0, x1, y0, y1)//假设x0 < x1; y0 < y1
    draw(x0, y0)，dx=x1-x0，dy=y1-y0
    int P0 := 2dy - dx
    for x from x0 to x1
       if Pi>0，then y(i+1) = yi+1，else y(i+1) = yi；
	draw(x(i+1), y(i+1))
	if Pi>0，then P(i+1) = Pi + 2dy - 2dx，else P(i+1) = Pi + 2dy；//calculate P(i+1)

至于线段方向改变等问题，则只要交换x和y即可；