如何简化Marching Squares网格？

Question

我正在运行一个 marching squares算法（与Marching Cubes相关），在等值平面上运行该算法，然后将数据转换为三角形网格。

这样可以运行，但会创建非常复杂的网格数据。我想将其简化为所需的最小三角形数量，如下图所示：

我已尝试循环遍历轮廓（点 -> 段 -> 点 -> ...），但如果一个点有超过2个附加段，轮廓可能会翻转。

理想情况下，解决方案应该相当快，以便可以在运行时完成。我使用的语言是C#，但可能可以从大多数其他类似C的语言进行移植。

- miketucker

---

你已经运行了你链接的维基页面上描述的等值线算法，它提供了一个网格，现在你想将其转换为最小三角形表示形式？ - JSQuareD

你正在尝试翻译的数据是如何表示的？ - JSQuareD

为什么一定要是“最小”的三角形？难道你不能只切割内部的正方形吗？ - Nicol Bolas

@JSQuareD，没错，我有一个二维数组的IsoCells，这会导致许多冗余的多边形（就像提供的图像一样）。因此，目标是尽可能减少多边形的数量，以优化网格。 - miketucker

@NicolBolas 它不必完全是最小的，但理想情况下非常简化。我正在使用生成的三角剖分来创建刚体碰撞网格，而使用复杂网格实例化非常缓慢。 - miketucker

Answer 1

这是3D计算机图形学中非常常见的问题。解决这个问题的算法被称为网格简化算法。 然而，在2D情况下，这个问题要简单得多，因为不需要考虑表面法线。

第一件重要的事情是拥有一个可靠的网格数据结构，提供修改网格的操作。例如，可以生成和修改任何网格的一组操作是“欧拉运算符”。

为了简化2D网格，请提供2D网格的密集版本。可以通过在对角线处分割每个四边形来将四边形网格简单转换为三角形网格。

密集三角形网格:

然后迭代地折叠长度最短的非边界边。"边缘折叠"是一种典型的网格操作，如下所示:

经过若干步骤后，您的网格将如下所示:

- Harry Berry

---

据我所知，这是一个很好的答案。我想知道为什么没有人投票。 - AturSams

Answer 2

简化由Marching Squares生成的网格（如上面所建议的）效率非常低。如果要从标量场（例如位图）中获取多边形，则应首先运行修改后的Marching Squares版本，仅生成多边形轮廓（即在Marching Squares的16种情况下不生成几何图形，而只向多边形添加点），然后运行三角剖分算法（例如Delaunay或Ear Clipping）。

- user2599140

---

OP也可以在GitHub上查找Triangle.Net for unity，用于三角剖分。对于轮廓上的二维点非常有效。 - Vignesh

Answer 3

立即行动，从音量表示转向网格表示。

之后，您可以将3、6、9、12情况的区域组合成更大/更长的版本。

您也可以尝试将方块分组为更大的方块，但这是一个NP问题，因此理想的优化可能需要很长时间。

然后，您可以将其转换为多边形版本。

将其转换为多边形后，您可以融合边缘。

- Quonux

Answer 4

编辑：在生成的轮廓上使用 Ear Clipping 算法：

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

- abenci

---

Ear Clipping 是一种三角剖分算法。它不适用于从标量场生成轮廓。 - user2599140

Ear Clipping 可以用最少的三角形填充多边形。 - abenci

当然，但这本身并不能回答OP的问题。他需要一种高效的方法来生成轮廓和三角剖分，而不仅仅是三角剖分。 - user2599140