The problem of taking an unorganized cloud of points in space and fitting a polyhedral surface to those points is both important and difficult. This paper presents an algorithm that achieves impressive results. It consists of two primary stages, with several subsidiary steps. The first stage is to define a function f that maps all points “near” the input data to a signed distance from the conjectured best fit surface. The second stage finds a triangulated surface that approximates the zero-set of f. This second stage applies a known contour-tracing technique, the “marching cubes” algorithm, and a postprocessing step to improve the aspect ratio of the triangles.

The first stage is innovative. Its first step is to assign an oriented tangent plane to each input data point p by first fitting a plane to the k nearest neighbors of p (the authors use values of k from 10 to 40), and then choosing an orientation for the planes to be consistent with nearby orientations. This step is key. Consistency is maintained by constructing a graph G connecting two points if either is one of k nearest to the other, and weighting these arcs by the degree to which the corresponding tangent planes are parallel. Then the weighted minimum spanning tree T of G is found.

Starting with the known orientation of the plane for the highest point, the orientations are propagated along T. This process has the effect of establishing the low-curvature orientations before the complex portions of the surface are tackled.

With the oriented tangent planes available, the signed distance f ( p ) from any point p to the surface can be approximated by using the tangent plane for the nearest point. Once a rule for computing f is in hand, the zero-set is constructed as previously described.

The algorithm makes certain sampling assumptions for the input data that may not hold in practical situations. It would be interesting to learn how the algorithm performs in practice. A rather different attempt to achieve the same goals was developed independently by Veltkamp [1]; neither work refers to the other, no doubt because they evolved simultaneously.