SMOOTH SURFACE RECONSTRUCTION FROM SCATTERED DATA POINTS

We describe here a new technique and a package for rapid reconstruction of smooth surfaces from scattered data points. This method is based on a fast recurrent algorithm for the Delauney triangulation followed by rational interpolation inside triangles. Preprocessing of data includes sorting and takes N log(N) time. Afterwards the computational cost is a linear function of the amount of data. This technique enables a user to construct a surface of any class of smoothness and degree of convergence. Our package reconstructs surfaces that can be uniquely projected either on a plane or on a sphere. The graphical section of this package includes three dimensional transformations, shading, hidden surface removal, interactive adding points into triangulation by mouse, etc. The graphics has been implemented on Iris-4D, SUN-4 and IBM-5080.