GIT-GVU-00-28

A Sampling of Surface Reconstruction Techniques

Huong Quynh Dinh

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 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.

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.

Surface reconstruction, algebraic fitting, least squares fitting, parametric surfaces, implicit surfaces, simplicial complexes

PDF

Postscript