Connecting points to make a triangle

Question

If I have a set of 3d points (AKA point cloud) what is the best way to determine the groups of 3 points (triangles) I should make, to create a surface reconstruction?

Answer 1

Delaunay Triangulation is your friend! There are lots of resources available about it if you Google the term, and the math/logic behind it isn't too tough. Making it FAST is a bit harder (but totally do-able), but that depends entirely on your requirements.

Answer 2

If you are willing to use an external application (or implement your own), MeshLab has lots of cool reconstruction algorithms under: Filters > Re-meshing, simplification and reconstruction. Ball Pivoting Surface Reconstruction and Poisson Reconstruction are good ones.

Answer 3

A new approach has been introduced by Vierjahn et al. sGNG: Online Surface Reconstruction based on Growing Neural Gas. Although it is a rather complex algorithm to implement it allows incremental refinements of the 3D mesh.

You can read the tech report here. Furthermore, the authors give hints and refer to other new techniques in the research field of 3D mesh reconstruction from 3D point clouds.