Hmm, why is it very hard? Wouldn't just connecting the points between them yield acceptable results? I can understand if the points are disparate, but this dataset is pretty much a grid, and it looks like you could easily generate the surface from the points.

What am I missing?

How do you decide which points to connect?

Use an unstructured grid (triangulation) to connect the elements. This is routinely used in numerical modelling (think computational fluid dynamics) to generate linked data sets from scatter data (such as this) in 2 and 3D (i.e. a surface and a volume).

That will work in about 50-70% of cases in the real world depending on the quality of your data and how sensitive you are to errors. For the remaining 30-50% you have to fix things by hand. The further problem is there is no good heuristics to separate the cases where it worked from where it didn't, so you still have to go through all the data to flag the cases which have to be fixed. Trust me, if you can come up with a way to make it work in general, you could build a very successful company around selling that software.

What phireal said. If it's a sparse point cloud, sure, it would be troublesome. The one in the example is pretty dense, and it's almost a grid, so just connect neighboring points together, no?

How do you decide which points are neighboring?