# 3D Assembly Model Retrieval Method for a Multiassembly Interface

Authors: Hu Qiao; Xufan Wang; Tianhang Xu; Zhenxing Wei; Ying Xiang
Journal: Scientific Programming
 (2022)

---

## Abstract

3D model retrieval is increasingly becoming a hot topic in today’s research. The existing model retrieval methods are limited to the retrieval between similar models, while the matching retrieval for models with assembly relationships is neglected. They cannot realize the prediction of the virtual assembly and make the assemblers to spend extensive time detecting when there are assembly errors in the model. This work proposes a 3D assembly model retrieval method for multiassembly interface, which can retrieve the parts or subassemblies that can be assembled with the input model. In this work, a method for the reuse of the 3D assembly mode is also provided. The method here involves a series of steps, which includes an attribute adjacency graph to express the 3D assembly models, followed by the definition of a conjugated subgraph, and the serialization of the vertices of the graph for the Atlas of the assembly model. Finally, the frequent subgraph mining method is improved, and the 3D assembly model that satisfies the multiassembly interface is extracted. The article claims through the obtained results that this method not only allows the performance of the 3D assembly model retrieval of multiassembly interfaces but also the extraction of the 3D model required by designers, improving, at the same time, the product design efficiency.


---

## Body

## 1. Introduction

In today’s digital design and manufacturing, most manufacturing enterprises modify existing products in the actual production process, and products designed from scratch almost do not exist [1–3]. The reuse of this model is particularly important. Especially in the aerospace, automotive, shipbuilding, and other fields produced more and more three-dimensional CAD models, and product design is based on the existing model above modification. The existing 3D model retrieval is more focused on the retrieval of parts themselves, and the technology is relatively mature, but in the practical application of enterprises, 3D CAD model mainly exists in the form of assembly, especially in manufacturing enterprises to achieve automatic workshop. This makes part model retrieval that cannot meet the actual needs of industry [4].At present, the existing 3D model retrieval technology is based on model similarity retrieval. Firstly, the characteristic information of the model itself is marked, and then, the similarity retrieval is carried out in the model library. This method does not consider the topology structure of the assembly model, assembly connection, and other information, leading to the difficulty in the development of 3D model retrieval method. Although the intelligent retrieval of models can realize the retrieval of similar parts among models, it cannot realize the retrieval of models with matching relationship. In actual enterprise manufacturing, model retrieval is not limited to the retrieval between similar parts, but is more applied to the virtual assembly process of products. What users need is not the retrieval of a single similar model, but the matching model with the input model.Most of the existing 3D model retrieval methods, such as 3D CAD model semantic retrieval based on sketch [5] and 3D model retrieval based on multilevel feature extraction [6], are based on assembly model granularity as the basis of reuse to retrieve the similarity of key semantic or geometric features. Most of these methods extract the features of 3D models, then compare the similarity based on the features, and finally achieve a purpose of retrieval.In terms of part retrieval, Qin et al. [7] proposed a 3D CAD model retrieval approach that considers the speed, accuracy, and ease of use at the same time based on sketches and unsupervised learning. Hojoon and Lee [8] abstracted the features of the model as nodes and then calculated their similarity to finalize the retrieval. Zhou et al. [9] completed 3D model retrieval based on 2D image features. Li et al. [10] proposed a multiview diagram matching method for 3D model retrieval, which aimed at breaking down and integrating the complex multiview diagram similarity degree measurement into several single view diagram similarity degree measurement. Mcwherter et al. [11] carried out 3D model retrieval based on invariant topological vector (ITV) and composed vector by multiple topological invariants in entity connection graph as feature descriptor of entity model. The effectiveness of invariant topological vector in 3D model retrieval is verified by comparing with many feature descriptors. Bespalov et al. [12] proposed a model retrieval method based on scale-space decomposition in view of the difficulty in local feature extraction and matching of 3D models. Based on parametric decomposition, the network of 3D model is decomposed into several local engineering surfaces. Then, according to the correlation features between local surfaces, a binary tree containing the correlation features is constructed, and the adjacency graph of feature attributes is established. Finally, the similarity between 3D models is calculated based on the attribute adjacency graph. McWherter et al. [13, 14] proposed a 3D model retrieval method based on attribute adjacency graph, in which the vertices of attribute adjacency graph represent different faces of 3D model, and adjacent faces are connected by edges. Edges represent surface properties such as size and concavity. The attribute adjacency graph of the 3D model is shown in the figure below.In terms of assembly retrieval, Dong and Xu [15] endowed the surface of assembly parts with the double attributes of function and structure and divided the surface into functional and nonfunctional surfaces so that it can account for the similarity of the part’s shape and functional properties. Zhang et al. [16] used the similarity of 3D assembly model attributes to propose a method of discovering common design units to find reusable information in the model. Zhou et al. [17] analyzed the similarity of the local structure of the assembly on the basis of the subgraph isomorphism and matching of the items and provided a theoretical basis for the retrieval of the 3D assembly model. Wang et al. [18] used random walk and optimal matching theories to analyze the topological relations and comparative attribute characteristics of each part so that it can obtain the similarity of the assembly as a whole. Wu and Gao [19] proposed a 3D assembly model retrieval method based on the similarity of spatial structure, where the similarity of the assembly can be obtained by the attribute feature similarity of the product model and the similarity of the part’s spatial position. Qiao et al. [20] proposed a single assembly interface 3D assembly model of information retrieval method, first using the preliminary model information retrieval, and then filtered according to the result of retrieval; assembly model geometry retrieval can be converted to look for problems with the attribute adjacency graph, finally using frequent subgraph mining algorithm with conjugate subgraph attribute adjacency graph search. In this paper, a three-dimensional assembly model with multiple assembly interfaces is studied.However, the retrieval target models of these methods are similar to the input models and do not consider the retrieval of part or subassemblies that can be assembled with the input model. By contrast, the 3D assembly model is connected through the geometric interface between the parts. The geometric interface can be a single connection or be connected through multiple interfaces, which increase the difficulty for the 3D assembly model retrieval.Considering the above problems, we take a multiassembly interface 3D assembly model as the object and study the 3D assembly model retrieval method. First, this method uses the attribute adjacency graph to express the graph of the 3D assembly model and builds the Atlas of the assembly model to establish the Atlas library. This method introduces the conjugated concept to define the conjugated subgraph between assembly parts. Then, the vertices of the graph are serialized for the Atlas of the assembly model, and the traversal times during the vertex matching process are reduced. On this basis, model retrieval is performed through the attribute adjacency graphs of parts, and it uses an improved frequent subgraph mining method to extract a 3D assembly model that satisfies multiple assembly interfaces. This article proposes a 3D assembly model retrieval method for the multiassembly interface, which can retrieve the parts or subassemblies that can be assembled with the input model, and it provides a method for the reuse of the 3D assembly model.


