複雜多邊形光栅化算法

雖然已經一年多沒有維護 gbox

這個圖形庫項目了，最近确實時間不夠用。。。

今年的重點是把

xmake

徹底正好，至少在架構和大功能（包依賴管理）上，要完全落實下來，後期就是零散的維護和插件功能擴充了。。

tbox我會陸陸續續一直進行一些小規模更新，明年上半年稍微重構一些子產品後，就開始重點重新搞gbox了，這才是我一直最想做，也是最喜歡做的項目了

是以我甯願開發的慢點，也要把它做精，做到最好。。

好了，回歸正題，雖然現在gbox還處于早期開發中，并不能用到實際的項目中去，但是裡面的一些算法，還是很有參考學習價值的。。

我這兩天沒事就拿出來分享下，如果有感興趣的同學，可以直接閱讀源碼：

monotone.c

畢竟這個算法我陸陸續續花了整整一年的時間，才把它徹底搞透，并且實作出來。。

為什麼會花這麼久呢，也許是我太笨了哈。。嘿嘿。。當然也有工作原因哈。。

我先簡單講講研究和實作這個複雜多邊形光栅化算法的背景：

我的gbox目前有兩套渲染裝置，一套是直接純算法渲染，其核心算法就是掃描多邊形填充算法，這個算法已經算是很普遍了，也很成熟，效率也很高

但是在我的另外一套基于opengl es渲染裝置中（為了能夠利用gpu進行加速渲染），在渲染複雜多邊形時，就遇到了問題：

opengl不支援複雜多邊形的填充

後來我想了很多辦法，也去google了下，發現可以通過opengl的模闆來實作，然後我就開寫了。。

寫到一半，整體效果也出來了，自以為搞定了，卻又遇到一個很難跨過的瓶頸，效率太低了，用這種方式渲染一個老虎頭，幀率隻有：15 fps

比我用純算法的實作還慢，後來就思考為什麼這麼慢呢，一個原因就是模闆确實很慢。。。

第二個原因就是：我要實作通用的渲染接口，要支援各種填充規則，裁剪規則，這些複雜性，也使得基于模闆的方式整體不太好優化。。

就這樣折騰了半年，最後決定，還是整體重構gbox吧，徹底不用模闆實作了，采用另外一種方式：

先在上層對複雜多邊形根據各種填充規則和裁剪，進行預處理，核心算法呢就是：

對複雜多邊形進行三角化分割，并且合并成凸多邊形

再送到opengl中進行快速渲染。。。

那問題來了，如果才能高效分割多邊形呢，而且還要支援各種填充規則？

繼續google，最後發現libtess2的光栅化代碼裡面的算法是可以完全做到的，但是我不可能直接用它的代碼，一個原因是維護不友善

另外一個原因是，它裡面的實作，很多地方效率不是很高，而我要實作的比他更高效，更穩定。。。

那就必須要先看透它的實作邏輯，然後再去改進和優化裡面的算法實作。。。

雖然裡面代碼不多，但是我光看透，就又花了半年時間，最後陸陸續續寫了半年，終于才完全搞定。。

最後效果嗎，還是不錯的，至少在我的mac pro上用opengl渲染老虎頭，幀率可以達到：60 fps

當然，裡面肯定還是有很多問題在裡面的，不做最近确實沒時間整了，隻能先擱置下來了，等以後在優化優化。。。

先曬曬，三角化後的效果：

然後再曬張老虎頭效果：

接着我再對分割算法做些簡要描述：

gbox中實作算法跟libtess2算法中的一些不同和改進的地方:

• 整體掃描線方向從縱向掃描，改成了橫向掃描，這樣更符合圖像掃描的席位邏輯，代碼處理上也會更友善
• 我們移除了3d頂點坐标投影的過程，因為我們隻處理2d多邊形，是以會比libtess2更快
• 處理了更多交點情況，優化了更多存在交點誤差計算的地方，是以我們的算法會更穩定，精度也更高
• 整體支援浮點和定點切換，在效率和精度上可以自己權衡調整
• 采用自己獨有的算法實作了活動邊緣比較，精度更高，穩定性更好
• 優化了從三角化的mesh合并成凸多邊形的算法，效率更高
• 對每個區域周遊，移除了沒必要的定點計數過程，是以效率會快很多

整個算法總共有四個階段：

