Method for establishing space index structure of product STL model

Abstract

The invention provides an establishing method of a product STL model spatial index structure, which is characterized in that a product STL model data file is read first, an axial bounding box of each triangular facet is established, corresponding data node of the triangular facet is established according to the center of the axial bounding box and the radius of a circumsphere and stored in a datanode sequence, each data node in the sequence is inserted in the index structure through steps such as insertion position selection, node splitting, node axial bounding box adjustment and the like, and the data node with larger volume of the axial bounding box is reinserted in the index structure to further optimize the index structure and achieve the establishment of the product STL model spatial index structure. The establishing method can establish spatial index structures of various triangular grids with complex profiles, and has the characteristics of strong stability and high query efficiency.

Description

technical field [0001] The invention provides a method for establishing a spatial index structure of a product STL model, which belongs to the technical field of product reverse engineering. Background technique [0002] In product reverse engineering, equipment such as laser scanners is usually used to obtain scattered point cloud data on the surface of the solid model, and the data is triangulated to generate a product STL model, which is close to the original solid model. The product STL model is composed of some discrete triangular patches. At present, the neighbor relationship between the triangular patches is mainly organized by establishing adjacency relationship tables, spatial octrees, R*-trees, etc., and a stable and efficient index is established for the product STL model. The structure is of great significance for improving the simplification and subdivision of the product STL model, the intersection of the product STL model and the generation of the NC machining...

AI Technical Summary

Problems solved by technology

[0003] In the existing technical literature, there is no method for establishing the spatial index structure of the product STL model. In the method for establishing the spatial index structure of the triangular grid, Wang Lei et al. published in the academic journal "Computer Application Research" (2004, 9, P95-97) In the paper "Ordered Adjacency Vertex Table Data Structure for Subdivision Surfaces" published on 2010, according to the vertex information and edge information of each triangle face in the triangular mesh model, an adjacency table is established for each triangle face, which stores the Triangular patches are topologically adjacent to the triangular patches. This method can accurately obtain the neighbor relationship of each triangular patch in the triangular mesh model. However, from the construction process of the adjacency relationship table, its indexing efficiency depends on the construction of the adjacency relationship table. The insertion sequence of triangle faces, and the adjacency relationship table is a static index structure. When inserting and deleting triangle faces, it is necessary to traverse the entire adjacency relationship table to reorganize the adjacency relationship between triangle faces, and the algorithm operation efficiency is low. High system resource consumption

Zhou Hai used the spatial octree as the spatial index structure of the triangular mesh model in his doctoral dissertation "Research on Subdivision Surface Modeling Technology" (Nanjing University of Aeronautics and Astronautics, 2005). The facets are inserted into the spatial octree, the index structure of the triangular mesh model is established, and the neighbor relationship between the triangular faces is organized. This method uses the center of the bounding box of the triangular facets to represent the triangular facets, which cannot accurately reflect the location and location of the triangular facets. The size of the occupied space area and poor accuracy reduce the quality of the index structure and the efficiency of spatial query based on the structure

Wang Zhanli used a large bounding box to enclose the triangular mesh model in his doctoral dissertation "Research on Simulation Technology of NC Machining Oriented to Virtual Manufacturing" (Jilin University, 2007). The patch is divided into two parts, each part is surrounded by a bounding box, and each bounding box is divided recursively until a bounding box only contains one triangle patch, and an unbalanced binary tree index structure of the triangular mesh model is established. The structure improves the spatial query efficiency of the triangular mesh model, but because the structure is an unbalanced binary tree, it is only suitable for the triangular mesh model with a relatively uniform distribution. When the distribution of the triangular mesh model is uneven, the tree is prone to Too many layers of a certain branch lead to a sharp deterioration of the data structure, seriously affecting the efficiency of spatial query based on this structure

[0004] To sum up, the current triangular grid spatial index structure has problems such as low construction efficiency and high system resource consumption. Therefore, establishing a stable and efficient index structure for product STL model data has become a technical problem to be solved urgently by those skilled in the art

Images