## 2. Materials and Methods

### 2.1. Representation of the 3D Assembly Model Based on Attribute Adjacency Graph and Definition of Conjugate Subgraph

There are many ways to represent the CAD model. Among them, the B-Rep model can easily obtain the geometric element information, topological relations, and attribute information of the model, so it is used by most commercial CAD systems. In the process of 3D model retrieval, the similarity degree of B-Rep model information needs to be compared, and how to express this information becomes the primary problem. The B-Rep can describe the modelled object more accurately. The B-Rep model not only describes the geometric information of all the geometric elements that constitute the modelling object but also describes the topological information of the object in detail. The topology information of a target object refers to the connections among all vertices, edges, and faces on the target. It can effectively improve the level of automation in the modelling process.Attributed adjacency graph (AAG) [18] can express the geometric element information, topological relations, and attribute information of the model, and it is widely used.


#### 2.1.1. Method for the Representation 3D Assembly Model Based on AAG

A 3D assembly model contains the relationship between parts, and its essence is a collection of information.The points, lines, and surfaces contained in the part and the topological relationship between parts can be effectively expressed by theAAG’s nodes and their attributes and edges. The AAG of CAD model is represented by G(V, E, α(V), β(E)):(1)
(V, E) is an undirected simple graph (without loops or heavy edges), V is the vertex set in the corresponding figure of the part, and V =  v1,v2,…,vi, Vi represents the ith face of the part.(2)
E is the edge set in the corresponding figure of the part, and E = {e1, e2, …, ej}, Ej is the edge connecting the vertices va and vb.(3)
α(V) represents the attribute set of the model’s vertex and is used to represent the properties of the model surface, including the geometric information of the model surface and the number of edges of the surface;(4)
β(E) represents the attribute set of the model’s edge, including the type of edge, information on the concavity and convexity, and the positional relationship between the faces of the model. This study focuses on 3D assembly retrieval, focusing on the concavity and convexity of the side.The cooperation relationship between the 3D assembly model parts can be converted into a certain attribute relationship between AAGs of part. A certain attribute relationship refers to the connection relationship and the type of contact surface between parts. The 3D assembly model can be represented by AAG’s Atlas, expressed asA = {G, S, P},(1)
G = {Gi,G2,G3,…,Gi} represents the AAG set of the assembly model part, and Gi represents the AAG of the ith part.(2)
S = {S1, S2, S3, …, Sm} represents the set of part’s connection type. The connection type can be divided into three categories, including threaded connection (screw connection, stud connection, nut connection, and special thread connection), keyway connection (round head flat key connection, flat head flat key connection, semicircular key connection, wedge key connection, and tangential key connection), and shaft hole connection (interference fit, clearance fit, and transition fit). m is the number of connections.(3)
P = {P1, P2, P3, …, Pn} represents the set of a part’s contact surface types. The contact surface types are plane and plane constraints (parallel on both sides, angled on both sides), plane and surface constraints (plane and cylinder tangent, and plane and sphere tangent), and surface and surface constraints, and coaxial constraints. n is the number of contact surfaces.According to the above method of representation, an Atlas library of a 3D assembly model can be constructed. The Atlas contains the AAG of the part, the connection between the parts, and the type of contact surface between the parts. Different atlases have different attribute tags. When it retrieves a 3D assembly model, the computer can find the corresponding Atlas from the Atlas library according to the attribute tag.


#### 2.1.2. Definition of Conjugated Subgraph

The assembly parts are connected by a geometric interface, and the conjugated relationship exists in the matching part of the geometric interface. That is, the topological connection of the mating parts is the same, but the concavity and convexity are opposite [21]. Therefore, through the AAG of the part, the 3D assembly model search can be transformed to find the AAG that satisfies the conjugate subgraph, to find the parts or subassemblies that can be assembled with the input model.Definition 1.
Conjugated subgraph: for the two AAGs to which the matching parts (assembly features) of the assembly parts correspond, their topological connection forms are the same, but their concavity and convexity are opposite, and they are called a conjugate subgraph. The conjugate subgraph features of assembly parts include the following: (1) the structure of the conjugate subgraph is the same; (2) the conjugate subgraph corresponds to the same vertex properties, the matching face has the opposite of the loss vector, and the matching area and radius of curvature are the same (nonessential conditions); and (3) the edge properties that the conjugate subgraph correspond to are the opposite.
For 3D assembly model retrieval of multiassembly interface, the input model has the features of multiple geometric interfaces, and its corresponding output model should also have multiple conjugate interfaces. As shown in Figure1, the input model has two geometric interfaces, and the subassemblies that can be assembled with the input model also have two corresponding conjugate interfaces. The portion marked with a red circle in the figure is a conjugated subgraph with a matching relationship. They have the same topological structure, but the concavity and convexity are opposite.Figure 1
AAG of multiassembly interface.


### 2.2. Serialization of AAG

The model retrieval is based on AAG, which needs to perform judgment of subgraph isomorphism, and the definition of graph isomorphism and subgraph isomorphism are as follows:Definition 2.
Graph isomorphism: there are two graphs, Gi= (Vi, Ei) and Gj = (Vj, Ej). If there is a mapping relationship between them, f: Vi⟶Vj, and ei=(vi, vi′) is one edge in Gi. If and only if ej=(vj, vj′) is an edge of Gj, then Gi and Gj are isomorphic.Definition 3.
Subgraph isomorphism: for a given symbol graph Gi and Gj, if there is a Gj′, then it is the subgraph of Gj and Gj′, and if Gi are isomorphic, then Gi and Gj have subgraph isomorphism.
Subgraph isomorphism is a typical NP problem, which requires repeated traversal of the vertices of the graph. However, the vertices of the graph are unordered, which leads to a very large amount of computation for isomorphism judgment. In addition, the 3D assembly model retrieval of multiassembly interface extracts atlases, from the Atlas library, that are similar to attribute information and topology of the input model. Then, it performs the judgment of isomorphism for each graph in the Atlas. There are multiple graphs in the Atlas, which also makes the calculation of graph isomorphism more difficult. Therefore, a method is needed to establish a unique sequence of vertices of graphs so that the judgment of graph isomorphism can reduce the amount of calculation.
Document [14] proposed that the sequence of the vertices of the AAG is determined according to the adjacency matrix M, and the adjacent vertices after serialization have adjacent edges in the graph. It defines the vector u as a sequence of vertex sets and satisfies(1)gu=∑i=1V−1∑k=1VLi,k+Li+1,kuk2,where uk is the k-th term of u and represents the sequence value of the k-th vertex of vertex set V. When u is the eigenvector corresponding to the largest eigenvalue of the adjacency matrix L, g (u) can obtain the maximum value. In this study, after serializing vertices, the same type of vertices is guaranteed to have adjacent edges in the graph and satisfy the maximum aggregation of vertices of the same type. The specific steps of serialization are as follows:
The flow chart of the algorithm is shown in Figure2.Step 1. Define the linked listW. The starting point has the largest sequence value in the AAG, W0=Vi, Vi = max(u).Step 2. FindWi−1 neighbors in AAG, NWi−1=i|W0,Vi∈E.Step 3. Theith point in the linked list W, Wi=Vi|maxu∩V∈NWi−1.Step 4. Get the serial number of the linked listWi is max(u)−i, and perform k-step iteration on the linked list and repeat step 2∼step 3. The list length is k + 1.Step 5. Judgek + 1 = n, n is the number of vertices of AAG, if equal, the algorithm ends and the output is serialized. If not, it goes to the next step.Step 6. Find the complement of vertex setsC=i|Vi∉W∩Vi∈V, and order AAG’s new vertex set V=C. Then, go to step 2.
After all vertices of the AAG are accessed, the sorting result of the output is shown in Figure3. The assembly interface can be summarized as “planar-plane,” “square rib-groove,” “circular pin-hole,” “curved surface-curved surface,” “dovetail rib-groove,” and “square pin-hole” [20]. When these assembly interfaces are represented by AAG, the vertices of them always have the largest sequence value in AAG, and the vertices corresponding assembly interfaces are independent of other vertices. Therefore, the conjugate subgraph does not disappear owing to serialization.
The significance of serialization is to improve the computational efficiency of the algorithm. The 3D assembly model retrieval of multiassembly interface extracts atlases that are similar to the attribute information and topology relationship of input model from the Atlas library, and then, it performs a judgment of isomorphism on each graph in Atlas. There are multiple graphs in an Atlas, which increases the calculation of graph isomorphism judgment. This makes the entire algorithm more efficient.Figure 2
Serialization of AAG.Figure 3
Result of AAG’s serialization.


