带孔的多边形三角剖分

Question

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

这是我到目前为止所发现的:

我非常感谢有此领域经验的人的一些意见.

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

Answer 1

Jonathan Shewchuk的三角图书馆非常出色; 我过去曾用它来自动化三角测量.你可以要求它试图避免小/窄三角形等,这样你就可以得出"好"的三角测量而不是任何三角测量.

Answer 2

为了给你更多的图书馆选择:

Polyboolean.我从未尝试过这个,但看起来很有希望:http://www.complex-a5.ru/polyboolean/index.html

General Polygon Clipper.这个在实践中非常有效,并且可以进行三角测量以及修剪和打孔:http://www.cs.man.ac.uk/~toby/alan/software/

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

如果您不喜欢在DirectX应用程序中包含OpenGL系统库的想法,那么也有一个解决方案:只需下载SGI OpenGL参考实现代码并从中提升三角形.它只使用OpenGL-Typedef名称和一个充满枚举的手.而已.您可以在一两个小时内提取代码并创建一个独立的库.

一般来说,我的建议是使用一些有用的东西,而不是开始编写自己的三角测量.

如果您已经阅读了关于耳朵剪切或扫描线算法的信息,那么很有可能推出自己的算法,但事实上,计算几何算法很难以一种稳定工作的方式编写,从不会崩溃并始终返回有意义的结果.数值舍入误差最终会累积并杀死你.

我在C中为我合作的公司编写了一个三角测量算法.让核心算法工作需要两天时间.让它与各种退化的输入工作又花了两年时间(我没有全职工作,但相信我 - 我花了更多的时间在它上面而不是我应该拥有的).

Answer 3

CGAL拥有您需要的工具: 约束三角测量

您可以简单地提供多边形的边界(包含孔的边界)作为约束(最好是插入所有顶点,然后将约束指定为Vertex_handles对).

然后,您可以通过任何遍历算法标记三角剖分的三角形:从入射到无限顶点的三角形开始并将其标记为外部,每次越过约束时,切换到相反的标记(如果您之前是标记,则在内部)三角形作为局外人,如果你之前将三角形标记为内幕,则在外面).

Answer 4

我发现poly2tri库正是我需要进行三角测量的.它产生了比我尝试过的其他库(包括libtess)更清晰的网格,并且它也支持漏洞.它已被转换为一堆语言.许可证是New BSD,因此您可以在任何项目中使用它.