CN102831241A - Dynamic index multi-target self-adaptive construction method for product reverse engineering data - Google Patents

Abstract

The present invention provides a method for constructing multi-target self-adaptive dynamic indexes of product reverse engineering data, which is characterized in that: firstly, the product reverse engineering data file is read, and the axial bounding boxes of each space object are established, and the center and circumscribed points of the axial bounding boxes are used to The radius of the ball establishes the data nodes corresponding to each spatial object and stores them in the data node sequence. Insert each data node in the sequence by selecting the insertion position, forcing reinsertion, node splitting, and adjusting the axial bounding box of the node. Into the index structure, re-insert the data nodes with larger axial bounding boxes into the index structure, further optimize the index structure, and realize the establishment of a dynamic index structure for product reverse engineering data. The invention can establish the spatial index structure of reverse engineering data of various complex products, and has the characteristics of low parameter dependence, strong stability and high query efficiency.

Description

Multi-objective self-adaptive construction method of product reverse engineering data dynamic index

technical field

The invention provides a multi-object self-adaptive construction method for product reverse engineering data dynamic index, which belongs to the technical field of product reverse engineering.

Background technique

In the field of product reverse engineering technology, the raw data processed are usually data formats such as scattered point clouds and polygonal mesh models obtained by sampling the surface of the physical object. Surface reconstruction based on such raw data to generate piecewise continuous surfaces is a product reverse engineering. core technology. Since data formats such as scattered point clouds, polygonal meshes, and sliced continuous surfaces all represent complex structures of large-scale or even massive spatial geometric objects, building a general and efficient indexing technology for these data types is crucial for improving product reverse engineering data. Processing efficiency is of great importance.

A search of existing literature reveals that the indexing technology for existing product reverse engineering data is usually only applicable to a certain type of data. In the processing of scattered point clouds, spatial octree and K-D tree are the most widely used static index and dynamic index respectively. 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 surround the triangular mesh model in his doctoral dissertation "Research on Simulation Technology of NC Machining Oriented to Virtual Manufacturing" (Jilin University, 2007), and used the bounding box as the root index node, and then the triangle mesh model 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 and seriously reduce the efficiency of index query. Sun Dianzhu and others improved the R*-tree in their academic paper "R*-tree node splitting algorithm based on four-dimensional clustering" (Journal of Mechanical Engineering, 2009, 45 (10): 180-184), making it It can uniformly index data types such as scattered point clouds and polygonal grids, and then the improved R* -The tree is used as the index structure of the sliced continuous surface to improve the query efficiency of intersecting triangular Bézier surface slices, but since the improved R-tree uses the k-means clustering algorithm in the process of splitting the index nodes, the user needs to interact to set the clustering The number of clusters and the number of clusters will lead to very different index node split results, resulting in unstable index structure and performance. In addition, the k-means clustering algorithm is a local search algorithm that is too sensitive to the initial value. The hill-climbing method iteratively searches for the optimal index node splitting result, which is easy to fall into the local extremum, and it is difficult to obtain the globally optimal index node splitting result, which leads to the failure to give full play to the advantages of the R*-tree.

To sum up, the current dynamic index structure of product reverse engineering data has a certain degree of versatility, and can handle various types of composite structures of spatial geometric objects based on a unified index mechanism, but there are still poor data adaptability, Due to problems such as low indexing performance and high system resource consumption, building a stable and efficient indexing mechanism for product reverse engineering data has become an urgent technical problem to be solved by those skilled in the art.

Contents of the invention

In order to overcome the deficiencies in the index mechanism of existing product reverse engineering data, the purpose of the present invention is to provide a dynamic index multi-objective self-adaptive construction method for product reverse engineering data, so that it can index various types of reverse engineering data, and has strong stability , The characteristics of high data query efficiency, the technical solution is as follows:

A kind of product reverse engineering data dynamic index multi-target self-adaptive construction method, it is characterized in that comprising the following steps: 1, read product reverse engineering data, establish the axial bounding box of each space object, according to the center of axial bounding box and circumscribed The radius of the ball establishes its corresponding data node and stores it in the data node sequence; 2. Insert the data node into the index structure. The specific steps for inserting the node into the index structure are: 1) Select the insertion position for the node; 2) Insert the node into the position obtained in step 1); 3) Insert the node under the node node, and judge whether the number of child nodes of the node node is greater than the maximum number of child nodes of the node, and if it is greater than the maximum number of child nodes of the node. The point node performs overflow processing. If the node node is a non-root index node and the layer where the node is located is overflow processing for the first time during the process of inserting a spatial object, then a part of nodes is selectively taken out from the node node. Reinsert them into the layer of the index structure, otherwise split the node; 4) Adjust the axial bounding box of each node; 3. Reinsert the oversized axial bounding box into the index structure to realize the index structure 4. Based on the dynamic index structure of product reverse engineering data, realize the topological nearest neighbor query of scattered point cloud, polygonal grid and sliced continuous surface.

In order to achieve the purpose of the invention, the multi-objective self-adaptive construction method of the dynamic index of product reverse engineering data, in step 1, read the reverse engineering data file, if the spatial object is a scattered point, then take this point as the center to establish the side length as the unit 1 and each edge is parallel to the axial bounding box of the coordinate axis. If the spatial object is a polygonal mesh, then establish an axial bounding box that just surrounds the vertices of the mesh. For the axial bounding box of the vertices, establish the data nodes corresponding to each spatial object and store them in the data node sequence. The data nodes include the information of the spatial object and the corresponding axial bounding box information.

为结点的最大子结点数(

为大于2的整数)、

为结点最小子结点数(

为小于或等于/2的整数)，除根索引结点外，每个索引结点的子结点数均小于等于

且大于等于

；索引结构中每个结点的轴向包围盒恰好包围该结点的所有子结点。 In order to achieve the purpose of the invention, the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index, in step 2, inserts the data node into the index structure, the method is: the node includes the index node and the data node, the index Nodes include root index nodes, internal index nodes and leaf index nodes. The topmost node of the index structure is the root index node, the bottommost node is the leaf index node, and the rest of the nodes are internal index nodes. definition

is the maximum number of child nodes of a node (

is an integer greater than 2),

is the minimum number of sub-nodes of the node (

is less than or equal to /2 integer), except for the root index node, the number of child nodes of each index node is less than or equal to

and greater than or equal to

; The axial bounding box of each node in the index structure exactly surrounds all child nodes of the node.

In order to achieve the purpose of the invention, the step of selecting the insertion position for the node in step 2 of the multi-objective self-adaptive construction method for the dynamic index of product reverse engineering data is as follows: 1) Let the current node be current_node, if the index structure is empty Return empty, otherwise let current_node be the root index node of the index structure; 2) Let the number of layers to be inserted by the node be level, if the node is a data node, then level is the leaf layer of the index structure, and the insertion of other types of nodes It is caused by forced re-insertion, and level is the number of layers before re-insertion; 3) Calculate the degree of overlap between each child node of current_node and the circumscribed ball of the axial bounding box of the node to be inserted, and select the one with the smallest degree of overlap as current_node; 4) Repeat step 2) until the level layer of the index structure.

、

轴向包围盒的外接球半径分别为

、

，轴向包围盒中心间的距离为

，两结点、

轴向包围盒的外接球重叠度的计算公式为

，以结点轴向包围盒外接球重叠度衡量两结点间的相似性大小，重叠度越大则结点间的相似性越大，否则越小。 In order to achieve the purpose of the invention, the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index, in step 2, inserts the node into the index structure, so that any two nodes

,

The circumscribed sphere radii of the axial bounding box are

,

, the distance between the centers of the axial bounding boxes is

, two nodes ,

The formula for calculating the overlapping degree of the circumscribed sphere of the axial bounding box is

