Bresenham線算法 - 決策參數來自哪裏？

Question

void line() 
{ 
    int x1 = 10, y1 = 10, x2 = 300, y2 = 500 , x, y; 
    int dx, dy, //deltas 
     e;  // decision parameter 

    glClear(GL_COLOR_BUFFER_BIT); 
    glColor3f(1 ,0, 0); 
    setPixel(x1, y1); //plot first point 

    // difference between starting and ending points 
    dx = x2 - x1; 
    dy = y2 - y1; 
    e = 2 * dy - dx; 
    x = x1; y = y1; 

    for(int k = 0; k < dx - 1; ++k) 
    { 
    if(e < 0) 
    { 
     //next pixel: (x+1, y) 
     e = e + 2*dy; 
    } 
    else 
    { 
     //next pixel: (x+1, y+1) 
     e = e + 2*dy - 2*dx; 
     ++y; 
    } 
    ++x; 
    setPixel(x, y); 
    } 

    glFlush(); 
} 

e = 2*dy - dx從何而來？爲什麼我們增加2*dy或2*dy - 2*dx？

Answer 1

Bresenham的算法只使用整數算術。關鍵的想法是儘量減少線方程增量評估的計算。

該算法非常簡單。讓我們先從線方程

f(x) = y = a*x +b 

（並假設0 < =一個< 1現在）。 當我們去一個像素的權利，我們得到：

f(x+1) = a * (x+1) + b = f(x) + a 

但無論A和Y不會爲典型的線路整數。所以我們只是介紹一個「錯誤」。我們總是去正確的鄰居。在這樣做的時候，我們通過不去上錯了a。如果我們的錯誤是成功的一半以上像素（0.5），我們去了（因此由像素再次減小誤差值）

float e=a; 
float y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > 0.5) { 
     y++; 
     e=e+a-1; 
    } else { 
     e=e+a; 
    } 
} 

（請注意，我們已經設置錯誤e到a開始，而不是零，因爲我們總是在繪製像素之後做出決定，並且在繪製第一個像素之前我們不需要檢查條件，因爲那個圖像總是在線上。）

現在，我們已經接近。但有兩件事阻止我們使用整數：0.5和a這是dy/dx。但是：我們可以通過一個仲裁因子來縮放錯誤值（和條件），而不用改變任何東西。考慮一下：迄今爲止我們已經測量了像素的誤差（因爲它起初看起來很直觀），但是該算法可以使用任意單位來計算誤差值 - 半像素，雙像素，pi像素。

所以讓我們把它縮小2*dx以擺脫上面公式中的兩個分數！ （從某種意義上說，這裏關鍵的技巧是我們測量誤差值的「單位」在算法中不是常數，而是線的函數）。

int e=2*dy; 
int y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > dx) { 
     y++; 
     e=e+2*dy - 2*dx; 
    } else { 
     e=e+2*dy; 
    } 
} 

現在，我們有我們想要的：只有整數。 （這裏有一點需要注意，從float到int，我們自動將線的端點「咬入」到整數座標 - 具有整數端點是Bresenham算法（和限制）的一些先決條件。

還有一個技巧：條件包含一個變量。如果我們要測試一個常量，並且理想情況下爲零（因爲符號或零標誌的分支節省了我們的比較操作），它會更加高效。我們可以通過改變我們的錯誤值來實現這一點。與以前一樣，不僅誤差值的範圍可以任意選擇，而且也可以來源。

由於我們的測試e > dx目前，由-dx偏移誤差將讓我們來測試針對0（和0現在意味着什麼dx之前的意思，即0.5像素）。這種轉變不僅影響e的初始值和條件下，所有的增量停留在以前一樣：

int e=2*dy-dx; 
int y=y1; 
int x=x1; 
while(x<=x2) { 
    SetPixel(x,y); 
    x++; 
    if (e > 0) { 
     y++; 
     e=e+2*dy - 2*dx; 
    } else { 
     e=e+2*dy; 
    } 
} 

瞧，在2*dy-dx術語突然間成爲了...;）