Scattered Data Triangulation In Surface Reconstruction Of Reverse Engineering

In reverse engineering, triangle net is not only the base of real objects surface reconstruction, but also plays an important role throughout the all stages of reverse engineering. Research on the techniques relative with triangle net construction and application has significance to the development of reverse engineering.This thesis aims at researching 3D scattered data triangulation algorithm. Based on the existed research achievements, taking advantage of some good ideas of plane triangulation, a direct space partition strategy is put forward, which is referred to dynamic circle algorithm and boundary loop merging and splitting. The algorithm starts at a random point, searching two nearest points, to initialize a triangle whose three edges are set as boundary edges. From these boundary edges, it searches the points that can construct triangles with them satisfying optimization rule to form the triangle net. Finally, it deals with the boundary loop according to the characteristic of all surfaces. The algorithm have great adaptability. It solves the problem that data points must be partitioned for multi-projection realized by traditional 2D triangulation methods, and can also manipulate the scattered data points of trimmed surface and concave boundary surface. What' s more, it builds the topology of points and triangulates them at the same time when it is searching the points, which effectively reduces the time complexity and improves the efficiency of algorithm.Furthermore, The concept of triangle net integrated optimization is introduced and the relevant algorithm is realized. Applying the algorithm, the triangle shape and the mesh are optimized with limited times of iterations.