download paper

The goal of surface reconstruction is to obtain a continuous representation of a surface described by a cloud of points. This problem is often called the \emph{unorganized points problem} because the cloud of points has no connectivity information. This paper surveys the solution techniques for the unorganized points problem. Two closely related formulations of the problem are surface interpolation and approximation. Many reconstruction techniques handle only exact interpolation, while others can vary from exact to approximate surfaces. Exact and approximate surfaces differ in that exact surfaces pass through the data points, while approximate surfaces pass near the data points.

The motivation behind surface reconstruction is to obtain a digital representation of a real world, physical object or phenomenon. Clouds of point data may be obtained from medical scanners (X-rays, MRI), laser range finders (optical, sonar, radar), or vision techniques (correlated viewpoints, voxel carving, stereo range images). Often, additional information on the cloud of points may be available, such as the order in which the data points were sampled, the orientation of the normal vector at each of the points, or the positions of the cameras used in stereo range images. Some surface reconstruction algorithms take into consideration this information, while others tackle the general problem.

Notions which often appear in the surface reconstruction literature include best fit, least error, distance metric, smooth, piecewise, and energy minimizing, among others. These notions help to distinguish the different techniques. One of the primary problems in reconstruction is that a "correct" surface does not generally exist. That is, we may have a cloud of points that is a discrete representation of an organ, but how can we evaluate a surface reconstructed from the data? How can we decide that we have obtained a good representation of the organ when we have no way to exactly measure the continuous surface of the organ? In addition, the data itself may be noisy. Even if we reconstruct the surface of an object whose surface we know analytically, such as a unit sphere or cube, we are not guaranteed that a reconstruction algorithm that perfectly reconstructs our known object would do as well with any other unknown object. As a result, notions such as least error, distance metrics, smoothness of the surface, and energy minimizing become important metrics with which to evaluate a reconstructed surface. In one scenario, the best reconstruction is one that minimizes the distance between all data points and the surface.

This paper compares several of the recent techniques in the universe of surface representation and reconstruction. In particular, more attention is given to the algebraic domain than to the computational geometry domain. There are three primary categories of surface representations:

Parametric
The surface is represented by a patch, described by a parametric equation. Multiple patches may be pieced together to form a continuous surface. Examples of parametric representations include B-spline, Bezier, and Coons patches. The basic parametric formulations such as B-splines will not be discussed in this paper. Instead, two examples of reconstruction to parametric representations will be presented. Sections 4 and 5 cover Terazopoulos' thin-plate parametric representation and Gossard fairing of parametric patches, respectively.

Implicit
The surface is a level set surface, and is defined to pass through all positions where the implicit function evaluates to some specified value (usually zero). The global algebraic representations used by Taubin and Gotsman are covered in section 2. The piecewise algebraic implicit functions of Bajaj are covered in section 3.

Simplicial
In this representation, the surface is a collection of simplicial complices including points, edges, and triangles. Techniques to identify which simplicial complex belongs to the surface include Alpha shapes and the Crusts algorithm. Both of these topics are covered briefly in this paper.