08/01/1997 09:00 AM
Computer Science
This survey presents several techniques for solving variants of the following scattered data interpolation problem: given a finite set of $N$ points in $R^3$, find a surface that interpolates the given set of points. Problems of this variety arise in numerous areas of applications such as geometric modeling and scientific visualization. A large class of solutions exists for these problems and many excellent surveys exist as well. The focus of this survey is on presenting techniques that are relatively recent. Some discussion of two popular variants of the popular variants of the scattered data interpolation problem - trivariate (or volumetric) case and surface-on-surface - is also included. Solutions are classified into one of the five categories: piecewise polynomial or rational parametric solutions, algebraic solutions, radial basis function methods, Shepard\'s methods and subdivision surfaces. Discussion on parametric solutions includes global interpolation by a single polynomial, interpolants based on data dependent triangulations, piecewise linear solutions such as alpha-shapes, and interpolants on irregular mesh. Algebraic interpolants based on cubic A-patches are described. Interpolants based on radial basis functions include Hardy\'s multiquadrics, inverse multiquadrics and thin plate splines. Techniques for blending local solutions and natural neighbor interpolants are described as variations of Shepard\'s methods. Subdivision techniques include Catmull-Clark subdivision technique and its variants and extensions. A brief discussion on surface interrogation techniques and visualization techniques is also included. NOTE: This paper supersedes ucsc-crl-96-07
