从点云生成三角形网格的算法
在一些模拟程序中，我们以点的形式生成物体表面，每个点都有 3D 坐标和表示该点表面法线的向量。出于可视化的目的，我们希望生成一个由三角形组成的网格；每三个接近的点与其法线形成一个三角形。然后我们可以将这些信息发送到一些渲染表面的标准可视化程序，例如 VMD（视觉分子动力学）。
我们想知道哪种算法是最快/可用的算法。
In some simulation program we generate object surfaces in terms of points, each point has 3D coordinates and the vector that represents the normal to the surface at that point. For visualization purposes we would like to generate a mesh composed of triangles; each three close points form one triangle with its normal. Then we can send this information to some standard visualization programs that render the surface like VMD (Visual Molecular Dynamics).
We wonder which is the fastest/available algorithm for doing this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
看看 Jonathan Shewchuk 的工作，尤其是他（和他的同事）的工作）著名论文和实现：
流式计算Delaunay 三角剖分
二维质量网格生成器和 Delaunay
三角仪
点云库（PCL）中还可以快速实现未排序的点云。查看他们关于无序点云的快速三角测量的演示。
Take a look at Jonathan Shewchuk's work, especially on his (together with his colleagues) famous papers and implementations of:
Streaming Computation of Delaunay Triangulations
A Two-Dimensional Quality Mesh Generator and Delaunay
Triangulator
There is also fast implementation of unsorted point clouds implemented in the Point Cloud Library (PCL). Check their presentation on Fast triangulation of unordered point clouds.
请注意，Delaunay 三角剖分可能不适合您的应用，因为 Delaunay 三角剖分不适合真正的 3D 问题（即 R3 中点分布均匀的情况）。它们更适合二维流形问题（即地形等）。
要在 R3 中生成曲面，请查看 Hugues Hoppe 的工作和他的“曲面重建”工作。
表面重建用于寻找适合点云的网格表面；然而，这种方法会产生大量三角形。如果这是一个问题，您可以应用网格缩减技术来减少多边形数量，从而最大限度地减少错误。作为示例，您可以查看 OpenMesh 的抽取方法。
休格·霍普
OpenMesh
Note that Delaunay triangulations may not suit your application in that Delaunay triangulations are not suited to true 3D problems (i.e. where points are well-distributed in R3). They are more appropriate for 2D manifold problems (i.e. terrain, etc).
To generate surfaces in R3, look at the work of Hugues Hoppe and his "surface reconstruction" work.
Surface reconstruction is used to find a meshed surface to fit the point cloud; however, this method yields high triangle counts. If this is a problem, you can then apply mesh a reduction technique to reduce the polygon count in a way to minimize error. As an example, you can look at OpenMesh's decimation methods.
Hugues Hoppe
OpenMesh
Misha Kazhdan 的泊松算法可能适用于您的数据。其软件页面位于此处。请注意，还存在 CGAL 版本。手册位于此处，并且可以使用 Windows 演示此处 （前提是您安装了这些 dll）。
Misha Kazhdan's poisson algorithm might work well on your data. Its software page is here. Note that there also exists a CGAL version. Manual is here and ready to use windows demo here (provided you installed these dlls).
在另一个答案中提到 Delaunay triangulation 是一种从 2D 点集构造 2D 三角形网格的方法，或者用于从 3D 点云创建四面体网格，但不适用于在 3D 中创建典型的非凸三角形表面网格（如问题中所示）。
泊松曲面重建确实解决了任务，但它很难被归类为“快”，因为它需要通过求解大型方程组来构造在体素网格或八叉树的节点中定义的附加场，并且只有在重建三角形之后表面作为水平集，并且该表面通常需要简化以减少三角形的数量直到可接受的水平。
从点云接收三角形网格的更快方法是考虑每个点周围的局部三角剖分（如提到的 PCL 中）。这种方法的好处是可以独立且并行地构建所有局部三角剖分。然后，这些实现在如何将各个局部三角剖分合并到最终网格中方面有所不同。其中一种方法是计算每个三角形的选票。具有 3 票的三角形（每个顶点的每个局部三角剖分各一票）会在最终网格中找到位置，而只有在不会在网格中引入非流形性的情况下，才会包含具有较低票数的三角形。其中一种实现位于 triangulatePointCloud 函数中https://github.com/MeshInspector/MeshLib" rel="nofollow noreferrer">MeshLib。
Mentioned in the other answer Delaunay triangulation is a means for constructing 2D triangular meshes from 2D point sets, or for creating tetrahedral meshes from 3D point clouds, but not for creating typically not-convex triangular surface mesh in 3D as in the question.
Poisson Surface Reconstruction indeed solves the task, but it is hardly can be classified as "fast", because it requires constructing of an additional field defined in the nodes of a voxel grid or octree by solving a large system of equations, and only after that reconstructing triangular surface as a level-set, and that surface typically requires simplification to reduce the number of triangles till acceptable level.
A faster method of receiving triangular meshes from point clouds is by considering local triangulations around each point (as in the mentioned PCL). The benefit with this method is that all local triangulations can be constructed independently and in parallel. The implementations then diverge in how individual local triangulations are merged in the final mesh. One of the approaches is to count the votes for each triangle. Triangles with 3 votes (one per each local triangulation of every its vertex) find the place in the final mesh, while triangles having lower number of votes are included there only if it does not introduce non-manifoldness in the mesh. One of the implementations is in triangulatePointCloud function of MeshLib.