从点云生成三角形网格的算法

Question

在一些仿真程序中，我们以点的形式生成物体表面，每个点都有三维坐标和表示该点处表面法线的向量。为了进行可视化，我们希望生成由三角形组成的网格; 每三个相邻的点形成一个具有其法线的三角形。然后，我们可以将这些信息发送给一些标准的可视化程序，如VMD（Visual Molecular Dynamics），以呈现表面。

我们想知道哪种算法是最快/可用于执行此任务的。

- Open the way

Answer 1

请查看Jonathan Shewchuk的作品，特别是他（以及他的同事们）著名的文献和以下实现：

• Delaunay三角测量的流式计算

• 二维优质网格生成器和Delaunay三角形分割器

此外，点云库（PCL）中还有未排序点云的快速实现。请查看他们关于无序点云快速三角化的演示文稿。

- mloskot

---

PCL案例中的魔法在于gp3.reconstruct(triangles) -- 不幸的是，这个魔法在演示中没有被揭示。 - wcochran

Answer 2

请注意，Delaunay三角剖分可能不适合您的应用程序，因为它们不适用于真正的3D问题（即在R3中点分布良好的情况）。它们更适用于2D流形问题（即地形等）。

要在R3中生成表面，请查看Hugues Hoppe及其“表面重建”工作。

表面重建用于找到网格化的表面以适应点云；但是，该方法会产生高三角形数量。如果这是一个问题，您可以应用网格化减少技术以减少多边形数量，以最小化误差。例如，您可以查看OpenMesh的简化方法。 Hugues Hoppe OpenMesh

- Throwback1986

Answer 3

Misha Kazhdan的泊松算法可能适用于您的数据。其软件页面在这里。请注意，还存在一个CGAL版本。手册在这里，可使用的Windows演示程序在这里（前提是您安装了这些dlls）。

- sloriot

Answer 4

在另一个答案中提到Delaunay三角剖分是一种从2D点集构建2D三角网格或从3D点云创建四面体网格的方法，但不适用于像问题中那样创建通常非凸的3D三角形表面网格。 Poisson表面重建确实解决了这个任务，但它很难被归类为“快速”，因为它需要通过求解大型方程组来构建定义在体素网格或八叉树节点上的附加场，并且仅在此之后才能将三角形表面重建为水平集，而该表面通常需要简化以将三角形数量减少到可接受的水平。

一种更快的从点云中获取三角网格的方法是考虑每个点周围的局部三角剖分（如上所述的PCL）。这种方法的好处在于所有局部三角剖分都可以独立并行地构建。然后，实现在如何合并最终网格中的单个局部三角剖分方面有所不同。其中一种方法是计算每个三角形的投票数。具有3个投票（每个顶点的每个局部三角剖分一个）的三角形将在最终网格中找到位置，而具有较少投票数的三角形仅在不引入非流形性时才包含在其中。其中一种实现是在MeshLib的triangulatePointCloud函数中。

- Fedor