[openGL] Drawing Line Algorithm

[一] Naive Algorithm

(1) 想法

    |m| < 1 時，用 x 算出 y，跑 for 時

    x++;
    y = y0 + m * (x - x0);

    用 x, y 畫出點

    |m| > 1 時，反過來用 y 算出 x，

    y++;
    x = x0 + (y - y0) / m;

    用 x, y 畫出點

 ( p.s ) m的算法是 dy / dx ，當 dy 或 dx 其中一個等於0時，代表畫直線，就不需要去算了

(3) 分析

    因為每次都要用乘法或除法重新算出值來，所以相較於其他兩者，

    這是最慢的一種畫線方法，但是非常簡單，很容易就可以想到。

(4) pseudo code

    dx = x2 - x1;

     dy = y2 - y1;

     for x from x1 to x2 {

        y = y1 + (dy) * (x - x1)/(dx);

        ... Draw point ...

    }

    Total: 2 + 2t addition, 2t multiplication.

[二] DDA Algorithm

(1) 想法

   
    先算出 x, y 的總差距 dx 和 dy，再看總共有幾個點要畫 (steps)，假如 |m| < 1，

    steps 就是 dx，反之，steps 就是 dy，以此為根據，將 dx 和 dy 分別除以 steps，

    來算出每個點兩兩之間的距離差，每次加上這個距離差來畫出線來，

    可以省去 naive 每次都要再多用乘法或除法才能算出 y 值消耗的時間，

    當然一樣的，當 dy 或 dx 等於 0 時，等於畫直線，不需要特別去算 x 值或 y 值。

(2) 分析

    相較於 naive ，少去很多乘法、除法運算，變快了許多，而且也很簡單就可以想到。

(3) pseudo code

    dx = x2 - x1;

    dy = y2 - y1;

    xIncrement = (float)dx / (float)steps;

    yIncrement = (float)dy / (float)steps;

    for i from 0 to steps - 1 {

        x += xIncrement;

        y += yIncrement;

        ... Draw point ...

    }

    Total: 2 + 2t float addition, 2 float multiplication

[三] Bresenham's Line Algorithm

(1) 想法
    
    |m| < 1時，先算出 p = 2 * dy - dx，twoDy = 2 * dy，twoDyMinusDx = 2 * ( dy - dx )

    也是一樣，用 x 算出 y，同時如果 p < 0 的話，p += twoDy；否則 y++ 且 p += twoDyMinusDx

    |m| > 1時，想法相同，但是其實就只要把 dy 跟 dx 交換，然後改成用 y 算出 x，

    最後在判斷 p >= 0 的 else 中，將原本的 y++ 改成 x++ 就好。

(3) 分析

    跟 DDA 差不多，但是 DDA 都是以 float 為資料型態，且每次加完 increment 之後，

    都要做 round 來四捨五入，而 Bresenham's Line Algorithm 不用做 round，

    但是每畫一個點就需要比 DDA 多判斷 1 次，而且每次除了 x, y 值改變之外，

    還要讓 p 做改變。

(4) pseudo code

    dx = fabs(x - x0);  
    dy = fabs(y - y0);

    p = 2 * dy – dx;   
    twoDy = 2 * dy;

    twoDyMinusDx = 2 * (dy - dx);

    for x from x1 to x2 {

        x++;
        if (p < 0)
            p += twoDy;
        else {
            y++;
            p += twoDyMinusDx;
        }

    ... Draw point ...

    }

    Total: 4 + 3t addition and 3 multiplication






( p.s ) 最後講一下，三種演算法都要另外去算垂直線和水平線的情況。