一个读取网格算法和网格库

Question

我对阅读和理解二维网格算法很感兴趣。在谷歌上搜索发现很多论文和资料，但大多数都过于学术化，对初学者不太友好。

因此，这里是否有人可以推荐适合初学者的阅读材料或开源实现，让我能够从头开始学习？谢谢。

此外，与三角形网格生成相比，我更感兴趣的是四边形网格和混合网格（四边形和三角形的组合）。

- Ngu Soon Hui

Answer 1

我赞同David的回答，Jonathan Shewchuk's 网站是一个很好的起点。

就开源软件而言，取决于你需要什么。

• 如果你对网格生成感兴趣，可以查看CGAL的代码。理解CGAL代码的低级部分对于初学者来说太过复杂。但是，即使对于初学者来说，查看较高级别的算法也可能非常有趣。此外，请注意CGAL文档非常详细。
• 你还可以查看TetGen，但其源代码是单块式的且未经过文档化（它更像是一款终端用户软件而不是库，尽管其他程序也可以从中简单调用）。尽管如此，它相当易读，用户手册包含了网格生成的简要介绍和一些参考资料。
• 如果你还对网格处理感兴趣，可以查看OpenMesh。

提供更多关于您目标的信息将有助于提供更相关的指针。

- Camille

Answer 2

您在Google搜索中的第一个链接将带您到Jonathan Shewchuk的网站。这实际上不是一个坏的起点。他有一个名为triangle的程序，可用于下载2D三角测量。在该页面上，有一个链接，指向创建三角形所使用的参考资料，包括一个指向三角测量算法描述的链接。

生成网格有几种方法。其中最常见的方法之一是创建Delanuay三角剖分。对一组点进行三角剖分非常简单，有几个算法可以实现这一点，包括Watson和Rupert's算法，如在triangle中使用。如果您想创建一个约束性的三角剖分，使得三角剖分的边缘与输入形状的边缘匹配，则会变得有些困难，因为您需要恢复某些边缘。

我建议先了解Delaunay三角剖分，然后再查看其他一些网格化算法。

在网格生成论文中，您会发现一些常见的主题：

• 健壮性 - 即如何处理浮点舍入误差。
• 网格质量 - 确保三角形/四面体的形状接近等边形。这是否重要取决于您创建网格的原因。对于分析工作，这非常重要。
• 如何选择在网格中插入节点以获得良好的网格分布。
• 网格生成速度
• 四边形/六面体网格生成。这比使用三角形/四面体更难。

3D网格生成比2D更困难，因此很多论文都是关于3D生成的。

网格生成是一个大主题。如果您可以提供一些更多信息（例如2D或3D），那将会很有帮助。如果您能够给出一些想要做什么的想法，那么也许我可以找到一些更好的信息来源。

- David Dibben

---

我赞同这个观点。如果您使用网格来近似函数，则网格质量很重要：逼近误差（在H^1范数中，即考虑梯度的均方误差）取决于三角形的“厚度”：其内圆与外圆半径之比。等边三角形最佳，但当点固定时，这就太难了，而Delaunay三角剖分的全部意义在于给定顶点获得最佳三角剖分。 - Alexandre C.

稳健性很难实现。我有一些关于这方面的论文，但主要是通过技术上的位操作来获得正确的精度。当研究 Delaunay 三角剖分时，你会自然地看到由于舍入误差而产生的问题，然后你就会明白，你不应该自己编写它。 - Alexandre C.