Surface reconstruction from unorganized points (PhD Thesis)
Department of Computer Science and Engineering, University of Washington, June 1994.
Robust surface topology and optimized geometry from scanned 3D points.
This thesis describes a general method for automatic reconstruction of accurate, concise, piecewise smooth
surfaces from unorganized 3D points. Instances of surface reconstruction arise in numerous scientific and
engineering applications, including reverse-engineering — the automatic generation of CAD models from
Previous surface reconstruction methods have typically required additional
knowledge, such as structure in the data, known surface genus, or orientation information. In contrast,
the method outlined in this thesis requires only the 3D coordinates of the data points. From the data, the
method is able to automatically infer the topological type of the surface, its geometry, and the presence
and location of features such as boundaries, creases, and corners.
The reconstruction method has
three major phases: 1) initial surface estimation, 2) mesh optimization, and 3) piecewise smooth surface
optimization. A key ingredient in phase 3, and another principal contribution of this thesis, is the
introduction of a new class of piecewise smooth representations based on subdivision. The effectiveness of
the three-phase reconstruction method is demonstrated on a number of examples using both simulated and real
Phases 2 and 3 of the surface reconstruction method can also be used to approximate existing
surface models. By casting surface approximation as a global optimization problem with an energy function
that directly measures deviation of the approximation from the original surface, models are obtained that
exhibit excellent accuracy to conciseness trade-offs. Examples of piecewise linear and piecewise smooth
approximations are generated for various surfaces, including meshes, NURBS surfaces, CSG models, and
Really, there was more work here than the stapling of three papers :-)
This surface reconstruction problem has continued to be an active area; see the recent
papers by Nina Amenta
and the commercial product by Geomagic.
This reconstructed mannequin head is my small contribution to the pool of geometric models commonly
used in graphics.
See also my 2006 work
Poisson surface reconstruction,
which assumes oriented points but achieves greater robustness using a global (yet efficient) solution.