Solid and surface reconstruction from random, scattered three-dimensional data

The reconstruction of solids from random, ungridded coordinate data in three dimensions is studied. The data may be acquired using a computer vision system, tomography or a coordinate measuring probe. Several solids can be constructed from any given set of non-convex data. The problem of identifying the best polyhedral solid for engineering applications from a given set of data is studied, and algorithms for the construction of this solid are developed.; The three-dimensional Delaunay triangulation of the point set is first constructed. Two different approaches to the construction of polyhedral solids from the Delaunay triangulation are studied. In the first method, the final polyhedral model is obtained by the successive removal of individual Delaunay tetrahedra till the surface of the model passes through all the data points. Two algorithms for reconstruction using this approach are developed--one using the surface area of the individual tetrahedra as the criterion for removal, and the other using the solid angles of the tetrahedra.; The second approach pioneers the use of techniques from graph theory and morphology to construct closed and open surfaces passing through the data set. The concepts of {dollar}alpha{dollar}-complexes, Gabriel complexes and relative neighborhood complexes in three dimensions are developed, and surface-based reconstruction algorithms using these complexes are described. Surface-based schemes are found to be more flexible since they can be used for the reconstruction of open surfaces as well as closed surfaces, and can reconstruct objects with holes and cavities as well. The reconstruction scheme based on the Gabriel complex is found to be the one most suitable for the test data. The use of three-dimensional Gabriel graphs and relative neighborhood graphs for characterizing tetrahedral meshes and for clustering algorithms in three dimensions is also explored.