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

Question

在一些模拟程序中,我们根据点生成对象表面,每个点具有3D坐标,并且向量表示该点处表面的法线.出于可视化目的,我们希望生成由三角形组成的网格; 每三个关闭点形成一个正常的三角形.然后我们可以将这些信息发送到一些标准的可视化程序,这些程序可以像VMD(Visual Molecular Dynamics)一样呈现表面.

我们想知道哪个是最快/可用的算法.

Answer 1

看看Jonathan Shewchuk的作品,特别是他(和他的同事们)的着名论文和实施:

• Delaunay三角剖分的流式计算

• 二维质量网格生成器和Delaunay三角剖分器

Point Cloud Library(PCL)中还实现了未分类点云的快速实施.检查他们关于无序点云的快速三角测量的演示.

Answer 2

请注意,Delaunay三角剖分可能不适合您的应用,因为Delaunay三角剖分不适合真正的3D问题(即R3中的点分布均匀).它们更适合2D流形问题(即地形等).

要在R3中生成曲面,请查看Hugues Hoppe的工作及其"曲面重建"工作.

表面重建用于找到适合点云的网格表面; 但是,此方法会产生高三角形计数.如果这是一个问题,则可以应用网格缩小技术来减少多边形数量,从而最大限度地减少错误.例如,您可以查看OpenMesh的抽取方法.

Hugues Hoppe

OpenMesh

Answer 3

Misha Kazhdan的泊松算法可能适用于您的数据.它的软件页面就在这里.请注意,还存在CGAL版本.手册是在这里,并准备演示使用windows 这里(前提是你安装了这些DLL文件).