A New Method Of Surface Mesh Reconstruction From Unorganized Points

In this paper we present a new method of meshing scheme for the points set which are gotten from the 3D digital camera. .This method combine the virtue which present in 2D and 3D method,according to the Delauney triangulation,realizing the high efficient and precise disposition through allude the points set from 3D to 2D.The final mesh generated by our meshing scheme approximates the original mesh well,and every triangle of the final mesh approximates equilateral triangle .The problem of triangulation is a key problem in CG/CAD (computer graphics/computer aided design).The quality of triangulation effect directly the precision of science calculation and engineering-oriented analysis.It is the study hot spot for many years and unsolved until now.The triangulation for the random large unorganized points is the outstanding problem.We present the definition of parametric plane, Least-square plane and the reconstruction of surface for large unorganized points.The definition of surface mesh reconstruction from unorganized points(unorganized point cloud) is given a set of unorganized pointsX, which located on an unknown surfaceU,request a triangle mesh can approach the original surface U.Parameterization: The problem of a triangle mesh parameterization can be stated as follow: given arbitrarily a set of points P_i∈(?)³ and the parameter domain of 2-dimension manifoldsΩ_P , to find the one-to-one mapφmapping points P_i^*∈Ω_P in parameter domain to P_i∈Ω, such that the mesh in parameter domain and original mesh topological harmony, and assurance the triangles cannot lap over in the parameter domain, seek a certain with several generous characters of of the original mesh transform a minimum. From mathematics, The function that satisfies this kind of parametcriztion turn usefulness. Least squares plane: using the least squares fitting method to fit all 3D point cloud to a plane. The methods of least squares have the formula as follow:where,ρ_i > 0,Σ_iρ_i = 1.From the standpoint of approach theories, that is the problem of the best square approach in discrete set {xⁱ}_i=1^N.From the geometry, it means to construct a curve(or a curved surface),make it reflect the variety regulation of the data. This is called curve(curved surface) approach.In the second chapter, we introduce the fundamental knowledge of triangulation. i.e.the definition of Voronoi diagram and D-triangle, given as follow:Supposed = v₁, u2,…u_n, N≥3 is a point set in the plane of Euclidean, these points are not co-line,and not co-circle for any four points. Let d(u_i, u_j) denote u_i, u_j the distance in Euclidean, and let x a point on the plane, such that the region V(i) = {x∈E² d(x,x_i)≤d(x,v_j),j = 1,2,... ,N,j≠i} is called V oronoi polygon (V-polygon). the V-polygon of every points compose the V-diagram.The definition of D-triangulation: the V-polygons which have common edges call the neighbour V-polygon Conjunction all closed V-polygon together growth from the center become of the triangle mesh be called D-triangulation.For a set Y(?)(?)³ and a point x∈(?)³, let d(x,y) denote the Euclidean distance of x from Y; that isThe set is a ball with radius r and center c. This paper introduced some basic algorithms in dimension triangulation in chapter 3. All of these algorithms depend on the D-triangulation discretion standard, became quality a better mesh. Among three kinds of algorithms, past two more for spread, the method of partition-merge take up less time, but take up more memory space, the method of insert one knot one step take up more time, but less memory space .In the chapter 4, we introduce two important methods of triangulation in 3D space: the method of project to plane, use this method we can transform the problem of 3D to 2D, Handle some point cloud on the plane, thus can make use of to the maturity methods of two to do triangulation;Another method is a directly triangulation method. Direct method usually has two type, one is the vertex of triangulation T is the points set P which is given, don't change the topology of the original points set, which the essence is linear insertion of P; the other type is to use triangulation within the scope of certain error margin for cent T to approach surface, The quantity and the position of vertex T are all differs from the original points set.In the direct triangulation method, the Choi raise a better method called increased method in 1988,which had an extensive application. Moreover another kind of method can handle the large data, also the better speed and quality, is the ball-pivoting algorithm, this algorithm is very efficient on the problem of both time and memory, it is not write all data into a memory at the same time, it complete gradually in performance process. This paper combines the advantage of above algorithms, given an efficiently algorithm of the triangulation method, this method can handle large data , and can get better result.This algorithms is firstly to transform 3D point cloud to 2D parameter plane,and handle the data, in 2D domain. It include a few steps as follows:Part of pro-process: first depart 2D plane as several pieces, the radius of each piece basis on the data. ,in the triangulation process, the radius of each piece enlarges gradually to carry out a mesh of the layering conjunction.Triangulation: It conclude two parts, seed selection and expand the triangle.layering conjunction:The sampling points are very uniform.after the first layering conjunction triangulation in the case of small radius of each piece,because of the limitation of the radius,there are some points which are not connected in original point set.we need enlarge the radius for forming the mesh.After that,projecting the mesh from 2D to 3D,the triangulation in 3D come true.Because of the disposition of points in 2D,the radius of each piece enlarges gradually in triangulation,carrying out a mesh of the layering conjunction.It can improve the speed of triangulation greatly,in another case, it can ensure the quality of mesh well,Our method have the advantage of speed and the good quality of mesh at the dealing with large point set through contrast.