[openGL] homework

[一] homework 1

Object:

implementation of 3 line algorithms, scan-line polygon-fill algorithm, boundary-fill algorithm, and antialiasing algorithm.

see files of homework 1

[二] homework 2

Object:

implementation of matrix transformation, back-face culling algorithm, etc...

see files of homework 2

[三] homework 3

Object: 

use functions that openGL included or functions you wrote before to design a simple car game

有簡陋的邊界判斷，之前一直在想好像沒有前進的感覺，直到DEMO時間到了，一直不知道該怎麼做出前進的感覺直到DEMO的時候老師說如果加上馬路上的白線就看的出來了我才恍然大悟，因為之前做兩次作業，老師都問怎麼不用MFC，看來她很想看我用MFC做，所以這次索性用了MFC include openGL XD

see files of homework 3

[openGL] Scan-Line Method (Surface-Visibility Algorithm) 實作

Surface-Visibility Algorithm 實作的演算法有很多，而其中我只有做過幾個，而這篇要談的是其中

的 Scan-Line Method

[一] 原文書的說法:

    To facilitate the search for surfaces crossing a given scan line, an active list of edges is formed for each scan line as it is processed. The active edge list contains only those edges that cross the current scan line, sorted in order of increasing x. In addition, we define a flag for each surface that is set to "on" or "off" to indicate whether a position along a scan line is inside or outside the surface. Pixel positions across each scan line are processed from left to right. This procedure works correctly only if surfaces do not cut through or otherwise cyclically overlap each other. If any kind of cyclic overlap is present in a scene, we can divide the surfaces to eliminate the overlaps.

(擷取部分內容)

[二] 作法

count the minimum and maximum y value of the surface to be drawn (slope of scan lines)
// scan line is a line which parallel to x axis

for each scan line {

    calculate the intersections of the boundaries and the scan line
    // assume that each surface has only 3 edges so we will get 2 intersections(x1 and x2) at most
    // than we draw pixel from (x1, scan line) to (x2, scan line)

    for each pixel to be drawn {
 
        calculate the depth (z) of the pixel (x, y) on that surface

        if z is smaller than the current depth of that pixel than
            draw the pixel with proper color and update the depth

        otherwise do nothing.

    }

}

[三] depth (z) 的算法

由面積公式可知 Ax + By + Cz + D = 0

得 z = -(Ax + By + D) / C，

下為 A、B、C 和 D 的算法，由平面上三點 (x1, y1, z1), (x2, y2, z2), and (x3, y3, z3) 計算而得

[openGL] 3D中 glTranslate()、glRotate() 和 glScale() 的實作

[一] glTranslate()

1.    拿來移動物體
2.    原理:

dx, dy, dz 是各個方向的移動距離

| x' |      | 1  0  0  dx |      | x |

| y' |      | 0  1  0  dy |      | y |

| z' |  =  | 0  0  1  dz |   ˙  | z |

| 1 |       | 0  0  0  1  |      | 1 |

[二] glRotate()

1.    物體繞某個軸線旋轉
2.    原理:

a是旋轉角度

[繞 y 軸旋轉]

| x' |      | 1     0          0        0 |      | x |

| y' |      | 0  cos(a)  -sing(a)  0 |      | y |

| z' |  =  | 0  sin(a)    cos(a)   0 |   ˙  | z |

| 1 |       | 0    0          0        1 |      | 1 |

[繞 x 軸旋轉]

| x' |      | cos(a)   0   sin(a)    0 |      | x |

| y' |      |     0       1     0        0 |      | y |

| z' |  =  | -sin(a)   0  cos(a)    0 |   ˙  | z |

| 1 |       |    0       0     0        1 |      | 1 |

3.    如果有要繞 x 軸轉也有要繞 y 軸轉，那就把兩個 matrix 乘起來就好

[三] glScale()

1.    放大縮小物體

2.    原理:

sx, sy, sz 是各個方向的放大縮小大小

| x' |      | sx  0  0  0 |      | x |

| y' |      | 0  sy  0  0 |      | y |

| z' |  =  | 0  0  sz  0 |   ˙  | z |

| 1 |       | 0  0  0  1  |      | 1 |

[四] 困難

因為在 rotate 之後，單位向量會跑掉，所以此時就須要做 glLoadIdentity()，不然在 translate的話，移動的方向也會不如預期，這也是為什麼人家說你要先移動之後再旋轉，因為先旋轉之後再移動，單位向量跑掉，之後的移動方向也會錯誤，此時，你可能會說，那我先旋轉 -> loadIdentity() -> 移動，這樣不就好了嗎? 錯，因為旋轉完之後 load identity，會把最初的資訊讀進 matrix，這樣就變回沒有旋轉的樣子了，所以每次都要先移動之後再做旋轉，這樣才會正確，如此一來就可以很清楚保留 matrix 資訊的功用到底是什麼了。