### 2.3. 3D Assembly Model Retrieval Method

The output model of this paper’s retrieval method is a part or the subassembly that can be assembled with the input model, and it has multiple geometric interfaces. The retrieval method needs to perform multiple isomorphism judgments of AAGs conforming to the conjugate subgraph; only when the conjugate subgraph of the target is greater than or equal to the input model, the corresponding Atlas can be selected, and then, the corresponding 3D assembly model can be extracted. On the basis of graph serialization, first, a method of efficient graph isomorphism judgment is used to judge the isomorphism of AAG that conforms to conjugate subgraph; then, on the basis of the method of graph isomorphism, the Atlas containing multiple conjugate subgraphs is selected by using the improved frequent subgraph mining algorithm so that the corresponding 3D assembly model is extracted. The overall algorithm flow is shown in Figure4.Figure 4
3D assembly model retrieval method for multiassembly interface.


#### 2.3.1. Method of Judgment of Graph Isomorphism

The 3D assembly model retrieval method based on AAG transforms the similarity analysis of the assembly parts model into the similarity analysis of the AAG with the conjugate subgraph. The graph similarity judgment is accomplished using the graph isomorphism judgment to determine whether two graphs are isomorphic; that is, it assesses whether there is a mapping relationship between two graph vertices. The mapping relationship between two graph vertices can infer the mapping relationship between two graph edges.The computational complexity of subgraph isomorphism determination is an NP-complete problem. In this study, an efficient graph isomorphism determination method is used. We assume that we haveG1 and G2, where G1 is the target graph, and G2 is the graph to be retrieved. The number of vertices of the vertex set V1 of the graph G1 is a, the number of vertices of the vertex set V2 of the graph G2 is b, and a < b. The mapping relationship of the vertices between the graphs G1 and G2 is represented by an a × b mapping matrix Ma×b. mij is the i-row and j-column element in the mapping matrix M. If V1 and V2 are related, then mij = 1; otherwise, mij = 0. For matrix Ma×b, if there is a map with only one 1 per row and no more than one 1 per column, the matrix Ma×b represents the isomorphic mapping between G1 and G2.The steps of the graph isomorphism matching algorithm are as follows:Step 1. Initialize the mapping matrixM and set two empty sets V1 and V2. Use these sets to hold the vertices that have been matched by the two graphs during the retrieval.Step 2. Retrieve from the first row of matrixM and look for columns with a value of 1 from left to right. For any ith row, if the value of the jth column is 1, and if the column is not occupied, it means that a possible vertex association is found.Step 3. Add the two vertices of the previous step to setsV1 and V2.Step 4. Determine whether the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph.If the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph, the subgraphs that are composed of the set of vertices V1 matched in G1 and the set of vertices V2 matched in G2 are isomorphic. Thus, it can be judged that the subgraph formed by V1 and the subgraph formed by V2 are isomorphic.


#### 2.3.2. Improved Frequent Subgraph Mining Algorithm

