Dynamic assembly simplification for virtual assembly process of complex product in cloud computing environment

Abstract

Three-dimensional model–based virtual assembly process planning plays an important role in assembly design of complex product and is typically time- and resource-intensive. There are limited effective solution frameworks for delivering the three-dimensional model–based assembly process information to assembly field in order to directly guide the assembly tasks on site. A cloud service architecture for mobile three-dimensional model is proposed to address these challenges. Under this cloud computing architecture, this article introduces a dynamic assembly simplification approach, which regards the virtual assembly process of complex product as an incremental growth process of dynamic assembly. During the growth process, the current-assembled-state assembly model is simplified with appearance preserved by detecting and removing its invisible features, and the to-be-assembled components are simplified with assembly features preserved using conjugated subgraphs matching method based on MapReduce. The proposed approach has been tested on several cases, and the results show its feasibility and superiority.

Keywords

Virtual assembly dynamic assembly model simplification assembly features subgraph isomorphism cloud computing MapReduce

Introduction

Three-dimensional (3D) model–based virtual assembly process planning is an important part of complex product design. It is of great significance for the rationality verification of complex product design, shortening the design cycle and reducing the cost. Meanwhile, the assembly tasks on assembly field are of high mobility. With the development of mobile computing and wireless network technologies, it seems that using mobile devices on assembly field to deliver, demonstrate and interact with 3D model–based assembly process information (i.e. 3D assembly order (3D AO)) of complex product is an irresistible trend.^1,2 However, complex product usually has hundreds or even thousands of components; it is a challenge to demonstrate, interact with and deliver its 3D AO to the assembly field. One cannot just rely on hardware and computing resources improvement to cope with this issue,^3,4 which could be addressed by an alternative approach named model simplification.

Computer-aided design (CAD) models are the primary carrier of the assembly process information contained in 3D AO. Besides, designing the assembly process based on CAD models and providing the assembly field with 3D AO are important parts of the implementation of model-based definition (MBD) technology in manufacturing industry. MBD technology aims to change the mode of product design and manufacturing by replacing the two-dimensional (2D) drawing with integrated 3D CAD model, which is the single source of product data and sole basis for the whole manufacturing process, including the assembling process.⁵ Current 3D model simplification methods^6–9 and lightweight 3D file formats—such as “JT,” put forward by Siemens AG,¹⁰ and “XVL,” proposed by Lattice technology Inc.¹¹—reduce the data volume of the boundary representation (B-Rep) CAD solid model by approximating the model with smooth rounded surfaces. For this reason, the simplified CAD model format has been changed to the one completely different from the original one,¹² that is, the engineering semantics information and features of the original CAD models have been lost during the simplification process. Therefore, these simplified CAD models are usually used to demonstrate the appearance of complex product other than being applied to several critical stages of virtual assembly process of complex product, such as collision detection, assembly path planning and 3D tolerance analysis, to name a few. Other B-Rep-oriented simplification methods simplify a CAD solid model either by recognizing and suppressing the blend features^13–15 or by suppressing certain form features defined in the design history of the input model.^16–20 However, all these works only simplify the single part but not the whole assembly model. Kanai et al.,¹² Russ²¹ and Koo and Lee²² presented the model simplification methods which simplify an assembly by deleting the components entirely, and no operations of assembly features identification and preservation were performed, and it is impossible to support the demonstration of the progressive assembling process of complex product. In other words, they could only be applied to static assembly, the one that is at its final-completely-assembled state, but not suitable for dynamic assembly, which grows progressively from the initial state only containing the reference components to the final-completely-assembled state. Since the progressive assembling process is vital for the process engineers to design the 3D AO which will be delivered to the assembly field to provide assembly workers with intuitional guidance, more efforts are needed to investigate the B-Rep-oriented simplification method for dynamic assembly during the assembly process planning of complex product. As for the mobile 3D model technology, currently, it is mainly used in animation^23,24 and construction site,^2,25 but rarely in manufacturing engineering such as assembly field of complex product.

Xiao et al.^26,27 presented CAD model simplification methods with assembly features preservation, which create prerequisites for delivering 3D AO to assembly field using mobile devices. Fast recognition of assembly features is the core algorithm. The problem of assembly features recognition has been translated into conjugated subgraphs matching. Based on the Ullmann algorithm²⁶ and the divide-and-conquer strategy,²⁷ assembly features can be recognized in real time when the scale of the corresponding graphs is not too large. As the scale of the conjugated subgraphs matching problem keeps increasing, the previous algorithms need to be improved to keep their efficiency. In the meantime, although the requirement for 3D AO on assembly field gets more and more imperative, it is costly and cumbersome for end users to install and maintain relevant software and operating system on mobile device for the demonstration and interaction of 3D AO. Therefore, a new problem-solving framework is needed for the large-scale dynamic assembly simplification and mobile 3D AO on assembly field.

In recent years, cloud computing has developed from concept speculation to successful application in various domains, including scientific computing,^28,29 mobile communication,³⁰ product design and manufacturing³¹ and military.³² It shows that cloud computing has the advantages of solving large-scale problems efficiently and being suitable for operations on mobile devices.³³ Taking the massive social network graph query as an example, cloud computing has been adopted to solve this problem with an acceptable response time and lower computational cost. Different from a single super-large social network graph, the graphs this article deals with are categorized into two types: a large graph that keeps increasing and a set of relatively small graphs. And the application environment of the proposed approach in this article puts more emphasis on the efficiency of the graph algorithm. Although the cloud computing is suitable for handling massive graph, it is just a generic framework and still at its infancy;³⁴ how to perform the conjugated subgraphs matching in cloud computing environment and support 3D AO on assembly field needs more thorough research.

The rest of this article is organized as follows. Section “Cloud service architecture for mobile 3D model” presents the cloud service architecture for mobile 3D model and introduces the outline of the proposed approach. Section “Assembly model simplification with appearance preservation” describes a dynamic assembly simplification method with appearance preservation by detecting and removing the invisible features of current-assembled-state assembly model. Section “CAD model simplification with assembly features preservation” discusses dynamic assembly simplification method with assembly features preservation, and the focus is assembly features recognition based on conjugated subgraphs matching using MapReduce (MR). Section “Results and analysis” demonstrates the performance of the proposed approach and shows experimental comparison of this approach with the one presented in Xiao et al.²⁷ Conclusions are drawn in the final section.

Cloud service architecture for mobile 3D model

In large enterprises, because of business independence and system stability, usually, there is a proprietary information technology (IT) system for every important project. Consequently, it causes “chimney phenomenon,” that is, lots of independent IT systems whose computing and storage resources are idle for most of the time. Cloud computing is an ideal solution framework for the full utilization of the computing and storage resources in order to reduce costs. Due to safety concerns, manufacturing industry of complex products should employ the private cloud which can feasibly and effectively solve the problem of IT resource wasting, even though it is not as dazzling as public cloud.³⁵ In addition to cloud security, interoperability is another core issue to implement cloud computing effectively. As a general term, “interoperability” is a property referring to the ability of diverse systems and organizations to work together. This property has the concrete meaning of exchanging information and use of the information that has been exchanged between two or more systems or components.³⁶ Strictly speaking, interoperability is the capability to communicate, execute programs or transfer data among various functional units under specified conditions.³⁷ Usually, interoperability of infrastructure components is achieved by virtualization architectures, while data components interoperate via application components rather than directly in private cloud computing systems. This is especially applicable for the large enterprises to have complete control over their own data. A cloud service architecture is proposed for mobile 3D model based on private cloud. Figure 1 shows its logical layers and components.

