Research On 3D Discrete Point Cloud Data Processing Technology

With the greatest development and improvement of technology, such as binocular vision, depth video technology, to gain the discrete points is much easier and precisely. Therefore, the 3D reconstruction technology based on scattered point cloud is becoming more and more hot and important, especially in the field of computer vision, artificial intelligence and so on.On the basis of surface reconstruction technology of scattered point cloud, this dissertation focus on the triangular mesh processing to the 3D discrete point cloud model of real objects, including searching k-nearest neighbors quickly, Delaunay triangulation, local triangular splicing and integration.The primary research and the main contents of this essay are as follows:1) Proposes a new and fast k-nearest neighbors searching algorithm, Based on twice spaced, the scattered point cloud space was divided into cell grids, then the algorithm assumes that there is a cubic grid which centered at target point. With the change of the cubic grid’s side length and the number of points containing in the cubic grid, the algorithm find the k-nearest neighbors finally.2) Proposes a fast Delaunay triangulation algorithm. Firstly, structuring a rectangle which can have all data included, at the same time, sorting the points in accordance with the coordinate values, and inserting the points with the sort order one by one, these processing can narrow t-he search area of the first triangle and help to find the target triangle rapidly. Secondly, picking the first triangle’s gravity center, connecting the gravity center and the insertion point, along this line and start with the first triangle, judging the relationship with the line and each edge of the triangle so that to find the search path of the target triangle fast and to improve the efficiency of plane triangle subdivision.3) Proposes a simple and practical mesh splicing algorithm. The first step is construct a bunch of triangle surface at the boundary points, then find the appropriate triangle patch to connecting the boundary points by patch matching.The experiment results show that the proposed algorithm can both splice and integrate the local triangular mesh and can make it quicker.