Document [original]

Procedia CIRP 38 ( 2015 ) 153 – 158

Available online at www.sciencedirect.com

(http://creativecommons.org/licenses/by-nc-nd/4.0/).

Peer-review under responsibility of the Programme Chair of the Fourth International Conference on Through-life Engineering Services.

doi: 10.1016/j.procir.2015.07.063

ScienceDirect

The Fourth International Conference on Through-life Engineering Services

Method for automated structuring of product data and its applications

Sebastian Adolphya,*, Hendrik Grossera, Lucas Kirscha, Rainer Starka,b

aDivision of Virtual Product Creation, Fraunhofer IPK Berlin, Germany

bChair of Industrial Information Technology, TU Berlin, Germany

* Corresponding author. Tel.: +49 (0)30 39006-216; fax: +49 (0)30 3930246. E-mail address: sebastian.adolphy@ipk.fraunhofer.de

Abstract

Product structures represent the data backbone for through-life management of complex systems. Product Lifecycle Management

(PLM) Systems are used to maintain product structures and track product changes. However, in maintenance, repair and overhaul

(MRO) product composition often is unknown when MRO service providers are not the original manufacturers. Thus, MRO

processes start with an exhaustive product diagnosis to identify elements to be maintained or replaced. Existing 3D scanning and

data post processing methods have to be improved to acquire structured product data. This paper presents a method for

automated derivation of product structures from 3D assembly models.

Peer-review under responsibility of the Programme Chair of the Fourth International Conference on Through-life Engineering Services.

Keywords: Product structure; graph theory; product data management; reverse engineering; 3D scanning

1. Introduction

Product data is essential for efficient through-life

engineering services, since it is the basis of any systematic

maintenance, repair and overhaul (MRO) planning and

operation. However, life cycle based documentation of

changes regarding product configuration, condition and

functionality is still an unsolved problem for holistic product

life cycle management approaches [1]. Consequently, MRO

service providers have to diagnose characteristics individually

for any specific product. Each life cycle stage modifies the

product structure: Stages to distinguish are design

(as-designed), production (as-produced), use (as-used), MRO

(as-maintained) and recycling (as-recycled). Change

notification is not shared in B2B and B2C networks due to

reasons of intellectual property, quitted businesses or data

conversion problems in incompatible or aging IT

infrastructure. Efficient data reconstruction or retrieval

strategies are needed for fast product diagnosis and

documentation. These strategies comprise reverse engineering

of 3D models for overhaul projects [2]. 3D models and other

product data required for MRO activities can be managed in

PLM-Systems. Today’s PLM-Systems are not restricted to the

creation of products, but can be used for spare part

management, reengineering processes, asset management and

many other MRO-tasks. The product structure forms the data

backbone of these PLM systems. Hence structured storage of

data generated within MRO activities is inevitable.

This paper deals with structuring of geometric product data

coming either from a reverse engineering or a forward CAD

modeling process within MRO processes. A method has been

developed for visually and algorithmically assisted structuring

of product models. The semiautomatic process uses a 2D-

contact graph which is derived from a 3D-model by a

neighborhood analysis to identify logical groups for building

a structure. Data transfer of structure information is performed

by a PDMXML file. Industrial benefits may be to reduce the

effort of structure management divisions within the product

engineering areas of large companies. Although this paper

addresses especially the through-life engineering topic the

solution approach is also relevant for the design stage within

the product creation process.

(http://creativecommons.org/licenses/by-nc-nd/4.0/).

Peer-review under responsibility of the Programme Chair of the Fourth International Conference on Through-life Engineering Services.

154 Sebastian Adolphy et al. / Procedia CIRP 38 ( 2015 ) 153 – 158

2. Initial situation and state of the art

Currently there is no approach for automatic identification

of product structures for 3D product models without a given

assembly structure available. If structured product data is

required within a MRO process (as described in chapter 4),

comprehensive knowledge on the respective product is needed

to manually model a proper product structure [3]. In many

cases this knowledge is not available, especially in cases of

long-life systems and for third party service contractors.

Research on Reverse Engineering and reconstruction of

mechanical products focuses on recognition of single surfaces

rather than on whole assemblies and its product structures.

Principles are based on basic primitives like spheres,

cylinders, cuboids [4] or other features and constraints [5].

Segmentation methods are used to detect edges and surfaces

[7,6]. The goal of reconstructing whole industry sites or

buildings including single object information is pursued by

Building Information Modeling (BIM) applications. Complete

elements of the structure are virtually rebuilt and component

lists can be created [8,9]. However, despite semi-automated

features for reverse engineering effort is still high [12,11,10].

For the understanding of the presented method and its

benefits regarding the current practice of generating structured

product data in MRO processes two questions have to be

answered:

1. What is the output of 3D scanning?

2. How are product structures generated?

2.1. Output of 3D scanning principles and post-processing

The result of a 3D scan is a point cloud which includes x-

,y-,z-information as well as a normal direction. Standard

software creates a mesh or polygon surface. Due to limitations

of visibility or difficult capturing of shiny or concave surfaces

the resulting mesh may be incomplete and may show artifacts.

Usually manual post-processing of these meshes with suitable

software features is performed. There are several data formats

for polygon models such as STL, PLY, OBJ or WRL. For

CAD modification a further processing step called surface

reconstruction is necessary. The results are Non-Uniform

Rational B-Spline (NURBS) surfaces.

Reverse engineering of assembly models consisting of

single parts is done as follows: First, a 3D scan of the

complete assembly is performed. Then, the physical assembly

is disassembled and 3D scans have to be made of each single

part. Finally, the resulting 3D polygon models are referenced

to the initial 3D scan. This is possible with special reference

markers that can be stickers put onto the object’s surface.

Creation of CAD assembly models is more elaborate. The

single part’s 3D polygon models have to be reverse

engineered to surface models respectively CAD parts. These

CAD parts are assembled in a CAD tool by visual comparison

with the physical model. There is no difference or advantage

to the forward engineering process. In previous research an

enhanced reverse engineering process has been presented to

automate reverse engineering of assembly models [2].

2.2. Generation of product structures

A given set of product parts can be classified and

structured in various ways. The chosen approach differs in

dependency of the intended use of the structured product data

[13]. For the generation of the initial product structure in the

begin of product life the two major rivaling perspectives in

industrial practice are those of engineering design on the one

hand and manufacturing on the other hand. Whereas designers

prefer functional oriented structures as this complies with

their mindset of thinking about products, manufacturing

favors a structure oriented on the production process. Other

stakeholders in later lifecycle phases – in particular MRO and

other services – have differing requirements on product

structures. This results in many cases in the use of different

product structures for the same system throughout its

lifecycle. Workload for creation, transformation, maintenance

and linking of these product structures cumulates in a

substantial share of the overall costs of product creation and

service.

Setting up of product structures in PLM systems is a

manual task if there is no interface to CAD system available

or if 3D product models have been generated by a reverse

engineering principle. Big companies have divisions for data

generation or modeling, product structure management in

PLM Systems and usage of data for reengineering. The

structure manager has to code single part files following the

company’s specific naming convention. Therefore he has to

set up a PLM structure template which includes main

structure nodes meaning sub-assemblies and related parts.

This template is custom made for a product and cannot easily

be transformed to another product or a variant of a product.

Then, he has to save CAD models in a proprietary file format

with a specific name and ID according to the structure

template. Afterwards he imports all CAD files into the PLM

system and stores them as datasets. For visualization he has to

create additional files such as JT files form the proprietary

files either with the CAD tool or an extra tool to import and

store it to the right data set. To sum up the whole process of

structure managing is highly manual and error-prone because

of no exiting error recognition system or functionality.

3. Method for automated structuring of product data

The developed method for automated generation of

product structures is a two-step procedure:

1. Identification of spatial relations between parts

2. Hierarchical structuring of related parts.

The approaches to these steps are described in the following.

3.1. Step 1: Neighborhood analysis using contact graphs

Prior to the explanation of the applications it is important

to understand the fundamentals of graphs and their

characteristic in this particular case. A graph  is an abstract

datatype which represents a structure. It consists of a finite set

of vertices (or nodes)  and edges . Additionally, it is

155

Sebastian Adolphy et al. / Procedia CIRP 38 ( 2015 ) 153 – 158

possible to assign attributes Ʉ and ݒ to edges and vertices

given a node label alphabet ܮ௩ and an edge label alphabetܮ௘

[14].

ܩൌ൛

ሼܸǡܧǡߤǡߟሽหݒǡ݁ א Թ (1)

ߟǣݒ ՜ ܮ௩Ǣߤǣ݁՜ܮ௘

Figure 2 shows an exemplary graph representation of a car

alternator. In this case vertices represent a physical

part/assembly of a product while an edge represents a direct

spatial contact between two parts/assemblies. The relations

(edges) between the vertices are saved in an adjacency matrix

or list. The advantages and disadvantages of a matrix or list

representation depend on the used algorithms. GraphML

offers a comfortable data format to archive and exchange the

graphs.

Figure 2: Example of a product graph (car alternator)

In a basic form the attributes of a vertex only consist of

two entries, the vertex name and a vertex ID for intern

processing. The undirected edges of the graph own no

attributes; this means the only information contained is the

existence of a connection between two parts.

For creating a contact graph, it is necessary to analyze the

neighborhood of the parts of a product in its 3D-model.

Geometric 3D-models can be represented in various formats.

It is important to consider the possible input formats before

deciding about a transformation method. This paper focuses in

particular on tessellated surface models as input data.

Prerequisite for the neighborhood analysis of the imported

tessellated surface models is the complete transformation of

the scanning generated point cloud into a global coordinate

system. Goal of the neighborhood analysis is to identify all

possible spatial contacts between the product parts. Using a

brute force approach for the identification of these contacts it

would be necessary to compare each triangle of the surface

model. In order to reduce computing time by avoiding

superfluous comparisons of triangles the method uses a three-

stage neighborhood analysis. The first two stages are based on

the comparison of bounding volumes (envelops). Especially

the highly simplified comparison for axis aligned bounding

boxes reduces the computation time significantly. The last

stage consists of tri-tri Möller intersection tests of only two

triangles at a time [15]. The procedure starts with assigning

bounding volumes to each part of the product. If they possess

an intersection there is no contact edge between these parts

and the analysis can turn to other parts. If they intersect, the

level of detail is increased for the analysis of this segment.

Now the bounding volume intersection test is repeated on the

mesh level. This means, bounding volumes are assigned to

every triangle of the two considered parts and mutually tested

for intersection. If each intersection test is negative there is

once again no edge between these parts. If there is an

intersection a detailed tri-tri Möller algorithm is applied to

these two triangles for verification of the contact. This kind of

collision approach is also a well-known procedure in game

development.

3.2. Step 2: Cluster analysis for product structuring

In the second step of the proposed method the derived 2D

graph representation is used as an input for a cluster analysis.

By applying a cluster algorithm to a graph it is possible to

divide it in several subgroups. In order to build a product

structure with more than one level it is necessary to apply a

cascading sequence of clustering steps in a top-down process

(Figure 4).

The graph theory provides different algorithm for

clustering. Based on the assumption that the structural groups

of a product structure are well-separated modules with sparse

connection between each other the Girvan-Newman algorithm

is selected. This algorithm has originally been developed for

identification of community structures in social and biological

networks. It is based on the so called “edge betweeness”

which is calculated for every edge of the created graph. A

high value of edge betweeness is an indicator for connecting

edges between two communities.

Figure 3: Schematic representation of a network with community structures

(grey edges = high betweeness value) [16]

It is calculated by the sum of shortest paths between pairs

of other vertices that run through the edge. The communities

are formed by progressively deleting the edges with the

highest betweeness value and recalculating the betweeness

values. The stop mechanism can be set by a betweeness-

threshold or a minimum number of communities [16].

156 Sebastian Adolphy et al. / Procedia CIRP 38 ( 2015 ) 153 – 158

The above described cluster analysis is resulting in a single

graph only. To build a product structure with multiple levels it

is indispensable to repeat the cluster analysis on every node of

the future product structure. After each cluster analysis a

manual check for correctness to enable potentially needed

modifications is recommended.

The top down procedure of structuring the product

hierarchical (Figure 4) starts with the root node of a product

structure which represents the entire product with all its parts.

Afterwards, those clusters are selected which require further

subdivision.

Figure 4: Top-down process for product structuring by cluster analysis

3.3. Implementation of the method

For its evaluation the above outlined method has been

implemented in a software prototype, which consists of the

following five functional elements:

1. STL Importer:

The STL importer parses single STL files. For the

assignment every part has to consist of an single STL

file and the point cloud of each file has to be

represented in a global coordinate system.

2. Neighborhood Analyzer:

The function analyzes the imported STL files and

draws a 2D-contact graph.

3. GN-Cluster function:

The function divides the selected graphs into

subgraphs.

4. Graphical User Interface (GUI):

The GUI consists of a 3D-visualization to support the

human decision process for group selection and

corrective actions. It displays the actual product

structure and highlights currently selected structure

knots via 3D visualization. Additionally, a drag and

drop feature for manual manipulation of product

structures is supported.

5. PLMXML Exporter

The module generates a PLMXML file for combined

and comfortable import of the derived product

structure and the STL files in a PDM system.

4. Applications of the method

This chapter describes the new principle of facilitated

product structuring.

4.1. Structuring of digitized systems

Reverse engineering in MRO processes is the major use

case for the developed method. The scanning of defective

systems enables detection of deviations between as-used and

as-design condition in the first place. If as-designed models

are not available they can be created based on the digitized

systems. When relevant deviations are found the digitized as-

used system model can be employed in the following for the

definition of repair measures or spare part production. As

defective systems are rarely isolated components, structuring

of the digitized system is necessary. The ability to generate

structured models by scanning systems without prior

disassembly is highly favorable in terms of downtime

reduction [2].

Step 1 - Neighborhood analysis using contact graphs - is

demonstrated by application of the method to a reverse

engineered car alternator. The imported parts are shown in

Figure 5.

Figure 5: 3D model of a car alternator generated from 3D scan data

(1. Pulley, 2. Fan, 3. Rotor, 4. Inductor, 5. Housing)

The single parts are optically 3D scanned with a GOM

Atos III®-Scanner and automatically matched in a scan of the

assembled parts by a best-fit algorithm in Geomagic Studio®.

Afterwards, the referenced parts are saved in single STL files.

The prepared STL files are imported and analyzed in the

software prototype. The resulting adjacency matrix is shown

in Figure 6.

157

Sebastian Adolphy et al. / Procedia CIRP 38 ( 2015 ) 153 – 158

Figure 6: Adjacency matrix of the imported files

The neighborhood has been analyzed correctly, except the

connection between rotor and inductor. The falsely identified

connection between these parts resulted from a poor

alignment in the 3D model (Figure 7). The gap between these

parts is very small which implies high demands on the

referencing process.

Figure 7: Connection between rotor and inductor in the 3D model of the

alternator

4.2. Structuring of 3D CAD models

Step 2 of the method, the structure generation by

clustering, can best be demonstrated by the analysis of an

original 3D model, as long as the neighborhood analysis is not

affected negatively by scanning imprecision or artifacts.

Structuring of given 3D CAD models is necessary in MRO

when a system model - generated by 3D scanning (as

described in the previous use case) – has to be compared with

the related as-designed model. A software supported

comparative analysis of product models requires identical

product structures. By application of the proposed method

identical structures can be generated for both the original and

the scanned model.

Demonstrated by the as-designed model of the before

mentioned alternator - imported as 25 separate tessellated

STL files - the part’s neighborhoods could be detected

without errors in the first step. When applied to the root node

in the second step, the clustering algorithm automatically

allocated the first level of the product structure in three

different groups. The first and second cluster is characterized

by the static parts grouped respectively to the two-parted-

housing. The third group is characterized by the rotating parts

of the alternator. To illustrate the generation of a product

structure with more than one structure level the authors opted

for a subdivision of group 3 into two parts. The algorithm

separated the coil and its holders from the rest of the group

and the whole structure was created without manual post-

editing.

The created product structure (Figure 8) is saved in a

PLMXML file while the imported STL files are automatically

linked. Then it is possible to import the structure and its parts

in a single import step in PLM systems.

Figure 8: Structured as-designed model of car alternator

4.3. Restructuring of product data

In the aforementioned application the structuring of given

3D CAD models has been described, in case of the need for

comparable as-designed and as-used models. A special variant

of this use case is given if the original model comes with a

given product structure in a PLM system. Unless the given

structure has been generated analog to the clustering

algorithm in the first place a restructuring of the product is

prerequisite for the model-based failure detection in MRO

processes.

This use case is demonstrated by the clustering of a fuel

tank assembly. The fuel tank model and its product structure

are provided by an automotive manufacturer. The model

consists of 37 parts which should be clustered in three groups

(Figure 9).

Figure 9: Target groups for clustering of a fuel tank

158 Sebastian Adolphy et al. / Procedia CIRP 38 ( 2015 ) 153 – 158

Under the assumption that the algorithm is not able to

identify the structural unconnected group I, the parts of this

group were excluded from the analysis. Thus, only group II

and group III had to be found. The algorithm created three

clusters.

The parts of group II are clustered correctly, except for one

part, which is assigned to group III. Considering group III, 12

out of 14 parts are clustered correctly. One missing part is

assigned to group II and the second is assumed to be a

separate cluster with just a single part in it.

5. Summary and Outlook

The basic import function and neighborhood analysis

works error-free, as long as the import model is error-free as

well. Thus, if the 3D assembly model is derived from a

reverse engineering in a MRO process the latter has to be very

precise which means no incorrect touching parts. Details of

the tests run on the software prototype related to the three

described use cases have been described in [17].

The top-down process is a possible way to create a

multilevel product structure. This process relies on a manual

selection for further clustering. Thus, the user needs a

minimum level of knowledge about the product and how to

structure it. The 3D visualization, especially the highlighting

of structural groups, is an important feature for support of

human interaction. In addition manual modification allows

fast drag and drop of datasets.

The developed method is not limited to the presented

applications within MRO processes. An interesting future area

of application could be a comparison of products by means of

pattern matching between two contact graphs. This could

enable fast query search of structural related products in big

data stocks.

Another application could be a metadata independent

product variant analysis by comparison of product structures.

This might help to detect errors of structure management

divisions.

A third field of application might be facilitation of data

exchange between incompatible software systems or structure

conventions of either different companies or of company’s

divisions. This could be achieved by provision of a platform

independent template structure in the PLMXML format that

supports translation of one specific product structure to the

structure convention of the other software system.

Acknowledgement

This research was supported by the senate administration

of Berlin (Senatsverwaltung für Bildung, Wissenschaft und

Forschung) and funded by the European Union with EFRE

means.

References

[1] Stark, R., Grosser, H., Beckmann-Dobrev, B., Kind, S., 2014. Advanced

Technologies in Life Cycle Engineering. Procedia CIRP 22, 3–14.

[2] Grosser, H., Stark, R., 2014. Advanced 3D scan data analysis for

performant reengineering maintenance processes, in: Farinha, J.T.,

Galar, D. (Eds.), Proceedings of Maintenance Performance

Measurement and Management (MPMM) Conference 2014. Imprensa

da Universidade de Coimbra, pp. 73–80.

[3] Stark, R., Grosser, H., Müller, P., 2013. Product analysis automation for

digital MRO based on intelligent 3D data acquisition. CIRP Annals -

Manufacturing Technology 62 (1), 123–126.

[4] Wang, J., Gu, D., Yu, Z., Tan, C., Zhou, L., 2012. A framework for 3D

model reconstruction in reverse engineering. Computers & Industrial

Engineering 63 (4), 1189–1200.

[5] Kang, L., Li, Y., Chen, Z.M., 2012. An Integrated Reverse Modeling

Approach Based on Reconstruction of Features and Constraints. AMM

215-216, 639–642.

[6] Ma, T.-C., Park, C.-s., Suthunyatanakit, K., Oh, M.-j., Kim, T.-w.,

Kang, M.-j., 2012. Features Detection from Industrial Noisy 3D CT

Data for Reverse Engineering, in: Lee, R. (Ed.), Software and Network

Engineering, vol. 413. Springer Berlin Heidelberg, Berlin, Heidelberg,

pp. 89–101.

[7] Digne, J., Morel, J.-M., Mehdi-Souzani, C., Lartigue, C., 2012. Mesh

Segmentation and Model Extraction, in: Hutchison, D., Kanade, T.,

Kittler, J., Kleinberg, J.M., Mattern, F., Mitchell, J.C., Naor, M.,

Nierstrasz, O., Pandu Rangan, C., Steffen, B., Sudan, M., Terzopoulos,

D., Tygar, D., Vardi, M.Y., Weikum, G., Boissonnat, J.-D., Chenin, P.,

Cohen, A., Gout, C., Lyche, T., Mazure, M.-L., Schumaker, L. (Eds.),

Curves and Surfaces, vol. 6920. Springer Berlin Heidelberg, Berlin,

Heidelberg, pp. 236–252.

[8] Ehm, M., Hesse, C., 2014. 3D-Laserscanning zur Erfassung von

Gebäuden - Building Information Modeling (BIM). Bautechnik 91 (4),

243–250.

[9] Oreni, D., Brumana, R., Cuca, B. Towards a methodology for 3D

content models: The reconstruction of ancient vaults for maintenance

and structural behaviour in the logic of BIM management, in: 2012 18th

International Conference on Virtual Systems and Multimedia (VSMM),

Milan, Italy, pp. 475–482.

[10] Yoon, S., Jung, J., Heo, J., 2015. Practical Implementation of Semi-

Automated As-Built BIM Creation for Complex Indoor Environments.

Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci. XL-4/W5, 143–

146.

[11] Hidaka, N., Michikawa, T., Yabuki, N., Fukuda, T., Motamedi, A.,

2015. Creating Product Models from Point Cloud of Civil Structures

Based on Geometric Similarity. Int. Arch. Photogramm. Remote Sens.

Spatial Inf. Sci. XL-4/W5, 137–141.

[12] Barazzetti, L., Banfi, F., Brumana, R., Gusmeroli, G., Oreni, D.,

Previtali, M., Roncoroni, F., Schiantarelli, G., 2015. BIM from Laser

Clouds and Finite Element Analysis: Combining Structural Analysis and

Geometric Complexity. Int. Arch. Photogramm. Remote Sens. Spatial

Inf. Sci. XL-5/W4, 345–350.

[13] Eigner, M., Stelzer, R., 2009. Product Lifecycle Management: Ein

Leitfaden für Product Development und Life Cycle Management, 2.

Aufl. ed. Springer-Verlag, s.l., 437 pp.

[14] Cook, D.J., Holder, L.B. (Eds.), 2007. Mining graph data. Wiley-

Interscience, Hoboken, N.J, 479 pp.

[15] Möller, T., 1997. A Fast Triangle-Triangle Intersection Test. Journal of

Graphics Tools 2 (2), 25–30.

[16] Girvan, M., Newman, M. E. J., 2002. Community structure in social and

biological networks. Proceedings of the National Academy of Sciences

99 (12), 7821–7826.

[17] R. Stark, H. Grosser, P. Müller, 2013. Product analysis automation for

digital MRO based on intelligent 3D data acquisition. CIRP Annals -

Manufacturing Technology 62 (1), 123–126.