On the basis of the method of graph isomorphism matching, the frequent subgraph mining algorithm is improved. Frequent subgraph mining is actually a graph isomorphism matching process, which is used to judge the Atlas extracted from the Atlas library. From this, it can be concluded whether the Atlas contains conjugate subgraphs that conform to the features of the assembly interface, and the number of conjugate subgraphs can be determined. If the number of conjugate subgraphs in the graph set is greater than or equal to the number of geometric interfaces of the input model, then the corresponding 3D assembly model of the Atlas is extracted. Otherwise, the Atlas is marked as a failure.The related definitions of frequent subgraph mining algorithms are as follows:Definition 4.
Frequency: there is a graph database B=b0,b1,…,bn for subgraph b such that(2)ϕb,bi=1,ifband the subgraph of bi are isomorphic0,ifband the subgraph of bi are not isomorphic,S=∑ϕb,biB,B represents the base of Atlas B, ∑ϕb,bi represents the total number of isomorphism of b and bi, bi∈B, and S is the frequency.Definition 5.
Frequency subgraph: for a given minimum frequency Smin, if there is a subgraph b that satisfies S ≥ Smin, then b is called a frequent subgraph of the Atlas database B.
The simple steps of the frequent subgraph mining algorithm are as follows:(1)
Connect theK-order frequent subgraphs to generate K + 1 candidate subgraphs;(2)
Clip the candidateK + 1 order subgraph Atlas, and delete all K + 1-order candidate subgraphs containing K-order infrequent subgraphs;(3)
Calculate the frequency of all subgraphs in theK + 1-order candidate subgraph set;(4)
Delete candidate subgraphs with frequencies less thanSmin in the K + 1-order candidate subgraphs.
By solving the loop fromk = 0 until it cannot generate higher-order frequent subgraphs, frequent subgraph mining is completed. Calculating the frequency of subgraphs is the process of graph isomorphism judgment. In extracting AAGs with conjugate subgraphs, the process needs to define some symbols to describe the algorithm. Table 1 lists some of these meanings.
The frequent subgraph Atlas generation algorithms are shown below. We start with AtlasB and frequency Smin, and the output is the set FK of the K-order frequent subgraph.
Frequent subgraph generation algorithm: (Algorithm 1)
Starting fromK = 0, the above algorithm is cyclically named, and the set of all frequent subgraphs is obtained as FF=F1,F2,….Fn.
The algorithm is based on theK-order frequent subgraphs to build K + 1 candidate subgraphs. The K + 1-order frequent subgraphs are obtained by using two K-order frequent subgraphs containing the same frequent subgraph of K − 1 order. The two most important steps in this process are identifying two identical K − 1-order subgraphs and connecting two K-order frequent subgraphs.
The recognition of two identicalK − 1-order subgraphs can record the IDs of all K − 1-order frequent subgraphs in the K-order frequent subgraph properties. The same K − 1-order frequent subgraph is obtained by the intersection of the two K-order frequent subgraph attribute values to avoid the judgment of subgraph isomorphism. The connection of two K-order frequent subgraphs can be seen as the process of generating the (K + 1 × K + 1) adjacency matrix by combining two (K × K) adjacency matrices.
The importance of the retrieval method proposed in this paper lies in the following:(1)
The retrieval of assembly information improves the semantic consistency of the model’s retrieval results from the perspective of assembly design intent.(2)
The search of the geometric structure adopts an efficient graph isomorphism decision method that is combined with frequent cartographic mining algorithms, thus improving the retrieval accuracy and retrieval efficiency.
The significance of the retrieval method proposed in this paper lies in the following: the graph that is extracted satisfies the conjugate subgraph with the features of the assembly interface and satisfies the set frequency. It can be used to judge the graph in the Atlas, resulting in a 3D assembly model with multiple conjugate interfaces.Table 1
Symbolic meaning.
SymbolMeaningCKK-order candidate frequent subgraph setsFKK-order frequent subgraph setsFFAll frequent subgraph sets,FF = {F1, F2, …, Fn}Algorithm 1: Frequent subgraph generation algorithm.
(1)
Begin(2)
FK+1 ← ∅, CK+1 ← Candidate(Fk)//generate candidate subgraphs.(3)
For ∀bK+1 ∈ CK+1 do//candidate sets downsizing and frequent count.(4)
Ifσ(bK+1) ≥ Smin then.(5)
FK+1 ← FK+1 ∪ {bK+1 }(6)
End if(7)
End for(8)
ReturnFK(9)
End


## 2.1. Representation of the 3D Assembly Model Based on Attribute Adjacency Graph and Definition of Conjugate Subgraph

There are many ways to represent the CAD model. Among them, the B-Rep model can easily obtain the geometric element information, topological relations, and attribute information of the model, so it is used by most commercial CAD systems. In the process of 3D model retrieval, the similarity degree of B-Rep model information needs to be compared, and how to express this information becomes the primary problem. The B-Rep can describe the modelled object more accurately. The B-Rep model not only describes the geometric information of all the geometric elements that constitute the modelling object but also describes the topological information of the object in detail. The topology information of a target object refers to the connections among all vertices, edges, and faces on the target. It can effectively improve the level of automation in the modelling process.Attributed adjacency graph (AAG) [18] can express the geometric element information, topological relations, and attribute information of the model, and it is widely used.


### 2.1.1. Method for the Representation 3D Assembly Model Based on AAG

A 3D assembly model contains the relationship between parts, and its essence is a collection of information.The points, lines, and surfaces contained in the part and the topological relationship between parts can be effectively expressed by theAAG’s nodes and their attributes and edges. The AAG of CAD model is represented by G(V, E, α(V), β(E)):(1)
(V, E) is an undirected simple graph (without loops or heavy edges), V is the vertex set in the corresponding figure of the part, and V =  v1,v2,…,vi, Vi represents the ith face of the part.(2)
E is the edge set in the corresponding figure of the part, and E = {e1, e2, …, ej}, Ej is the edge connecting the vertices va and vb.(3)
α(V) represents the attribute set of the model’s vertex and is used to represent the properties of the model surface, including the geometric information of the model surface and the number of edges of the surface;(4)
β(E) represents the attribute set of the model’s edge, including the type of edge, information on the concavity and convexity, and the positional relationship between the faces of the model. This study focuses on 3D assembly retrieval, focusing on the concavity and convexity of the side.The cooperation relationship between the 3D assembly model parts can be converted into a certain attribute relationship between AAGs of part. A certain attribute relationship refers to the connection relationship and the type of contact surface between parts. The 3D assembly model can be represented by AAG’s Atlas, expressed asA = {G, S, P},(1)
G = {Gi,G2,G3,…,Gi} represents the AAG set of the assembly model part, and Gi represents the AAG of the ith part.(2)
S = {S1, S2, S3, …, Sm} represents the set of part’s connection type. The connection type can be divided into three categories, including threaded connection (screw connection, stud connection, nut connection, and special thread connection), keyway connection (round head flat key connection, flat head flat key connection, semicircular key connection, wedge key connection, and tangential key connection), and shaft hole connection (interference fit, clearance fit, and transition fit). m is the number of connections.(3)
P = {P1, P2, P3, …, Pn} represents the set of a part’s contact surface types. The contact surface types are plane and plane constraints (parallel on both sides, angled on both sides), plane and surface constraints (plane and cylinder tangent, and plane and sphere tangent), and surface and surface constraints, and coaxial constraints. n is the number of contact surfaces.According to the above method of representation, an Atlas library of a 3D assembly model can be constructed. The Atlas contains the AAG of the part, the connection between the parts, and the type of contact surface between the parts. Different atlases have different attribute tags. When it retrieves a 3D assembly model, the computer can find the corresponding Atlas from the Atlas library according to the attribute tag.


### 2.1.2. Definition of Conjugated Subgraph

The assembly parts are connected by a geometric interface, and the conjugated relationship exists in the matching part of the geometric interface. That is, the topological connection of the mating parts is the same, but the concavity and convexity are opposite [21]. Therefore, through the AAG of the part, the 3D assembly model search can be transformed to find the AAG that satisfies the conjugate subgraph, to find the parts or subassemblies that can be assembled with the input model.Definition 1.
Conjugated subgraph: for the two AAGs to which the matching parts (assembly features) of the assembly parts correspond, their topological connection forms are the same, but their concavity and convexity are opposite, and they are called a conjugate subgraph. The conjugate subgraph features of assembly parts include the following: (1) the structure of the conjugate subgraph is the same; (2) the conjugate subgraph corresponds to the same vertex properties, the matching face has the opposite of the loss vector, and the matching area and radius of curvature are the same (nonessential conditions); and (3) the edge properties that the conjugate subgraph correspond to are the opposite.
For 3D assembly model retrieval of multiassembly interface, the input model has the features of multiple geometric interfaces, and its corresponding output model should also have multiple conjugate interfaces. As shown in Figure1, the input model has two geometric interfaces, and the subassemblies that can be assembled with the input model also have two corresponding conjugate interfaces. The portion marked with a red circle in the figure is a conjugated subgraph with a matching relationship. They have the same topological structure, but the concavity and convexity are opposite.Figure 1
AAG of multiassembly interface.