, the similarity between two nodes is measured by the overlapping degree of the circumscribed ball of the axial bounding box of the node. The larger the overlapping degree is, the greater the similarity between nodes is, otherwise it is smaller.

In order to achieve the purpose of the invention, in the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index, in the step 3) of the second step, the step of selecting the re-insertion node is specifically: 1) the overflow node node sub-nodes, calculate the distance from the center of their axial bounding box to the center of the axial bounding box of node node; 2) take the distance value calculated in step 1) as the key word, for the child nodes of node node Sort in descending order, select the former child nodes.

，将分簇作为结点node的子结点，为分簇集合

分别新建结点，计算新结点的轴向包围盒，并将新节点

作为结点node的父结点的子结点插入到索引结构中。 In order to achieve the purpose of the invention, in the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index, in the step 3) of the second step, the step of splitting the node is specifically: 1) Binary the child nodes of the node node Code, 0 means non-clustering center, 1 means clustering center, and construct and initialize the population P(t) of specified size, t=1, calculate its objective function and fitness value; Dominate the solution set E(t); 3) Perform selection, crossover, and mutation operations on the population P(t) to obtain the next generation population P(t+1), let t=t+1; 4) Calculate the population P(t) 5) Calculate the non-dominated solution set of the population P(t), and then update the non-dominated solution set E(t); 6) If the cut-off evolution algebra is reached, go to step 7), otherwise Skip to step 3); 7) Decode the non-dominated solution set E(t), and then select the splitting scheme with the smallest sum of axial bounding box overlap and axial bounding box volume as the optimal split of node scheme; 8) Let the optimal splitting scheme of node node be

, will cluster As a child node of node node, it is a clustering set

Create new nodes separately , calculate the axial bounding box of the new node, and put the new node

The child nodes that are the parent nodes of the node node are inserted into the index structure.

，分簇的簇数k为个体编码中1的个数，计算类内聚

需先对个体解码，即从个体编码中提取出聚类中心，计算其他结点的轴向包围盒中心到聚类中心的距离，将其归到距其最近的聚类中心所代表的分簇，形成分簇集合

实现个体的解码，则类内聚的定义为

，其中k表示簇数，

为结点，

为分簇

的聚类中心；若不存在任何

使得公式

成立，且至少一个解是严格不等的，则认为解

为非支配解，其中表示所有的可行解，

表示各个目标函数，即簇数k与类内聚

，由所有非支配解构成非支配解集E(t)；如果可行解中的两个解

满足公式

和

则认为支配；适应值定义为

，其中

表示个体

的排序值，如果个体

为非支配解则其排序值为1，否则其排序值为支配该个体的的个体数目加一。 In order to achieve the purpose of the invention, in the multi-objective self-adaptive construction method of product reverse engineering data dynamic index, in the process of node splitting in step 3) of step 2, the objective function includes the number k of clusters and the intra-class get together

, the number of clusters k is the number of 1s in the individual code, and the calculation of class cohesion

The individual needs to be decoded first, that is, the cluster center is extracted from the individual code , calculate the distance from the center of the axial bounding box of other nodes to the cluster center, and classify it into the cluster represented by the nearest cluster center to form a cluster set

To achieve individual decoding, the class cohesion is defined as

, where k represents the number of clusters,

for the node,

for clustering

cluster center; if there is no

makes the formula

holds, and at least one solution is strictly unequal, the solution is considered

is a non-dominated solution, where represents all feasible solutions,

Represents each objective function, that is, the number of clusters k and the cohesion of the class

, constitutes a non-dominated solution set E(t) from all non-dominated solutions; if two solutions in the feasible solution

satisfy the formula

and

then think dominate ; The fitness value is defined as

,in

means individual

The sort value of , if the individual

If it is a non-dominated solution, its ranking value is 1; otherwise, its ranking value is the number of individuals dominating the individual plus one.

