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

Question

在一些仿真程序中，我们根据点生成物体表面，每个点都具有3D坐标以及代表该点表面法线的向量。为了可视化目的，我们希望生成由三角形组成的网格;每三个关闭点与正常点形成一个三角形。然后，我们可以将这些信息发送给一些标准的可视化程序，使VMD（视觉分子动力学）等表面呈现出来。

我们不知道哪个是最快/可用的算法。

Answer 1

看看Jonathan Shewchuk的工作，特别是对他（与他的同事一起）著名的论文和实现：

• Streaming Computation of Delaunay Triangulations

• A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

有也是点云库（PCL）中实现的未分类点云的快速实现。请在Fast triangulation of unordered point clouds上查看他们的介绍。

Answer 2

Misha Kazhdan的泊松算法可能适用于您的数据。其软件页面为here。请注意，还有一个CGAL版本。手册是here并准备使用Windows演示here（假设您安装了这些dlls）。

Answer 3

请注意，Delaunay三角剖分可能不适合您的应用，因为Delaunay三角剖分不适合真正的3D问题（即点在R3中分布均匀）。它们更适合二维流形问题（即地形等）。

要在R3中生成曲面，请查看Hugues Hoppe和他的“曲面重建”工作。

表面重建用于找到网格表面以适应点云;然而，这种方法产生高三角形数量。如果这是一个问题，那么可以应用网格缩减技术来减少多边形数量，从而最大限度地减少错误。作为一个例子，你可以看看OpenMesh的抽取方法。

Hugues Hoppe

OpenMesh