2D地圖擦除算法
. 關於2D地圖擦除算法，去年我寫過一個實現，勉強實現了地形擦除，但跟最終效果還相差甚遠，此次我寫了一個完整的實現，在此記錄，留個印象。html
. 去年的版本<<算法 & 數據結構——裁剪多邊形>>，由於受限於當時框架用GDI實現的渲染器，只有擦除地形沒有擦除地圖，此次換了OpenGL渲染器，終於能夠實現最終效果了。程序員
這個算法看似簡單，實際上就是很簡單，大體可分爲三個部分。算法
地圖擦除：擦除地圖的圖像，產生視覺效果。數據結構
地形擦除：擦除地圖的形狀，用於物理計算。框架
橡皮擦：用於定義擦除的形狀。3d
地圖擦除
假設這是一副畫在紙上的彩筆畫，若是要擦除畫上的一部分，有過生活經驗的人立馬就能想到用橡皮擦就行了，不少算法靈感來自生活，生活多姿多彩的人適合作程序員。這個實現過程大概就是：綁定地圖到當前渲染目標，渲染「橡皮擦」讓其覆蓋範圍內的像素，從而達到擦除效果。htm
橡皮擦
接着上一個環節，「橡皮擦」能夠是從文件讀取的一張圖，也能夠是程序生成的一張圖。若是從文件讀取，設置合適的BlendFunc，直接渲染覆蓋像素顏色就好了，本例使用程序生成的圖，由於這個靈活度更高。blog
這是一個正10邊形的「橡皮擦」，從圖中可看出，裏面有幾條線，把正10邊形分割成了8個三角形，這8把三角形的面積和形狀等於這個正10邊形，若是你困惑爲何要切成三角形，你運氣很好，有一個大佬恰好懂你的困惑，併爲你量身定作了一篇答案<<算法 & 數據結構——任意多邊形填充>>。遊戲
以上則是地圖的擦除效果，其中有一處細節，擦除的邊緣有點生硬，若是要製做相似《彈彈堂》這樣的遊戲，地圖是經過炮彈炸掉的，那麼被擦除的邊緣應該留下被炸過的痕跡，不用作的太真實，只要讓邊緣產生一些不同的漸變色就好了，要實現這一點，只需擴展一下「橡皮擦」的邊緣。get
柔滑邊緣，用於生成描邊。
拆分三角網格，用於渲染。
柔滑邊緣後的擦除效果。
地形擦除
以上是一張加了地形的圖，你沒有看錯，就只是多了一個黑邊。
如今要經過「橡皮擦」擦除這個黑邊，與地圖擦除不一樣的是，地圖擦除是覆蓋像素，而地形則是幾何計算。
算法：
從「橡皮擦」與地形相交部分計算出N條切線。
取第i（0 <= i < N）條切線將地形一分爲二。
丟棄徹底包含在「橡皮擦」內的地形。
i + 1，返回 2。
當前地形被切分完畢，若是還有下一個地形則返回 1，不然結束。
最終效果