graphics - 带孔的多边形三角剖分

Question

我正在寻找一种算法或库（更好）将多边形分解为三角形。我将在 Direct3D 应用程序中使用这些三角形。最好的可用选项是什么？

这是我到目前为止发现的：

我真的很感谢在这方面有经验的人的一些意见。

编辑：这是一个二维多边形。

score 21 · Accepted Answer

为您提供更多的库选择：

多布尔值。我从未尝试过这个，但它看起来很有希望：http: //www.complex-a5.ru/polyboolean/index.html

通用多边形剪裁器。这个在实践中效果很好，可以进行三角测量以及剪裁和孔洞：http ://www.cs.man.ac.uk/~toby/alan/software/

我个人的建议：使用 GLU（OpenGL 实用程序库）中的镶嵌。该代码坚如磐石，比 GPC 更快，生成的三角形更少。您不需要初始化的 OpenGL-Handle 或类似的东西来使用 lib。

如果您不喜欢在 DirectX 应用程序中包含 OpenGL 系统库的想法，那么也有一个解决方案：只需下载 SGI OpenGL 参考实现代码并从中取出三角测量器。它只使用 OpenGL-Typedef 名称和一堆枚举。就是这样。您可以在一两个小时内提取代码并制作一个独立的库。

一般来说，我的建议是使用已经有效的东西，不要开始编写自己的三角测量。

如果您已经阅读过耳剪或扫线算法，您很想自己动手，但事实是计算几何算法很难以一种稳定工作、永不崩溃并且总是返回有意义的结果的方式编写. 数值舍入误差最终会累积并杀死你。

我为与我合作的公司用 C 语言编写了一个三角测量算法。让核心算法工作需要两天时间。让它与各种退化的输入一起工作又花了两年时间（我没有全职工作，但相信我——我花在这上面的时间比我应该做的要多）。

score 20 · Accepted Answer

Jonathan Shewchuk 的Triangle 库非常出色。我过去用它来自动化三角测量。您可以要求它尝试避免使用小/窄三角形等，因此您可以提出“好的”三角剖分，而不仅仅是任何三角剖分。

score 12 · Accepted Answer

CGAL 拥有您需要的工具：约束三角剖分

您可以简单地提供多边形的边界（包括孔的边界）作为约束（最好是插入所有顶点，然后将约束指定为 Vertex_handles 对）。

然后，您可以通过任何遍历算法标记三角剖分的三角形：从入射到无限顶点的三角形开始并将其标记为在外部，每次越过约束时，切换到相反的标记（如果您之前标记过，则在内部三角形为局外人，如果您之前将三角形标记为内部人，则在外部）。

score 5 · Accepted Answer

我发现 poly2tri 库正是我进行三角测量所需要的。它产生的网格比我尝试过的其他库（包括 libtess）要干净得多，而且它也支持孔。它已被转换为多种语言。许可证是New BSD，因此您可以在任何项目中使用它。

score 3 · Accepted Answer

尝试 libtess2

基于原始的 SGI GLU tesselator（具有自由许可）。解决了许多小型 malloc 的一些内存管理问题。

score 2 · Accepted Answer

您可以自己相对轻松地添加孔。基本上按照 CGAL 对输入点的凸包进行三角剖分，然后删除其中心位于任何孔多边形内（或任何外部边界之外）的任何三角形。在处理大型数据集中的大量漏洞时，可以使用掩蔽技术来显着加快这一过程。

编辑：该技术的一个常见扩展是去除船体上的弱三角形，其中最长边或最小内角超过给定值。这将形成一个更好的凹壳。

score 2 · Accepted Answer

我使用耳剪法在 C# 中实现了一个 3D 多边形三角测量器。它易于使用，支持孔，数值稳健，并支持任意（非自相交）凸/非凸多边形。

score 1 · Accepted Answer

这是有限元分析中的常见问题。它被称为“自动网格生成”。Google 发现此站点包含指向商业和开源软件的链接。他们通常假设某种几何图形的 CAD 表示开始。

score 0 · Accepted Answer

另一种选择（具有非常灵活的许可证）是从 VTK 移植算法：

这个算法工作得相当好。直接使用它是可能的，但需要到 VTK 的链接，这可能比您想要的开销更大（尽管它还有许多其他不错的功能）。

它支持约束（孔/边界/等），以及对不一定在 XY 平面中的表面进行三角剖分。它还支持一些我在其他地方没有看到的特性（参见关于 Alpha 值的注释）。

9 回答 9