c++ - 如何使用 Marching Squares 生成位图的多边形网格？

Question

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

问题是虽然我看到很多人提到使用 Marching Squares 来做到这一点，但我找不到任何解释如何做的东西!我什至找不到任何关于行进方 block 算法本身的特别好的解释/教程，尽管我认为我从我所发现的内容中非常理解它。我想不通的是如何根据 MS 给我的线创建多边形。

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

http://deltaluca.me.uk/docnew/swf/DestructableTerrain.html

我不想简单地浏览物理引擎的源代码来了解它是如何工作的，所以希望某个地方知道一个地方可以更好地解释这个过程! C++ 中的任何东西都是首选，但如果过程解释得当，其他语言应该没问题。

Answer 1

What I can't figure out is how to create polygons from the lines that MS will give me.

行进正方形或 2D 行进立方体为您提供许多线段，每个线段从一个边到一个正方形内的另一边。线段开始和结束的边缘连接两个不同符号的网格顶点。并且共享这条边的两个正方形产生一个线段，每个线段在边上都有公共(public)点。参见 marching cubes tutorial .

接下来需要做的就是将公共(public)点处的线段连接起来形成多段线。其中一种方法如下:

1. 使用 2D 网格中边的唯一 ID 作为 HashMap 中每个段的起点和终点的键。
2. 然后依次处理所有线段，如果 HashMap 中缺少当前线段的起始(或结束)点，则将其添加到那里并引用该线段；否则从 HashMap 中取出段并将其与公共(public)点中的当前段合并。

Anything in C++ would be preferred, but other languages should be fine if the process is explained well.

例如，看一下 MeshLib C++ 库，具体关于 distanceMapTo2DIsoPolyline 的实现功能。