## 2.1.1. Method for the Representation 3D Assembly Model Based on AAG

A 3D assembly model contains the relationship between parts, and its essence is a collection of information.The points, lines, and surfaces contained in the part and the topological relationship between parts can be effectively expressed by theAAG’s nodes and their attributes and edges. The AAG of CAD model is represented by G(V, E, α(V), β(E)):(1)
(V, E) is an undirected simple graph (without loops or heavy edges), V is the vertex set in the corresponding figure of the part, and V =  v1,v2,…,vi, Vi represents the ith face of the part.(2)
E is the edge set in the corresponding figure of the part, and E = {e1, e2, …, ej}, Ej is the edge connecting the vertices va and vb.(3)
α(V) represents the attribute set of the model’s vertex and is used to represent the properties of the model surface, including the geometric information of the model surface and the number of edges of the surface;(4)
β(E) represents the attribute set of the model’s edge, including the type of edge, information on the concavity and convexity, and the positional relationship between the faces of the model. This study focuses on 3D assembly retrieval, focusing on the concavity and convexity of the side.The cooperation relationship between the 3D assembly model parts can be converted into a certain attribute relationship between AAGs of part. A certain attribute relationship refers to the connection relationship and the type of contact surface between parts. The 3D assembly model can be represented by AAG’s Atlas, expressed asA = {G, S, P},(1)
G = {Gi,G2,G3,…,Gi} represents the AAG set of the assembly model part, and Gi represents the AAG of the ith part.(2)
S = {S1, S2, S3, …, Sm} represents the set of part’s connection type. The connection type can be divided into three categories, including threaded connection (screw connection, stud connection, nut connection, and special thread connection), keyway connection (round head flat key connection, flat head flat key connection, semicircular key connection, wedge key connection, and tangential key connection), and shaft hole connection (interference fit, clearance fit, and transition fit). m is the number of connections.(3)
P = {P1, P2, P3, …, Pn} represents the set of a part’s contact surface types. The contact surface types are plane and plane constraints (parallel on both sides, angled on both sides), plane and surface constraints (plane and cylinder tangent, and plane and sphere tangent), and surface and surface constraints, and coaxial constraints. n is the number of contact surfaces.According to the above method of representation, an Atlas library of a 3D assembly model can be constructed. The Atlas contains the AAG of the part, the connection between the parts, and the type of contact surface between the parts. Different atlases have different attribute tags. When it retrieves a 3D assembly model, the computer can find the corresponding Atlas from the Atlas library according to the attribute tag.


## 2.1.2. Definition of Conjugated Subgraph

The assembly parts are connected by a geometric interface, and the conjugated relationship exists in the matching part of the geometric interface. That is, the topological connection of the mating parts is the same, but the concavity and convexity are opposite [21]. Therefore, through the AAG of the part, the 3D assembly model search can be transformed to find the AAG that satisfies the conjugate subgraph, to find the parts or subassemblies that can be assembled with the input model.Definition 1.
Conjugated subgraph: for the two AAGs to which the matching parts (assembly features) of the assembly parts correspond, their topological connection forms are the same, but their concavity and convexity are opposite, and they are called a conjugate subgraph. The conjugate subgraph features of assembly parts include the following: (1) the structure of the conjugate subgraph is the same; (2) the conjugate subgraph corresponds to the same vertex properties, the matching face has the opposite of the loss vector, and the matching area and radius of curvature are the same (nonessential conditions); and (3) the edge properties that the conjugate subgraph correspond to are the opposite.
For 3D assembly model retrieval of multiassembly interface, the input model has the features of multiple geometric interfaces, and its corresponding output model should also have multiple conjugate interfaces. As shown in Figure1, the input model has two geometric interfaces, and the subassemblies that can be assembled with the input model also have two corresponding conjugate interfaces. The portion marked with a red circle in the figure is a conjugated subgraph with a matching relationship. They have the same topological structure, but the concavity and convexity are opposite.Figure 1
AAG of multiassembly interface.


## 2.2. Serialization of AAG

The model retrieval is based on AAG, which needs to perform judgment of subgraph isomorphism, and the definition of graph isomorphism and subgraph isomorphism are as follows:Definition 2.
Graph isomorphism: there are two graphs, Gi= (Vi, Ei) and Gj = (Vj, Ej). If there is a mapping relationship between them, f: Vi⟶Vj, and ei=(vi, vi′) is one edge in Gi. If and only if ej=(vj, vj′) is an edge of Gj, then Gi and Gj are isomorphic.Definition 3.
Subgraph isomorphism: for a given symbol graph Gi and Gj, if there is a Gj′, then it is the subgraph of Gj and Gj′, and if Gi are isomorphic, then Gi and Gj have subgraph isomorphism.
Subgraph isomorphism is a typical NP problem, which requires repeated traversal of the vertices of the graph. However, the vertices of the graph are unordered, which leads to a very large amount of computation for isomorphism judgment. In addition, the 3D assembly model retrieval of multiassembly interface extracts atlases, from the Atlas library, that are similar to attribute information and topology of the input model. Then, it performs the judgment of isomorphism for each graph in the Atlas. There are multiple graphs in the Atlas, which also makes the calculation of graph isomorphism more difficult. Therefore, a method is needed to establish a unique sequence of vertices of graphs so that the judgment of graph isomorphism can reduce the amount of calculation.
Document [14] proposed that the sequence of the vertices of the AAG is determined according to the adjacency matrix M, and the adjacent vertices after serialization have adjacent edges in the graph. It defines the vector u as a sequence of vertex sets and satisfies(1)gu=∑i=1V−1∑k=1VLi,k+Li+1,kuk2,where uk is the k-th term of u and represents the sequence value of the k-th vertex of vertex set V. When u is the eigenvector corresponding to the largest eigenvalue of the adjacency matrix L, g (u) can obtain the maximum value. In this study, after serializing vertices, the same type of vertices is guaranteed to have adjacent edges in the graph and satisfy the maximum aggregation of vertices of the same type. The specific steps of serialization are as follows:
The flow chart of the algorithm is shown in Figure2.Step 1. Define the linked listW. The starting point has the largest sequence value in the AAG, W0=Vi, Vi = max(u).Step 2. FindWi−1 neighbors in AAG, NWi−1=i|W0,Vi∈E.Step 3. Theith point in the linked list W, Wi=Vi|maxu∩V∈NWi−1.Step 4. Get the serial number of the linked listWi is max(u)−i, and perform k-step iteration on the linked list and repeat step 2∼step 3. The list length is k + 1.Step 5. Judgek + 1 = n, n is the number of vertices of AAG, if equal, the algorithm ends and the output is serialized. If not, it goes to the next step.Step 6. Find the complement of vertex setsC=i|Vi∉W∩Vi∈V, and order AAG’s new vertex set V=C. Then, go to step 2.
After all vertices of the AAG are accessed, the sorting result of the output is shown in Figure3. The assembly interface can be summarized as “planar-plane,” “square rib-groove,” “circular pin-hole,” “curved surface-curved surface,” “dovetail rib-groove,” and “square pin-hole” [20]. When these assembly interfaces are represented by AAG, the vertices of them always have the largest sequence value in AAG, and the vertices corresponding assembly interfaces are independent of other vertices. Therefore, the conjugate subgraph does not disappear owing to serialization.
The significance of serialization is to improve the computational efficiency of the algorithm. The 3D assembly model retrieval of multiassembly interface extracts atlases that are similar to the attribute information and topology relationship of input model from the Atlas library, and then, it performs a judgment of isomorphism on each graph in Atlas. There are multiple graphs in an Atlas, which increases the calculation of graph isomorphism judgment. This makes the entire algorithm more efficient.Figure 2
Serialization of AAG.Figure 3
Result of AAG’s serialization.