Figure 1.

Logical layers and components of the cloud service architecture for mobile 3D model.

The proposed cloud service architecture consists of three layers: infrastructure layer, platform layer and application layer. The infrastructure layer creates a pool of computing and storage resources by virtualizing the physical resources. It also includes a parallel computing framework (i.e. MR). The platform layer builds on top of the infrastructure layer to lower the burden of deploying applications directly into virtual machine (VM) containers.³⁴ In this article, the widely used 3D design and assembly software Computer Aided Three-dimensional Interactive Application (CATIA) and its corresponding secondary development platform Component Application Architecture (CAA) are added to the platform layer. The application layer is the highest layer of this cloud service architecture, mainly including the mobile 3D model application. The cloud service architecture for mobile 3D model is demonstrated in Figure 2. It includes network, product data management (PDM) database and solver. In industry, some meaningful attempts based on mobile computing platforms have been made to provide a convenient means to access information on shop floor or construction site.^38–40 Compared to these efforts, the major advantages of the proposed cloud service architecture over these systems include cost reduction, fast service provision and high service scalability promised by cloud computing.³³ Besides, the proposed cloud service architecture not only supports the end users on site to browse the desired information, like most of the existing mobile computing platforms do, but also offers the engineers with solution for the assembly process planning of complex product.

Figure 2.

The cloud service architecture for mobile 3D model.

The outline of the proposed approach is described as follows. The invisible features of current-assembled-state assembly model $A_{C}$ are detected and removed so that the appearance of the assembly model can be preserved during the simplification. As the assembly process goes on, the to-be-assembled components will be assembled with $A_{C}$ successively. For the sake of complexity reduction, the currently selected to-be-assembled component should be simplified with assembly features preserved before the assembly operation. Here, $A_{C}$ can be regarded as a “large-scale component” which is equivalent to other to-be-assembled components. So, all the relatively independent CAD models in assembly scene can be regarded as components $C_{i}$ ( $0 \leq i \leq n_{R}$ , where $n_{R}$ is the number of the to-be-assembled components and $C_{0} : = A_{C}$ ). In order to simplify the currently selected to-be-assembled component while keeping its assembly features, the notion of “conjugation” is incorporated into the definition of assembly features; subsequently, the attributed adjacency graphs (AAGs) of every $C_{i}$ are established; the assembly features are automatically recognized by searching conjugated subgraphs between every two AAGs using MR; then, simplified component with assembly features preserved is constructed after suppressing the common form features. The simplified component assembles with $A_{C}$ , and the assembly state is updated so that the next assembly operation could carry on.

Assembly model simplification with appearance preservation

The invisible features of current-assembled-state assembly model $A_{C}$ are detected and removed so that the appearance of the assembly model can be preserved during the simplification, and it is an important step to demonstrate the growth process of a dynamic assembly.

Kanai et al.¹² detected invisible features by pre-rendering the models from multiple view directions and reading the rendered results from the frame buffer. Despite the method is simple and effective, pre-processing is required, that is, it needs to generate mesh models per component of the assembly by tessellating surfaces of the CAD models and pre-render the mesh models based on OpenGL. However, as mentioned above, the triangular meshing of original CAD model is time-consuming and will change its format and cause data loss. Therefore, improvements on the invisible features detection method have been made so that it can be applied to the B-Rep CAD models directly. (Kanai et al.¹² could not directly access the frame buffer of a CAD system so that format conversion of CAD model is required, while the authors can access the frame buffer of the current mainstream CAD systems (e.g. CATIA, UG, Pro-E) since they have accumulated rich experience in the secondary development of these CAD systems.) The procedure to determine the visibility of the features in an assembly consists of the following three steps, which are viewpoints setting, information extraction of rendering results and visibility determination.

Step 1. Initialize the positions and directions of a set of viewpoints (see Figure 3) and assign an ID and color to each feature (recognized by form feature recognition method⁴¹) of $A_{C}$ .

Step 2. Render each feature and $A_{C}$ at each viewpoint. In order to extract the rendering results, $P_{α}^{β}$ and $Q_{α}^{β}$ are defined as the number of pixels with αth feature’s color when the feature and $A_{C}$ are rendered at βth viewpoint, respectively, as shown in Figure 4.

Step 3. According to the rendering results of every viewpoint, the maximum exposure rate of αth form feature among all view is calculated by $F_{α}^{visible} = max {Q_{α}^{β} / P_{α}^{β}}$ . If $F_{α}^{visible} < η$ (where $η$ is the threshold of visibility), then the feature is determined as invisible.

Figure 3.

Viewpoints setting.

Figure 4.

Information extraction of rendering results: (a) $P_{α}^{β}$ and (b) $Q_{α}^{β}$ .

If a feature is determined as invisible, it means that this feature has been occluded by other components or features, and there will be no barrier-free path for a to-be-assembled component to access the feature to complete the assembly process with it. In other words, an invisible feature either has completed the assembly process with some component or it will not form assembly features with any other form features.

However, it should be pointed out that the invisible features which are the reference features to other visible features need to be preserved, that is, an invisible feature can only be suppressed in condition that it will not cause geometric invalidation to other visible features after removing the invisible feature. An invisible feature is determined if it is suppressible based on its dependency chain, which is an array storing the features depending on this invisible feature.

A dependency matrix of adjacent features for every component is first established by extracting the geometry information of corresponding CAD model, denoted as $D_{n \times n}$ , where $n$ is the feature number on the corresponding component. $d_{uv} (1 \leq u, v \leq n)$ is the element of $D_{n \times n}$ , and

d_{uv} = {\begin{matrix} 1, & if the v th feature depends on u th feature \\ 0, & otherwise \end{matrix}

Since a feature usually has dependency relationship with only a few adjacent features, the dependency matrix $D_{n \times n}$ of one component is a sparse matrix. The dependency chain of uth feature of a component $C_{D}^{u}$ is calculated by

\begin{matrix} C_{D} = D_{n \times n} + D_{n \times n}^{2} + \dots + D_{n \times n}^{n} \\ C_{D}^{u} = {(C_{D})}^{T} \times {[\begin{matrix} 0 & 0 & \dots & 1 & \dots & 0 & 0 \end{matrix}]}^{T} \end{matrix}

If the uth feature of a component is invisible, and there is no visible features in its dependency chain $C_{D}^{u}$ , then the uth feature is suppressible, otherwise it cannot be suppressed or deleted. For example, in Figure 5, the dependency matrix $D_{3 \times 3}$ is

D_{3 \times 3} = [\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}]

