Research On The Reconstruction Algorithm Of 3D Constrained Delaunay Triangular Mesh Based On Local Dimension Reduction Principle

Aiming at the problem that the 2D Delaunay reconstruction algorithm is difficult to realize automatic reconstruction of the true three-dimensional surface from unorganized points, this paper focuses on the reconstruction algorithm of 3D constrained triangular mesh based on local dimension reduction principle. The main contributions are as follows:(1) A method for extracting and matching line segments based on epipolar line constraint is designed and implemented. The features of the line endpoint is used as line’s descriptor, and fundamental matrix is computed by feature points extraction and matching, then the fundamental matrix is used as the epipolar line constraint, which reduces the false matching ratio. The matched lines provide linear constraint data for constrained triangulation based on local dimension reduction.(2) A reconstruction algorithm of 3D triangular mesh based on local dimension reduction principle is implemented. Firstly, filter the point cloud, secondly, search topology neighbor points, then estimate tangent plane, and at last, connect triangular network. An acquisition algorithm for topological neighbors is proposed by statistic of information of each point’s neighbors and removing the outliers, which ensures the triangulation connects real neighbor points. The experiments show that the triangular mesh is in good shape and reduce the narrow triangles.(3) A reconstruction algorithm of 3D constrained triangular mesh based on local dimension reduction principle is proposed. The efficiency of the search of constraint line’s affected area is improved by using a line’s k-nearest neighbor search algorithm based on Kd-tree. And the constrained Delaunay triangulation of impact region is completed by using divide and conquer algorithm based on the local dimension reduction. Experiments show that the algorithm improves the accuracy of the surface triangulation.