雖然已經(jīng)一年多沒有維護gbox這個圖形庫項目了建炫，最近確實時間不夠用。疼蛾。。
今年的重點是把xmake徹底正好艺配，至少在架構和大功能（包依賴管理）上察郁，要完全落實下來，后期就是零散的維護和插件功能擴展了转唉。皮钠。
tbox我會陸陸續(xù)續(xù)一直進行一些小規(guī)模更新，明年上半年稍微重構一些模塊后赠法，就開始重點重新搞gbox了麦轰，這才是我一直最想做，也是最喜歡做的項目了
所以我寧愿開發(fā)的慢點砖织，也要把它做精款侵，做到最好。侧纯。
好了新锈，回歸正題，雖然現(xiàn)在gbox還處于早期開發(fā)中眶熬，并不能用到實際的項目中去妹笆，但是里面的一些算法，還是很有參考學習價值的娜氏。拳缠。
我這兩天沒事就拿出來分享下，如果有感興趣的同學贸弥，可以直接閱讀源碼：monotone.c
畢竟這個算法我陸陸續(xù)續(xù)花了整整一年的時間窟坐，才把它徹底搞透，并且實現(xiàn)出來。狸涌。
為什么會花這么久呢切省，也許是我太笨了哈。帕胆。嘿嘿朝捆。。當然也有工作原因哈懒豹。芙盘。
我先簡單講講研究和實現(xiàn)這個復雜多邊形光柵化算法的背景：
我的gbox目前有兩套渲染設備，一套是直接純算法渲染脸秽，其核心算法就是掃描多邊形填充算法儒老，這個算法已經(jīng)算是很普遍了，也很成熟记餐，效率也很高
但是在我的另外一套基于opengl es渲染設備中（為了能夠利用gpu進行加速渲染）驮樊，在渲染復雜多邊形時，就遇到了問題：opengl不支持復雜多邊形的填充
后來我想了很多辦法片酝，也去google了下囚衔，發(fā)現(xiàn)可以通過opengl的模板來實現(xiàn)，然后我就開寫了雕沿。练湿。
寫到一半，整體效果也出來了审轮，自以為搞定了肥哎，卻又遇到一個很難跨過的瓶頸，效率太低了疾渣，用這種方式渲染一個老虎頭篡诽，幀率只有：15 fps
比我用純算法的實現(xiàn)還慢，后來就思考為什么這么慢呢榴捡，一個原因就是模板確實很慢霞捡。。薄疚。
第二個原因就是：我要實現(xiàn)通用的渲染接口碧信，要支持各種填充規(guī)則，裁剪規(guī)則街夭，這些復雜性砰碴，也使得基于模板的方式整體不太好優(yōu)化。板丽。
就這樣折騰了半年呈枉，最后決定趁尼，還是整體重構gbox吧，徹底不用模板實現(xiàn)了猖辫，采用另外一種方式：
先在上層對復雜多邊形根據(jù)各種填充規(guī)則和裁剪酥泞，進行預處理，核心算法呢就是：對復雜多邊形進行三角化分割啃憎，并且合并成凸多邊形
再送到opengl中進行快速渲染芝囤。。辛萍。
那問題來了悯姊，如果才能高效分割多邊形呢，而且還要支持各種填充規(guī)則贩毕？
繼續(xù)google悯许，最后發(fā)現(xiàn)libtess2的光柵化代碼里面的算法是可以完全做到的，但是我不可能直接用它的代碼辉阶，一個原因是維護不方便
另外一個原因是先壕，它里面的實現(xiàn)，很多地方效率不是很高谆甜，而我要實現(xiàn)的比他更高效垃僚，更穩(wěn)定。店印。。
那就必須要先看透它的實現(xiàn)邏輯倒慧，然后再去改進和優(yōu)化里面的算法實現(xiàn)按摘。。纫谅。
雖然里面代碼不多炫贤，但是我光看透，就又花了半年時間付秕，最后陸陸續(xù)續(xù)寫了半年兰珍，終于才完全搞定。询吴。
最后效果嗎掠河，還是不錯的，至少在我的mac pro上用opengl渲染老虎頭猛计，幀率可以達到：60 fps
當然唠摹，里面肯定還是有很多問題在里面的，不做最近確實沒時間整了奉瘤，只能先擱置下來了勾拉，等以后在優(yōu)化優(yōu)化。。藕赞。
先曬曬成肘，三角化后的效果：
然后再曬張老虎頭效果：
接著我再對分割算法做些簡要描述：
gbox中實現(xiàn)算法跟libtess2算法中的一些不同和改進的地方:
- 整體掃描線方向從縱向掃描，改成了橫向掃描斧蜕，這樣更符合圖像掃描的席位邏輯双霍，代碼處理上也會更方便
- 我們移除了3d頂點坐標投影的過程，因為我們只處理2d多邊形惩激，所以會比libtess2更快
- 處理了更多交點情況店煞，優(yōu)化了更多存在交點誤差計算的地方，因此我們的算法會更穩(wěn)定风钻，精度也更高
- 整體支持浮點和定點切換顷蟀，在效率和精度上可以自己權衡調(diào)整
- 采用自己獨有的算法實現(xiàn)了活動邊緣比較，精度更高骡技，穩(wěn)定性更好
- 優(yōu)化了從三角化的mesh合并成凸多邊形的算法鸣个，效率更高
- 對每個區(qū)域遍歷，移除了沒必要的定點計數(shù)過程布朦，因此效率會快很多
整個算法總共有四個階段：
- 從原始復雜多邊形構建DCEL mesh網(wǎng)(DCEL雙連通邊緣鏈表, 跟quad-edge類似囤萤，相當于是個簡化版).
- 如果多邊形是凹多邊形或者復雜多邊形，那么先把它分割成單調(diào)多邊形區(qū)域（mesh結構維護）
- 對基于mesh的單調(diào)多邊形進行快速三角化處理
- 合并三角化后的區(qū)域到凸多邊形
其中光柵化算法實現(xiàn)上分有七個階段：
- 簡化mesh網(wǎng)是趴，并且預先處理一些退化的情況（例如：子區(qū)域退化成點涛舍、線等）
- 構建頂點事件列表并且排序它 (基于最小堆的優(yōu)先級排序).
- 構建活動邊緣區(qū)域列表并且排序它(使用局部區(qū)域的插入排序，大部分情況下都是O(n)唆途，而且量不多).
- 使用
Bentley-Ottman掃描算法富雅，從事件隊列中掃描所有頂點事件，并且計算交點和winding值（用于填充規(guī)則計算） - 如果產(chǎn)生交點改變了mesh網(wǎng)的拓撲結構或者活動邊緣列表發(fā)生改變肛搬，需要對mesh的一致性進行修復
- 當我們處理過程中没佑，發(fā)生了一些
mesh face的退化情況，那么也需要進行處理 - 將單調(diào)區(qū)域的
left face標記為"inside"温赔，也就是最后需要獲取的輸出區(qū)域
如果你想要了解更多算法細節(jié)蛤奢，可以參考： libtess2/alg_outline.md
光柵化接口的使用例子，來自源碼：gbox/gl/render.c:
更詳細的算法實現(xiàn)細節(jié)陶贼，請參考我的實現(xiàn): monotone.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/