And the dependency chain of all the features is

C_{D} = D_{3 \times 3} + D_{3 \times 3}^{2} + D_{3 \times 3}^{3} = [\begin{matrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}]

So, the dependency chain of feature f1 can be obtained by

C_{D}^{1} = {(C_{D})}^{T} \times {[\begin{matrix} 1 & 0 & 0 \end{matrix}]}^{T} = {[\begin{matrix} 0 & 1 & 1 \end{matrix}]}^{T}

It shows that the invisible feature f2 and visible feature f3 are in the dependency chain of feature f1; therefore, the invisible feature f1 cannot be suppressed.

Figure 5.

(a) Assembly model, (b) the cross-sectional view of the assembly model and (c) dependency relationship among the features.

Repeat the above operation until all the suppressible invisible features of $A_{C}$ are labeled. By suppressing the suppressible invisible features of $A_{C}$ , the data volume of the dynamic assembly will not increase dramatically as the assembling progresses.

CAD model simplification with assembly features preservation

This section focuses on the simplification of currently selected to-be-assembled component $C_{i}$ . A good definition of assembly features should be compact and instructive for downstream applications such as assembly features recognition and preservation. The notion of “conjugation” is incorporated into the definition in order to find the mating subgraphs between the AAG $G_{i}$ corresponding to $C_{i}$ and other AAGs $G_{j} (0 \leq j \leq n_{R}, j \neq i)$ accurately and efficiently.

Assembly features definition and representation

Features are generic shapes useful in some computer-aided applications,⁴² and assembly features are essentially the connections between form features. So, discarding all the additional constraints, the core of assembly features is mating relation of two form features on different components of an assembly. There are more than 20 kinds of mating relations. But for the sake of stability and economy, mating relations can be roughly divided into “Against” (see Figure 6(a) and (d)) and “Fit” (see Figure 6(b), (c), (e) and (f)).^43,44 In general, a class of mating relations usually has several subclasses. For instance, rib-slot in Figure 6(b) and pin-hole in Figure 6(c) are the subclasses of “Fit.” Meanwhile, every subclass of mating relations can derive many subinstances from its own basic instance. For example, the plane–plane type of “Against” mating relation in Figure 6(a) can derive surface–surface type in Figure 6(d), dovetail rib-slot in Figure 6(e) is derived from square rib-slot in Figure 6(b) and round pin-hole in Figure 6(c) can derive rectangular pin-hole in Figure 6(f). By analyzing these instances of mating relations, it shows that the mating areas of the components are similar in topology but have contrary concave–convex property. Based on this observation, the notion of “conjugation” is incorporated into the definition of assembly features. Conjugation, whose original meaning is the “yoke” upon two bulls in order to keep their footsteps consistent,⁴⁵ is the mating pair according to certain pattern, or, in other words, is coupled. So, assembly features are defined as “the conjugated mating relation between two form features on different components of an assembly.”

Figure 6.

Assembly mating relations: (a) plane-plane, (b) square rib-slot, (c) round pin-hole, (d) surface-surface, (e) dovetail rib-slot, and (f) rectangular pin-hole.

AAG can effectively express B-Rep CAD model, and conjugated subgraphs between two AAGs represent the assembly features. Converting the CAD models into AAGs is the precondition for assembly features recognition using graph-based methods. In order to represent component $C_{i}$ of a given assembly, a labeled graph $G_{i} = (V_{i}, E_{i}, α (V_{i}), β (E_{i}))$ is defined here, where $(V_{i}, E_{i})$ is a simple undirected graph;⁴⁶ $V_{i} = {v_{i 1}, v_{i 2}, \dots, v_{in}}$ is the node set of $G_{i}$ , where node $v_{ik}$ is the kth face of component $C_{i}$ ; $E_{i} = {e_{i 1}, e_{i 2}, \dots, e_{im}} \subseteq V_{i} \times V_{i}$ is the edge set of $G_{i}$ , where $e_{ik}$ is the edge linking nodes $v_{ik}$ and $v_{il}$ , that is, $e_{ik}$ represents that there exists adjacency relation between the kth and lth faces of component $C_{i}$ ; $α (v_{ik})$ denotes the attributes associated to $v_{ik}$ ; and $β (e_{ik})$ is the attributes associated to $e_{ik}$ .

For every component of an assembly, search every face and create a node correspondingly; extract the geometric and engineering semantics information of each face, such as surface type (plane or curve surface), normal vector, region area (or radius of curvature for curve surface), surface roughness and so on, and associate them to the corresponding node. For every two faces, acquire their relationship (i.e. concavity) and set it as the edge attribute.

Conjugated subgraphs have the following characteristics (Figure 7). (1) Conjugated subgraphs are isomorphic with each other. (2) The attributes of corresponding nodes are mostly identical except the normal vector, that is, the surface types are identical, the directions of normal vectors are opposite, region areas are the same (not mandatory) or the radii of curvature for curve surfaces are equal, the corresponding surface roughness of mating surfaces should meet the dimensioning and tolerancing standard⁴⁷ and so on. (3) The concavity of corresponding edges is contrary.

Figure 7.

The conjugated subgraphs of round pin-hole: (a) an assembly of round pin-hole type, (b) the region-level representation of the assembly, and (c) the corresponding AAGs.

Assembly features recognition based on MR

As stated in section “Introduction,” the problem of assembly features recognition is translated into the problem of conjugated subgraphs matching. Specifically, given the currently selected to-be-assembled component $C_{i}$ , the form features of this component are recognized using the graph-based method,⁴¹ and the AAGs of these form features are a series of subgraphs (the pattern graphs) of the AAG corresponding to this component. Finding form features on other components $C_{j} (j \neq i)$ to form assembly features with the form features on component $C_{i}$ is essentially finding subgraphs isomorphic with the pattern graphs in the AAGs (the target graphs) of components $C_{j}$ . The definition of subgraph isomorphism is given as follows. Given two graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ , if there is a bijection function $f : V_{1} \to V_{2}$ such that $\forall u, v \in V_{1}, (u, v) \in E_{1}$ if and only if $(f (u), f (v)) \in E_{2}$ , then $G_{1}$ and $G_{2}$ are called graph isomorphism, denoted by $G_{1} ≅ G_{2}$ . If $G'_{2} \subseteq G_{2}$ and $G_{1} ≅ G'_{2}$ , then $G_{1}$ and $G_{2}$ are called subgraph isomorphism.

