Scattered Point Cloud Model Hole Boundary Extraction Algorithm And Implementation

Improving precision of3D scanning device make it much easier to acquire data from real objects and point cloud becoming more and more popular. At present, a common laser scanner can acquire millions of points from surface of a real object. However, due to problems with accessibility, or due to the special physical properties of the scanned surface, the data acquired by the scanning device may have problems. For instance, some parts of the objects can be missing. This produces holes in the point cloud, which do not correspond to any holes in the object. We describe a algorithm for detecting these holes. This algorithm combines maximum angle measured criterion, half-disk measured criterion and shape measured criterion. This presentation is divided into five chapters, the major work of this paper are:1. For each point of the point cloud, we used Kd-tree to search the k-nearest points of them. After finding the k-nearest points, we used Principal Component Analysis to estimate the normal of each point. The computed k-nearest points and normals provide the underlying basis for detecting boundary points.2. Based on the own property of point cloud, we decided to use the topotaxy of each point of point cloud. We choose three criterions to detect holes:maximum angle measured criterion, half-disk measured criterion and shape measured criterion. For the maximum angle measured criterion, if a point and its k-nearest points distribute on one side, we can believe that this point may be a boundary point. The most important thing is project the k-nearest points onto the tangent plane and sort these projected points. For the half-disk measured criterion, if a point is in the interior of the point cloud, the points of k-nearest points projected on tangent plane can homeomorphic to a disk, on the other hand, if a point is a boundary point, the projected points can homeomorphic to a half-disk. To reduce the influence of the changing sampling density, we use the Gauss kernel as the weight function in computing the centroid of the projected point of k-nearest points. For the shape measured criterion, we extracted two quantities, The center location of the neighbor and the correlation matrix. The eigenvectors of the correlation matrix together with the corresponding eigenvalues define the correlation ellipsoid that adopts the general form of the k-nearest points. We use the eigenvalues to detect the boundary points.3. In order to make good use of the different advantages of the criteria and increase the robustness of the boundary probability computation, a weighted sum is given as the final boundary probability. We use this final boundary probability to detect boundary points.4. After detecting boundary points, we are ready to find the boundary polygons. Boundary polygons have practical significance in solid modeling. We use greedy algorithm to sort these boundary points. Generally, there are several holes in a point cloud rather than one, in other words, we must divide the initial ploygon into ploygons according to the holes.