带孔的多边形三角剖分
我正在寻找一种算法或库（更好）将多边形分解为三角形。 我将在 Direct3D 应用程序中使用这些三角形。 最好的可用选项是什么？
以下是我到目前为止发现的内容：
- Ben Discoe 的笔记
- FIST：快速工业强度多边形三角测量
- 我知道 CGAL 提供三角测量，但不确定它是否支持孔。
我非常感谢在该领域有过经验的人的一些意见。
编辑：这是一个二维多边形。
I am looking for an algorithm or library (better) to break down a polygon into triangles. I will be using these triangles in a Direct3D application. What are the best available options?
Here is what I have found so far:
- Ben Discoe's notes
- FIST: Fast Industrial-Strength Triangulation of Polygons
- I know that CGAL provides triangulation but am not sure if it supports holes.
I would really appreciate some opinions from people with prior experience in this area.
Edit: This is a 2D polygon.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
为了给你更多的库选择：
Polyboolean。 我从未尝试过这个，但它看起来很有希望：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 语言编写了一个三角测量算法。 让核心算法发挥作用花了两天时间。 让它与各种退化的输入一起工作又花了两年的时间（我没有全职工作，但相信我 - 我在这上面花了比我应该花的时间更多的时间）。
To give you some more choices of libraries out there:
Polyboolean. I never tried this one, but it looks promising: http://www.complex-a5.ru/polyboolean/index.html
General Polygon Clipper. This one works very well in practice and does triangulation as well as clipping and holes holes: http://www.cs.man.ac.uk/~toby/alan/software/
My personal recommendation: Use the tesselation from the GLU (OpenGL Utility Library). The code is rock solid, faster than GPC and generates less triangles. You don't need an initialized OpenGL-Handle or anything like this to use the lib.
If you don't like the idea to include OpenGL system libs in a DirectX application there is a solution as well: Just download the SGI OpenGL reference implementation code and lift the triangulator from it. It just uses the OpenGL-Typedef names and a hand full of enums. That's it. You can extract the code and make a stand alone lib in an hour or two.
In general my advice would be to use something that alreay works and don't start to write your own triangulation.
It is tempting to roll your own if you have read about the ear-clipping or sweep-line algorithm, but fact is that computational geometry algorithms are incredible hard to write in a way that they work stable, never crash and always return a meaningful result. Numerical roundoff errors will accumulate and kill you in the end.
I wrote a triangulation algorithm in C for the company I work with. Getting the core algorithm working took two days. Getting it working with all kinds of degenerated inputs took another two years (I wasn't working fulltime on it, but trust me - I spent more time on it than I should have).
Jonathan Shewchuk 的 三角形库 非常出色； 我过去用它来自动进行三角测量。 您可以要求它尝试避免小/窄三角形等，这样您就可以得出“好的”三角剖分，而不仅仅是任何三角剖分。
Jonathan Shewchuk's Triangle library is phenomenal; I've used it for automating triangulation in the past. You can ask it to attempt to avoid small/narrow triangles, etc., so you come up with "good" triangulations instead of just any triangulation.
CGAL 拥有您需要的工具：
约束三角剖分
您可以简单地提供边界多边形（包括孔的边界）作为约束（最好是插入所有顶点，然后将约束指定为 Vertex_handles 对）。
然后，您可以通过任何遍历算法标记三角剖分的三角形：从与无限顶点相关的三角形开始，并将其标记为外部，每次跨越约束时，切换到相反的标记（如果您之前标记为内部）三角形为局外人，如果您之前将三角形标记为局内人，则为局外人）。
CGAL has the tool you need:
Constrained Triangulations
You can simply provide boundaries of your polygon (incuding the boundaries of the holes) as constraints (the best would be that you insert all vertices, and then specify the constraints as pairs of Vertex_handles).
You can then tag the triangles of the triangulation by any traversal algorithm: start with a triangle incident to the infinite vertex and tag it as being outside, and each time you cross a constraint, switch to the opposite tag (inside if you were previously tagging the triangles as outsider, outside if you were tagging triangles as insider before).
我发现 Poly2tri 库正是我三角测量所需的。 它产生的网格比我尝试过的其他库（包括 libtess）干净得多，并且它也支持孔。 它已被转换为多种语言。 许可证是New BSD，因此您可以在任何项目中使用它。
Google 代码上的 Poly2tri 库
I have found the poly2tri library to be exactly what I needed for triangulation. It produces a much cleaner mesh than other libraries I've tried (including libtess), and it does support holes as well. It's been converted to a bunch of languages. The license is New BSD, so you can use it in any project.
Poly2tri library on Google Code
尝试 libtess2
https://code.google.com/p/libtess2/downloads/list
基于原始的 SGI GLU tesselator（具有自由许可）。 解决了围绕大量小型 malloc 的一些内存管理问题。
try libtess2
https://code.google.com/p/libtess2/downloads/list
based on the original SGI GLU tesselator (with liberal licensing). Solves some memory management issues around lots of small mallocs.
您可以自己相对轻松地添加孔。 基本上按照 CGAL 对输入点的凸包进行三角测量，然后删除其中心位于任何孔多边形内部（或任何外部边界外部）的任何三角形。 当处理大型数据集中的大量漏洞时，可以使用屏蔽技术来显着加快此过程。
编辑：此技术的常见扩展是清除船体上的弱三角形，其中最长边或最小内角超过给定值。 这将形成更好的凹形船体。
You can add the holes relatively easily yourself. Basically triangulate to the convex hull of the input points, as per CGAL, and then delete any triangle whose incentre lies inside any of the hole polygons (or outside any of the external boundaries). When dealing with lots of holes in a large dataset, masking techniques may be used to significantly speed this process up.
edit: A common extension to this technique is to weed weak triangles on the hull, where the longest edge or smallest internal angle exceeds a given value. This will form a better concave hull.
我使用耳朵剪切方法在 C# 中实现了 3D 多边形 三角器。 它易于使用，支持孔，数值稳健，并且支持任意（非自相交）凸/非凸多边形。
I have implemented a 3D polygon triangulator in C# using the ear clipping method. It is easy to use, supports holes, is numerically robust, and supports aribtrary (not self-intersecting) convex/non-convex polygons.
这是有限元分析中的常见问题。 这称为“自动网格生成”。 Google 发现此网站包含商业和开源链接软件。 他们通常会假设某种几何形状的 CAD 表示形式开始。
This is a common problem in finite element analysis. It's called "automatic mesh generation". Google found this site with links to commercial and open source software. They usually presume some kind of CAD representation of the geometry to start.
另一种选择（具有非常灵活的许可证）是从 VTK 移植算法：
vtkDelaunay2D
这个算法效果相当好。 直接使用它是可能的，但需要链接到 VTK，这可能比您想要的有更多的开销（尽管它还有许多其他不错的功能）。
它支持约束（孔/边界/等），以及对不一定位于 XY 平面中的表面进行三角测量。 它还支持一些我在其他地方没有见过的功能（请参阅有关 Alpha 值的注释）。
Another option (with a very flexible license) is to port the algorithm from VTK:
vtkDelaunay2D
This algorithm works fairly well. Using it directly is possible, but requires links to VTK, which may have more overhead than you want (although it has many other nice features, as well).
It supports constraints (holes/boundaries/etc), as well as triangulating a surface that isn't necessarily in the XY plane. It also supports some features I haven't seen elsewhere (see the notes on Alpha values).