1. 從原始複雜多邊形建構DCEL mesh網(DCEL雙連通邊緣連結清單, 跟quad-edge類似，相當于是個簡化版).
2. 如果多邊形是凹多邊形或者複雜多邊形，那麼先把它分割成單調多邊形區域（mesh結構維護）
3. 對基于mesh的單調多邊形進行快速三角化處理
4. 合并三角化後的區域到凸多邊形

其中光栅化算法實作上分有七個階段：

1. 簡化mesh網，并且預先處理一些退化的情況（例如：子區域退化成點、線等）
2. 建構頂點事件清單并且排序它 (基于最小堆的優先級排序).
3. 建構活動邊緣區域清單并且排序它(使用局部區域的插入排序，大部分情況下都是O(n)，而且量不多).
4. 使用

   Bentley-Ottman

   掃描算法，從事件隊列中掃描所有頂點事件，并且計算交點和winding值（用于填充規則計算）
5. 如果産生交點改變了mesh網的拓撲結構或者活動邊緣清單發生改變，需要對mesh的一緻性進行修複
6. 當我們處理過程中，發生了一些

   mesh face

   的退化情況，那麼也需要進行處理
7. 将單調區域的

   left face

   标記為”inside”，也就是最後需要擷取的輸出區域

如果你想要了解更多算法細節，可以參考：

libtess2/alg_outline.md

光栅化接口的使用例子，來自源碼：

gbox/gl/render.c

:

更詳細的算法實作細節，請參考我的實作:

static tb_void_t gb_gl_render_fill_convex(gb_point_ref_t points, tb_uint16_t count, tb_cpointer_t priv)
    {
        // check
        tb_assert(priv && points && count);

        // apply it
        gb_gl_render_apply_vertices((gb_gl_device_ref_t)priv, points);

#ifndef GB_GL_TESSELLATOR_TEST_ENABLE
        // draw it
        gb_glDrawArrays(GB_GL_TRIANGLE_FAN, 0, (gb_GLint_t)count);
#else
        // the device 
        gb_gl_device_ref_t device = (gb_gl_device_ref_t)priv;

        // make crc32
        tb_uint32_t crc32 = 0xffffffff ^ tb_crc_encode(TB_CRC_MODE_32_IEEE_LE, 0xffffffff, (tb_byte_t const*)points, count * sizeof(gb_point_t));

        // make color
        gb_color_t color;
        color.r = (tb_byte_t)crc32;
        color.g = (tb_byte_t)(crc32 >> 8);
        color.b = (tb_byte_t)(crc32 >> 16);
        color.a = 128;

        // enable blend
        gb_glEnable(GB_GL_BLEND);
        gb_glBlendFunc(GB_GL_SRC_ALPHA, GB_GL_ONE_MINUS_SRC_ALPHA);

        // apply color
        if (device->version >= 0x20) gb_glVertexAttrib4f(gb_gl_program_location(device->program, GB_GL_PROGRAM_LOCATION_COLORS), (gb_GLfloat_t)color.r / 0xff, (gb_GLfloat_t)color.g / 0xff, (gb_GLfloat_t)color.b / 0xff, (gb_GLfloat_t)color.a / 0xff);
        else gb_glColor4f((gb_GLfloat_t)color.r / 0xff, (gb_GLfloat_t)color.g / 0xff, (gb_GLfloat_t)color.b / 0xff, (gb_GLfloat_t)color.a / 0xff);

        // draw the edges of the filled contour
        gb_glDrawArrays(GB_GL_TRIANGLE_FAN, 0, (gb_GLint_t)count);

        // disable blend
        gb_glEnable(GB_GL_BLEND);
#endif
    }
    static tb_void_t gb_gl_render_fill_polygon(gb_gl_device_ref_t device, gb_polygon_ref_t polygon, gb_rect_ref_t bounds, tb_size_t rule)
    {
        // check
        tb_assert(device && device->tessellator);

#ifdef GB_GL_TESSELLATOR_TEST_ENABLE
        // set mode
        gb_tessellator_mode_set(device->tessellator, GB_TESSELLATOR_MODE_TRIANGULATION);
//      gb_tessellator_mode_set(device->tessellator, GB_TESSELLATOR_MODE_MONOTONE);
#endif

        // set rule
        gb_tessellator_rule_set(device->tessellator, rule);

        // set func
        gb_tessellator_func_set(device->tessellator, gb_gl_render_fill_convex, device);

        // done tessellator
        gb_tessellator_done(device->tessellator, polygon, bounds);
    }           

個人首頁：

TBOOX開源工程

原文出處：

http://tboox.org/cn/2016/07/21/tessellate-polygon-algorithm/