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

Question

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

这是我迄今为止发现的内容:

1. Ben Discoe's notes
2. FIST: Fast Industrial-Strength Triangulation of Polygons
3. 我知道CGAL提供三角测量，但不确定它是否支持孔。

我非常感谢有该领域经验的人提供一些意见。

编辑:这是一个 2D 多边形。

Answer 1

为您提供更多库选择:

多元 bool 。我从未尝试过这个，但它看起来很有前途:http://www.complex-a5.ru/polyboolean/index.html

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

我个人的建议:使用 GLU(OpenGL 实用程序库)中的曲面分割。该代码坚如磐石，比 GPC 更快，并且生成的三角形更少。您不需要初始化 OpenGL-Handle 或类似的东西来使用该库。

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

<小时/>

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

如果您读过耳朵剪裁或扫线算法，那么您可能会很想自己动手，但事实是，计算几何算法很难以稳定运行、永不崩溃且始终返回的方式编写一个有意义的结果。数字舍入错误会累积并最终杀死你。

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