最後，因為這是我自己讀現代寫的 function ，所以只是拿來記錄情況，方便我用來回憶這些動作的原理。

(p.s) 這一部分比較需要會線性代數，其實不過就只是把新的 model matrix算出來，再重新跟 modelview 和 projection 乘在一起就好

[openGL] glLoadIdentity() 實作時的問題

因為之前自己在實作 "不用gluLookAt(), glOrtho(), glFrustum(), gluPerspective()"這些 function 只透過自

己算 transformation matrix 來畫出3D圖，除了這些，translate、rotate和scale也承接著自己來動手做看看

，當時遇到一個問題就是單獨只做 translate 或 rotate 等等這些動作，執行正確，但是當要在rotate之後做

translate時，就會出現問題，座標的方向好像變了，x, y, z不再是原本的方向，查了一下，網路上說做之前

要先 loadIdentity()，那這就又出現了另一個問題，loadIdentity() 是做什麼用的，要怎麼實作它，才能讓我

自己寫的translate和rotate正常執行，查了很久，每個地方都只說 set the current matrix to identity

matrix，卡關卡了好久，後來看到:

http://stackoverflow.com/questions/628796/what-does-glloadidentity-do-in-opengl

裡面寫的:

The identity matrix, in terms of the projection and modelview matrices, essentially resets the matrix back to its default state.

As you hopefully know, glTranslate and glRotate are always relative to the matrix's current state. So for instance, if you call glTranslate, you are translating from the matrix's current 'position', not from the origin. But if you want to start over at the origin, that's when you call glLoadIdentity(), and then you can glTranslate from the matrix which is now located at the origin, or glRotate from the matrix which is now oriented in the default direction.

I think Boon's answer, that it is the equivalent of 1, is not exactly correct. The matrix actually looks like this:

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

That is the identity matrix. Boon is correct, mathematically, that any matrix multiplied with that matrix (or a matrix that looks like that; diagonal ones, all else 0s) will result in the original matrix, but I don't believe he explained why this is important.

The reason why this is important is because OpenGL multiplies all positions and rotations through each matrix; so when for instance you draw a polygon (glBegin(GL_FACE), some points, glEnd()), it translates it to "world space" by multiplying it with the MODELVIEW, and then translates it from 3D to 2D by multiplying it with the PROJECT matrix, and that gives it the 2D points on screen, along with the depth (from the screen 'camera'), which it uses to draw pixels. But when one of these matrices are the identity matrix, the points are multiplied with the identity matrix and therefore are not changed, so the matrix has no effect; it does not translate the points, it does not rotate them, it leaves them as-is.

簡單說，

在做 translate 或 rotate 時，是以相對於儲存在 current matrix 裡面資訊的位置來做動作，以之前遇到的例

子來說，在rotate之後，單位座標向量跑掉了，所以 x, y, z 軸的方向都跟原本不同，因此在 translate 時，

移動的方向也會跟著改變，此時就須要透過 loadIdentity() 把 current matrix 變回去 default 的樣子，這樣

就可以對正確的相對位置做動作，而前面提到的 current matrix 也就真的是 current matrix 的意思XD

但是 translate 和 rotate 都是屬於 modelview 的 matrix，所以這裡的 current matrix 是 model_view matrix

[openGL] glDrawPixels問題紀錄

只是想要筆記一下遇到的問題

int W = 200;

int H = 200; 

unsigned int data[3][W][H];
    for( size_t y = 0; y < W; ++y )
    {
        for( size_t x = 0; x < H; ++x )
        {
            data[0][x][y] = ( rand() % 255 ) * 255 * 255 * 255;
            data[1][x][y] = ( rand() % 255 ) * 255 * 255 * 255;
            data[2][x][y] = ( rand() % 255 ) * 255 * 255 * 255;
        }
    }

    glDrawPixels( W, H, GL_RGB, GL_UNSIGNED_INT, data );

    glutSwapBuffers();

原本不知道怎麼用

http://stackoverflow.com/questions/20056174/gldrawpixel-rgb-value-from-a-array

但是在這邊找到之後，複製下來回到自己的電腦做，對data的宣告做一下修改，用C++的方式

對他做動態記憶體配置，當W和H是200的時候，使用正常沒問題，但是在W和H都大於400的

時候，就會莫名出現access violate的runtime error，查了非常久都查不到，程式碼也看了很多

