Bresenham
宣告：本博客作者與此博客https://blog.csdn.net/cjw_soledad/article/details/78886117相同，因“博客搬家”功能效果不好，不得不重新發布
bresenham演算法是計算機圖形學中為了“顯示幕（螢屏或列印機）系由像素構成”的這個特性而設計出來的演算法，使得在求直線各點的程序中全部以整數來運算，因而大幅度提升計算速度，
實作代碼
這篇文章主要對下面的代碼進行解釋，如果能夠理解下面的代碼，完全可以跳過這篇文章，
// 來源:https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#C
void line(int x0, int y0, int x1, int y1) {
int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1;
int err = (dx>dy ? dx : -dy)/2, e2;
for(;;){
setPixel(x0,y0);
if (x0==x1 && y0==y1) break;
e2 = err;
if (e2 >-dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}
直線方程
眾所周知，最基本的斜截式直線方程為\(y=kx+b(k為斜率, b為截距)\)，這個方程存在的缺點是無法表示直線\(x=\alpha\)，所以用一個新的方程來代替\(Ax+By+C=0\)，
Bresenham
Bresenham畫直線的演算法主要步驟是判斷下一點的位置，維基百科中有一張圖比較形象
圖中，每一個點代表的是一個像素，假定我們有直線\(f(x,y)\)且當前坐標為\((x,y)\)，判斷下一個點的y軸坐標步驟為（如果要確定x軸坐標也類似）：
代碼理解
如上面所述，我們現在能夠判斷直線的下一個像素點在那里了，但是Bresenham演算法的優點還沒有體現：我們還需要計算浮點數，為了避免浮點數計算，我們要更深入地發現劃線的規律，
這里我們只考慮 \(x_1<x_2\) 并且\(y_1<y_2\)的情況，實際上我們也只需要考慮這種情況，正如前面代碼所寫的sx, sy，通過這兩個變數我們便能控制要畫的直線方向是正確的，
- Bresenham的輸入為兩個點\((x_1, y_1), (x_2,y_2)\)，根據這兩個點，我們能夠計算出兩點之間的“距離“，這里的距離用的是絕對值，對應的是代碼里的
dx, dy，
\[\Delta x=|x_1-x_2|\\ \Delta y=|y_1-y_2| \]
根據斜截式\(y=kx+b\)，我們有\(y=\frac{\Delta y}{\Delta x}x+b\)，進而有
\[\Delta y x-\Delta x y+C = 0 \]
在這條公式中：
\[x+1 \Rightarrow y+\frac{\Delta y}{\Delta x} \\ y+1 \Rightarrow x +\frac{\Delta x}{\Delta y} \]
- 實際上，用于判斷下一個點的位置的就是\(\frac{\Delta y}{\Delta x}\)和\(\frac{\Delta x}{\Delta y}\)，這兩個值變化的根本目的是使上面的方程成立，根據這一點，我們直接引入一個變數\(err\)避免浮點數運算（對應代碼中的
err和e2）
\[\Delta y x-\Delta x y+C +err= 0 \\ x+1 \Rightarrow err-\Delta y \\ y+1 \Rightarrow err+\Delta x \]
- 現在我們已經能夠將 \(err\) 和 \(x, y\) 聯系起來，但是還有一個很重要的問題沒有解決：判斷增加x軸坐標還是增加y軸坐標
首先假設我們在起始坐標\((x,y)\)，當前的\(err\)也是正確的，現在需要判斷下一個點的坐標，
根據傳統的Bresenham演算法：
\[(x+\frac{\Delta x}{\Delta y})-(x+1)>0 \Rightarrow \Delta x-\Delta y>0 \Rightarrow x+1\\ (y+\frac{\Delta y}{\Delta x})-(y+1)>0 \Rightarrow \Delta y-\Delta x>0\Rightarrow y+1 \]
我們更關注中間的部分，結合上一點所說的\(err\)和\(\Delta x,\Delta y\)的關系對其進行變形
\[ \Delta x-\Delta y>0 \Rightarrow -\Delta y>-\Delta x\\ \Delta y-\Delta x>0\Rightarrow +\Delta x < \Delta y \]
- 從上面的公式看來似乎是與\(err\)有點關系了，但是還不明確，那是因為我們的推到基于起始點，倘若基于的不是起始點，那么該公式應當為
\[ \Delta x-\Delta y>0 \Rightarrow \varepsilon -\Delta y>-\Delta x\\ \Delta y-\Delta x>0\Rightarrow \varepsilon+\Delta x < \Delta y \]
\(\varepsilon\)為一個累加值，其來源與當前點\((x,y)\)和起始點\((x_0,y_0)\)的相對位置有關，個人理解是：每一次\(x+1\)或\(y+1\)都會讓原來的直線平移，這個平移便會造成誤差，而這個誤差會隨著程式的進行而不斷累加，而這個累加值對應的正是\(err\)
- 現在我們就有能力將\(err\)和程式中的
err聯系起來了，
if后的條件與上面的公式對應，而err與\(\varepsilon\)不同，不同之處是：err是已經計算好的\(\varepsilon-\Delta y\)和\(\varepsilon+\Delta x\)，我們可以這樣思考：在某一個點\((x,y)\)處，我們已經計算得到了正確的、可以用于判斷的\(err\)，當我們選擇下一個點時，我們可以順便把下一個點的\(err\)給計算了，這就是代碼中err -= dy; err += dx;蘊含的意思，
if (e2 >-dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
- 關于
err的初始化 Updated in 2020
我們注意到代碼中對err進行了初始化，在前面我們的推導忽略了一個部分：起始點\((x_1,y_1)\)的\(err\)，從公式\(Ax+By+C+err=0\)上看，起始點的\(err\)應當為\(0\)才對，但是代碼中用了一個奇怪的值進行了初始化，看起來二者是矛盾的，但是err的初始化實際上是另一個小技巧，
int err = (dx>dy ? dx : -dy)/2
看回前面提到的那張圖，藍色點為起始點，倘若人工進行判斷，我們會根據黑色點的位置\(black\)決定下一個點在何處，當\(black>0.5\)時我們會選擇下面的綠點，否則選擇上面的綠點，
然而此處的0.5會引入浮點數運算，我們還有一種選擇：將起始點\((x_1,y_1)\)上移半個單位(這里只考慮\(\Delta x>\Delta y\)，其余情況同理)，因為起始點相對于第一個像素有了偏移，引入了誤差\(err\)，根據前面對\(err\)的推導有：
\[x_1+0.5\Rightarrow err-\Delta y/2\\ y_1+0.5\Rightarrow err+\Delta x/2 \]
這樣便能解釋err的初始值問題，而且與我們前面的推導是一致的，
- 至此，Bresenham演算法理解完成，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5184.html
標籤：其他