RECONSTRUCTING SURFACES AND FUNCTIONS ON SURFACES FROM UNORGANIZED 3-DIMENSIONAL DATA

Creating a computer model from an existing part is a common problem in reverse engineering. The part might be scanned with a device like the laser range scanner, or points might be measured on its surface with a mechanical probe. Sometimes, not only the spatial location of points , but also some associated physical property can be measured. The prob lem of automatically reconstructing from this data a topologically con sistent and geometrically accurate model of the object and of the samp led scalar field is the subject of this paper. The proposed algorithm can deal with connected, orientable manifolds of unrestricted topologi cal type, given a sufficiently dense and uniform sampling of the objec t's surface. It is capable of automatically reconstructing both the mo del and a scalar field over its surface. It uses Delaunay triangulatio ns, Voronoi diagrams, and cu-shapes for efficiency of computation and theoretical soundness. It generates a representation of the surface an d the field based on Bernstein-Bezier polynomials, with the surface mo deled by implicit patches (A-patches), that are guaranteed to be smoot h and single-sheeted.