c# - 将基于 2D Tile 的形状转换为简化的多边形

Question

如上图所示，我有一个二维图块数组，每个图块在我的游戏世界中有 4 个点。我正在寻找一种方法，将这些由单个图块构造的形状转换为简化的（没有不必要的顶点，只有那些需要形成轮廓的顶点）多边形形状。

我一直在环顾四周，在这里和其他地方，但运气不佳。但也许我不知道要搜索的正确术语。任何帮助表示赞赏。

额外信息：我希望用它来优化动态照明。如果有人有不同的方法在基于图块的世界中实现快速动态阴影，那也将回答这个问题。

Answer 1

我建议下一个算法：

1. 将所有边缘位置存储到二维数组中（边缘位置是边缘的中心）。
2. 计算此数组中的重复边（1 没有重复，2 与另一条边相交。其他值是不可丢失的）。
3. 从具有重复计数 1（无重复）的数组中选取第一个未标记的边，并在特定方向（例如顺时针）应用简单的递归填充算法，直到到达第一个边。所有这些边将形成一个简化的多边形。如果未建立未标记的边缘，则转到 5。
4. 将步骤 3 中的所有这些边标记为已使用。转到第 3 步。
5. 结尾。

为了更直观地表示算法，我在下面发布了一张图片。

Answer 2

幼稚的方法是简单地遍历每个图块并将任何过渡边缘标记为多边形，但您可以重用通用边缘检测例程以获得更好的性能。

之后，您可能会对细分这些多边形感兴趣，以便将它们转换为三角形的集合（使后面的阴影/照明/相交数学变得简单得多），在这种情况下，唯一的问题是如果您最终得到一个凹面多边形，但是一个不错的镶嵌器应该允许您将其分解为凸多边形。我认为 XNA 没有内置任何用于镶嵌的东西，因此您可能需要找到一个实用程序库来为您完成它。