遍，仍然沒有找到BUG，完全不知道到底為什麼會這樣反正也不知道原因就來亂試看看好

了，所以我就把C++動態配置的方式改成C的動態記憶體配置，然後竟然就成功了，但是到現

在還是不懂為什麼會出現 access violate，看了很多國內外網站論壇，很像沒有人有這樣的問

題，倒是有人直接歸咎是 harward造成的，害我好擔心呢。

而除此之外仍然也可能遇上其他 access violate 的 runtime error，原因通常是原本的座標在矩陣轉

換運算出新座標後，算出來的座標超出視窗範圍，而你把超出範圍的pixel資訊存進 frame buffer

中，可能沒問題，但是在 drawpixels() 時，就會出現 access violate，所以座標範圍都要進行裁

切，裁切方式可以看 transformation。

最後，drawPixels 的第三個要注意的就是，確定好第三個參數到底是 GL_RGB 還是

GL_RGBA，可能平常的時候不構成問題，但是當畫面 reshape 之後，access violate 的情形可能

又會再次發生。

-----------------------------------------------------------------------------------------

bool setSubPixel(int x, int y, GLbyte R, GLbyte G, GLbyte B)
{
if (x < W - 1 && x > 0) {
if (y < H - 1 && y > 0) {
GLbyte *subp = subImage;
subp += ((y * W + x) * 4);
*subp = (GLbyte)R;
*(subp + 1) = (GLbyte)G;
*(subp + 2) = (GLbyte)B;
*(subp + 3) = (GLbyte)27;
return true;
}
} else return false;
return false;
}

// W 和 H 分別是視窗寬度和視窗高度

[openGL] 3D Viewing - transformation 實作

為了瞭解觀念，所以做的實作

[一] 在介紹之前應該要知道的事

World Coordinate	target 客觀所在的位置
Viewing Coordinate	人站在某個位置往某個方向看，所看到 target 所在的位置，算是相對於人所在的位置
Target	目標物體，我覺得用一個點(point)來想比較好思考
View Plane	簡單說就是人看到的畫面
Model-View Matrix	用來將modeling轉換成view coordinate
Projection Matrix	用來將view轉換成clip coordinate

[二] Transformation From World To View Coordinate

目的就是將物體從客觀的座標位置轉換成某人站在某處往某個方向看的一種相對座標，詳細原由就不講了，總之在轉換的時候，因為是從客觀的位置轉換到人站在某個位置看某個方向所看到的情形，所以需要:

void glhLookAtd2(float *eye, float *reference, float *viewUp)
人的客觀座標位置	eye position
人看在哪個點上	reference point
哪邊是上方	viewUp

由這三組向量可以算出 transformation matrix的uvn Viewing-Coordinate Reference Frame，

(Nx, Ny, Nz) = (eye[0] - reference[0], eye[1] - reference[1], eye[0] - reference[0])
(Vx, Vy, Vz) 通常都是等於 (0, 1, 0)，因為x是當作螢幕的橫軸，y是螢幕的縱軸，z則是距離螢幕的遠近，所以上方就是在y的正值

由以上兩組向量可以求得

(nx, ny, nz) = (Nx/|N|, Ny/|N|, Nz/|N|) -> normalize
(ux, uy, uz) = ((Vx, Vy, Vz) cross (nx, ny, nz)) / |V|
(vx, vy, vz) = (nx, ny, nz) cross (ux, uy, uz)

又由此可以得到如下 4x4 的transformation matrix

ux	uy	uz	-x0*ux-y0*uy-z0*uz
vx	vy	vz	-x0*vx-y0*vy-z0*vz
nx	ny	nz	-x0*nx-y0*ny-z0*nz
0	0	0	1

[三] Transformation From View Coordinate To Clip Coordinate

目的是為了讓原本計算之後，無法預期大小的座標透過矩陣運算 縮小到視窗範圍內，

glFrustum(float left, float right, float bottom, float top, float dnear, float dfar)
值	簡單說就是看到的範圍吧

用以上這些值，可以求的如下的 4x4 transformation matrix

znear = -dnear
zfar = -dfar

-2znear/(right-left)	0	(right+left)/(right-left)	0
0	-2znear/(top-bottom)	(top+bottom)/(top-bottom)	0
0	0	(znear+zfar)/(znear-zfar)	(-2znear*zfar)/(znear-zfar)
0	0	-1	0

但是即便如此仍然可能會超出範圍，而超出視窗範圍時，就應該用上裁切的概念，

如上圖，假設螢幕的範圍是黑色的框框，物體畫在螢幕上是紅色的三角形，此時有可能會出現 run-time error 原因是存取違規，access violate，原因可以去看另一篇「drawpixels問題紀錄」

