c# - 如何简化行进方块网格？

Question

我在 iso 平面上运行行进方块（相对于行进立方体）算法，然后将数据转换为三角形网格。

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

我尝试过围绕轮廓循环（点 -> 段 -> 点 -> ...），但如果一个点有超过 2 个附加段，则轮廓可能会倒置。

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

Answer 1

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

首先重要的是要有一个可靠的网格数据结构，它提供了修改网格的操作。一组可以生成和修改任何网格的操作是例如一组“欧拉算子”。

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

密集的三角形网格：

然后迭代地折叠不在边界处的最短边。“边缘塌陷”是一种典型的网格操作，如下所示：

经过一些步骤后，您的网格将如下所示：

Answer 2

简化由行进方块生成的网格（如上面的答案中所建议的）效率非常低。要从标量场（例如位图）中获取多边形，您应该首先运行仅生成多边形轮廓的行进正方形的修改版本（即在 16 个行进正方形的情况下您不生成几何图形，您只需添加点到多边形），然后运行三角测量算法（例如 Delaunay 或 Ear Clipping）。

Answer 3

编辑：在生成的轮廓上使用耳朵剪裁：

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

Answer 4

立即执行此操作，从您的体积表示转到网格表示。

之后，您可以将具有案例 3、6、9、12 的区域分组为更大/更长的版本。

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

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

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