Surface reconstruction from unorganized points

Surface reconstruction from unorganized points
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle.
ACM SIGGRAPH 1992 Proceedings, 71-78.
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 {x1, ... , xn} in R3 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.

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.

ACM Copyright Notice
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or The definitive version of this paper can be found at ACM's Digital Library