三角测量 3D 算法

Question

6

我有数千个包含三个以上顶点的三维空间多边形。我想把每个多边形划分成一组三角形。我在网上搜索了很久，但没有找到任何用于三维的算法。我找到了许多针对二维的算法，例如“耳剪辑”和“Delaunay三角剖分”。但我无法找到任何适用于三维的算法。

我在这个网站上看到了许多相同的问题，回答是“使用Delaunay三角剖分算法”。但是我发现这个算法只适用于二维: http://www.geom.uiuc.edu/~samuelp/del_project.html 有哪些适用于三维的三角剖分算法呢？我正在使用C++的OpenGL。

- OpenGL97

2

Delaunay 用于点集三角剖分，而你需要的是多边形三角剖分，而耳切法正是为此而设计的。你可以通过将多边形投影到不会使其退化的任意平面上来将耳切法应用于三维。 - Nico Schertler

约束Delaunay三角剖分适用于多边形。 - Brandon Kohn

只是为了确保你不会把这件事情搞得比必要的更复杂：这些多边形可以是凹多边形吗？只要它们是凸的，那当然就是一个简单的问题。另外，使用模板缓冲区，有方法可以直接用OpenGL渲染任意多边形。根据您的使用情况，这可能是一种替代方案。 - Reto Koradi

Reto Koradi - 是的，模型可以是凹形的。而且我需要将数据存储在变量中，而不是直接渲染它。您能否以您的方式实现？如果可以，如何做到？ - OpenGL97

我假设每个多边形都相对于由其面法线和其中一个点定义的平面是平的？如果是这样，为什么不将其缩小到该平面上的2D，并只使用您已知的常规三角剖分方法之一呢？ - CynicismRising

2个回答

1

你可以使用一个四面体的德劳内三角剖分。基本上是使用 Bowyer-Watson 算法和外接球来实现: http://blog.mmacklin.com/tag/meshing/。

- Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brandon Kohn · Accepted Answer

您可以使用GLUTesselator：

注意，一个3D多边形将有许多面，这些面可以转换到一个轴对齐的2D平面上，进行三角剖分，然后将结果翻译回由该面定义的平面。