A3D Data Reduction And Smoothing Algorithm For Point Clouds

As an advanced manufacturing technique, reverse engineering, which can beapplied to product design, development and innovation, has become an independentsubject in Computer Aided Design. Data processing, one of the key techniques inreverse engineering, mainly covers data reduction, data smoothing and othertechniques. Because the quality and the numbers of3D data point have vital effects onthe quality of subsequent model reconstruction, it’s very significant to study on datareduction and smoothing. The point cloud studied in this thesis is achieved by a newtype of3D data scanning system, a hand-held3D laser scanning system. Concerningthe scattered and layered characteristic of the point cloud, a reduction and smoothingalgorithm is proposed, in addition to the concept and development of reverseengineering represented in this thesis, and the contents of the research are as follows:1. A spatial index of point cloud is created based on known marked points using amethod integrating Octree and3D R-tree, ensuring fast and correct access to local data.First the three dimensional information of the bounding box containing all points canbe obtained based on known marked points. Then the bounding box is divided intomany same sized3D meshes equally. At last clustering the meshes containing datapoints centered about meshes containing marked points, and subdividing meshescontaining data points by using Octree subdivision method until all3D meshesconverges.2. According to the demand of actual applications as well as having consideredthe properties scattered and layered of point clouds, a novel ordering reduction methodis presented in this thesis. First define the data points within27bounding boxescentered about leaf nodes of the spatial index as local data points, which can be usedfor least-squares plane fitting, and a local reference coordination system is establishedbased on the normal vector of local reference plane. Second the local data aretransformed into the local reference coordination system and parameterized points inthe parameterization coordination system established on local reference coordinationsystem. Then sampling the quadratic surface approximated by local referencecoordinates and parameterization coordinates of data point cloud. Finally the orderedset of reference points is obtained by transformed back into the workpiece coordinationsystem. 3. The fine reduction algorithm proposed in this thesis is tested by usingMicrosoft Visual C++on the Windows XP operation system.As the experimental results demonstrate, the high efficiency of correct dataretrieval method is achieved for the fast establishment of special index in this thesis. Inaddition, the reduction algorithm presented in this thesis not only can efficientlypreserve critical surface characteristics and high reduction rate thus greatly improvethe accuracy of reduction for3D point clouds, but can reduce the scattered and layeredpoint cloud into ordered smoothing point cloud in a single layer.