三角剖分非平面多边形

Question

我想要对一个非平面多边形进行三角剖分（即顶点不在同一3D平面上）。该多边形由许多点（数百个）组成。三角形表面不必光滑，实际上，它越密集越好。

我最初的想法是：

• NURBS
• 生成“多边形内部”的其他点并应用3D Delaunay三角剖分。
• 只需在中间放置一个（或少数）顶点并将其与轮廓顶点相连。

我不确定这些想法哪个适用于我的情况，或者也许有更好的方法？ 更多细节： 尽管轮廓上的点有数百个，但它们可以分成3到~10个子集，以便每个子集都能紧密地逼近一条线。所生成的线仍然不在同一平面上。可以将其看作是一群鸟，在多边形内飞行，但高度不完全相同。

- Violin Yanev

---

以下文件描述了这样的算法： Peter Liepa，“网格填孔”，SGP 2003。 - sloriot

虽然我很喜欢阅读技术论文，但目前我需要一个现成的解决方案（库或伪代码），而且无法自己实现...一旦我有更多时间，我会仔细阅读的:)谢谢！ - Violin Yanev

Answer 1

我最终做了以下事情：

1. 对点拟合一个平面。
2. 将点投影到拟合的平面上。
3. 将点转换到拟合平面的坐标系中，使每个点都有一个二维坐标 (x, y) 和深度 z。
4. 计算点云的边界。
5. 在边界内生成额外的二维点（可以使用等距离点或扭曲的点，以任意密度）。
6. 对所有点（边界 + 生成的点）进行二维 Delaunay 三角化。
7. 根据边界深度值插值生成内部点的深度值。可以使用任何插值方法 - 我使用了 MATLAB 的 triscatteredinterp()，效果不错。
8. 使用第三步的反变换将所有点平移回来。
9. 使用步骤6得到的三角剖分和步骤8获得的点。

你可以在这里看到结果： http://www.youtube.com/watch?v=4AqHxKsM7Iw&feature=g-upl

- Violin Yanev

---

非常酷！你能够将更复杂的结构“挤出”或者三维化吗？如果是一个圆锥体，你会怎么做呢？ - angainor

好的，我还没有实现曲线。已经用多边形非常困难了。但我认为应该可以让它与光滑的对象一起工作。它可以处理相当复杂的结构。 - Violin Yanev

Answer 2

你可能想要看一下点云库。它可以进行表面重建等操作。

- angainor