## 2.3. 3D Assembly Model Retrieval Method

The output model of this paper’s retrieval method is a part or the subassembly that can be assembled with the input model, and it has multiple geometric interfaces. The retrieval method needs to perform multiple isomorphism judgments of AAGs conforming to the conjugate subgraph; only when the conjugate subgraph of the target is greater than or equal to the input model, the corresponding Atlas can be selected, and then, the corresponding 3D assembly model can be extracted. On the basis of graph serialization, first, a method of efficient graph isomorphism judgment is used to judge the isomorphism of AAG that conforms to conjugate subgraph; then, on the basis of the method of graph isomorphism, the Atlas containing multiple conjugate subgraphs is selected by using the improved frequent subgraph mining algorithm so that the corresponding 3D assembly model is extracted. The overall algorithm flow is shown in Figure4.Figure 4
3D assembly model retrieval method for multiassembly interface.


### 2.3.1. Method of Judgment of Graph Isomorphism

The 3D assembly model retrieval method based on AAG transforms the similarity analysis of the assembly parts model into the similarity analysis of the AAG with the conjugate subgraph. The graph similarity judgment is accomplished using the graph isomorphism judgment to determine whether two graphs are isomorphic; that is, it assesses whether there is a mapping relationship between two graph vertices. The mapping relationship between two graph vertices can infer the mapping relationship between two graph edges.The computational complexity of subgraph isomorphism determination is an NP-complete problem. In this study, an efficient graph isomorphism determination method is used. We assume that we haveG1 and G2, where G1 is the target graph, and G2 is the graph to be retrieved. The number of vertices of the vertex set V1 of the graph G1 is a, the number of vertices of the vertex set V2 of the graph G2 is b, and a < b. The mapping relationship of the vertices between the graphs G1 and G2 is represented by an a × b mapping matrix Ma×b. mij is the i-row and j-column element in the mapping matrix M. If V1 and V2 are related, then mij = 1; otherwise, mij = 0. For matrix Ma×b, if there is a map with only one 1 per row and no more than one 1 per column, the matrix Ma×b represents the isomorphic mapping between G1 and G2.The steps of the graph isomorphism matching algorithm are as follows:Step 1. Initialize the mapping matrixM and set two empty sets V1 and V2. Use these sets to hold the vertices that have been matched by the two graphs during the retrieval.Step 2. Retrieve from the first row of matrixM and look for columns with a value of 1 from left to right. For any ith row, if the value of the jth column is 1, and if the column is not occupied, it means that a possible vertex association is found.Step 3. Add the two vertices of the previous step to setsV1 and V2.Step 4. Determine whether the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph.If the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph, the subgraphs that are composed of the set of vertices V1 matched in G1 and the set of vertices V2 matched in G2 are isomorphic. Thus, it can be judged that the subgraph formed by V1 and the subgraph formed by V2 are isomorphic.


### 2.3.2. Improved Frequent Subgraph Mining Algorithm

On the basis of the method of graph isomorphism matching, the frequent subgraph mining algorithm is improved. Frequent subgraph mining is actually a graph isomorphism matching process, which is used to judge the Atlas extracted from the Atlas library. From this, it can be concluded whether the Atlas contains conjugate subgraphs that conform to the features of the assembly interface, and the number of conjugate subgraphs can be determined. If the number of conjugate subgraphs in the graph set is greater than or equal to the number of geometric interfaces of the input model, then the corresponding 3D assembly model of the Atlas is extracted. Otherwise, the Atlas is marked as a failure.The related definitions of frequent subgraph mining algorithms are as follows:Definition 4.
Frequency: there is a graph database B=b0,b1,…,bn for subgraph b such that(2)ϕb,bi=1,ifband the subgraph of bi are isomorphic0,ifband the subgraph of bi are not isomorphic,S=∑ϕb,biB,B represents the base of Atlas B, ∑ϕb,bi represents the total number of isomorphism of b and bi, bi∈B, and S is the frequency.Definition 5.
Frequency subgraph: for a given minimum frequency Smin, if there is a subgraph b that satisfies S ≥ Smin, then b is called a frequent subgraph of the Atlas database B.
The simple steps of the frequent subgraph mining algorithm are as follows:(1)
Connect theK-order frequent subgraphs to generate K + 1 candidate subgraphs;(2)
Clip the candidateK + 1 order subgraph Atlas, and delete all K + 1-order candidate subgraphs containing K-order infrequent subgraphs;(3)
Calculate the frequency of all subgraphs in theK + 1-order candidate subgraph set;(4)
Delete candidate subgraphs with frequencies less thanSmin in the K + 1-order candidate subgraphs.
By solving the loop fromk = 0 until it cannot generate higher-order frequent subgraphs, frequent subgraph mining is completed. Calculating the frequency of subgraphs is the process of graph isomorphism judgment. In extracting AAGs with conjugate subgraphs, the process needs to define some symbols to describe the algorithm. Table 1 lists some of these meanings.
The frequent subgraph Atlas generation algorithms are shown below. We start with AtlasB and frequency Smin, and the output is the set FK of the K-order frequent subgraph.
Frequent subgraph generation algorithm: (Algorithm 1)
Starting fromK = 0, the above algorithm is cyclically named, and the set of all frequent subgraphs is obtained as FF=F1,F2,….Fn.
The algorithm is based on theK-order frequent subgraphs to build K + 1 candidate subgraphs. The K + 1-order frequent subgraphs are obtained by using two K-order frequent subgraphs containing the same frequent subgraph of K − 1 order. The two most important steps in this process are identifying two identical K − 1-order subgraphs and connecting two K-order frequent subgraphs.
The recognition of two identicalK − 1-order subgraphs can record the IDs of all K − 1-order frequent subgraphs in the K-order frequent subgraph properties. The same K − 1-order frequent subgraph is obtained by the intersection of the two K-order frequent subgraph attribute values to avoid the judgment of subgraph isomorphism. The connection of two K-order frequent subgraphs can be seen as the process of generating the (K + 1 × K + 1) adjacency matrix by combining two (K × K) adjacency matrices.
The importance of the retrieval method proposed in this paper lies in the following:(1)
The retrieval of assembly information improves the semantic consistency of the model’s retrieval results from the perspective of assembly design intent.(2)
The search of the geometric structure adopts an efficient graph isomorphism decision method that is combined with frequent cartographic mining algorithms, thus improving the retrieval accuracy and retrieval efficiency.
The significance of the retrieval method proposed in this paper lies in the following: the graph that is extracted satisfies the conjugate subgraph with the features of the assembly interface and satisfies the set frequency. It can be used to judge the graph in the Atlas, resulting in a 3D assembly model with multiple conjugate interfaces.Table 1
Symbolic meaning.
SymbolMeaningCKK-order candidate frequent subgraph setsFKK-order frequent subgraph setsFFAll frequent subgraph sets,FF = {F1, F2, …, Fn}Algorithm 1: Frequent subgraph generation algorithm.
(1)
Begin(2)
FK+1 ← ∅, CK+1 ← Candidate(Fk)//generate candidate subgraphs.(3)
For ∀bK+1 ∈ CK+1 do//candidate sets downsizing and frequent count.(4)
Ifσ(bK+1) ≥ Smin then.(5)
FK+1 ← FK+1 ∪ {bK+1 }(6)
End if(7)
End for(8)
ReturnFK(9)
End


