Reconstructing surfaces and functions on surfaces from unorganized three-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 problem of automatically reconstructing from this data a topologically consistent and geometrically accurate model of the object and of the sampled scalar field is the subject of this paper. The proposed algorithm can deal with connected, orientable manifolds of unrestricted topological type, given a sufficiently dense and uniform sampling of the object's surface. It is capable of automatically reconstructing both the model and a scalar field over its surface. It uses Delaunay triangulations, Voronoi diagrams, and cu-shapes for efficiency of computation and theoretical soundness. It generates a representation of the surface and the field based on Bernstein-Bezier polynomials, with the surface modeled by implicit patches (A-patches), that are guaranteed to be smooth and single-sheeted.