如何使用Marching Squares算法生成位图的多边形网格？

Question

3

我需要能够准确地检测和响应与任何位图地形的碰撞，最好的方法似乎是使用行进方块生成多边形网格，然后将其与物理引擎（如Bullet）一起使用，这比我自己编写的任何东西都要好得多。

问题是，虽然我看到很多人提到使用行进方块来做到这一点，但我找不到任何解释！我甚至没有找到关于行进方块算法本身的特别好的解释/教程，尽管我认为我从我所发现的东西中基本上理解了它。我无法弄清楚如何从MS给我的线条创建多边形。

我已经找到了这个，这几乎正是我想要制作的，但我要么需要为C ++找到类似的物理库，要么自己编写网格生成。

我不想仅仅查看物理引擎的源代码来了解它的工作原理，希望有人知道一个更好地解释这个过程的地方！最好用C ++编写，但如果过程解释得好，其他语言也可以。

- Megadanxzero

我们应该明确一点：MS不是生成多边形网格的方法，而是生成可用于制作网格的轮廓的方法。您遇到了哪个问题，尝试了什么，期望的结果是什么？您是否有特定的问题需要解决，还是这只是一项作业任务？ - Russ Clarke

哦，我知道微软本身不会生成网格，但我完全不明白的是如何从微软提供的内容中生成网格。我实际上还没有开始写它，因为我想提前计划并确保在开始之前可以制作所需的内容。至于具体问题，我想为我正在开发的游戏制作2D可摧毁地形，并进行准确的碰撞响应（就像我发布的链接中一样）。 - Megadanxzero

你能再详细解释一下你的问题吗？输入是什么？对于 marching squares/cubes，输入通常是灰度图像和一个确定等值轮廓的阈值。你提供的链接以网格开始。最初的输入是什么？ - killogre

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fedor · Answer 1

我无法理解的是如何从MS给我的线条中创建多边形。

行进方块或2D行进立方体会给你一些线段，每个线段都从一个正方形的一条边到另一条边。线段开始和结束的边连接两个不同符号的网格顶点。共享这种边的两个正方形分别产生一个线段，每个线段在边上有一个公共点。请参见marching cubes tutorial。

后续需要做的就是在公共点处连接线段以形成折线。其中一种方法如下：

1.使用2D网格中边缘的唯一ID作为哈希映射中每个段的起始和结束点的键。 2.然后依次处理所有线段，如果当前线段的起始（或结束）点在哈希映射中不存在，则将其添加到哈希映射中，并引用该线段；否则，从哈希映射中获取该线段并将其与公共点处的当前线段合并。

任何用C++编写的内容都是首选，但如果过程解释得很好，其他语言也应该没问题。例如，看一下MeshLib C++库，特别是distanceMapTo2DIsoPolyline函数的实现。