Constructing solid models using implicit functions defining connectivity

Abstract

A solid model is constructed from surface point data that represent layers of an object. The model is represented as the level set of an implicit function that is fitted to the surface point data. In the two-dimensional application of the technique, a Delaunay triangulation is performed for each layer. In this step, surface points are connected to form Delaunay triangles; the data points are the vertices of the Delaunay triangles. A circumcircle is then created around each Delaunay triangle, passing through the three vertices of the triangle. To decimate the circumcircle data, overlapping circumspheres are merged according to a merging criterion. A pseudo-union of implicit functions for the reduced number of circumcircles provides an initial implicit function for the layer. Errors in the implicit function are substantially reduced by optimizing the position and/or radii of the circumcircles. The implicit functions for a plurality of adjacent layers are blended to define an implicit function for the object that is used for reconstruction or modeling of the object. The technique is generally extended to n dimensional objects by using simplices instead of the Delaunay triangles and hyperspheres instead of the circumcircles. The method is capable of constructing solid models with highly localized surface curvature.