Nina Amenta and I have worked on the problem of reconstructing a surface from scattered sample points. (David Eppstein and Manolis Kamvysselis also contributed to parts of this work.) The result is a simple new algorithm for surface reconstruction based on Voronoi diagrams and Delaunay triangulations. Our algorithm computes a piecewise-linear surface, vertex set exactly equal to the sample points, with a provable guarantee: if the original surface was sampled sufficiently densely, then the reconstructed surface lies within a small error tolerance of the original.
"Sufficiently densely" is defined locally as proportional to the distance to the medial axis, which incorporates both curvature and proximity to "other" parts of the surface. If you look closely, you can see some artifacts in the surface above: the pig seems to have a few sharp teeth and a spiky dog collar. These extra triangles appear near high-curvature parts of the surface where the sampling density is too low.
The algorithm in a nutshell:
Our algorithm is especially suitable for scientific visualization, because it has no tuning parameters, computes an interpolating (rather than approximating) surface, and makes no assumptions about the geometry or topology of the surface (other than the minimal assumption that the sample points are dense enough to capture surface features). Other algorithms (for example, one at Stanford) are designed more specifically for capturing 3D models in computer graphics. These algorithms use the sample points to define a distance to the surface, then contour the zero set of the distance function on a grid of voxels.
Our algorithm is quite sensitive. Notice the subtle "3" and the lettering on the golf club below (sample points courtesy of Hugues Hoppe). These shallow features would be missed by any voxel-based algorithm, unless the voxels were very small.
