每次想寫點東西的時候，都不知道該寫點什麼，想起來在AI for Game Developer上看到使用bresenham算法來做tile地形中的追逐和逃避算法，正好可以寫點關於直線畫法的東西，這也是計算機圖形學中的基本圖元生成算法了，還是比較簡單的。很多人都寫過，網上資料也很多，這裡也就不怕再重復一次了。
首先從最直觀的DDA算法說起，已知過端點P0 (x0, y0), P1(x1, y1)的直線段L：y = kx + b，容易得知直線斜率為：k = (y1-y0)/(x1-x0)，（假設x1 ≠ x0）。
我們假設|k| ≤ 1，這樣x每增加1，y將增加k，並且保證x每增加1，y的增量不能大於1；如果|k| > 1,則應該將x和y互換。由於k是浮點數，因此算法中需要將y捨入為int型，並圓整到最接近的位置。
算法本身也很簡單，C++形式的算法實現如下：
void drawLineDDA(int x0, int y0, int x1, int y1, long color)
{
int dx = x1- x0;
itn dy = y1- y0;
float k = dy/dx;
float y = y0;
for (int x = x0; x <= x1; x++){
setpixel (x, int(y+0.5), color);
y=y+k;
}
}
很明顯DDA算法在每次迭代中的x, y值是上一步的值加上一個增量獲得的，因此它是一個增量算法。
但是這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次捨入運算。
Bresenham畫線算法是使用最廣泛的直線生成算法，DDA算法確定下一個點坐標的方式是根據直接斜率k得到，由於k是浮點數，因此將不得不使用浮點運算，並將浮點數轉換整數。而Bresenham算法的思想則是根據誤差項來決定下一個像素是取正右方還是右上方（|k| < 1的情況），因此就不需要求斜率k的除法運算和浮點數運算，提高了效率。
假設以確定了第i個點Pi(xi, yi)，接下來需要確定第i+1個點P(x, y)，那麼根據直線方程有：
y = yi + k;
1) 求出k = (y1 – y0)/(x1 – x0)，初始化delta = -0.5;
2) 迭代x，每次delta += k，如果delta ≥ 0則表明需要取右上方的點，使y增1，同時使e減1；
算法代碼如下：
int dx = x1- x0;
itn dy = y1- y0;
float k = dy/dx, delta = -0.5f;
for (int x = x0, y = y0; x <= x1; x++){
setpixel (x, y, color);
delta +=k;
if(delta >= 0){delta -= 1; y++;}
}
}
考察上面的方法，依然需要計算k和使用浮點數；好像比起DDA沒有什麼改進嘛，只不過是將浮點運算搬到了誤差項delta上而已，其實我們距目標已經非常近了，從算法中可以看到只用到誤差項delta的符號來判斷，因此可以做如下的簡單替換：
e = delta*dx*2
現在一切水落石出了，我們已經可以消除浮點數了，也不必計算k了。好了，下面是完整的Bresenham算法程序：
void drawLineBresenham(int x0, int y0, int x1, int y1, long color)
{
int dx = x1- x0;
itn dy = y1- y0;
if(dx >= dy){ // |k| <= 1
int e = -dx;
for (int x = x0, y = y0; x <= x1; x++){
setpixel (x, y, color);
e += 2*dy;
if(e >= 0){e -= 2*dx; y++;}
}
}
else{ // |k|> 1
int e = -dy;
for (int x = x0, y = y0; y <= y1; y++){
setpixel (x, y, color);
e += 2*dx;
if(e >= 0){e -= 2*dy; x++;}
}
}
}
