Quynh's
Den

A
Sampling
of
Surface
Reconstruction
Techniques

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 (Xrays, 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:
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.