Algorithm for generating a triangular mesh from a cloud of points

Question

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.

Scutcheon

Answer 1

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.

Range

The magic is in gp3.reconstruct (triangles) for the PCL case -- alas this magic is not revealed in the presentation. – Concatenate

Answer 2

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

Passel

Answer 3

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).

Disband

Answer 4

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.

Jansen