這時候就要像上圖一樣，上面的水平線依照原本的斜率畫到視窗的邊界，下面的斜線也是一樣，裁切方式如下

bool setPixel (int x, int y, GLbyte R, GLbyte G, GLbyte B)

{

if (x < W && x > 0) {

if (y < H && y > 0) {

GLbyte *p = image;

p += ((y * W + x) * 3);

*p = R;

*(p + 1) = G;

*(p + 2) = B;

}

}

}

image 是我的 frame buffer (拿來存 pixel 顏色的資訊)，W和H是螢幕的寬跟高

drawLine (int x0, int y0, int x, int y)

{

...

setPixel(...........);

...

}

[四] Viewport Transformation for screen coordinate

因為算出來的值有正有負，而理想狀況下，座標原點在screen正中間，所以做以下調整之後，就可以將物體放在視窗中間

x = (w / 2) * (x + 1)

y = (w / 2) * (y + 1)

z就可以不用算了

但是前面在做 clip coordinate 的時候，因為算出來 x, y, z 的範圍都有可能因為glFrustum代入的值的關係而不是在 -1 ~ 1之間，所以來做個 normalize

x' = x / (第四項)

y' = y / (第四項)

最後再求

x = (w / 2) * (x' + 1)

y = (w / 2) * (y' + 1)

[五] 簡單小範例

function帶入的parameter

glLookAt({100, 50, 50}, {50, 50, 0}, {0, 1, 0});

glFrustum(-40.0, 40.0, -60.0, 60.0, 25.0, 125.0);

一個面4個點的資訊

v1[4] = { 0.0, 0.0, 0.0, 1.0 } 

v2[4] = { 100.0, 0.0, 0.0, 1.0 }

v3[4] = { 100.0, 100.0, 0.0, 1.0 }

v4[4] = { 0.0, 100.0, 0.0, 1.0 }

紅色為4個點構成的面，綠點是人眼的位置，藍線是人看的方向，黑點是人看的位置

結果應該是要看到類似這樣的梯形，這樣才有像人看到的情況

modelview 的 matrix 應該是這樣  (假設為A)

0.707107	0	-0.707107	-35.3553
0	1	0	-50
0.707107	0	0.707107	-106.066
0	0	0	1

projection 的 matrix 應該要是 (假設為B)

0.625	0	0	0
0	0.416667	0	0
	0	-1.5	-62.5
0	0	-1	0

以 v1 為例，點的matrix如下 (假設為 x)

0

0

0

1

而要把點的座標算出來就需要做 BAx，而v1算出來為

-22.0971

-20.8333

96.599

106.066

因為範圍不在-1~1之間所以normalize一下，把值除以第四項

-22.0971/106.066

-20.8333/106.066

96.599/106.066

106.066/106.066

再透過上面寫的viewport得到

237.5

241.074

45.5372

1

則最後只留前兩項，四個點分別算出來是

v1(237.5, 241.074)

v2(487.5, 123.223)

v3(487.5, 476.777)

v4(237.5, 358.926)

[openGL] Antialiasing

[一] 線段反鋸齒

(1) 想法

    將每個 pixel 分成 9 個 subpixel，將顏色的強度算出來，如圖，(x, y) 強度為 3，

    (x+1, y) 強度為 1，(x+1, y+1) 強度為 2

(2) 作法

    如上圖，對 9 個 subpixel 而言，因為假設一條 line 的寬度等於一個 pixel 的寬度，

    就是像左上角的 pixel 中那九個點中左側的三個點依照斜率往上跳，因為 |m| < 1，

    所以由 y 出發，範例 code:

    //以下程式片段以將 pixel 分為 16 個 subpixel 為例
    int up = 0;  // up 只是一個 counter
    for (int i = 0; i < 4; i++) {
        float yt = y + 0.125 + i * 0.25;
        float temp = yt + m * 0.125;
        if (temp > (int)y + 1) up++;
        temp = yt + m * 0.375;
        if (temp > (int)y + 1) up++;
        temp = yt + m * 0.625;
        if (temp > (int)y + 1) up++;
        temp = yt + m * 0.875;
        if (temp > (int)y + 1) up++;
    }

    算出 up (也就是跑上去 y+1 的有幾個)後，up / 16 就是 (x, y+1) 的顏色強度，

    (16 - up) / 16 就是 (x, y) 的強度，如果是要算 |m| > 1 的話，就要改過來用 y 算 x 唷

[二] 圖形反鋸齒

(1) 想法:

    以上圖為例，假設 line 的下方為圖形內部，上方為外部，

    將每一個 line 上的 pixel 等分成 9 個 subpixel，以此來計算顏色的比例，

     上圖中，該 pixel 由 5 / 9 的紅色和 4 / 9 的圖形內部的顏色混合起來

(2) 作法:

    以上圖為例，跟前面畫線演算法一樣，假如 |m| < 1，用 x 算 y 的值；反之亦然。

    而上圖的 slope 小於 1 ，所以用 x 算出 y 值，

    對於 3 個 x 值 { x + (1 / 6), x + (3 / 6), x + (5 / 6) }，

    可以算出 x + (1 / 6) 的 y 值介於 y + (1 / 6) 到 y + (3 / 6) 之間，

     x + (3 / 6) 的 y 值介於 y + (1 / 6) 到 y + (3 / 6) 之間，

     x + (5 / 6) 的 y 值介於 y + (3 / 6) 到 y + (5 / 6) 之間，所以，總共有 5 個黑點在 line 之上，

    4 個黑點在 line 之下，以此為顏色的比例，

    所以 (x, y) 要用 5 / 9 的 border 顏色和 4 / 9 的內部顏色算平均的顏色

[openGL] Fill Polygon Algorithm

[一] Scan Line Fill Algorithm

(1) 想法

    先定義在圖形中，從最小 y 值到最大 y 值都分別是一條 scan line，

    對每一條 scan line 透過 slope 算出其與所有 edge 的交點 (intersection)，

    將這些 intersection 排序，假如排序後資料如下: 10 20 30 40，

    則代表從 (10, y) 畫到 (20, y)，(20, y) 到 (30, y)中間不畫，畫 (30, y) 到 (40, y) 之間

(2) 困難

        a. 先假設 vertex 的意思是 polygon 上的頂點，而當 scan line 上遇到 vertex 時，

          在算 intersection 時，scan line 會跟 edge1 和 edge2 相交在同一個位置，

          此時會抓到兩個值相同的 intersection。

        b. 解決第一個情況之後，新的問題是，在遇到 vertex 之後，到底要不要畫，

          如下圖，上面的 scan line 遇到 vertex 後不應該畫，

          而下面的 scan line 遇到 vertex 之後應該要畫。

(3) 解決方法

    對每一 vertex 的上一個點 A 和下一個點 B 做判斷，假如 A, B 都在該 vertex 的上方或下方，

    那麼就讓他在 intersection 的點集合中出現兩次，如果一個在上方一個在下方，

    則使其在 intersection 中只出現一次，以上圖星星上面那條scan line為例，

    假設該 vertex 的 x 值為50，則 intersection 的內容為 { 50, 50 }，讓他畫在 50 ~ 50，

    也就可以避免畫在 0 ~ 50 和 50 ~ ；而以星星圖下面那條scanline為例，

    因為只出現一次，所以假設 intersection 的內容為 { 50, 100 }，即可正確畫在星星內部。

(4) 分析

    - 實作很難，要考慮很多事情 = =

    - 計算很多，很吃CPU效能，時間複雜到高於空間複雜度

[二] Boundary Fill Algorithm

(1) 想法

    從圖形內部選擇一個 initial point，透過特別的 glReadPixel 取得該 pixel 的顏色，

    假設 borderColor 和 FillColor 為邊界的顏色和圖形內部所填的顏色，

    在得到 pixel 的顏色之後，判斷他是不是borderColor 和 FillColor，

    如果都不是才能畫這個點，而後再 recursive 去試看看四周的點是不是要畫，

    終止條件為取得 pixel 的顏色是 borderColor 或 FillColor。

(2) 困難

    initial point 要從何開始找起？

　因為想不到其他方法，所以用scanline的方法，就是取最大 y 值和最小 y值，

    平均之後，找到中間的scanline，一樣以這條 scanline 去找跟所有 edge 交點的 x 值，

    對第一條和第二條 edge 的 x 值取平均，如此一來，一定可以在圖形內部

(3) 補充: 取得某位置 pixel 的顏色資訊

    unsigned char pixel[3];
    glReadPixels(x, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, pixel);
    int R = (int)pixel[0];
    int G = (int)pixel[1];
    int B = (int)pixel[2];

(4) 分析

    - 實作很簡單

    - 但是遞迴會建立很多個 stack，之前把我的 RAM 吃光了

    - 因為判斷很多，在內部很多 pixel 要著色時，會很明顯的比 scanline 慢

    - 個人另外還覺得，CPU 對 device 讀取資料也有一定的影響，每個 pixel 都要讀取，

    CPU通過北橋、南僑送命令給 device，device 又要通過南橋北橋回傳

[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 ) 最後講一下，三種演算法都要另外去算垂直線和水平線的情況。