將2D基於平鋪形狀，以簡化的多邊形

Question

如以上在圖像中看到的，我有瓷磚的2D陣列，每個具有在自己的遊戲世界4分。我正在尋找一種方法將這些由單個拼接塊構建的形狀轉換爲簡化形式（不需要不必要的頂點，只有形成輪廓所需的頂點）多邊形形狀。

我一直在環顧四周，在這裏和其他地方，運氣都很差。但也許我不知道要搜索的正確術語。任何幫助表示讚賞。

額外信息：我正在尋找使用它來優化動態照明。如果某人在基於瓦片的世界中完成快速動態陰影的方法不同，那麼這也將回答這個問題。

Answer 1

我建議下算法：

1. 存儲所有邊緣位置爲二維陣列（邊緣位置是邊緣的中心）。
2. 計算此數組中的重複邊（1不重複，2與另一個邊交叉，其他值不可見）。
3. 從數組中挑選第一個未標記的邊，重複計數1（不重複），並在確定方向（順時針）應用簡單的遞歸填充算法，直到第一個邊到達。所有這些邊將形成一個簡化的多邊形。如果未標記的邊緣尚未建立，則GOTO 5.
4. 標記所使用的步驟3中的所有邊緣。 GOTO到第3步。
5. 結束。

爲了更直觀地表示算法，我在下面張貼了一張圖。

Answer 2

簡單的方法是簡單地遍歷每個單獨的貼圖並將任何過渡邊緣標記爲多邊形，但您可以重複使用普通的edge detection例程以獲得更好的性能。

之後，您可能會對這些多邊形進行鑲嵌以便將它們轉換爲三角形的集合（使後面的陰影/照明/交點數學更簡單），唯一的問題是如果您結束一個凹多邊形，但一個體面的tessellator應該讓你把它分解成凸多邊形。我不認爲XNA有嵌入鑲嵌的任何東西，所以你可能需要找到一個實用程序庫來爲你做。