In graph theory, walk, tree and subgraph are usually used to represent the intrinsic characteristics of a graph. Walk is a simple and effective representation for the graphs which are simple in topology. The assembly features are usually simple in shape in consideration of stability and economy. Therefore, walk is suitable to represent the graphs of assembly features. Define $W = (v_{0}, e_{0}, v_{1}, \dots, e_{k - 1}, v_{k})$ as a walk through graph $G = (V, E, α (V), β (E))$ , where $e_{i} = {v_{i}, v_{i + 1}} \in E$ and $(v_{i}, e_{i}, v_{i + 1})$ is a step of walk $W$ . A walk is called a path if all the edges are nonidentical to each other. A path with no repeated nodes is called a simple path. The walk in this article is ordinary walk which may have repeated edges and nodes. Let $W_{p} = (v_{0}^{p}, e_{0}^{p}, v_{1}^{p}, \dots, e_{k - 1}^{p}, v_{k}^{p})$ and $W_{t} = (v_{0}^{t}, e_{0}^{t}, v_{1}^{t}, \dots, e_{k - 1}^{t}, v_{k}^{t})$ be the walks through $G_{p}$ and $G_{t}$ , respectively. If step $(v_{i}^{p}, e_{i}^{p}, v_{i + 1}^{p})$ of $W_{p}$ and step $(v_{i}^{t}, e_{i}^{t}, v_{i + 1}^{t})$ of $W_{t}$ satisfy the conditions that $α (v_{i}^{p})$ and $α (v_{i}^{t})$ , and $α (v_{i + 1}^{p})$ and $α (v_{i + 1}^{t})$ meet Characteristic 2 of conjugated subgraphs and $β (e_{i}^{p})$ and $β (e_{i}^{t})$ meet Characteristic 3, then $G_{p}$ and $G_{t}$ are called conjugated subgraphs.

MR is a parallel programming paradigm and software framework for cloud computing. Computation in MR is divided into two major phases called map and reduce, separated by an internal grouping of the intermediate results.⁴⁸ This two-phase computation was developed after recognizing that many different computations could be solved by first computing a partial result (map phase) and then combining those partial results into the final result (reduce phase).⁴⁹ This framework automatically provides common services for parallel computing, such as the partitioning of the input data, scheduling, monitoring and intermachine communication necessary for remote execution. Users only need to design the serial map and reduce functions for specific applications,^49,50 while the data parallel processing can be handled using the functions encapsulated in a library (e.g. Message Passing Interface (MPI) or Hadoop library) since the data processing is independent of specific applications. Figure 8 demonstrates the execution process of MR. According to the number of the worker machines, the input data are divided into pieces and represented in the format of $〈 key, value 〉$ pairs, which are processed by map function to generate a set of intermediate $〈 key, value 〉$ pairs. The reduce function reads the intermediate $〈 key, value 〉$ pairs and merges all the intermediate values with the same key.

Figure 8.

The execution process of MapReduce.

MR-based graph algorithms are mainly used to analyze large-scale graphs, which are categorized into two types, that is, a single large graph and a large set of small graphs. Current MR-based graph algorithms are either designed for a single large graph^50,51 or large set of small graphs.⁵² This article needs to discuss the graph algorithm both for a single large graph $G_{0}$ corresponding to current-assembled-state assembly model $A_{C}$ and a large set of small graphs $G_{i}$ corresponding to the to-be-assembled components $C_{i}$ . In order to improve the efficiency of searching conjugated subgraphs between the large graph $G_{0}$ and the large graph set $G_{i}$ , $G_{0}$ is preprocessed using filter algorithm⁵³ to reduce its search space.

The filter algorithm for reducing the search space of $G_{0}$

Constraint satisfaction problem (CSP) is expressed as $P = (X, D, C)$ , where $X = {x_{1}, x_{2}, \dots, x_{n}}$ is the variable set, $D = {D (x_{1}), D (x_{2}), \dots, D (x_{n})}$ contains the respective domains for the variables in $X$ and $P$ should subject to constraint set $C$ .⁵⁴ Zampelli et al.⁵⁵ formulated the subgraph isomorphism problem as CSP, that is, variable $x_{u}$ is associated with every node $u$ of the pattern graph $G_{p}$ , and its domain $D (x_{u})$ is the node set of target graph $G_{t}$ ; this CSP should meet the AllDiff constraint, which means all variables in this constraint must be pairwise different.

The concept of CSP is adopted to the filter algorithm. Define labeling $l$ as $l = (L, \underline{≺}, α)$ , where $L$ is the attribute set (e.g. the node degree, the geometric and engineering semantics information of CAD model) associated to the nodes; $\underline{≺} \subseteq L \times L$ is a partial order on $L$ and function $α$ assigns label $α (u)$ to node $u$ . Meanwhile, nodes $u \in V_{p}$ and $v \in V_{t}$ are called compatible couples if $C C_{l} = {(u, v) \in V_{p} \times V_{t} | α (u) \underline{≺} α (v)}$ . Using the compatibility relation between the nodes of $G_{p}$ and $G_{t}$ , the domain of a variable associated with a node $u$ of $G_{p}$ can be filtered by removing from it every node $v$ of $G_{t}$ if $(u, v) \notin C C_{l}$ . The node degree is used as filtering label because of its ease of calculation, that is, $l_{\deg} = (N, \leq, \deg)$ , while the geometric and engineering semantics information of CAD model is mainly used in the conjugated subgraphs matching process, as described in Algorithm 2 in section “Conjugated subgraphs matching based on MR.” The filtering effect of node degree as the label of one node is strengthened by adding information from the node degree of the neighbors.⁵³ Define $l' = (L, \underline{≺}', α')$ as the neighborhood extension of labeling $l = (L, \underline{≺}, α)$ , where $L' = L \cdot (L \to N)$ , $α' (v) = α (v) \cdot m$ and $m = # {u | (u, v) \in E \land α (u) = l_{i}}$ ; the partial order on the extended labels of $L'$ is decided by $l_{1} \cdot m_{1} \underline{≺}' l_{2} \cdot m_{2}$ iff $l_{1} \underline{≺} l_{2} \land m_{1} \underline{≺} m_{2}$ ( $m_{1} \underline{≺} m_{2}$ iff for every element of $m_{1}$ there exists a different element of $m_{2}$ which is greater or equal). The filter algorithm is described in Algorithm 1.

