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.