I am trying to figure out what algorithms there are to do surface reconstruction from 3D range data. At a first glance, it seems that the Ball pivoting algorithm (BPA) and Poisson surface reconstruction are the more established methods?
Not sure if it's exactly right for your case, since it seems weird that you omitted it, but marching cubes is commonly mentioned in cases like these.
You might start looking at some recent work in the field - currently something like Fast low-memory streaming MLS reconstruction of point-sampled surfaces by Gianmauro Cuccuru, Enrico Gobbetti, Fabio Marton, Renato Pajarola, and Ruggero Pintus. Its citations can get you going through the literature pretty quickly.
I have been facing this dilemma for some months now, and made exhaustive research.
Mainly there are 2 categories of algorithms: computation geometry, and implicit surfaces.
They fit the mesh on the existing points.
Probably the most famous algorithm of this group is powercrust, because it is theoretically well-established - it guarantees watertight mesh.
Ball Pivoting is patented by IBM. Also, it is not suitable for pointclouds with varying point density.
One fits implicit functions on the pointcloud, then uses a marching-cube-like algorithm to extract the zero-set of the function into a mesh.
Methods in this category differ mainly by the different implicit functions used.
Poisson, Hoppe's, and MPU are the most famous algorithms in this category. If you are new to the topic, i recommend to read Hoppe's thesis, it is very explanatory.
The algorithms of this category usually can be implemented so that they are able to process huge inputs very efficiently, and one can scale their quality<->speed trade-off. They are not disturbed by noise, varying point-density, holes. A disadvantage of them is that they require consistently oriented surface normals at the input points.
You will find small number of free implementations. However it depends on whether You are going to integrate it into free software (in this case GPL license is acceptable for You) or into a commercial software (in this case You need a more liberal license). The latter is very rare.
One is in VTK. I suspect it to be difficult to integrate (no documentation is available for free), it has a strange, over-complicated architecture, and is not designed for high-performance applications. Also has some limitations for the allowed input pointclouds.
Take a look at this Poisson implementation, and after that share your experience about it with me please.
Also: here are a few high-performance algorithms, with surface reconstruction among them.
CGAL is a famous 3d library, but it is free only for free projects. Meshlab is a famous application with GPL.
While not a mesh representation, an ex-colleague recommended me this link to source code for a Thin Plate Spline method:
Anyone tried it?
On the same website there are a series of open source works.
(I can only post one hyperlink because of spam firewall)
http://www.advancedmcode.org/surface-recostruction-from-scattered-points-cloud-mycrust-robust.html
Anyway the problem solution strictly depends from your cloud. If you need a hint contact me on my e-mail.
If you want make some direct experiments with various surface reconstruction algorithms you should try MeshLab, the mesh-processing system, it is open source and it contains implementations of many of the previously cited surface reconstruction algorithms, like:
Sources are protected by GPL, so you could not use them in a commercial closed source project, but it is very important to get the right feeling about the properties of the various surface reconstruction algorithms (how sensitive to noise they are, the speed, the robustness to outliers, how they preserve fine details etc etc) before starting to implement one of them.