In order to achieve the purpose of the invention, in the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index, the steps of inserting nodes into the index structure and adjusting the axial bounding box of the nodes are: 1) inserting a new index structure into the index structure The parent node of the node is src_node; 2) Adjust the axial bounding box of the parent node src_node so that it just contains all the child nodes of the parent node src_node; 3) If the parent node src_node is the root index node, The program returns, otherwise continue to execute; 4) Let the parent node src_node be the parent node of the parent node src_node in step 1), and return to step 2).

， 

为用户设定的阈值，通常取3~5，则将其包含的数据结点添加到临时序列L中，并将其包含的数据结点从索引结构中删除；3)将序列L中的数据结点重新插入到索引结构中，实现索引结构的全局优化。 In order to achieve the purpose of the invention, the multi-objective self-adaptive construction method of the product reverse engineering data dynamic index optimizes the index structure in step 3, and the steps are specifically: 1) traverse the index structure, and calculate the leaf index node layer axially surrounded average box size ; 2) Traversing each leaf index node of the index structure, if the volume of the axial bounding box of the leaf index node is greater than

,

The threshold set for the user, usually 3~5, will add the data nodes contained in it to the temporary sequence L, and delete the data nodes contained in it from the index structure; 3) the data in the sequence L Nodes are reinserted into the index structure to achieve global optimization of the index structure.

表示在以结点N为根索引结点的索引结构中查询空间对象T的邻近对象集合，若结点N为数据结点且与外接球S相交，则返回其包含的空间对象集合，若结点N不是数据结点，则

，其中

表示结点N中与外接球S相交的子结点；3) 将当前结点N初始化为索引结构的根索引结点，则空间对象T的邻近对象集合为

。 In order to achieve the purpose of the invention, in the method for constructing a multi-objective self-adaptive multi-objective index of product reverse engineering data, in step 4, the specific steps of querying the adjacent objects of any spatial object are as follows: 1) Let the axial bounding box of the spatial object T The outside ball is S; 2) Order

Indicates querying the adjacent object set of spatial object T in the index structure with node N as the root index node. If node N is a data node and intersects with circumscribed ball S, return the set of spatial objects contained in it. If Point N is not a data node, then

,in

Indicates the child node intersecting the circumscribed ball S in node N; 3) Initialize the current node N as the root index node of the index structure, then the set of adjacent objects of the spatial object T is

.

Compared with the prior art, the present invention has the following four characteristics:

1) The similarity of spatial objects is measured according to the overlapping degree of the circumscribed ball of the axial bounding box of the node, which not only reflects the location of the spatial object but also reflects the size of the spatial area it occupies, which improves the aggregation of nodes in the spatial range and clusters The result is more reasonable;

2) Combining the genetic multi-objective optimization algorithm for node splitting to solve the optimal solution of node splitting, which reduces the parameter dependence of the node splitting process and improves the efficiency of establishing the spatial index structure of spatial objects;

3) Reinsert the data nodes contained in the oversized leaf index nodes into the index structure, avoiding the generation of singular nodes in the axial bounding box and improving the quality of the index structure;

4) The depth-first traversal method is used to quickly and accurately obtain the topological neighbors of the triangles, which can effectively narrow the query range and improve the query efficiency of the topological neighbors of the target triangle.

Description of drawings

Fig. 1 is the realization flow chart of the procedure for establishing the dynamic index structure of product reverse engineering data of the present invention;

Fig. 2 is a schematic diagram of a polygonal grid and its axial bounding box;

Fig. 3 is a schematic plan view of the index structure of the present invention;

Fig. 4 is a schematic tree structure diagram of the index structure of the present invention;

Fig. 5 is a new node insertion flow chart of the product reverse engineering data dynamic index structure of the present invention;

Fig. 6 is a flow chart of node splitting in the dynamic index structure of product reverse engineering data of the present invention;

Fig. 7 is the face polygon mesh model of the present invention;

8-11 are the axial bounding boxes of the nodes of each layer of the spatial index structure established by the present invention for the polygonal mesh model of the face.

Detailed ways