## 2.3.1. Method of Judgment of Graph Isomorphism

The 3D assembly model retrieval method based on AAG transforms the similarity analysis of the assembly parts model into the similarity analysis of the AAG with the conjugate subgraph. The graph similarity judgment is accomplished using the graph isomorphism judgment to determine whether two graphs are isomorphic; that is, it assesses whether there is a mapping relationship between two graph vertices. The mapping relationship between two graph vertices can infer the mapping relationship between two graph edges.The computational complexity of subgraph isomorphism determination is an NP-complete problem. In this study, an efficient graph isomorphism determination method is used. We assume that we haveG1 and G2, where G1 is the target graph, and G2 is the graph to be retrieved. The number of vertices of the vertex set V1 of the graph G1 is a, the number of vertices of the vertex set V2 of the graph G2 is b, and a < b. The mapping relationship of the vertices between the graphs G1 and G2 is represented by an a × b mapping matrix Ma×b. mij is the i-row and j-column element in the mapping matrix M. If V1 and V2 are related, then mij = 1; otherwise, mij = 0. For matrix Ma×b, if there is a map with only one 1 per row and no more than one 1 per column, the matrix Ma×b represents the isomorphic mapping between G1 and G2.The steps of the graph isomorphism matching algorithm are as follows:Step 1. Initialize the mapping matrixM and set two empty sets V1 and V2. Use these sets to hold the vertices that have been matched by the two graphs during the retrieval.Step 2. Retrieve from the first row of matrixM and look for columns with a value of 1 from left to right. For any ith row, if the value of the jth column is 1, and if the column is not occupied, it means that a possible vertex association is found.Step 3. Add the two vertices of the previous step to setsV1 and V2.Step 4. Determine whether the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph.If the newly added vertices inV1 and V2 correspond to the matching vertex pairs in the final isomorphism graph, the subgraphs that are composed of the set of vertices V1 matched in G1 and the set of vertices V2 matched in G2 are isomorphic. Thus, it can be judged that the subgraph formed by V1 and the subgraph formed by V2 are isomorphic.


## 2.3.2. Improved Frequent Subgraph Mining Algorithm

On the basis of the method of graph isomorphism matching, the frequent subgraph mining algorithm is improved. Frequent subgraph mining is actually a graph isomorphism matching process, which is used to judge the Atlas extracted from the Atlas library. From this, it can be concluded whether the Atlas contains conjugate subgraphs that conform to the features of the assembly interface, and the number of conjugate subgraphs can be determined. If the number of conjugate subgraphs in the graph set is greater than or equal to the number of geometric interfaces of the input model, then the corresponding 3D assembly model of the Atlas is extracted. Otherwise, the Atlas is marked as a failure.The related definitions of frequent subgraph mining algorithms are as follows:Definition 4.
Frequency: there is a graph database B=b0,b1,…,bn for subgraph b such that(2)ϕb,bi=1,ifband the subgraph of bi are isomorphic0,ifband the subgraph of bi are not isomorphic,S=∑ϕb,biB,B represents the base of Atlas B, ∑ϕb,bi represents the total number of isomorphism of b and bi, bi∈B, and S is the frequency.Definition 5.
Frequency subgraph: for a given minimum frequency Smin, if there is a subgraph b that satisfies S ≥ Smin, then b is called a frequent subgraph of the Atlas database B.
The simple steps of the frequent subgraph mining algorithm are as follows:(1)
Connect theK-order frequent subgraphs to generate K + 1 candidate subgraphs;(2)
Clip the candidateK + 1 order subgraph Atlas, and delete all K + 1-order candidate subgraphs containing K-order infrequent subgraphs;(3)
Calculate the frequency of all subgraphs in theK + 1-order candidate subgraph set;(4)
Delete candidate subgraphs with frequencies less thanSmin in the K + 1-order candidate subgraphs.
By solving the loop fromk = 0 until it cannot generate higher-order frequent subgraphs, frequent subgraph mining is completed. Calculating the frequency of subgraphs is the process of graph isomorphism judgment. In extracting AAGs with conjugate subgraphs, the process needs to define some symbols to describe the algorithm. Table 1 lists some of these meanings.
The frequent subgraph Atlas generation algorithms are shown below. We start with AtlasB and frequency Smin, and the output is the set FK of the K-order frequent subgraph.
Frequent subgraph generation algorithm: (Algorithm 1)
Starting fromK = 0, the above algorithm is cyclically named, and the set of all frequent subgraphs is obtained as FF=F1,F2,….Fn.
The algorithm is based on theK-order frequent subgraphs to build K + 1 candidate subgraphs. The K + 1-order frequent subgraphs are obtained by using two K-order frequent subgraphs containing the same frequent subgraph of K − 1 order. The two most important steps in this process are identifying two identical K − 1-order subgraphs and connecting two K-order frequent subgraphs.
The recognition of two identicalK − 1-order subgraphs can record the IDs of all K − 1-order frequent subgraphs in the K-order frequent subgraph properties. The same K − 1-order frequent subgraph is obtained by the intersection of the two K-order frequent subgraph attribute values to avoid the judgment of subgraph isomorphism. The connection of two K-order frequent subgraphs can be seen as the process of generating the (K + 1 × K + 1) adjacency matrix by combining two (K × K) adjacency matrices.
The importance of the retrieval method proposed in this paper lies in the following:(1)
The retrieval of assembly information improves the semantic consistency of the model’s retrieval results from the perspective of assembly design intent.(2)
The search of the geometric structure adopts an efficient graph isomorphism decision method that is combined with frequent cartographic mining algorithms, thus improving the retrieval accuracy and retrieval efficiency.
The significance of the retrieval method proposed in this paper lies in the following: the graph that is extracted satisfies the conjugate subgraph with the features of the assembly interface and satisfies the set frequency. It can be used to judge the graph in the Atlas, resulting in a 3D assembly model with multiple conjugate interfaces.Table 1
Symbolic meaning.
SymbolMeaningCKK-order candidate frequent subgraph setsFKK-order frequent subgraph setsFFAll frequent subgraph sets,FF = {F1, F2, …, Fn}Algorithm 1: Frequent subgraph generation algorithm.
(1)
Begin(2)
FK+1 ← ∅, CK+1 ← Candidate(Fk)//generate candidate subgraphs.(3)
For ∀bK+1 ∈ CK+1 do//candidate sets downsizing and frequent count.(4)
Ifσ(bK+1) ≥ Smin then.(5)
FK+1 ← FK+1 ∪ {bK+1 }(6)
End if(7)
End for(8)
ReturnFK(9)
End


