Presented in this thesis is a fast method for surface reconstruction from 3D scattered points. Surface reconstruction methods are used in various engineering applications to generate CAD models in reverse-engineering, facet models for DMU system, STL files for rapid prototyping and NC codes for CAM system from physical objects. Previous surface reconstruction methods using 3D Delaunay triangulation algorithm have typically required much time for handling very large data set.
The suggested reconstruction method is to partition the given point set by recursive cell decomposition and to project the sub-point sets on the tangent planes for applying 2D Delaunay triangulation algorithm. The reconstruction method has three major phases: 1) generating a triangular net composed of reference points of 3D uniform grid cells, 2) partitioning the point set into sub-point sets which are projected to the extended planes of triangles and testing the validity of projecting each sub-point set to each plane, 3) generating sub-triangular nets from sub-point sets by 2D Delaunay triangulation algorithm and merging the sub-triangular nets. In step 2) if projection of a sub-point set is invalid, step 1) and 2) are repeated after the sub-point set is decomposed into smaller cells. The effectiveness of the reconstruction method is demonstrated on several examples using real data obtained from 3D laser scanner.