The Research Of Theory And Method Of Triangular Mesh Surface Reconstruction And Intersection

The theory and method of triangular mesh surface reconstruction and intersection are studied in-deeply and systematically. The mesh reconstruction method which is based on mesh boundary expanding combined with local triangulation is realized. Based on dynamic spatial indexing method, an efficient triangular mesh surface intersection algorithm is proposed which has significance for the development efficiency of product. The main research and achievements are as follows:1) Based on k-means algorithm the four-dimensional clustering algorithm which is fit for all types of three dimensional objects clustering is proposed, and the theory of building R*S-tree is proposed. The dynamic spatial indexing mechanism for spatial data object such as scattered cloud points is built, and the query of sample point topology neighbor data is realized based on the mechanism. The advantages of the R*S-tree dynamic spatial indexing such as flexibility of complex data type, efficient space query and the high utilization rate of storage space are proved;2) A triangular mesh surface reconstruction algorithm which is based on the dynamic spatial indexing method of scattered cloud points is proposed. To rapidly obtain a reconstructed mesh model with the same topology as product shapes, the mesh construction with the same topology as the local shape through Delaunay triangulation of neighbor points. And the triangular mesh reconstruction is completed by expanding, splitting and self cut out operation of mesh boundary. Experiments improve that the algorithm can guarantee the quality of reconstructed mesh and all detailed features are effectively reconstructed.3) An efficient triangular mesh surface intersection algorithm is proposed, which is based on the dynamic spatial indexing method of triangulated surface. The intersecting triangular facets are rapidly obtained according to the bounding box intersecting detection of nodes for every level of indexing structure. And an improved triangular facet intersection algorithm is adopted to get scattered intersection segments of intersecting curves. A tracing algorithm for picking-up intersection curves is also proposed, which is based on the dynamic spatial indexing structure of scattered intersecting segments. And the process of triangular mesh surface intersection which can establish the groundwork for geometric operation is realized. The adaptivity of complex mesh surface intersection is proved by experiment, and it is also improved that the algorithm can effectively improve the efficiency of triangular mesh intersection.