The present invention will be further described below in conjunction with accompanying drawing:

Fig. 1 is the flowchart of realization of the program for establishing the dynamic index structure of product reverse engineering data in the present invention, the program for establishing the dynamic index structure of product reverse engineering data includes program 1 for reading product reverse engineering data files, inserting data nodes into index structure program 2, optimizing Index structure program 3 and target spatial object neighbor object query program 4, wherein, read product reverse engineering data file program 1 read product reverse engineering data file, establish the axial bounding box of each spatial object, according to the center of the axial bounding box and the radius of the circumscribed ball to establish its corresponding data node and store it in the data node sequence; insert the data node into the index structure program 2 to read the data node sequence, select the node insertion position, and determine the number of child nodes of the node Whether it is greater than the maximum number of child nodes of the node, if it is greater than the node overflow processing, if the node is a non-root node and in the process of inserting a spatial object, the layer where the node is located performs overflow processing for the first time, then in the node Selectively take out a part of the nodes from the points, and reinsert them into the layer of the index structure, otherwise, split the nodes; change the nodes from the axial bounding box, along a branch of the index structure, from bottom to top Adjust the axial bounding box of each node; optimize the index structure program 3 delete the leaf index node whose axial bounding box is too large or too narrow, and reinsert the child nodes contained in it into the index structure to realize the index structure Optimization; target spatial object topology neighbor object query program 4 Depth-first traversal product reverse engineering data index structure, obtain data nodes intersecting with the circumscribed sphere of the axial bounding box of the target spatial object, and select the target spatial object from the contained spatial objects Topological neighbors.

Figure 2 is a collection of several polygon meshes. Define the minimum number of sub-nodes m=3 and the maximum number of sub-nodes M=8 of the nodes in the index structure. Figure 3 is a schematic diagram of the axial bounding box of the nodes in the spatial index structure established for the polygonal grid shown in Figure 2, Figure 4 It is a tree structure diagram of the index structure, node A is the root index node, B, C, D are the leaf index nodes, E, F, G, H, I, J, K, L, M, N, O , P, and Q are data nodes, and each data node contains a polygon grid.

Figure 5 shows the implementation flow chart of program 2 for inserting nodes into the index structure, calling program 1) to select the position where the node should be inserted, inserting the node into the position obtained by program 1), and judging the node Whether the number of child nodes of the parent node is greater than the maximum number of child nodes of the node, if it is larger, the node overflow processing will be performed, if the node is a non-root index node and the node is located in the first layer during the process of inserting a spatial object One-time overflow processing, then call the selection re-insert node program 2) Select several nodes from the nodes to re-insert into the index structure, otherwise call the node splitting program 3) For the parent of the newly inserted node Split the node, and call the program to adjust the axial bounding box of the node. The bounding box exactly surrounds the child nodes it contains.

与待插入结点

的的轴向包围盒中心间的距离为，采用公式

计算两结点的外接球重叠度，其中

、

分别为结点与的轴向包围盒外接球半径，选择重叠度最小的作为当前结点current_node；3）重复步骤2）直到当前结点current_node所在层为叶索引结点层。 Insert the node into the index structure program 2, and select the node insertion position. The specific steps of program 1) are: 1) If the current index structure is empty, return empty; otherwise, set the current node current_node as the root index node of the index structure point; 2) Calculate each child node of the current node current_node

with the node to be inserted

The distance between the centers of the axial bounding boxes of is , using the formula

Calculate the overlapping degree of circumscribed balls of two nodes, where

,

nodes respectively and The radius of the circumscribed ball of the axial bounding box of , select the one with the smallest degree of overlap as the current node current_node; 3) Repeat step 2) until the layer where the current node current_node is located is the leaf index node layer.

个子结点，计算它们的轴向包围盒的中心到结点node的轴向包围盒的中心的距离；2）以步骤1）中计算的距离值为关键字，对结点node的子结点进行降序排序，选出前

