[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 又要通過南橋北橋回傳