如何简化行进方格网格？

Question

我正在iso平面上运行行进方块(相对于行进立方体)算法,然后将数据转换为三角形网格.

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

我试过在轮廓周围循环(点 - >段 - >点 - > ...),但如果一个点有超过2个附加段,轮廓可能会反转.

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

Answer 1

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

第一个重要的是拥有一个可靠的网格数据结构,它提供修改网格的操作.可以产生和修改任何网格的一组操作例如是"欧拉算子"的集合.

为了简化2D网格,提供2D网格的密集版本.您可以通过在对角线上分割每个四边形,将四边形网格转换为三角形网格.

密集三角网格:

然后迭代地折叠不在边界处的最短边." 边缘折叠 "是典型的网格操作,如下所示:

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

Answer 2

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

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

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

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

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