## 3. Discussion

To verify the validity of this method, a CAD model library for machine tool fixtures and accessories was established. An experiment of 3D assembly model retrieval of multiassembly interface is performed using MATLAB software. The computer used was an Intel Core I7-8700K CPU with 4 GB of memory.It takes the machine’s jaws as the input model, which has two fixing holes. It needs to extract models that have conjugate features with the fixed holes in the model library, and there are two or more conjugate features.In the retrieval process, first, the system reads the attribute information and topology of the input model. Then, it passes the reading input model information to the Atlas library of models, queries the Atlas library based on this information, and extracts the atlases whose attribute information and topology are similar to the input model. The corresponding 3D models of the retrieved atlases are listed in Table2.Table 2
Extraction results of attribute information and topology relation from Atlas library.According to the table, the corresponding models of the Atlas are single assembly parts, and some are subassemblies. They all have the features of axial hole connection, plane and surface contact, or plane and plane contact.After extracting the Atlas that is similar to the input model’s attribute information and topology, the judgment of graph isomorphism is performed on the AAG of the Atlas. It judges whether the AAG in the Atlas contains conjugate subgraphs, and its number must be greater than or equal to the number of conjugate subgraphs of the input model. To verify the search conditions in the case ofSmin with different frequency, experiments were performed with Smin = 1.00 and Smin = 0.60, respectively. The results of the retrieval are listed in Table 3.Table 3
Retrieval of judgment of graph isomorphism.After graph isomorphism judgment, the atlases of AAGs that do not conform to conjugate subgraphs are eliminated. Moreover, because the frequent subgraph mining algorithm is based on the idea of layer-by-layer iteration, the number of extracted atlases is reduced as theSmin increases. The meaning of changing Smin is that the scope of the output model can be set according to the designer’s needs. When the design intent is clear, Smin can be increased to accurately output the model; when the design intent is ambiguous, Smin can be reduced to extend the range of the output model, which gives the designer more choices.From Table3, it can be seen that the retrieval method of judgment of graph isomorphism can accurately match the assembly interface of the 3D model. The Atlas of the model has similar attribute information and topological relations. Using the advantages that the AAG can express the topological structure of the 3D model, the model is retrieved from the shape structure, and the conjugate subgraph can retrieve the matching structure of the two models with the assembly relationship. Therefore, the matching 3D model of the assembly interface can be extracted through the judgment of graph isomorphism, which significantly improves the accuracy of model retrieval results.Although the vertices of AAG are serialized and the number of vertices traversing in the judgment of graph isomorphism decreases, the calculation amount of judgment of AAG isomorphism in the Atlas is still large. Therefore, in order to verify the time efficiency of retrieval algorithm, the execution time of the algorithm under differentSmin is verified. Experiments show that the larger Smin is, the shorter the execution time of the algorithm is. This is the result of the algorithm’s iterative idea. The experimental results are shown Figure 5.Figure 5
Operation of differentSmin.


## 4. Conclusions

In this paper, a 3D assembly model retrieval method for multiassembly interface is proposed. First, the 3D assembly model is represented by an attribute adjacency graph, and the definition of the conjugate subgraph is given according to the coordination relation between the assembly interfaces. Then, the graph in the Atlas is serialized so that the vertex of the attribute adjacency graph has a unique sequence. Finally, through the method of efficient graph isomorphism judgment and the improvement of frequent subgraph mining algorithm, the attribute adjacency graph that conforms best to the assembly conjugate subgraph is judged in the Atlas, to extract the 3D assembly model of the multiassembly interface. Experimental results show that the method proposed in this paper can retrieve the parts or subassemblies that match the input model, and it provides a method to reuse the 3D assembly model.


### 4.1. Future Work

This paper proposes a 3D assembly model retrieval method incorporating assembly semantics, which is based on the existing 3D models of the subject group, whose semantic information has already been marked up, and the model information reflected is not perfect. In order to achieve a better 3D model retrieval system, further research can be done in terms of semantic annotation specification, similarity metric method, and 3D assembly model information subnetwork acquisition and pushing method.(1)
According to the different needs and influences of designers on 3D assembly model information in the early, middle, and late stages of design, the components of design intent in the time dimension are summarized and the semantic annotation specification of 3D assembly model information reflecting design intent is constructed.(2)
A design intent semantic information association mapping specification is constructed, and design intent information subnetworks of different sizes are formed according to different granularity of design intent. The similarity measure between the design intent information subnetwork and the subnetwork in the 3D assembly model information network is investigated, and the best matching subnetwork is searched for in the 3D assembly model information network.


## 4.1. Future Work

This paper proposes a 3D assembly model retrieval method incorporating assembly semantics, which is based on the existing 3D models of the subject group, whose semantic information has already been marked up, and the model information reflected is not perfect. In order to achieve a better 3D model retrieval system, further research can be done in terms of semantic annotation specification, similarity metric method, and 3D assembly model information subnetwork acquisition and pushing method.(1)
According to the different needs and influences of designers on 3D assembly model information in the early, middle, and late stages of design, the components of design intent in the time dimension are summarized and the semantic annotation specification of 3D assembly model information reflecting design intent is constructed.(2)
A design intent semantic information association mapping specification is constructed, and design intent information subnetworks of different sizes are formed according to different granularity of design intent. The similarity measure between the design intent information subnetwork and the subnetwork in the 3D assembly model information network is investigated, and the best matching subnetwork is searched for in the 3D assembly model information network.



---

*Source: 1984979-2022-07-18.xml*