个子结点。 Insert the node into the index structure program 2, and choose to reinsert the node program 2) The specific steps are: 1) For the overflow node node

sub-nodes, calculate the distance from the center of their axial bounding box to the center of the axial bounding box of node node; 2) take the distance value calculated in step 1) as the key word, for the child nodes of node node Sort in descending order, select the former

child nodes.

的二进制串表示，每一位对应于一个结点，1表示聚类中心，0表示非聚类中心，随机地将个体中每一位置为0或1，实现个体初始化，然后分配并初始population_size个个体，完成种群的初始化；过程(2)中目标函数包括簇数k以及类内距

，统计个体中1的个数即为簇数k，计算类内距需先对个体解码，提取出个体中1所对应的结点，即分簇中心，然后计算其他结点到各分簇中心的距离，将其归为距离最近的分簇中心所表示的分簇，形成分簇集合，计算类内距

，其中k表示簇数，

为结点，为分簇

的聚类中心；过程(3)计算种群中个体的适应值，计算公式为

，其中

表示个体

的排序值，若个体与

，满足

和

且其中有一个公式是严格不等的，则个体

支配个体

，若没有任何个体能支配个体

，则个体

为非支配解，对种群中的非支配个体分配排序值1，其他个体的排序值等于支配该个体的个体数目加一；过程(4)构造Pareto解集合

，遍历每个个体，对于每个个体寻找是否有能支配该个体的个体存在，若不存在则将该个体加入集合

；过程(5)对Pareto解集合

的个体解码，从中选择轴向包围盒重叠度与轴向包围盒体积之和最小的分裂方案作为结点的最优分裂方案

，将分簇

作为结点的子结点，为分簇集合分别新建结点

，计算新结点的轴向包围盒，并将新节点

作为结点的父结点的子结点插入到索引结构中。 Insert the node into the index structure program 2, if the number of child nodes n of the node node is greater than the maximum number of child nodes M , then call the node splitting program 3) to split the node node, the specific process is shown in Figure 6 As shown, in the process (1), the individual adopts a length of

The binary string representation, each bit corresponds to a node, 1 represents the cluster center, 0 represents the non-cluster center, randomly set each position in the individual to 0 or 1, realize the individual initialization, and then allocate and initialize population_size Individual, to complete the initialization of the population; the objective function in process (2) includes the number of clusters k and the intraclass distance

, counting the number of 1 in the individual is the number of clusters k. To calculate the intra-class distance, you need to decode the individual first, and extract the node corresponding to 1 in the individual , that is, the clustering center, and then calculate the distance from other nodes to each clustering center, and classify it into the clustering represented by the nearest clustering center to form a clustering set , to calculate the inter-class distance

, where k represents the number of clusters,

for the node, for clustering

clustering center; process (3) calculates the fitness value of the individual in the population, and the calculation formula is

,in

means individual

The sort value of , if the individual and

,satisfy

and

and one of the formulas is strictly unequal, the individual

dominate individual

, if no individual can dominate the individual

, the individual

As a non-dominated solution, the non-dominated individuals in the population are assigned a ranking value of 1, and the ranking value of other individuals is equal to the number of individuals dominating the individual plus one; process (4) constructs a Pareto solution set

, traverse each individual, and for each individual, find whether there is an individual that can dominate the individual, and if not, add the individual to the set

; Process (5) sets Pareto solutions

The individual decoding of , from which the splitting scheme with the minimum sum of axial bounding box overlap and axial bounding box volume is selected as the optimal splitting scheme of the node

, will cluster

As a child node of a node, it is a clustering set Create new nodes separately

, calculate the axial bounding box of the new node, and put the new node

The child nodes that are the parent nodes of the node are inserted into the index structure.

；2）遍历索引结构各叶索引结点，若该叶索引结点轴向包围盒的体积大于

（为用户设定的阈值，通常取3-5），则将其从索引结构中删除，并将其包含的空间对象添加到临时序列L中；3）将序列L中的空间对象重新插入到索引结构中，实现索引结构的全局优化。 The steps of optimizing the index structure program 3 are specifically: 1) traverse the index structure, and calculate the average volume of the axial bounding box of the leaf index node layer

