Parallel surface reconstruction through virtual milling

Surface definition deals with representing a surface analytically using a finite number of parameters and with acceptable levels of error. In the past few years it has become a key discipline in Computational Fluid Dynamics (CFD). Recent advances in computers and numerical algorithms have made it possible for CFD practitioners to attempt flow solutions about complex three-dimensional geometries. The first step in this process is having a numerical representation of the shape. In many cases of interest such a representation already exists; i.e., aircraft designed on a computer. Such Computer-Aided Design (CAD) descriptions do not exist, though, for objects found in nature or predating CAD. In such situations a technique for measuring the object and then constructing a surface conforming to these measurements is needed. Existing techniques for 3-D surface definition often require considerable human intervention, both in the measuring and the reconstruction process. This is a time consuming proposition. It is desirable to develop a fully automated alternative. Three-dimensional objects can be measured accurately and quickly from multiple viewpoints using a Cyberware laser digitizer. The digitizer returns the coordinates of a set of surface points. The problem is then to construct a faithful representation of the original object from these points. The algorithm proposed here has two distinct stages. In the first stage, surface fragments, using information from a single view, are produced by employing a visibility constraint and a 2-D Delaunay triangulation technique. In the next stage, surfaces from multiple views are combined through an approach that emulates the machining operation of milling. The final result is a non-convex, triangular faceted, polyhedron that approximates the object shape. A sequential version of the virtual milling algorithm exists on a Silicon Graphics workstation. The algorithm is of O(NlogN) complexity, where N is the number of data points. Experimental results have been obtained for a scaled F117-A model scanned from multiple viewpoints. Several topological issues have been addressed. A parallel version of the algorithm has been implemented on the Intel Gamma Prototype, a 128 node, distributed-memory, MIMD computer. Run times are compared to those obtained on an Iris 310/VGX workstation.