The Simplification Of Scattered Point Cloud And Triangular Mesh Surface Reconstruction

Reverse Engineering can be simply defined as"understanding original design intention and mechanism", including many aspects such as shape, material, technology and so on. At present, the investigation and application of RE are mostly for the geometrical shape of model of object. In RE, we call the data that can be got by scanning object in 3D space point cloud data. Point cloud data include scattered point cloud, scanning beam point cloud, Grid-Based point cloud and polygonal point cloud.With the development of coordinate metrical device, people can get millions of points or even more. But there are lots of data and we need to measure more complicated models, so it is a challenge for RE. Also the simplification of point cloud becomes the investigative hotspot for people. Surface reconstruction process is one of the pivotal technologies, and triangular mesh model has more important application value in the expression of the surface of geometry model. The goal of mesh reconstruction of point cloud is finding some kind of mathematic expression form, and constructing a triangular mesh model with vertex and topological relation, for which we can analyze, optimize, modify and draw mesh. So it is further convenient for parameterization and constructing surface. For scattered point cloud, it is very important to get optimum triangular mesh model.In RE, if you want to reconstruct the surface of object, first, you must get scattered points and triangulate, and then do surface approximation based on triangular mesh that have constructed. The redesigning of the reconstructed surface can be achieved by the distortion of triangular mesh or other operations. In the input data for multi-resolution display of rapid prototyping system and virtual reality system, the format of triangular mesh is also applied widely. Thus, triangular mesh are not only the basis of reconstruction of practical prototype, but also acting on the whole process of RE.This paper researches the scattered point cloud with no organization and no orderliness. How to simplify scattered point cloud and reconstruct the model of triangular mesh surface of the original measured object from the simplified scattered point cloud are the hotspot for people to research in recent years.This paper uses K-nearest neighbors to create the topological relation of the scattered point cloud in 3D space. There are lots of methods to create K-nearest neighbors, and many papers have widely discussed how to create K-nearest neighbors .But the most familiar methods are Octree, spatial cells and KD-Tree. KD-Tree usually can be used to seek for the two points whose distance is the shortest, and it is a data structure to be convenient for searching in space. KD-Tree is a kind of data structure that is very characteristic. Each node on the KD-Tree represents a rectangle area, and each node corresponds to a partition on coordinate axis, and the partition line that the node corresponding to corresponds to the depth. KD-Tree also has the characteristic that its nodes distribute equably, so the efficiency of searching is rather rapid. Thus, we use KD-Tree to create K-nearest neighbors.There are many simplification methods for point cloud, such as clustering, the simplification method based on average distance and so on. According to the former methods that people have presented, this paper presents a kind of simplification method of scattered point cloud based on the density of the points in K-nearest neighbors. We use the simplification method based on average point to simplify the point cloud where the density of the point is big. And we use the method based on average distance where the density of the point is small. By later experiment, it is testified that the method which this paper presents is not only simply and high efficiency but also well whether on the smoothness of the object or on the part of the object where the curvature varies greatly.This paper researches and analyzes several arithmetic of reconstruction of triangular mesh surface of plane and 3D scattered points. Typically is the triangulation arithmetic based on Delaunay. The method of Delaunay has better theoretic basis of mathematics, and the triangles got by Delaunay method is the optimum. Though Delaunay method can be used in plane and also in space, yet in the triangulation in 3D space there are some shortcomings for Delaunay method. Delaunay method can only partition the point cloud into a convex hull. The scattered point cloud have no organization and no orderliness, so the Delaunay method can not solve all the problems in actual. At the same time, it is very difficult to compute Delaunay triangle, and it needs larger spending of memory and longer time, especially for large amount of points. This paper also introduces incremental extensible method, Incremental extensible method is based on region-growth theory, and it can deal with large amount of point cloud data and can directly deal with the closed-curve convex surfaces and open surfaces. However, this method usually needs people to partition the point cloud into areas, so it is uncertain, and also reduces automatic degree. It can do nothing when there is noise. In the mean time, this paper introduces the method of optimization for mesh model. According to the result of adjusted triangular mesh model, we classify the method of optimization and adjusting for triangular meshes model as: the method of optimization and adjusting of keeping topology fixedness, the method of optimization and adjusting of permitting part of topology change, and the method of optimization and adjusting of no topology limit.This paper analyzes and researches previous triangulation method, and presents a kind of triangulation method that directly triangulate the scattered point cloud in 3D space. In this method we apply the box technology. At the same time, we introduce some optimistic methods for triangular mesh. Experiments show that the triangular method are not only simply but also can do well in surface reconstruction. Our method is for the scattered point in space, and it means to create optimistic triangular mesh quickly, and then prepares for constructing NURBS. Thus, the method of triangulation is very helpful in the process of surface reconstruction in RE.In this paper, experiments show that the simplification method of scattered point cloud based on the density of the points in K-nearest neighbors combines with the method of triangulation are very helpful. Using them to deal with scattered point cloud in 3D space is simply and efficient. The method not only ensures the integral quality of the mesh after triangulation but also the details.