Research On Implicit Surface Reconstruction Algorithms Based On Moving Least Squares

3D data acquisition and object reconstruction is an emerging technology for 3D digitization. It can generate digital representation of a real object in the following way: first obtain the point cloud of the object by 3D scanning, then preprocess the obtained point cloud for a more compact one, and finally generate a 3D model from the cleaned point cloud by surface reconstruction. 3D acquisition and object reconstruction is useful for a wide variety of applications, e.g. Industrial design, Architecture, Medical CAD/CAM, Cultural heritage, Entertainment, and 3D printing.Surface reconstruction is a critical step for 3D data acquisition and object reconstruction. Surface reconstruction is the process of constructing a mesh representation from scatter 3D points, it mainly faces these two difficulties: the obtained point cloud may be very huge, may requires a lot of time to reconstruct it, and the scatter points have no evident hints about the topology of the real object, may be difficult to get the toplogy right in the reconstruction process, these difficulties make surface reconstruction a very hard problem, requiring the underlying algorithms to be both correct and efficient. Thus, improving underlying algorithms of surface reconstruction is significant, in both theory and practice.This thesis focuses on algorithms of surface reconstruction applied to scatter 3D points. An implicit approach based on moving least squares is adopted. Main topics of this thesis are some improvements on correctness and efficiency of this implicit approach, and eventually a brand new algorithm based on all improvements is proposed. The main contributions of this thesis are:Proposed an approximation strategy based on nearest neighbors, and this strategy leads to an approximate algorithm that can compute implicit surface function efficiently;Proposed an identification algorithm for no-sampling areas of non-closedsampling surfaces, based on this identification process, a capable surface reconstruction algorithm is proposed, it can handles non-closed sampling surfaces correctly;Defined the concept of generalized no-sampling areas for characterizing areas distant to overall scatter points. An identification algorithm for generalized no-sampling areas is also developed, it can omit many areas distant to overall scatter points, thus improve performance greatly;To balance the precision and speed of Marching Cubes algorithm, a quasi-non-uniform grid based on trilinear interpolation is proposed and utilized, this grid handles areas with different levels of details differently. It can maintain current Marching Cubes resolution in details-sparse areas, and increase Marching Cubes resolution in details-rich areas, thus obtain desired precision in details-rich areas with a small cost;The final algorithm is proposed by incorporating all improvements of this thesis, namely, approximate implicit surface function, identification of no-sampling areas and generalized no-sampling areas, and quasi-non-uniform Marching Cubes grid. This final algorithm is capable of reconstructing non-closed sampling surfaces correctly and efficiently.Designed and implemented a prototype surface reconstruction system based on algorithms of thesis and related algorithms, for research and production purposes.A lot of experiments are also conduced to verify the proposed algorithms, to demonstrate capabilities of the proposed algorithms, showing that the proposed algorithms are feasible and practical at some extent.