Study On Algorithm For Mesh Surface Reconstruction From Point-Cloud Data

Study on Algorithm for Mesh Surface ReconstructionAlong with the rapid development and popularization of the computer and laser measuring technology,the computer-aided design and manufac-turing technology is developing rapidly, and thus promoted application and development of the reverse engineering technology. At present, the re-verse geometr is a research focus on the reverse engineering, namely, the complex three-dimensional surface data points are collected accurately and efficiently from physical or samples, and then CAD models are obtained quickly. The way of reverse thinking that products are rapidly design, up-date and recovery from the existing information has been widely applied to industry, construction, archeology, medicine and many other subject areas. The one of the most important and most difficult the issues in the reverse engineering is surface reconstruction techniques based on three-dimensional surface point cloud data,and it has been an attractive subject. Its purpose is to find a form of mathematical description to describe an existing phys-ical surface accurately and simply, simplicity description of, and based on it to analyse, calculate, modify and draw the surface itself.At present, Surface reconstruction method Based on three-dimensional point-cloud data,according to the form of reconstruction, the methods can be divided into surface fitting, piecewise linear reconstruc-tion (triangular mesh reconstruction), the reconstruction based on physi- cal deformation and the reconstruction based on neural networks and so on. In this paper.we mainly studies surface reconstruction algorithm from three-dimensional point-cloud data, and repair algorithm of holes in the triangular mesh. The text is divided into five parts.The first part, we detailed described development history and key technologies of reverse engineering,and carefully summarized and analysed the main problems involved in key technologies and research results. The second part,we mainly introduced triangulation algorithm and its development history.We analysed and compared Some typical triangulation algorithms on the two-dimensional plane and three-dimensional space, respectively.In third part.we summarized the mesh denoising algorithm and mainly introduced the development process of Laplace algorithm. We done an analysis and comparison for some algorithms from theory to concrete implementation.The fourth and fifth part were the main results we obtained and were the main parts of the text. In the fourth section, we presented a region-growing algorithm for triangular mesh surface reconstruction from point-cloud data.In the algorithm, we reduced point-cloud data through the application of cube and spherical way, so that points are more evenly distributed. In the triangulation process, we used a series of constraint conditions.such as the smallest angle, the biggest dihedral angle and the biggest edge length and so on, so that triangles were as full as possible, triangular mesh surface were as smooth as possible. This avoids generating overlapping facets, self-intersection and wrong topologyIn fifth section,we presented a filling holes algorithm in triangle mesh In the algorithm,the first,we triangulated polygon holes through using the principle of the smallest interior angle and getted a set of new tri-angles. Then.we subdivided the set of new triangles based on the density of the boundary vertices and optimization principles of the distance and round.The final, we usedλ-μmethods to optimize initiai patching mesh and a final patch mesh was obtained.Now we come to describe the main results of the fourth and fifth part,respectively.In the region growing algorithm,1. we reduce point-cloud data in-putted into cmputer:(1)We calculate the average density of the point-cloud, denoted by l, and be used as the reference value of data reduction. (2) First, we reduce the point-cloud data through using uniform grid method, and record the adjacent relationship between grid; (3) Second, we take out the first point in the list, delete points their distance be-tween with the first point is less thanαl and behind the first point.We do same operation for the next point in the list of points until the end of the list. In the step, computing speed is improved and travelling entire list is avoided through the applicatoin of the adjacent relationship between-the grid recorded in first step.The point-cloud date reduced is more evenly distributed through using the method.2. Triangulation of point-cloud re-duced:(1) Construct seed triangle, we remove first point in the list of the points, denoted by firstpoint, remove point that is the nearest point between with firstpoint and is behind firstpoint, denoted by secondpoint. The two points constitute an edge. We selected a point that is not second-point and behind the firstpoint,this point must satisfy the sum of distance to be the minimum with the firstpoint and the secondpoint, denoted by thirdpoint.If the smallest angles of the triangle is less thanπ/6, then we sc-lected next point behind firstpoint to replace firstpoint and to recalculate, otherwise the end. (2) We take out a side been known as activities edge as the current side.For this current side, we selected the best matching point to constitute a new triangle with the current side. In order to select the best matching points, we first selected the candidate points, through apply-ing constraints such as the minimum angles, the minimum dihedral angle ane the maximum edge length and so on.The minimum angles restrain is that the minimum angles of new triangle must meet no less than 30°and 10°, respectively, according to the type of candidate points. The minimum dihedral angle restrain is that dihedral angle of two triangles with a com-mon edge must meet no less than 5π/7 andπ/2, respectively, according to the type of candidate points. The maximum edge length restrain is that the longest side of a new triangle must meet no more than three times of radius reduced point-cloud. Through using these restrain condition.we avoided generating overlapping facets and wrong topology. In accordance with the problem of the advancing front broken, the overlapping edge of the opposite direction is used. This ensures to have only one bound-ary of advancing front throughout. Experimental results show that the algorithm have many advantages, such as high efficiency and accuracyIn fifth part of filling holes algorithm in triangle mesh, we first obtained initial patching mesh of simple polygon according to density of vertex on boundary edges through applying optimization principle of the smallest inner angle,the circle and the largest angle,then we getted final patching mesh through usingλ-μmethods to optimize initiai patching mesh.In practice.1. The boundary edge of hole, the boundary vertexes of hole and the boundary triangles of hole were extract.Because we made use of triangulation algorithm for point-clouds in chapter 3, the boundary edge of hole can only be the death side in the list of boundary edge. It provided us with a convenient conditions to extract the boundary edge.2. We calculated inner angles of space polygon that been composed of boundary edge, first we distinguish between the convex and concave angles, then calculated the size of angles and arrange sequence them from small to large.We calculate the vertex density for each hole boundary points.3. we getted a set of new triangle that been composed of boundary vertexes through triangulating the hole polygon according to principle of the small-est inner angle.4. We getted initial patch mesh through increasing points to subdivision set of new triangle and applying optimization principle of the circle and the largest angle according to density of vertex. In order to avoid the generation of parallel triangle,we used constrained condition of the largest inner angle such that triangles in initiai patching mesh are more plump.5. Final we usedλ-μmethods to optimize further initiai patching mesh such that the final patch mesh is smoothing connections with the original mesh.We have a brief summary for full text at the end of paper.and put forward specific ideas for further work.