Research On Surface Reconstruction From 3D Point Cloud Based On Delaunay Growth Algorithm

With the rapid development of science and technology, especially computer graphics and 3D scanning technology, research on surface reconstruction from 3D scattered point has become a hotspot in computer graphics. A surface reconstruction technology is a method to reconstruct three dimension model by sampling points to make model realistic. The technology of 3D reconstruction can quickly, accurately and correctly reconstruct High-quality mesh surface, so it is widely used in geology, reverse engineering, robotics, CAD / CAM, medical, protection of cultural relics and other fields.Currently popular 3D reconstructions are plane projection algorithm and Poisson algorithm. The main idea of Greedy projection algorithm is letting the points to project onto a plane, and using the technology of plane triangulation to generate triangular mesh on projection plane, so that we can obtain each point of connection relationship. This idea of the algorithm is very easy to implement, however, it has a problem of multi- valued projection which leads to produce cavities when the model has complicated surface structure, and triangular mesh stitching is easily to produce errors. Poisson algorithm is based on the theory that gradient value of indication function is equal to normal of cloud points, and the indication function was obtained by using the Poisson equation, then can get a suitable surface reconstruction with iso-surface extraction. The surface by Poisson reconstruction algorithm is very smooth. However, Poisson can't bring out the details of the high surface model, besides, the algorithm only applies to closed and normal point cloud model. Because the 3D surface reconstruction algorithm has highly time and space complexity, small scope and low surface quality shortcomings. With theory of two-dimensional Delaunay growth algorithm, we propose a new Delaunay growth algorithm based on adaptive circumscribed circle strategy, the algorithm can quickly narrow down the range of extension points, compared with the traditional growing algorithm, the efficiency has been greatly improved. Using the improved two- dimensional Delaunay growth algorithm to three-dimensional space, proposing a new 3D Delaunay growth algorithm based on adaptive circumscribed ball strategy, the algorithm obtains a set of expansion point by an adaptive external space sphere method, usually the set contains one point, we filter points through binding guidelines and evaluation function to ensure that the triAngel is close to Delaunay triAngel when the set contains multiple points.The improved algorithm can make up for the lack of Greedy projection algorithm and Poisson algorithm and has the following three advantages: First, the adaptive circumscribed ball strategy, which greatly improves the efficiency of the searching point, can quickly find the best expansion points. Second, constraining guidelines not only ensure the smoothness of the surface and limit the growth of narrow tri Angels, but also have a good result. Third, the algorithm can make a good 3D reconstruction model without normal point cloud. Therefore, the algorithm, which can deal with large-scale cloud points without normal, can quickly and accurately to build a high-quality surface meshes.