Research For Spatial Scattered Point Based On Delaunay Triangulation Algorithm

3D reconstruction has always been the popular problem of Computer Vision, Computer Graphics, Virtual Reality and other disciplines. Triangulation of spatial scattered point is an important link of technical route of3D reconstruction, and a key technology which is widely used in Reverse Engineering. The group of spatial scattered point sets from3D scanner need to be recovered to the three-dimensional morphology of the measured object by triangulation, and then, we can reproduce a realistic3D model after textures. Compared with other triangulation methods, Delaunay triangulation has good mathematical characteristics and its3D mesh subdivision is uniform which make it an optimal triangulation and widely used.The main research contents of space scattered point is directly Delaunay triangulations algorithm, on detailed analysis of conventional incremental insertion algorithm after,According to the key links s proposed for optimized and improved method. The first, spatial scattered point set has been pre-processing and optimization, using the method of K neighborhood create index for spatial scattered point in order to make the scattered point set ordering,accordingly improve positioning efficiency of the point in the triangle network. Second, using Watson technology in tetrahedral remodeling process, so as to dentify if the boundary has been optimized. About the optimized boundary, the paper using Flip local transformation technology. The technology to reduce the optimization process of redundancy operation, improve the tetrahedron optimization speed, has the very high convergence.The algorithm analysis and experimental results show that this method which containment the integrity of triangulation on condition that greatly improves construction efficiency of the Delaunay triangulation.