Surface reconstruction from unorganized points

Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle.

ACM SIGGRAPH 1992 Proceedings, 71-78.
(Seminal Graphics Papers Vol 2.)

Signed-distance field estimated from a set of unoriented noisy points.

Abstract: We describe and demonstrate an algorithm that takes as input an unorganized set of points {x₁, ... , x_n} in R³ on or near an unknown manifold M, and produces as output a simplicial surface that approximates M. Neither the topology, the presence of boundaries, nor the geometry of M are assumed to be known in advance — all are inferred automatically from the data. This problem naturally arises in a variety of practical situations such as range scanning an object from multiple view points, recovery of biological shapes from two-dimensional slices, and interactive surface sketching.

Hindsights:

This paper addresses the difficult case where the data points have no inherent structure. This was useful for data we had obtained from the company Technical Arts, which manufactured a laser-sheet scanner mounted on a coordinate measuring machine. For traditional range images which have more structure in the data, a more specialized technique is the volumetric approach of Curless and Levoy (SIGGRAPH 1996), which also uses a signed-distance implicit function.

Our "Riemannian Graph" construction is similar to that used to estimate manifold geodesics in Isomap construction.

See also my 2006 work Poisson surface reconstruction, which assumes oriented points but achieves greater robustness using a global (yet efficient) solution.