Algorithm 1 Filter the large-scale target graph for the pattern graph in terms of node degree
Input: Pattern graph $G_{p} = (V_{p}, E_{p})$ and target graph $G_{t} = (V_{t}, E_{t})$ .
Output: Filtered domain for the pattern graph.
1: Initialize the labeling $l^{0} = (L^{0}, {\underline{≺}}^{0}, α^{0})$ and the domain of pattern graph $D : V_{p} \to P (V_{t})$ .
2: for every node $u \in V_{p}$ do: $D (u) \leftarrow D (u) \cap {v \in V_{t} \| α^{0} (u) {\underline{≺}}^{0} α^{0} (v)}$
3: $i \leftarrow 1$
4: while $\forall u \in V_{p}$ , $D (u) \neq \emptyset$ do
5: for every node $u \in V_{p} \cup V_{t}$ do
6: $m_{u}^{i} \leftarrow multiset containing an occurrence of a^{i - 1} (v)$ , $\forall (u, v) \in E_{p} \cup E_{t}$
7: $α^{i} (u) \leftarrow α^{i - 1} (u) \cdot m_{u}^{i}$
8: $L^{i} \leftarrow {α^{i} (u) \| u \in V_{p} \cup V_{t}}$
9: ${\underline{≺}}^{i} \leftarrow {(α^{i} (u), α^{i} (v)) \| u \in V_{p} \land v \in D (u) \land test (m_{u}^{i}, m_{v}^{i}, {\underline{≺}}^{i - 1})}$
10: for every node $\forall u \in V_{p}$ do: $D (u) \leftarrow D (u) \cap {v \in V_{t} \| α^{i} (u) {\underline{≺}}^{i} α^{i} (v)}$
11: $i \leftarrow i + 1$
12: return $D$ , i.e. the filtered target graph ${G_{t}}^{'}$

First, calculate the node degree of every node of $G_{p}$ and $G_{t}$ and set $V_{t}$ as the domain of every node of $G_{p}$ (Line 1). According to the node degree of $G_{p}$ and $G_{t}$ , filter the domain of every node of $G_{p}$ (Line 2). Add the information from the node degree of the neighbors (Line 6), that is, add one node the node degrees of its neighbors (Line 7), so that the filtering effect of node degree as the label is extended (Lines 8–10). The output of Algorithm 1 is the filtered domain of $G_{p}$ , that is, the simplified graph $G'_{t}$ of $G_{t}$ with certain nodes and edges deleted. As stated in section “Cloud service architecture for mobile 3D model,” the scale of $G_{p}$ usually is relatively small compared to $G_{0}$ , whose filtered version $G'_{0}$ will become much smaller. Consequently, the search space will reduce dramatically when searching conjugated subgraphs between $G_{0}$ and graph set $G_{i}$ . The influence of the filter algorithm applied to $G_{0}$ on the efficiency of the proposed approach will be discussed in section “Results and analysis.”

Conjugated subgraphs matching based on MR

The MR-based assembly features recognition algorithm is shown in Algorithm 2. This algorithm needs to deal with two kinds of objects: the walks through the target graphs and the steps forming walks. Walks and steps are all represented with $〈 key, value 〉$ pairs. The last node ID is the key of a walk, and all other node IDs and attributes associated with the nodes are stored in the value. A step is composed of an edge and its two nodes. The key of a step is the ID of its first node, and the value stores the ID of second node and all other attributes attached to the step.

Algorithm 2 Assembly features recognition based on MapReduce
Input: The AAG $G_{i}$ corresponding to the currently selected to-be-assembled component $C_{i}$ , all the other AAGs $G_{j} (0 \leq j \leq n_{R}, j \neq i)$ .
Output: The AAG $G_{i}$ with all the assembly features labeled.
1: Decompose $G_{i}$ and the series of subgraphs $s g_{k} (1 \leq k \leq N_{i})$ are the form features of $G_{i}$
2: Express every subgraph $s g_{k}$ as walk $W_{Pk}$
3: Establish the step set $S_{j}$ for every AAG $G_{j} (1 \leq j \leq n_{R}, j \neq i)$ if its step set does not exist
4: for every walk $W_{Pk}$ do
5: Execute the filtering algorithm for the corresponding subgraphs $s g_{k}$ and $G_{0}$
6: Establish the step set $S_{0}$ for the filtered graph ${G_{0}}^{'}$
7: for every step set $S_{j} (0 \leq j \leq n_{R}, j \neq i)$ do
8: Read a step $s_{j}^{l}$ from $S_{j}$ . If it matches the first step $(v_{pk}^{0}, e_{pk}^{0}, v_{pk}^{1})$ from $W_{Pk}$ , then add $s_{j}^{l}$ to the candidate walk and emit
9: for $t \leftarrow 2$ to $k$ do
10: Mapper:
11: Read a step $s_{j}^{l}$ from $S_{j}$ . If it matches the step $(v_{pk}^{t - 1}, e_{pk}^{t - 1}, v_{pk}^{t})$ from $W_{Pk}$ , then emit the step
12: Read a candidate walk from the most recent MapReduce output and emit
13: Collate:
14: Place the candidate walk ahead of the matching step
15: Reducer:
16: Append the most recent matched step to the candidate walk of length $t - 1$ to generate a candidate walk of length $t$ and emit
17: Label all the form features on $C_{i}$ as assembly features if their corresponding walks have found matched walks on other components

First, decompose $G_{i}$ and obtain a series of subgraphs $s g_{k}$ ,⁴¹ where $1 \leq k \leq N_{i}$ , and $N_{i}$ is the number of form features on the currently selected to-be-assembled component $C_{i}$ (Line 1). Then, express $s g_{k}$ as walk $W_{Pk}$ (Line 2). Establish the step set $S_{j}$ for every AAG $G_{j} (1 \leq j \leq n_{R}, j \neq i)$ if its step set does not exist, that is, every edge of $G_{j}$ corresponds to a step in the step set $S_{j}$ (Line 3). As for $G_{0}$ , get its filtered version $G'_{0}$ by applying the filtered algorithm Algorithm 1 to $s g_{k}$ and $G_{0}$ and establish the step set $S_{0}$ for $G'_{0}$ (Lines 4–6). For every walk $W_{Pk}$ of $G_{i}$ , find matched walk(s) in step set $S_{j} (0 \leq j \leq n_{R}, j \neq i)$ (Lines 7–16). Or in other words, find conjugated subgraphs in $G_{j} (0 \leq j \leq n_{R}, j \neq i)$ for the subgraph $s g_{k} (1 \leq k \leq N_{i})$ of $G_{i}$ . Specifically, read a step $s_{j}^{l}$ from $S_{j}$ and test if it matches the first step $(v_{pk}^{0}, e_{pk}^{0}, v_{pk}^{1})$ of walk $W_{Pk}$ , that is, if the corresponding nodes satisfy Characteristic 2 and the corresponding edges satisfy Characteristic 3. Add $s_{j}^{l}$ to the candidate walk and emit if $s_{j}^{l}$ matches $(v_{pk}^{0}, e_{pk}^{0}, v_{pk}^{1})$ (Line 8). For the rest of the steps of $W_{Pk}$ , similarly, find matched steps from $S_{j}$ gradually (Lines 9–11). Collate the intermediate output of the reduce phase by placing the candidate walk ahead of the matching step (Line 14). Append the most recent matched step to the candidate walk of length $t - 1$ to generate a candidate walk of length $t$ and emit (Line 16). Repeat the matching operation for all the form features on currently selected to-be-assembled component $C_{i}$ .

The implementation of assembly features recognition and preservation

This section details the procedure of assembly features recognition and preservation using conjugated subgraphs matching method described in section “Assembly features recognition based on MR” as follows:

Step 1. As stated in section “Introduction,” construct the AAGs of simplified current-assembled-state assembly model $A_{C}$ and to-be-assembled components $C_{i}$ , expressed as $G_{i}$ ( $0 \leq i \leq n_{R}$ , where $n_{R}$ is the number of the to-be-assembled components and $G_{0}$ is the AAG corresponding to $A_{C}$ ), as shown in Figure 7(c). A form features set $F_{s}$ is defined here, which is used to store the features that need to be suppressed.

Step 2. Apply Algorithm 2 in section “Conjugated subgraphs matching based on MR” to recognize the assembly features on the currently selected to-be-assembled component $C_{i}$ . All other form features on $C_{i}$ which are not labeled as assembly features are put into set $F_{s}$ . Note that there may be features which are conjugated with a form feature $F_{i}^{*}$ on $C_{i}$ but cannot mate with it to form assembly features. For example, in Figure 9, Slots 1 and 2 are both conjugated with Rib 1, but Rib 1–Slot 2 cannot form assembly features. In order to ensure the uniqueness and effectiveness of the mating feature of $F_{i}^{*}$ , much more engineering semantics information of the CAD model is extracted (including the size, form, orientation and positional tolerances of the mating surfaces) to eliminate those features which are conjugated with $F_{i}^{*}$ but cannot mate with it to form assembly features, and a few interactions may be also necessary.

Step 3. Suppress the features in set $F_{s}$ ^15,56 and assemble the simplified component $C_{i}$ with $A_{C}$ to generate a new $A_{C}$ . Execute the appearance-preserving simplification described in section “Assembly model simplification with appearance preservation” on the new $A_{C}$ .

Step 4. Update $G_{0}$ with the AAG of the new $A_{C}$ and repeat Step 2 until all the components have been assembled.

Figure 9.

The uniqueness of the assembly mating relation.

Results and analysis

Experimental setup

The experiments were performed on a three-node cluster. Each node is a HP Z820 station equipped with two 2.0 GHz Intel Xeon Hexa-core E5-2620 processors, 16 GB memory and 1 TB disk, running on 64-bit Windows 7. All these nodes are connected via a Gigabit switching hub. And CATIA is installed on one of the three stations to intuitively demonstrate the virtual assembly process using the proposed dynamic assembly simplification approach.

Based on CAA, which can integrate an algorithm or solution into CATIA system seamlessly, the proposed approach has been implemented as a C++ program using the MR-MPI library,⁵⁷ and a module has also been developed to test it on several CAD assembly models.

Assembly model simplification with appearance preservation

In Figure 10, the proposed assembly model simplification method with appearance preservation has been tested on a CAD assembly model of HP engine. First, the number of viewpoints $N_{vp}$ and the threshold of visibility $η$ are initialized, as shown in Figure 11(a). In order to acquire balanced amount of rending results to determine the visibility of features, $N_{vp}$ should satisfy $N_{vp} = 3 e_{p} + 2$ , where $e_{p}$ is the edge number of the polygon constructed by the viewpoints at the second level (or third or fourth) (see Figure 3). The parameters are as follows: $N_{vp} = 20$ ( $e_{p} = 6$ ) and $η = 0.1$ (see Figure 11(a)). The simplification result is demonstrated in Figure 11(b). It demonstrates that the CAD assembly model of HP engine is simplified by removing the invisible features, and the appearance of the engine is preserved well.

Figure 10.

CAD assembly model of HP engine.

Figure 11.

CAD model simplification with appearance preservation: (a) parameters setting and (b) the simplification result.

CAD model simplification with assembly features preservation

Given an assembly model (see Figure 12(a)), in order to demonstrate the mating relations of the components clearly, the simplification with assembly features preservation is carried out under exploded view (see Figure 12(b)). First, the geometric and engineering semantics information of the CAD models is extracted to construct the corresponding AAGs, and every face of the models is marked as shown in Figure 12(b). For the sake of efficiency, the blending features and other detail features (the deep pink features in Figure 12(b)) are pre-suppressed. The intermediate state of final simplification is shown in Figure 12(c). The proposed assembly features recognition method is applied to the models in Figure 12(c), and the assembly features are located and marked as yellow. Figure 12(d) shows the final simplification result with assembly features preservation after suppressing the common form features.

Figure 12.

The simplification result: (a) the original CAD models of an assembly in its mating view, (b) the exploded view of the assembly, (c) simplification results after suppressing the blending features and other detail features, and (d) the models are simplified using the proposed simplification method with assembly features preservation.

The simplification degree of the CAD models is an important criterion by which to judge the effectiveness of the simplification method. In Figure 12(a), the original CAD models have 235 faces. After deleting the blending features and other detail features, the number of faces is reduced by 48.1%, and that is 122 faces, as shown in Figure 12(c). The number of faces drops to 96 after further suppressing the common form features (see Figure 12(d)). It confirms that the blending features dramatically increase the data volume of CAD models.¹⁵ On the contrary, the assembly features are usually simple in shape in consideration of stability and economy. So, it will not increase the complexity of the CAD models too much if the assembly features are preserved. More examples are demonstrated in Figure 13.

Figure 13.

Simplification of different assemblies: (a) assembly 1 and (b) assembly 2.

The performance analysis of assembly features recognition

Further experiments and analysis are required to test the efficiency of assembly features recognition method based on MR. Let the AAGs of Feature 1 in Figure 14(a) and Feature 3 in Figure 14(b) be $G_{p}^{1}$ and $G_{p}^{3}$ , respectively, and note that $G_{t}^{2}$ and $G_{t}^{4}$ are the AAGs of dynamic assemblies (actually, the dynamic assembly mentioned here is incomplete and it excludes the component containing Feature 1 in Figure 14(a) or Feature 3 in Figure 14(b)) containing Feature 2 in Figure 14(a) and Feature 4 in Figure 14(b), respectively. Assembly features recognition in Figure 14 is finding the subgraphs (i.e. the AAGs corresponding to Feature 2 and Feature 4) of $G_{t}^{2}$ and $G_{t}^{4}$ conjugated with $G_{p}^{1}$ and $G_{p}^{3}$ , respectively.

Figure 14.

Assembly features recognition: (a) Part 1-DA 1 and (b) Part 2-DA 2.

For the assembly features recognition problem in Figure 14, Table 1 shows the comparison of performances between the algorithm using the divide-and-conquer strategy²⁷ and the proposed assembly features recognition approach. In order to explore the concrete relationship between the matching time and the complexity of the to-be-matched component (here, it refers to a dynamic assembly), suppose the face number of a given form feature (e.g. Feature 1 or Feature 3) is fixed and progressively increase the face number of the to-be-matched component DA 1 or DA 2 and record the corresponding matching time to find assembly features. The face number of the to-be-matched component increases as it keeps growing to the final-completely-assembled state. As shown in Figure 15, when the face number of the to-be-matched component $| V_{t} |$ is relatively small, the proposed approach based on MR does not perform much better than the divide-and-conquer-based algorithm, only costing 2.04% and 8.33% less of time for State 1 of Part 1-DA 1 and Part 2-DA 2, respectively. However, as $| V_{t} |$ increases, it would cost much less time to complete the matching process by employing the proposed approach other than the divide-and-conquer-based algorithm. It indicates that using the filter algorithm to reduce the search space of the large-scale graph and adopting the characteristics of conjugated subgraphs during the conjugated subgraphs matching process can improve the efficiency of assembly features recognition.

Table 1.

Results obtained by the algorithm using the divide-and-conquer strategy and the proposed approach.

Assembly		Face number of feature/assembly	Matching time/ms		$\frac{T_{2} - T_{1}}{T_{1}}$ (%)
		Face number of feature/assembly	T₁ (the proposed approach)	T₂ (the divide-and-conquer–based algorithm)	$\frac{T_{2} - T_{1}}{T_{1}}$ (%)
Part 1-DA 1	State 1	3/51	2.94	3.00	2.04
	State 2	3/298	13.52	17.38	28.55
	State 3	3/601	20.09	28.11	39.92
Part 2-DA 2	State 1	7/26	1.32	1.43	8.33
	State 2	7/555	36.02	44.23	22.79
	State 3	7/709	50.27	60.34	20.03

Figure 15.

The relationship between the matching time and the complexity of to-be-matched component.

Conclusion

With the purpose of demonstrating and interacting with the virtual assembly process of complex product in real time and delivering the 3D-based assembly process information to assembly field, this article proposes a cloud service architecture for mobile 3D model and a dynamic assembly simplification method in cloud computing environment. The current-assembled-state assembly model is simplified by removing the invisible features while preserving its appearance; the to-be-assembled component model is simplified with assembly features well preserved so that it can complete the assembly process more smoothly in 3D virtual assembly scene. The problem of assembly features recognition is translated into conjugated subgraphs matching. In order to improve the efficiency of conjugated subgraphs matching among the AAG of the currently selected to-be-assembled component, the large-scale AAG corresponding to the current-assembled-state assembly and a large set of small AAGs corresponding to the rest of the to-be-assembled components, a filter algorithm is introduced based on the idea of constraint programming to reduce the search space of the large-scale AAG. Meanwhile, the serial code of conjugated subgraphs matching is parallelized by using MR. Experiments illustrate the superiority of the proposed approach over the algorithm using the divide-and-conquer strategy.

The proposed cloud service architecture for mobile 3D model and dynamic assembly simplification method present a feasible solution for mobile 3D model on assembly field of complex product, which would facilitate the assembly task, shorten the design cycle and reduce the cost.

However, the current research is limited in several ways. First, the goals of all the stakeholders (architecture builder, cloud service users, etc.) of the proposed cloud service architecture are often conflicting. For example, performance of the architecture is the major concern of the end users, while the architecture builder or provider is mostly interested in cost reduction, and these two goals (or concerns) are competing and conflicting. Further work will focus on analyzing the most appropriate trade-offs among goals of stakeholders by using the goal-oriented simulation approach⁵⁸ to further refine the detail design (mainly at the infrastructure layer) of the proposed cloud service architecture. Second, more experiments are needed to justify the superiority of the proposed approach. Limited kinds of experimental environments have been established at this stage. And it will be necessary to consider the possibility of adopting the cloud computing simulation tool CloudSim to set up more homogeneous experimental environments.

Footnotes

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

The authors would like to thank the Basic Research Foundation of Northwestern Polytechnical University (Grant No. JC201137) and National Key Technology R&D Program for financially supporting this research.

References

Silva

Rodrigues

MAF

. A lightweight 3D visualization and navigation system on handheld devices. In: Proceedings of the 2009 ACM symposium on applied computing, Honolulu, HI, 8–12 March 2009, pp.162–166. New York: ACM.

Chen

Kamara

. A framework for using mobile computing for information management on construction sites. Automat Constr 2011; 20: 776–788.

Gobbetti

Kasik

Yoon

. Technical strategies for massive model visualization. In: Proceedings of the 2008 ACM symposium on solid and physical modeling, Stony Brook, NY, 2–4 June 2008, pp.405–415. New York: ACM.

Thakur

Banerjee

Gupta

. A survey of CAD model simplification techniques for physics-based simulation applications. Comput Aided Design 2009; 41: 65–80.

Quintana

Rivest

Pellerin

. Will Model-based Definition replace engineering drawings throughout the product lifecycle? A global perspective from aerospace industry. Comput Ind 2010; 61: 497–508.

Qiu

Wong

Fuh

. Geometric model simplification for distributed CAD. Comput Aided Design 2004; 36: 809–819.

Zhu

Hyyppä

Chen

. An approach of 3D model simplification for mobile phone based navigation application. In: Ubiquitous positioning indoor navigation and location based service (UPINLBS), Kirkkonummi, 14–15 October 2010, pp.1–4. IEEE: New York.

Yang

Choi

Lee

. CAD data visualization on mobile devices using sequential constrained Delaunay triangulation. Comput Aided Design 2009; 41: 375–384.

Yang

Choi

. Triangulation of CAD data for visualization using a compact array-based triangle data structure. Comput Graph 2010; 34: 424–429.

10.

SIEMENS. JT Open, http://m.plm.automation.siemens.com/en_us/products/open/jtopen/ (accessed 31 January 2014).

11.

Wakita

Yajima

Harada

. XVL: a compact and qualified 3D representation with lattice mesh and surface for the internet. In: Proceedings of the fifth symposium on virtual reality modeling language (Web3D-VRML), Monterey, CA, 20–24 February 2000, pp.45–51. New York: ACM.

12.

Kanai

Iyoda

Endo

. Appearance preserving simplification of 3D CAD model with large-scale assembly structures. Int J Interact Des Manuf 2012; 6: 139–154.

13.

Venkataraman

Sohoni

Rajadhyaksha

. Removal of blends from boundary representation models. In: Proceedings of the seventh ACM symposium on solid modeling and applications, Saarbrucken, 17–21 June 2002, pp.83–94. New York: ACM.

14.

Venkataraman

Sohoni

Elber

. Blend recognition algorithm and applications. In: Proceedings of the sixth ACM symposium on solid modeling and applications, Ann Arbor, MI, 4–8 June 2001, pp.99–108. New York: ACM.

15.

Zhu

Menq

. B-Rep model simplification by automatic fillet/round suppressing for efficient automatic feature recognition. Comput Aided Design 2002; 34: 109–123.

16.

Lee

J-H

Kim

. A cellular topology-based approach to generating progressive solid models from feature-centric models. Comput Aided Design 2004; 36: 217–229.

17.

Lee

. A CAD–CAE integration approach using feature-based multi-resolution and multi-abstraction modelling techniques. Comput Aided Design 2005; 37: 941–955.

18.

Lee

. Feature-based multiresolution modeling of solids. ACM T Graphic 2005; 24: 1417–1441.

19.

Lee

. Feature-based non-manifold modeling system to integrate design and analysis of injection molding products. J Mech Sci Technol 2009; 23: 1331–1341.

20.

Lee

. Simultaneous and incremental feature-based multiresolution modeling with feature operations in part design. Comput Aided Design 2012; 44: 457–483.

21.

Russ

. Development of a CAD model simplification framework for finite element analysis. Master Thesis, University of Maryland, College Park, MD, 2012.

22.

Koo

Lee

. Wrap-around operation to make multi-resolution model of part and assembly. Comput Graph 2002; 26: 687–700.

23.

Knödel

Hachet

Guitton

. Visualization and interaction with mobile technology. In: Proceedings of the 10th international conference on human computer interaction with mobile devices and services, Amsterdam, The Netherlands, 2–5 September 2008, pp.557–558. New York: ACM.

24.

Ericsson

Olwal

. Interaction and rendering techniques for handheld phantograms. In: Proceedings of the 2011 annual conference extended abstracts on human factors in computing systems, Vancouver, BC, Canada, 7–12 May 2011, pp.1339–1344. New York: ACM.

25.

Kamat

Martinez

Fischer

. Research in visualization techniques for field construction. J Constr Eng M 2011; 137(10): 853–862.

26.

Xiao

. CAD mesh model simplification with assembly features preservation. Sci China Inform Sci. Epub ahead of print 2013. DOI: 10.1007/s11432-013-4791-z.

27.

Xiao

. Dynamic assembly simplification for virtual assembly process of complex product. Assembly Autom 2013; 34(1): 1–15.

28.

Vecchiola

Pandey

Buyya

. High-performance cloud computing: a view of scientific applications. In: Proceedings of 10th international symposium on pervasive systems, algorithms, and networks (ISPAN), 2009, Kaohsiung, Taiwan, 14–16 December 2009, pp.4–16. New York: IEEE.

29.

Ari

Muhtaroglu

. Design and implementation of a cloud computing service for finite element analysis. Adv Eng Softw 2013; 60–61: 122–135.

30.

Kallur

Mugli

Priyadarshini

. Applications of cloud computing technology in mobile communication engineering. World J Sci Tech 2012; 2(10): 204–208.

31.

. From cloud computing to cloud manufacturing. Robot Cim: Int Manuf 2012; 28: 75–86.

32.

Cheng

Liao

. The application of cloud computing in military intelligence fusion. In: 2011 International conference on information technology, computer engineering and management sciences (ICM), Nanjing, China, 24–25 September 2011, pp.241–244. New York: IEEE.

33.

Fox

Griffith

Joseph

. Above the clouds: a Berkeley view of cloud computing. Department of Electrical Engineering and Computer Sciences. Report no. UCB/EECS-2009-28, 10 February 2009. Berkeley, CA: University of California.

34.

Zhang

Cheng

Boutaba

. Cloud computing: state-of-the-art and research challenges. J Internet Serv Appl 2010; 1: 7–18.

35.

Babcock

. Why “Private Cloud” computing is real—and worth considering. InformationWeek, 2009, www.informationweek.com/story/showArticle.jhtml?articleID=216500083 (accessed 9 May 2013).

36.

Petcu

. Portability and interoperability between clouds: challenges and case study. In: Abramowicz

Llorente

Surridge

. (eds) Towards a service-based Internet. Berlin, Heidelberg: Springer, 2011, pp.62–74.

37.

Marinescu

. Cloud computing: theory and practice. Working paper, Computer Science Division, Department of Electrical Engineering & Computer Science, University of Central Florida, Orlando, FL, 2012.

38.

Kim

Lim

Kim

. Mobile computing platform for construction site management. In: Proceedings of 28th international symposium on automation and robotics in construction, Seoul, Korea, 29 June–2 July 2011, pp.1164–1169. Eindhoven, The Netherlands: IAARC.

39.

Goose

Guven

Zhang

. Mobile 3D visualization and interaction in an industrial environment. In: HCI international 2003, Crete, 22–27 June 2003. Mahwah, NJ: Lawrence Erlbaum Associates, Inc.

40.

Hammad

Zhang

. Mobile model-based bridge lifecycle management system. Comput: Aided Civ Inf 2006; 21: 530–547.

41.

Joshi

Chang

T-C

. Graph-based heuristics for recognition of machined features from a 3D solid model. Comput Aided Design 1988; 20: 58–66.

42.

Shah

Anderson

Se Kim

. A discourse on geometric feature recognition from CAD models. J Comput Inf Sci Eng 2001; 1: 41–51.

43.

Sambhoos

Koc

Nagi

. Extracting assembly mating graphs for assembly variant design. J Comput Inf Sci Eng 2009; 9: 034501 (9 pp.).

44.

Bohez

Irfan

. Assembly features: definition, classification, and instantiation. In: International conference on emerging technologies 2006 (ICET ’06), Peshawar, Pakistan, 13–14 November 2006, pp.617–623. New York: IEEE.

45.

Wikipedia. Yoke, http://en.wikipedia.org/wiki/Yoke (accessed 9 May 2013).

46.

Brandes

Erlebach

. Network analysis: methodological foundations. Berlin, Heidelberg: Springer, 2005.

47.

ASME Y14.5M:1994. Dimensioning and tolerancing.

48.

Dean

Ghemawat

. MapReduce: simplified data processing on large clusters. Commun ACM 2008; 51: 107–113.

49.

Schatz

. BlastReduce: high performance short read mapping with MapReduce. University of Maryland, https://www.cs.umd.edu/grad/scholarlypapers/papers/MichaelSchatz.pdf (accessed 9 May 2013).

50.

Plimpton

Devine

. MapReduce in MPI for large-scale graph algorithms. Parallel Comput 2011; 37: 610–632.

51.

Plantenga

. Inexact subgraph isomorphism in MapReduce. J Parallel Distr Com 2013; 73: 164–175.

52.

Kim

S-H

Lee

K-H

Choi

. Parallel processing of multiple graph queries using MapReduce. In: The fifth international conference on advances in databases, knowledge, and data applications (DBKDA 2013), Seville, 27 January–1 February 2013, pp.33–38. New York: IARIA.

53.

Zampelli

Deville

Solnon

. Filtering for subgraph isomorphism. In: Bessière

(ed.) Principles and practice of constraint programming—CP 2007. Berlin, Heidelberg: Springer, 2007, pp.728–742.

54.

Van Hoeve

W-J

. The alldifferent constraint: a survey, http://arxiv.org/pdf/cs/0105015v1.pdf (accessed 31 January 2014).

55.

Zampelli

Deville

Solnon

. Solving subgraph isomorphism problems with constraint programming. Constraints 2010; 15: 327–353.

56.

Sun

Gao

Zhao

. An approach to B-rep model simplification based on region suppression. Comput Graph 2010; 34: 556–564.

57.

Plimpton

Devine

. MapReduce—MPI library, http://mapreduce.sandia.gov/ (accessed 9 May 2013).

58.

Chung

Hill

Legunsen

. A goal-oriented simulation approach for obtaining good private cloud-based system architectures. J Syst Software 2013; 86: 2242–2262.

Dynamic assembly simplification for virtual assembly process of complex product in cloud computing environment

Abstract

Keywords

Introduction

Cloud service architecture for mobile 3D model

Assembly model simplification with appearance preservation

CAD model simplification with assembly features preservation

Assembly features definition and representation

Assembly features recognition based on MR

The filter algorithm for reducing the search space of G 0

Conjugated subgraphs matching based on MR

The implementation of assembly features recognition and preservation

Results and analysis

Experimental setup

Assembly model simplification with appearance preservation

CAD model simplification with assembly features preservation

The performance analysis of assembly features recognition

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

The filter algorithm for reducing the search space of $G_{0}$