;2) Traversing each leaf index node of the index structure, if the volume of the leaf index node’s axial bounding box is greater than

( The threshold set by the user, usually 3-5), delete it from the index structure, and add the spatial objects it contains to the temporary sequence L; 3) Reinsert the spatial objects in the sequence L into the index In the structure, the global optimization of the index structure is realized.

Figure 7 is a polygonal mesh model of a human face. The surface features of this model are relatively complex, consisting of 47,765 polygonal meshes. The spatial index structure is established by using the present invention. The effect of the axial bounding box of each layer of nodes is shown in Figure 8-Figure 11 shown. Figure 8 is the axial bounding box of the root index node, Figure 9 is the axial bounding box of the internal index node, Figure 10 is the axial bounding box of the leaf index node, and Figure 11 is the axial bounding box of the data node , except for the root index node, the number of child nodes of each index node is in the range of 8 to 20, and each data node contains a polygonal grid.

表示在以结点N为根索引结点的索引结构中查询空间对象T的邻近对象集合，若结点N为数据结点且与外接球S相交，则返回其包含的空间对象集合，若结点N为内部结点，则

，其中表示结点N中与外接球S相交的子结点；3) 将当前结点N初始化为索引结构的根索引结点，则空间对象T的邻近对象集合为

。 The specific steps for querying the adjacent objects of any spatial object T are: 1) Solve the circumscribed sphere S of the axial bounding box of the spatial object T; 2) Define the function

Indicates querying the adjacent object set of spatial object T in the index structure with node N as the root index node. If node N is a data node and intersects with circumscribed ball S, return the set of spatial objects contained in it. If Point N is an internal node, then

,in Indicates the child node intersecting the circumscribed ball S in node N; 3) Initialize the current node N as the root index node of the index structure, then the set of adjacent objects of the spatial object T is

.

The construction method of the dynamic index structure of the reverse engineering data of other products is the same as above.

Claims (3)

1. A multi-objective self-adaptive construction method for dynamic indexing of product reverse engineering data, characterized in that it comprises the following steps: one, read product reverse engineering data, and set up the axial direction of each scattered point cloud, polygon grid and sliced continuous curved surface Bounding box, according to the center of the axial bounding box and the radius of the circumscribed ball, the data nodes corresponding to each spatial object are established and stored in the data node sequence, where the nodes include index nodes and data nodes, and the index nodes include the root index Nodes, internal index nodes, and leaf index nodes. The topmost node of the index structure is the root index node, the bottommost node is the leaf index node, and the rest of the nodes are internal index nodes. Define

is the maximum number of child nodes of a node, is the minimum number of sub-nodes of the node, where

is an integer greater than 2, is less than or equal to

Integer of /2, except the root index node, the number of child nodes of each index node is less than or equal to

and greater than or equal to

; The axial bounding box of each node in the index structure just surrounds all the child nodes of the node; 2. Insert the data node into the index structure, the steps are: 1) Select the insertion position for the node, specifically The steps are: (1) Let the current node be current_node, if the index structure is empty, return empty, otherwise let current_node be the root index node of the index structure; (2) Let the level to be inserted into the node be level, if the node If it is a data node, level is the leaf layer of the index structure. The insertion of other types of nodes is caused by forced re-insertion, and level is the number of layers before re-insertion; The overlapping degree of the circumscribed ball of the axial bounding box of the node, select the one with the smallest overlapping degree as the current_node, and the method of calculating the overlapping degree of the circumscribed ball of the axial bounding box of two nodes is: let any two nodes

,

The radii of the circumscribed sphere of the axial bounding box are

,

, the distance between the centers of the axial bounding boxes is , using the formula

