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.

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.

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

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