Construction And Application Of The Dynamic Spatial Index Of The Mesh Surface

In the field of reverse engineering, the introduction of dynamic spatial index R*-tree has effectively improved the efficiency and quality of the data processing in various aspects of the reverse engineering. The merits and defects of the index structure directly affect the efficiency and accuracy of the modeling. Through the deep study of the dynamic spatial index and it’s implementations in mesh processing, an algorithm of constructing the dynamic spatial index based on the improved R*-tree(R*S-tree) and the half-edge data structure was proposed. And based on the dynamic spatial index of mesh surface the algorithm created, the simplification, intersection and Boolean operation of the triangular mesh were realized. The main research contents and results are as follows:1) An algorithm of constructing a dynamic spatial index of mesh surface was proposed, which chose the half-edge data structure as the underlying data structure of the mesh surface and organized the vertices, edges, faces of the mesh surface by transforming the original mesh surface model into the form of half-edge data structure. Through the transforming process, facets of the mesh surface were inserted into the R*S-tree, which accomplished the construction of the dynamic spatial index when the relation between the half-edge data structure and the R*S-tree was established and finally obtained the integrated dynamic spatial index of mesh surface. Using this dynamic spatial index, the queries of topological information of a mesh unit can be processed and the mesh models presented by STL files were tested. The experimental results show that this algorithm has high efficiency of constructing the dynamic spatial index and the index it constructed can query the neighborhood of a mesh unit in the constant time.2) A simplification algorithm of triangular mesh was put forward, which can quickly get the topological neighborhood of the triangular facets based on the integrated dynamic spatial index of the mesh surface. This algorithm can obtain the information of curvature distribution of the triangular mesh by calculating the angle between the normal vectors of the adjacent facets, which was regarded as the basis for clustering the triangular facets, and clustered the neighborhood of the triangular facets. Then each clustered triangular facets were simplified through a vertex clustering simplification algorithm and the shape of each triangular facet was effectively controlled, finishing the simplification process and maintaining the surface features of the triangular mesh. The results show that this algorithm has a high simplification efficiency and great ability to maintain the surface features.3) The existing simplification and Boolean operation algorithms of triangular mesh were improved. The dynamic spatial index construction algorithm of mesh surface proposed above was applied into the process of the intersection and Boolean operations of the triangular mesh. Through the intersection test with the R*S-tree, the intersection area was quickly obtained. Then the query range of the spatial neighboring bounding boxes was narrowed by using the extended hollow ball algorithm. After the bounding boxes were sorted, the lines were calculated and connected to get the cross. Then the integrated dynamic spatial index of the triangulated triangular mesh was constructed, based on which the rapid segmentation of the triangular mesh was achieved, improving the efficiency of Boolean operations.