Calculate the overlapping degree of circumscribed balls of the axial bounding boxes of two nodes; (4) repeat step (2) until the level layer of the index structure; 2) insert the node into the insertion position obtained in step 1); 3) make the node Insert the point under the node node, and judge whether the number of child nodes of the node node is greater than the maximum number of child nodes of the node , if it is greater than , overflow processing will be performed on the node node. If the node node is a non-root index node and the layer where the node is located is overflowing processing for the first time in the process of inserting a spatial object, then calculate the value of the overflow node node

The distance from the center of the axial bounding box of the child node to the center of the axial bounding box of the node node, using the distance as the key, sort the child nodes of the node node in descending order, and select the top

child nodes reinsert them into the layer of the index structure, otherwise divide the child nodes of the node node into k clusters

, will cluster

As a child node of node node, it is a clustering set

Create new nodes separately

, calculate the axial bounding box of the new node, and put the new node

The child node of the parent node of the node node is inserted into the index structure to realize the splitting of the node; 4) Adjust the axial bounding box of each node, the specific process is: (1) Set a new insertion into the index structure The parent node of the node is src_node; (2) Adjust the axial bounding box of the parent node src_node so that it just contains all the child nodes of the parent node src_node; (3) If the parent node src_node is the root index node point, the program returns, otherwise continue to execute; (4) Make the parent node src_node the parent node of the parent node src_node in step (1), and return to step (2); 3. Renew the axial bounding box that is too large Insert into the index structure to realize the optimization of the index structure; 4. Based on the dynamic index structure of product reverse engineering data, realize the topological nearest neighbor query of scattered point cloud, polygonal grid and sliced continuous surface, in which the adjacency of any spatial object T is queried The specific steps of the object are as follows: 1) Let the circumscribed sphere of the axial bounding box of the spatial object T be S; 2) Let

Indicates to query the adjacent object set of spatial object T in the index structure with node n as the root index node. If node n is a data node and intersects with circumscribed ball S, return the set of spatial objects contained in it. If Point n is an internal node, then

,in

Indicates the child node intersecting the circumscribed ball S in node N; 3) Initialize the current node N as the root index node of the index structure, then the set of adjacent objects of the spatial object T is

. 2. The method for establishing multi-objective self-adaptive establishment of dynamic index of product reverse engineering data as claimed in claim 1, characterized in that: in step 3) of step 2, the step of splitting the node is specifically: 1) for the node node Sub-nodes are binary coded, 0 means non-clustering center, 1 means clustering center, and construct and initialize a population P(t) of specified size, t=1, and calculate its objective function and fitness value; 2) According to the individual The objective function selects the non-dominated solution set E(t); 3) Perform selection, crossover, and mutation operations on the population P(t) to obtain the next generation population P(t+1), let t=t+1; 4) Calculate The objective function value and fitness value of the population P(t); 5) Calculate the non-dominated solution set of the population P(t), and then update the non-dominated solution set E(t); 6) Jump to Step 7), otherwise skip to step 3); 7) Decode the non-dominated solution set E(t), and then select the splitting scheme with the smallest sum of axial bounding box overlap and axial bounding box volume as the node The optimal splitting scheme of node; 8) Let the optimal splitting scheme of node node be

, will cluster

As a child node of node node, it is a clustering set

Create new nodes separately

, calculate the axial bounding box of the new node, and put the new node

The child nodes that are the parent nodes of the node node are inserted into the index structure. 3. the product reverse engineering data dynamic index multi-objective self-adaptive establishment method as claimed in claim 1, it is characterized in that: in step 3, index structure is optimized, and step is specifically: 1) traverse index structure, calculate leaf index structure The average volume of the axial bounding box of the point layer ; 2) Traversing each leaf index node of the index structure, if the volume of the axial bounding box of the leaf index node is greater than

(

The threshold set for the user, usually 3~5), then add the data nodes contained in it to the temporary sequence L, and delete the data nodes contained in it from the index structure; 3) add the data nodes in the sequence L Data nodes are reinserted into the index structure to achieve global optimization of the index structure.

Images