The Auto-Classification Of Unorganized Points In Surface Reconstruction

Based on data cloud, which is measured from 3-coordinate measuring machine (CMM) or so, an algorithm to search lopological structure from 3D unorganized points using Envelopment-box technology is proposed in this thesis. Based on this method, we searching neighbor points of sampling point. We also improve the Max-Min angle criteria to realize local triangulation, and then get the normal of sampling point from the triangulation. Using the normal and neighbor relationship, classification of scattered data points is realized according to the quadric surface.The typical algorithms of surface reconstruction from 3D scattered data points are introduced, and then we discuss the current surface tessellation algorithms about their adaptive range, low efficiency. From this, we bring out our solution.Based on the theory of space dividing using envelopment-box, an algorithm to search topological relationship from 3D unorganized points is proposed in this thesis. According to points' space position, we only go on dividing the envelopment-box that has data until reaching the precision request in the dividing process. The dividing process is recorded by octree, and then we make out the rapid adjacent-field searching algorithm using envelopment-box's recursion feature. This algorithm can also kick off some noise-points from the data cloud. It make the consequent process of surface reconstruction more convenience and precise. We use a size changeable adjacent field to describe the topological structure of 3D unorganized points in our algorithm. It can offer essential dynamic information for tessellation and points' normal.The typical optimizing criterion of triangulation is Max-Min angle criteria, but it has some restriction when applying in three dimensions. We proposed some amelioration by taking into consider the relationship of points and their neighbors. That can make the triangulation's space variation more even, and can reach the surface fairness request.We using the triangulation constructed from the point's adjacent field, which is the nearest to the original local surface, to compute the point's normal. It can get a good result. As to the problem that plane's normal has two opposite direction, we using "direction spread" to resolve it. Examination result show that adopting adjacent points' main normal direction as current point's normal direction can resolve that problem andprovide reliable information to points' classification.As it can be expressed easily by argument equations, we use the conicoid as the criteria of points' classification. Based on the point's normal and the adjacent field, corresponding to the conicoid equation such as plane, ball and cylinder, we search the points that fit the equation along the adjacent field. Using this method, we realized the automatic classification of unorganized points.The experiments using the algoritlim and criteria approved from this thesis are also carried out. It shows that the simulation results are in well agreement with the experiment results. This demonstrates that the method proposed in this thesis can be used in surface reconstruction of dada dividing processes.