Surface reconstruction is
a problem in the field of computational geometry that is concerned with
recreating a surface from scattered data points sampled from an unknown
surface. To date, the primary application of surface reconstruction algorithms
has been in computer graphics, where physical models are digitized in three
dimensions with laser range scanners or mechanical digitizing probes
(Bernardiniet al., 1999). Surface reconstruction algorithms
are used to convert the set of digitized points into a wire frame mesh model,
which can be colored, textured, shaded, and placed into a 3D scene (in a movie
or television commercial, for example). In this paper, we discuss some
computational geometry preliminaries, and then move on to a summary of some different
techniques used to address the surface reconstruction problem. The coming
sections describe two algorithms: that of Hoppe,et al. (1992) and Amenta,et al. (1998
Crossno, P.J. and Angel, E.S. (1999) Spiraling Edge: Fast Surface Reconstruction from Partially Organized Sample Points. IEEE Visualization’99, 24-29 October 1999, San Francisco, 317-324.
Boissonnat, J.-D. and Cazals, F. (2000) Smooth Shape Reconstruction via Natural Neighbor Interpolation of Distance Functions. ACM Symposium on Computational Geometry, 12-14 June 2000, Hong Kong, 223-232.
Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C. and Evans, T.R. (2001) Reconstruction and Representation of 3D Objects with Radial Basis Functions. Proceedings of ACM SIGGRAPH’01, 12-17 August 2001, Los Angeles, 67-76.