RECOGNITION FROM LOSSY CAD MODELS
A Thesis submitted to Goa University for the Award of the Degree of
DOCTOR OF PHILOSOPHY
in
Computer Science
By
Deepali Tatkar
Research Guide
Dr. V. V. Kamat
Goa University Taleigao Goa
May 2015
As required by the ordinances OB-9.9 of Goa University, I state that the present Ph.D thesis entitled “MANUFACTURING FEATURE RECOGNITION FROM LOSSY CAD MODELS” being submitted to Goa University for the award of Ph.D degree in Computer Science. Further I state that this is my original contribution and the thesis or any part of it has not been previously submitted for the award of any degree/diploma at any University or Institute in India or abroad. To the best of my knowledge present study is the first comprehensive work of its kind in the area mentioned.
The literature related to the research investigation has been cited. Due acknowl- edgements have been made whenever facilities and material have been availed of.
——————————————–
Deepali Tatkar
Department of Computer Science and Technology Goa University, Goa
Date: May 2015 Place: Goa University
i
This is to certify that Deepali Tatkar has worked on this thesis entitled “MAN- UFACTURING FEATURE RECOGNITION FROM LOSSY CAD MODELS”in Department of Computer Science and Technology under my supervision and guid- ance. This thesis being submitted to Goa University Taleigao Plateau, Goa for the award of the degree of Doctor of Philosophy in Computer Science is an original record of work carried out by the candidate herself and has not been submitted for the award of any other degree or diploma of this or other university in India or abroad.
Research Guide:
———————————————–
Dr. V.V. Kamat
Department of Computer Science and Technology Goa University, Goa
Date and Place: May 2015 , Goa University
Examiner:
—————————————
ii
Abstract
Department of Computer Science and Technology
Doctor of Philosophy byDeepali Tatkar
data models that contains missing or incomplete topology/geometry information.
The input to the algorithm is data model of mechanical part saved in neutral file format such as STEP or STL. This is an inverse problem and the challenge is to recover the missing design information by reverse engineering. The input file may have been created either using any one of the popular CAD modellers or by scanning the existing mechanical part using a 3D scanner. In either case, the original design related information is not available, missing or non-existing.
In this thesis we have called such data models as lossy model. With constant pressures on minimizing product development life cycle, there is a demand for recovering the design information from neutral file formats for many practical downstream applications in the domain of manufacturing such as process planning, cost estimation, re-design, design intent etc. In the thesis we have proposed three different algorithms to address some of these practical problems that arise due to lossy data model.
The first algorithm that we have proposed is useful in the context of data exchange when the data models are saved in the neutral file format such as STEP. It is often observed that while translating the design information from proprietary file format to STEP data exchange format, there is loss of information due to incorrect mapping of geometric entities. This loss of information due to representational issue results into an error in automatically identifying features in downstream applications. We have proposed an algorithmic solution to this problem which will identify such representational errors and heal the data set so that the downstream application can work correctly. The second algorithm that we have proposed is useful in the context of data models that have compound design features wherein one or more simple features interfere. In scenarios like this, the geometry and topology in the proximity of the simple features gets modified giving rise to more complex or compound features. These compound features are difficult to recognize
problem we have proposed a semi-automatic solution which allows the user to interactively define compound features which then can be used to search the data model to locate its instance.
In the end we have taken an extreme case where the input file is a STL file which contains only triangles and no other design information. To reconstruct design level information from such low level input data is very challenging. The problem is analogues to reconstruction of 2D shape information from bunch of pixels. However, the problem on hand has much higher order complexity than its 2D analogue. In this scenario, we reconstructs the shape information by first segmenting the mesh data model into set of simple analytical shapes before passing it on to rule based engine which extracts higher order semantic information from the input data model to locate simple features. In the thesis we have restricted ourselves to mesh models of mechanical parts and demonstrated the working of the algorithm for simple features such as slots, pockets, through hole and blind hole. However, the idea could be extended further to other manufacturing features and not limited to few prototypical cases.
During my childhood I used to ask my father where are we going?” and My father would always respond ’just there and back . These few words (and sense of secrecy remembered) have been intensely recollected as I have undertaken my greatest journey to date, the record of which is detailed in this thesis.
There are many people whose advice, direction, contributions and support have proven priceless during the entire research journey. Primarily I would like to thank my Guide and mentor Professor V.V . Kamat, It has been an honour to be his first Ph.D. student. His support nurtured my research skills and allowed me to grow as a research scholar. I appreciate all his contributions in terms of time, ideas, and funding to make my Ph.D. experience constructive and inspirational. The zeal he has for research was inspiring for me in the Ph.D. pursuit. His advice on both research as well as on my career have been priceless.
I would like to take this opportunity to give a special thanks to Dr.Ketil Bo(Prof.
Norwegian University and CEO of Trollhetta AS) for his encouragement and guid- ance during initial period of my research work. I would also like to thank Govind Kelkar and Diker Pagui for their special help and valuable advice during crucial period of my thesis. I would also like to thank Professor Luis Mesquita, Dr. Jyoti Pawar, Mrs. Shailaja Sardesai for their valuable feedback and suggestions during my research journey. I would especially like to thank entire staff of Department of Computer Science and Technology for their support during my research work.
I would also like to thank the Vice Chancellor Dr. Satish Shetye, Registrar Pro- fessor V.P Kamat and all the concern administrative staff of Goa University for their support.
I also take an opportunity to thank Dr. Nandini V. Kamat for her moral support.
I always remember the words “Go Ahead you can do it my dear”, said by Aai which always inspired me every time I use to feel down. It would have just remained a dream for me without support of my Aai, Baba, Dada and Pallu. I would deeply thank Sneha Kaku and Uday Kaka for giving all the love and care to my little angel in my absence during completion of thesis. My family also supported me all these years and no words can express how grateful I am to my Aaji , mother-in law and father-in-law, for showing patience all these years. I would also like to thank
vi
I have dedicated my work to my eight months old angel whose age was actually to get most of mummy’s love and attention but unknowingly and innocently gave me room and inspiration to complete my work on fast track. And finally no formal words for my ’pillar of strength’, my soul mate. It was his love, sacrifice, patience and enthusiasm that kept me going and made my ’Quest’ delightful.
Statement i
Certificate ii
Abstract iii
Acknowledgements vi
List of Figures ix
1 Introduction 1
1.1 Scope of Thesis . . . 1
1.2 Motivation and Problem Statement . . . 2
1.3 Thesis Overview. . . 4
1.3.1 Feature Recognition with Parametric Data . . . 5
1.3.2 Handling Lossy Parametric CAD Data . . . 6
1.3.3 Feature Recognition with Discrete Data . . . 6
1.4 Main Contribution . . . 7
1.5 Thesis Layout . . . 9
2 Research Background 10 2.1 CAD/CAM and Product Development Life Cycle . . . 10
2.1.1 Automated Process Planning . . . 11
2.2 Automatic Feature Recognition . . . 14
2.3 CAD Features . . . 15
2.4 Reverse Engineering . . . 17
2.5 CAD Data Representation . . . 18
2.5.1 Metamathematical Representations . . . 19
2.5.1.1 Analytical Curve and Surfaces. . . 19
2.5.1.2 Free-form Curves and Surfaces . . . 19
2.5.1.3 Discrete Representations . . . 21 viii
2.6 CAD Exchange . . . 22
2.7 Feature Recognition and Problems . . . 24
2.7.1 Information Loss In Data Exchange . . . 24
2.7.2 Information Loss with Complex Object Design . . . 24
2.7.3 Data Reconstruction from Discrete CAD Representation . . 26
2.8 Summary . . . 27
3 Related Work 28 3.1 Introduction . . . 28
3.2 Overview of Feature Recognition Techniques . . . 28
3.2.1 Syntactic Pattern Recognition . . . 29
3.2.2 Graph-based Feature Recognition . . . 30
3.2.3 Rule-based Feature Recognition . . . 31
3.2.4 Volumetric Methods . . . 32
3.2.4.1 Convex-Hull Technique. . . 32
3.2.4.2 Cell-Based Technique . . . 33
3.3 Inconsistent CAD Data and Healing Techniques . . . 34
3.3.1 Feature Recognition with Interacting Features . . . 35
3.4 Reverse Engineering and Mesh Reconstruction . . . 37
3.4.1 Semantic Level Mesh Reconstruction . . . 39
4 Knowledge Management and Intelligent Process Planning 41 4.1 Introduction . . . 41
4.2 Manufacturing Knowledge Management System . . . 43
4.3 Implementation . . . 44
4.3.1 Feature Recognition Module . . . 45
4.3.1.1 3D Viewer. . . 46
4.3.1.2 Solid Model Geometry Information . . . 46
4.3.1.3 Recognised Features Tree View . . . 48
4.3.1.4 Defining Manufacturing Feature Parameters . . . . 49
4.3.1.5 Generating XML File . . . 50
4.3.2 Knowledge base module . . . 50
4.3.2.1 Define rules for manufacturing method selection . . 52
4.3.2.2 Defining machine tool selection rule. . . 53
4.3.2.3 Defining Fixture Selection Rule . . . 54
4.3.2.4 Defining manufacturing sequence selection rule . . 55
4.3.3 ResourceBase Module . . . 56
4.3.3.1 Machine Tools resources definition . . . 57
4.3.3.2 Fixtures Tools resources definition . . . 58
4.3.3.3 Rotating Tools resources definition . . . 58
4.3.3.4 Turning Tools resources definition. . . 58
4.3.3.5 Raw material definition . . . 59
4.3.4 Automatic Process Planning . . . 59
4.4 Reasoning Engine and Process Planning . . . 61
4.4.1 Example with Manufacturing Knowledge Management System 65
4.5 Summary . . . 67
5 Feature Recognition and Lossy Parametric Data 69 5.1 Introduction . . . 69
5.2 Feature Recognition Algorithm . . . 70
5.2.1 Check for Shape Representation . . . 72
5.2.2 Generate Geometry from STEP File . . . 72
5.2.3 Search Form Features. . . 73
5.2.3.1 Cylindrical Holes recognition . . . 74
5.2.3.2 Pockets recognition . . . 76
5.2.3.3 Slots and Steps recognition . . . 77
5.2.3.4 Chamfers, Fillets , Edge Rounds recognition . . . . 79
5.2.3.5 Rib Feature recognition . . . 81
5.2.3.6 Thread Feature recognition . . . 82
5.2.3.7 Grooves Feature recognition . . . 83
5.2.3.8 Boss Feature recognition . . . 84
5.2.3.9 Irregular Feature . . . 86
5.2.3.10 Cones/Tapers/Spheres Features . . . 86
5.3 Proposed Algorithm for Handling Lossy Parametric CAD Data. . . 88
5.3.1 Free Form Curve/Surface Conversion Algorithm . . . 88
5.3.2 Free Form Surface Conversion Algorithm . . . 92
5.4 Handling Complex Features - A User Defined Feature Approach . . 94
5.4.1 Enter Geometric Information for a New Feature . . . 96
5.4.2 Adding Feature Properties . . . 97
5.4.3 Adding User Defined Features to Feature Tree . . . 97
5.5 Summary . . . 98
6 Feature Recognition with Discrete Data 100 6.1 Introduction . . . 100
6.2 Hierarchical Mesh Segmentation Algorithm . . . 101
6.3 Proposed Methodology . . . 104
6.4 Implementation . . . 106
6.4.1 Segment Preprocessing . . . 106
6.4.2 Data Structure . . . 107
6.4.3 Feature Recognition . . . 108
6.4.4 Basic Terminology for Recognition . . . 108
6.5 Recognition Procedures in Details . . . 110
6.5.1 GetHoleAdjacents . . . 110
6.5.2 GetHoleFeatures . . . 112
6.5.3 GetPlanFeatureAdjacents . . . 113
6.6 Feature Recognition Rules for Planar Features . . . 116
6.6.1 Direction Shift Pattern . . . 116
6.6.2 GetFeatures . . . 118
6.7 Results and Discussion . . . 120
7 Conclusions 122
7.1 Summary of Thesis . . . 122 7.2 Future Scope . . . 125
Publications 127
Bibliography 128
2.1 CAD/CAM integration . . . 11
2.2 Step in process plan generation [1, Mortenson] . . . 12
2.3 Simple manufacturing features . . . 16
2.4 Some more manufacturing features . . . 17
2.5 Reverse engineering process . . . 18
2.6 B spline surface map [2, CAG] . . . 20
2.7 CAD model with mesh representation . . . 22
2.8 Representational issue as explained by [3, You and Chan] . . . 25
2.9 Complex CAD model design with interacting features . . . 25
3.1 General architecture of syntactic pattern recognition . . . 30
3.2 Graph based recognition(a)CAD model with slot feature;(b)Graph representation of entire model;(c) Recognised slot feature as subgraph 31 3.3 (a)ASVP decomposition;(b)feature level decomposition . . . 33
3.4 (a)A CAD model;(b),(c)cell decomposition;(d)cell composition . . . 34
4.1 Architecture of Knowledge Management System . . . 43
4.2 The basic flowchart of Automatic Process Planning System . . . 45
4.3 3D Viewer . . . 47
4.4 Geometry Information Tree View . . . 47
4.5 Highlighted face and corresponding properties . . . 48
4.6 Feature Tree View . . . 48
4.7 Feature Properties . . . 49
4.8 Solid model with recognised features and properties . . . 50
4.9 A XML file with manufacturing feature information . . . 51
4.10 Structure of Reasoning Rules in Knowledge base . . . 52
4.11 Structure of Reasoning Rules in Knowledge base . . . 53
4.12 Machine tool selection rule . . . 54
4.13 Fixture selection rules . . . 55
4.14 Sequence selection rules . . . 56
4.15 Resource Base Module for resource management . . . 57
4.16 Machine Tools definition . . . 57
4.17 Fixture Tools definition . . . 58
4.18 Rotating Tools definition . . . 59
4.19 Turning Tools definition . . . 59
4.20 Raw Material definition . . . 60 xii
4.21 Methods to generate process plan . . . 60
4.22 Entire data flow during reasoning process . . . 61
4.23 Input feature XML and raw material selection phase . . . 66
4.24 Reasoning process . . . 66
4.25 Process planning data . . . 67
4.26 Final Process plan for given CAD data . . . 67
5.1 A sample STEP file with corresponding CAD model . . . 73
5.2 Solid Model topology information tree . . . 73
5.3 Types of hole features recognised by the Recognizer module . . . . 74
5.4 Types of pocket features recognised by the Recognizer module . . . 76
5.5 Types of Slot features recognised by the Recognizer module. . . 78
5.6 Types of Steps features recognised by the Recognizer module . . . . 78
5.7 Chamfers, Fillets , Edge Rounds recognised by the Recognizer module 79 5.8 Rib features recognised by the Recognizer module . . . 81
5.9 Thread feature recognised by the Recognizer module . . . 83
5.10 Groove feature recognised by the Recognizer module . . . 84
5.11 Boss feature recognised by the Recognizer module . . . 85
5.12 Irregular feature recognised by the Recognizer module . . . 86
5.13 Sphere and Cone feature recognised by the Recognizer module . . . 87
5.14 Circular and elliptical curve case in B-spline conversion algorithm . 90 5.15 Original curve representing line as B-Spline curve (a) and recovered linear curve by conversion algorithm (b) . . . 91
5.16 (a) Linear curve represented as B-Spline,(b)Converted to linear curve 91 5.17 (a)Circle represented as B-Spline,(b)Converted to circle . . . 92
5.18 (a)Elliptical curve represented as B-Spline,(b)Converted to Ellipti- cal curve . . . 92
5.19 (a)Before conversion algorithm cylindrical surface as B-Spline,(b)converted to Cylindrical surface . . . 93
5.20 (a)Before conversion algorithm planar surface as B-Spline,(b)converted to planar surface . . . 94
5.21 Models with interacting features . . . 95
5.22 Unrecognised pocket features due to complex topology . . . 95
5.23 Adding geometric properties . . . 96
5.24 Adding feature properties . . . 97
5.25 Adding User Defined feature . . . 98
6.1 In (a) a triangle mesh and the corresponding dual graph are de- picted. In (b) an arc of the dual graph has been contracted, and the two triangles corresponding to the dual arcs end-points have been marked as belonging to the same single cluster. In (c) another arc has been contracted producing a resulting cluster made of three triangles [4, Attene et al.] . . . 103
6.2 In (a) Shows two levels of segmentation for same model, 26 and 139 clusters each (b) Model segmented with different fitting primitives.
[4, Attene et al.]. . . 103 6.3 Framework for proposed algorithm . . . 104 6.4 Mesh model . . . 105 6.5 Feature recognition from segmented model using proposed algorithm105 6.6 The Segmented mesh object representation using our data structure 107 6.7 Features and normal direction . . . 108 6.8 Different types of features labelled with their parts (a) Blind pocket
feature (b) Through pocket (c) Rounded blind pocket (d) Blind hole (e) Blind slot (f) Through slot (g) Step . . . 109 6.9 rounded pocket feature and its parts . . . 110 6.10 Adjacents of hole feature . . . 111 6.11 Iterations of getting adjacents in case of rounded pocket, (a) Iter-
1,(b) Iter-2, (c) Iter-3 ,(d) Iter-4 . . . 115 6.12 Direction shift of faces . . . 116 6.13 Input segmented mesh models and extracted features. . . 121
xv
Introduction
1.1 Scope of Thesis
Features play a key role in mechanical design and manufacturing. Design by fea- tures and design by manufacturing are core concepts in feature technology. The benefit of feature technology comes from the fact that it reduces the cycle time and increases the productivity of the designer and manufacturer. Typically the designer works in his own space during the design phase and then passes on the design information digitally to a manufacturing facility which may be located at a distant location. In traditional manufacturing setup, on receiving the design a manufacturing expert prepares a process plan. At this stage, design may under go rework in order to satisfy various manufacturing constraints. The feature technol- ogy attempts to integrate design and manufacturing process by automating the process plan[5, Regli and Gaines] . This is a two-stage process. The first stage deals with recognition of the manufacturing features from the CAD model de- scription and the second stage involves generating detailed process plan based on available manufacturing resources. One of the challenges faced in automating the process plan is the inconsistency that gets introduced into the design data while converting it into neutral file formats such as STEP or IGES [3, You and Chan].
1
As a consequence, feature recognition module fails to identify correctly the manu- facturing features. In recent times, with rapid advancement in 3D scanning/print- ing technology, new ways of reverse engineering the design and manufacturing is gaining popularity. 3D printing is a additive manufacturing technique as against traditional machining which is subtractive manufacturing technique. The digitally scanned model contain very large number of low level polygonal data that is not suitable for traditional manufacturing. During the design phase, both traditional and the modern method of creating digital artefacts can work in tandem. But if one desires to manufacture the object using traditional machining process than the polygonal data need to be converted to higher level manufacturing features.
Feature level shape reconstruction is a novel way of addressing feature recognition problem in reverse engineering [6, T.Varady]. Central focus of this work is to address the problem of CAD/CAM integration using feature recognition there by overcoming the issues in automating the process plan.
1.2 Motivation and Problem Statement
Design and manufacturing are two different activities and require different skill sets and expertise. Often these activities are carried out at different locations in- volving different sets of people. Seldom, design and manufacturing setup is owned by the same company. Depending upon the availability of in-house expertise, firms routinely outsource either design or manufacturing to third party. Design- ers use proprietary software to design parts and would not like to share design information with third party for obvious reason. The industry has resolved this issue by evolving standard neutral file format for data exchange such as STEP or IGES. At present these file formats only share shape information using low level geometric primitives. Often there is no one-to-one mapping between geometric primitives used by proprietary CAD modellers and the neutral file formats. This
results into loss of topology/geometry information which makes it harder for fea- ture recognition system to identify a particular feature. Another most common problem of loss or missing topology/geometry information is feature interaction problem which has been cause of concern for research community for many years [7,Vandenbrande and Requicha].
CAD model can also be represented as triangulated mesh model stored using STL file format. There are two methods to generate a mesh. One method is through forward engineering using the graphics pipeline. The second method is through reverse engineering by scanning the existing object and using computer vision pipeline. In the first case, the objects are parametrically modelled using B-rep and the mesh is automatically generated from the model by sub-division method.
In the second case, model is created by scanning the 3D object by first creat- ing a point cloud and then by applying series of mesh processing algorithms to create a mesh. The second method is data driven and is gaining importance in CAD/CAM industry. The recent trend is to merge the two pipelines for a quick turnaround time [8, Chang]. The technique shows some operational similarity to document image analysis where one can scan a document and then using OCR technology create an editable document that could be modified/improved using standard word processor. Since mesh model captures the shape information using discrete representation, it becomes more challenging to extract semantic level in- formation such as manufacturing features or design intent[9, Li et al.] from mesh data. Our motivation to the thesis problem whether it is data exchange problem, complex design or discrete mesh representation problem, in all these cases there is some loss of information in terms of geometry/topology data that make the model lossy. Automatically constructing the accurate high level manufacturing information from such lossy CAD data is abstruse process particularly for most of the feature recognition systems.
Ideally accurate and consistent design information of object shape is expected for
most of the downstream applications such as feature recognition, process plan- ning, and integrated manufacturing [10, Marefat]. Generally all feature recogni- tion methods are based on some kind of geometry/topology reasoning on given parametric(B-Rep) data. If given input design data is complete, consistent and accurate then feature recognition system will produce correct output in terms of feature tree. However if the input CAD model is lossy i.e it has lost some geometric or topological information during the data exchange or there is missing information due to interference of two or more manufacturing features then correctly recog- nizing underlying features becomes very challenging. Another interesting problem arises when the CAD design data is available at the lowest level in the form of triangles stored in file formats such as STL, PLY, OFF etc. In this case also to reconstruct feature level information from discrete data is a herculean task. Goal of our thesis is to reconstruct the feature information for a mechanical CAD object from CAD data model with missing/incomplete geometry/topology information.
In our thesis we have referred such CAD models as lossy CAD models. We also discuss the cause and the reasons which leads to information loss, leaving the CAD model in a ’Lossy’ state.
1.3 Thesis Overview
In this thesis work is carried out to do automated feature recognition from CAD models with lossy parametric data(B-rep model) and also from discrete data (CAD mesh model) which has no design information at all. The proposed solutions are divided into two parts, CAD data with parametric representation and discrete representation. In the first part, manufacturing features are recognized from con- sistent B-rep geometry, by matching it with the pre-defined set of manufacturing features. Here the input to the feature recognizer is described using the STEP format with parametric CAD data. Further, a method is proposed to handle lossy
CAD model when there is missing information due to geometry representational errors and missing information due to complex topology or interacting features.
Proposed solutions are implemented and tested using real industry CAD objects for an industry project of Automated Process Planning System[11, Tatkar and Kamat]. System consist of two parts, Automatic Feature Recognition and Au- tomated Process Planning. This system deals only with parametric CAD data files i.e STEP files and has also proposed solutions with lossy parametric data implemented as part of Automatic Feature Recognition module.
In second part we are addressing the problem of manufacturing feature recognition where input CAD data is in discrete form in terms of set of triangles. An algo- rithm is developed to recognise manufacturing features from CAD mesh models.
Here the input data is triangulated CAD mesh model and the input is simplified by segmenting mesh model using well know segmentation algorithm [4, Attene et al.]. Proposed feature recognition algorithm assumes input as segmented mesh model that gives primary surface geometry. Using information of type of surface associated with each segment, we try to detect connected set of surfaces forming some feature in CAD model. We restrict ourselves to only simple features made of connected simple plane primitives. These extracted features information then can be used for other CAD/CAM application.
1.3.1 Feature Recognition with Parametric Data
Automated recognition of features from CAD models has been attempted for a wide range of application domains in mechanical engineering. However, the ab- sence of a clear mathematical formalism for the feature definition has made it difficult to develop a general approach and thus most of these methods are lim- ited in scope. The objective here of automatic feature recognizer is to develop a template based form-feature extraction system. Each individual feature to be
recognized is described using a simple rule with a structure if ’condition’ then
’feature’ .
1.3.2 Handling Lossy Parametric CAD Data
In this part of work we have concentrated on data inconsistency issues with exact geometry obtained from traditional CAD software. As discussed above, issues with these data generally arises due to CAD data transfer or complex geometry or topology. We address these problem in two steps, first step tries to overcome the issue of inconsistency due to different CAD representation and try to recover feature information. In second step when the model is represented with complex geometry or topology, identifying simple features also becomes difficult. In these cases we have proposed a method called ’User Defined Features’, it is an interactive approach to ease the feature recognition. This method is best suitable to overcome feature interference problem with the help of manufacturing experts. Both of these solutions are explained in chapter five in the thesis.
1.3.3 Feature Recognition with Discrete Data
Here we propose a methodology for manufacturing feature recognition from a triangulated mesh model where even primary surface information is not available.
Reconstructing features from mesh data is proposed as a step by step process, reconstructing the high level geometry from low level triangles at each step. A rule based approach is used to define each manufacturing feature uniquely in terms of geometric primitives and its connectivity information. Rule based approach is being tried on mesh data where very limited geometric/topological information is available for approximated surface primitive. The algorithm takes approximate primitive with adjacency information as input. At present feature rules are defined
in terms of two simple geometric primitives mainly planar surface and cylindrical surface. The primary reason for choosing these primitives being, much of the manufacturing features are dominated by machining operations such as drilling and milling. This extracted features information then can be used for downstream CAD/CAM application such as process planning, cost estimation and generating feature tree.
1.4 Main Contribution
This thesis describes the issues of high level semantic data reconstruction from inconsistent data with respect to manufacturing features recognition. Work is car- ried out to give solution for reconstructing feature information when given input CAD data has insufficient geometry or topology. Methodology is proposed and implemented with respect to both traditional B-rep CAD geometry and discrete CAD geometry which is widely becoming popular due to upcoming reverse engi- neering field. The major contribution of thesis is highlighted in following points.
• Thesis highlights general problem of how to best correlate low-level shape data with the higher-order manufacturing features which is an open area of research with many practical applications like cost estimation, process planning, redesign, design intent etc.
• Initial part of work focus on studying different issues related to inconsistent data leaving CAD model in lossy state and difficulties in feature recognition from such lossy data.
• Although issues with feature recognition problem have been studied by com- munity for last several years with successful algorithms, this thesis gives perspective of recognising features from insufficient CAD data due to lossy B-rep data or complete discrete data in form of mesh.
• Automatic free form curve/surface conversion algorithm successfully checks and converts the given freeform curve/surface to its original analytical form if possible. This has solved representational issues that arise due to CAD data transfer from different kernels. This conversion algorithm has direct effect on feature recognition as it simplifies the input geometry from complex freeform representation to simple analytical form. It was found that the feature which remained unrecognised before applying conversion algorithm can then be recognised automatically.
• The user defined feature method proposed allows the user to solve the prob- lem by interactively defining custom features. Unlike a fully automatic fea- ture recognition system that may not work correctly for all possible test solids, our solution is guaranteed to work since it allows the process plan- ner to explore the solution interactively by making use of his manufacturing knowledge.
• Keeping in view the recent development in CAD industry, the work in this thesis has been extended to address the problem of manufacturing feature recognition from reverse engineering perspective by developing an algorithm to extract manufacturing features from mesh data [12,Tatkar et al.]. Frame- work for manufacturing feature recognition from mesh model is proposed and implemented with goal to extract design related information of the mechani- cal CAD object at high level of abstraction. The method tries to extract high level geometry from low level data points. i.e given a triangular mesh model as an input, the algorithm automatically recognizes different manufacturing features present in model.
1.5 Thesis Layout
The layout of this thesis is as follows: Chapter 2 presents the research problem in detail and discusses background of research problem and its context. It covers traditional CAD/CAM integration process and advance reverse engineering pro- cess with respect to different CAD data representations. In chapter 3, extensive literature review is undertaken, that will cover in the first part the CAD data loss problem for B-rep geometry and the associated recovering techniques. Methods for handling interacting features are reviewed for feature recognition issue. Second part will focus on discrete mesh representation and techniques that are available for high level data abstraction from segmentation to semantic level mesh repre- sentation. In Chapter 4 we have given details of CAD/CAM integration with a Manufacturing Knowledge Management System implemented as part of industry project. In chapter 5 we discussed the implementation of proposed solutions with parametric CAD data taking into account sufficient examples. In, chapter 6 we discuss in detail the feature recognition algorithm developed for discrete CAD data i.e for mesh objects. Finally chapter 7 will give the conclusion and future scope of work carried out as part of this thesis
Research Background
2.1 CAD/CAM and Product Development Life Cycle
To succeed in the global market, manufacturing firms frequently release innovative products with continuous improvement in price, quality and response competitive- ness. Innovative products incorporate new features, better user interfaces or higher efficiency. Aggressive innovation by competing firms is leading to more complex products. Manufacturers often have to satisfy conflicting demands which forces them to adopt new sophisticated technologies. Evidence of this trend can be seen from the extent to which Computer Aided Design (CAD),Computer Aided Manu- facturing (CAM),Computer-Integrated Manufacturing (CIM), Materials Resource Planning (MRP), Enterprise Resource Planning (ERP), Product Data Manage- ment (PDM), Numerically Controlled (NC) Machines and Computer-Aided Pro- cess Planning (CAPP) are being used in industry today. Current interest in man- ufacturing systems focuses heavily on integrating isolated computer-based sys- tems into a unified system that handles and transforms information to facilitate a smooth production environment.
10
Figure 2.1: CAD/CAM integration
The ultimate goal of CAD/CAM would be to make design and manufacturing task as simple as desktop publishing. For instance, in desktop publishing, the designer of the document is not worried about how to print the document while designing the document. All information required by the printer for printing the document is available in the design document itself and it does not matter where the printer is located. The CAD/CAM integration has several benefits, first the automation of process planning directly following design stage and this results in consistent and accurate production plans. Second, integration reduces the workload on pro- duction planners and consequently decreases the planning cost and time. Third, it provides faster responses to change in product design. Fourth, CAPP systems enable the firms to transfer a new product from concept into manufacturing in a short time. All these benefits have a substantial impact on overall productivity of the manufacturing company.
This chapter will present in depth view of research background and its context.
It will cover traditional CAD/CAM integration process and advance reverse engi- neering process with respect to different CAD data representations. Towards end of chapter, we shall discuss the research problem in detail.
2.1.1 Automated Process Planning
The objective of Computer Aided Process Planning (CAPP) is to facilitate CAD/- CAM data integration. Figure 2.1 illustrates the relationship between CAD/CAP- P/CAM. CAPP usually contains two parts, feature recognition and process plan- ning. The feature recognition module takes CAD model as input and extracts
Figure 2.2: Step in process plan generation [1,Mortenson]
the manufacturing features. Manufacturing features are typically defined as high level geometric entities representing volumes of material to be removed from the workpiece. The process planning part generates the appropriate manufacturing processes based on the extracted features and other manufacturing information.
The recognized manufacturing features serve as the input to the second stage.
Here the task is to generate manufacturing process plan by removing manufactur- ing features from the workpiece block model with a certain sequence and accuracy so that a product model is approached. That is
W =W0 - P
Fk ; k = 1,2,...N
where W is the product model andW0 is the work piece block model,Fkis a man- ufacturing feature removed from the work piece, and N is the number of manufac- turing features, as shown in the figure 2.2. In addition to geometric information, manufacturing features are defined to transmit non-geometric information such as tolerance, type of material, possible manufacturing methods, machine tools, type, size, feed motion direction etc.
There exist two approaches to the design of CAPP systems. They are a variant and generative frameworks [13, Kalpakjian and Schmid]. In variant CAPP approach, a process plan for a new part is created by recalling, identifying and retrieving an existing plan for a similar part and making necessary modifications for the new part. Sometimes, the process plans are developed for parts representing a family of parts called ’master parts’. The similarities in design attributes and manufacturing methods are exploited for the purpose of formation of part families.
A number of methods have been developed for part family formation using coding and classification schemes of group technology (GT), similarity-coefficient based
algorithms and mathematical programming models. The variant process planning approach can be realized as a four step process; 1. Definition of coding scheme, 2.
Grouping parts into part families, 3. Development of a standard process plan, 4.
Retrieval and modification of standard process plan. A number of variant process planning schemes have been developed and are in use.
The next stage of evolution is towards generative CAPP. In the generative CAPP, process plans are generated by means of decision logic, formulas and geometry based data to perform uniquely many processing decisions for converting part from raw material to finished state. There are two major components of gen- erative CAPP; geometry based coding scheme and process knowledge in form of decision logic data. The geometry based coding scheme defines all geometric features for process related surfaces together with feature dimensions, locations, tolerances and the surface finish desired on the features. The level of detail is much greater in a generative system than a variant system. For example, details such as rough and finished states of the parts and process capability of machine tools to transform these parts to the desired states are provided. Process knowledge in the form of decision logic and data matches to the part geometry requirements and the manufacturing capabilities using knowledge base. It includes selection of pro- cesses, machine tools, jigs or fixtures, tools, inspection equipments and sequencing operations. Development of manufacturing knowledge base is backbone of gen- erative CAPP. The tools that are widely used in development of this database are flow- charts, decision tables, decision trees, iterative algorithms, concept of unit machined surfaces, pattern recognition techniques and artificial intelligence techniques such as expert system shells. In this thesis we have described imple- mentation process planning framework based on generative method using artificial intelligence techniques [14,Tatkar and Kamat].
Automated Process Planning has been an area of research in Artificial Intelligence (AI)for almost three decades. A system by[15, Descotte and Latombe] developed
at the University of Grenoble in France was one of the early applications of AI in process planning . The system uses a set of production rules as representation of its knowledge base. A part is represented to the process planning module in terms of a set of features like holes, notches etc. which includes geometrical and other manufacturing related information. The system provides the capability of backtracking mechanism from any of the intermediate stages of the process planning development to provide necessary revisions. It assigns weights to different pieces of advices at each stage of the process planning development to resolve any conflicts. Computer Managed Process Planning (CMPP)[16, T. W. Liao and Guha] is a generative process planning system that was developed by the United Technologies Research Center for machined cylindrical parts that are characterized by tight tolerances and complex manufacturing processes. The system builds and maintains manufacturing database and based on the description of the part model generates process plan. Techno structure of Machining (TOM)[17,K. Matsushima and Sata] is a rule-based expert system developed at the University of Tokyo. TOM uses production rules as its knowledge representation scheme about machining operations, sequencing and geometry of a part. It employs a backtracking search mechanism to generate a process plan.
2.2 Automatic Feature Recognition
Computer Aided Design (CAD) was introduced to the world of designing, to help users to design products (Solid Models) which are composed of geometric primi- tives or design feature. CAM (Computer Aided Manufacturing) system has been designed to automate the manufacturing process based on the manufacturing fea- tures. In particular, CAD data cannot be used directly by CAM system because it lacks high level geometric entities that are meaningful from manufacturing point
of view. To bridge this gap between CAD and CAM systems, methods for auto- matically extracting the manufacturing information from design data have been developed based on the concept of features. Automatic Feature recognition in- volves 3-D matching between feature definition and geometric representation of the CAD data model in standard file formats (e.g. IGES, PDES, STEP, etc.)[18, Mangesh P. Bhandarkar]. Feature recognition may be done for various applica- tions, Computer Aided Process Planning(CAPP) is one such application which creates automatic process plan for manufacturing a part. Beside this, there are other applications such as determining the design intent, finite element analy- sis, cost estimations etc. In spite of wide application of feature technology in mechanical engineering, there is no clear mathematical formalism for the feature definition. As a result it is difficult to develop a general approach for feature recog- nition techniques and thus most of these methods are limited in scope. Feature, recognition from low level geometric entities in the solid model in order to facil- itate process planning and manufacturing has been of significant importance in Computer Integrated Manufacturing (CIM). There are plenty of AFR techniques available, however the recognition performance of most of the existing AFR sys- tem are limited to the requirement of particular manufacturing applications [19, Babic et al.].
2.3 CAD Features
A feature is the medium of information transmission in the integration of CAD/- CAM systems. Features definitions vary from different view points however in broader sense features can be interpreted as a generic shape useful in some CAM applications. Features provide vocabulary to experts to communicate design/man- ufacturing related information in a concise manner. They serve similar purpose like design pattern in software engineering. Feature definitions are domain-dependent
Figure 2.3: Simple manufacturing features
and application-oriented, in other words features usually are suitable either for a design itself or for an application do-main (such as manufacturing). There have been many efforts to classify features into hierarchies [20, JungHyun Han and Regli]. However, till date there is no consensus in the feature community as to what should be the canonical set of features for any application. Therefore, the interest of the feature community has now moved from defining a standard set of features to a standardized way of describing features [21, Hunten et al.]. Design and manufacturing features are often different and direct mapping from design fea- tures to manufacturing features is not possible. Designers designs using features that may involve various solid modelling operations. Manufacturing experts then studies the design and expresses it using the vocabulary of manufacturing features . The type of features to be used in a particular application will depend upon the intention, i.e. whether the intent is to design or to manufacture. In manufacturing context, a volume resulting from a machining operation is called a manufacturing (machining) feature. Manufacturing features are defined with respect to their ma- chining operations, i.e. Hole feature will refer to drilling operation and pocket, slot refers to milling and so on. Also accuracy of feature dimensions (width, height, radius etc.) is equally important as it decides size and settings for tools to be used.
Therefore recognizing correct manufacturing features automatically has influence on whole manufacturing process. Figure 2.3 and 2.4 shows examples of common manufacturing features like pocket, slot, hole, step and more.
Figure 2.4: Some more manufacturing features
2.4 Reverse Engineering
Conventional CAD/CAM system are designed for CAD data with continuous ge- ometry represented using parametric surfaces. However for many applications such as finite analysis, visualization,rapid prototyping etc.,the continuous parametric data has to be discretized into a large polygonal mesh model. Furthermore, with the advent of 3D scanners, it is now possible to reverse engineer the shape of the object without going through any design phase or even a sketch. Scanning extracts sufficient information from physical objects to reconstruct the CAD models for a particular purpose. Reconstructing complete B-Rep surface model from discrete 3D meshes is one of the objective of reverse engineering [22,Martin and Va]. Re- searchers in this field are further pursuing the dream of discovering semantic level information from the mesh model such as feature-based shape reconstruction and design intent [9, Li et al.].
The process of Reverse engineering starts with data capture in which object is scanned with laser scanner with multiple views to get data in terms of densely spaced points called point cloud. Next step is to do triangulation i.e. creating triangular mesh from point cloud. Segmentation is the next step where set of
Figure 2.5: Reverse engineering process
triangles are partitioned into regions based on some common properties. At this stage an attempt is made to combine the adjacent regions forming natural surfaces such as planar, cylindrical or spherical[23, Ma et al.]. Finally a complete B-rep model is created by stitching the fitted surfaces. Figure 2.5 explains the reverse engineering process in detail. Boundary representation models reverse engineered from 3D range data suffer from inaccuracies in the measured data because of approximation and numerical errors during the reconstruction process.[24,Oleksiy et al.]
2.5 CAD Data Representation
In conventional design and manufacturing, product information is described in an engineering drawing. Because the information is described in this form, it can be interpreted only by trained engineers. A designer describes the product model in a drawing such that it satisfies various engineering requirements. In the case of CAD/CAM, information must be stored in a computer so that it can manipulated
by software. When using CAD for mechanical design, it is necessary to represent a 3D product model in a computer and therefore techniques are required to con- struct the representation. The representation objects in CAD is a combination of mathematical representation described points, curves and surfaces data structures.
The data structures describe the topology of the CAD-model, how volumes are bounded by faces, faces bounded by edges and edges are bounded by vertices. The geometric description of a face is a mathematically described surface, the geomet- ric description of an edge is a mathematically described curve, and the description of a vertex is a point described by coordinates.
2.5.1 Metamathematical Representations
A planar face can be represented in many different ways: using an analytical equation, and parametric equation. There are two categories of curves that can be represented parametrically: analytic curves and synthetic curves.
2.5.1.1 Analytical Curve and Surfaces
Analytic curves are defined as those that can be described by analytic equations such as lines, circles, and conics. Lines and circles are often expressed in analytic equations. They can also be expressed using parametric representation.
2.5.1.2 Free-form Curves and Surfaces
Analytic curves are usually not sufficient to meet geometric design requirements of mechanical parts. Free-form curves provide designers with greater flexibility and control of a curve shape by changing the positions of the control points [1, Mortenson]. Products such as car bodies, ship hulls, airplane fuselage and wings,
Figure 2.6: B spline surface map [2,CAG]
propeller blades, shoe insoles, and bottles are a few examples that require free- form, or synthetic, curves and surfaces. The parametric curves and surfaces in CAD are piecewise polynomial and rational curves of degree >0. The representa- tion chosen in NURBS - Non Uniform Rational B-splines, a representation format that is numerically stable (minimized rounding errors) and that has very stable numerical algorithms for evaluation, differentiation and more complex operations such as subdivision. These curves and surfaces are described by a set of data points (control points) such as splines and Bezier curves. Spline curve are gener- ated by giving a set of coordinate positions, called control points, which indicate the general shape of the curve[2, CAG]. These control points are then fitted with piecewise continuous parametric polynomial functions. When polynomial sections are fitted so that the curve passes through each control point, the resulting curve is said to interpolate the set of control points.
Surfaces are displayed with their poles of constant U or constant V values con- nected by line are called control polygons. Points at which two surfaces are con- nected with continuity, these joints are called knots, see figure 2.6. NURBS are Non-Uniform Rational B-splines an most important entity of the current geometric modeling systems. NURBS are part of numerous industry wide used standards, such as IGES, STEP. The basis functions used in NURBS are usually denoted as
N in(u) in which i corresponds to the ith control point, and n corresponds with the degree of the basis function. General form of a NURBS is
2.5.1.3 Discrete Representations
As explained in above sections, analytic geometry defines curves and surfaces with mathematical functions. It represents CAD model with continuous geometry form.
Non-uniform rational basis spline (NURBS) curves and surfaces form the founda- tion of the most common analytic geometry representations. In contrast, discrete geometry (also known as faceted geometry) describes a shape as a mesh, discrete points usually connected to form triangles. [23,Ma et al.]This representations are point-based and generally constitute discretizations of the continuous shapes. An analogy to geometry representation is digital image representation in which im- ages can be described analytically with vectors (e.g. PostScript) or discretely with raster graphics (JPEG, PNG). Analytic geometry has effectively unlimited resolu- tion, but discrete geometry is limited to the resolution of the point density used to describe the shape. Discrete geometry models are now easily available and tech- niques developed to process such models makes it suitable for use in CAD/CAM systems. These mesh models are most commonly found in reverse engineering, vi- sualization in finite element analysis and rapid prototyping. 3D scanning machines analyse the surface position at thousands or millions of locations, and construct a discrete digital model. Stereolithography is the process of fabricating solid com- ponents using an additive manufacturing process. These processes create and use discrete geometry, respectively. STL is most common file format for mesh model representations. Other popular file formats includes OBJ,PLY,WRL etc. Figure 2.7 shows a example of mesh CAD model with discrete geometry.
Figure 2.7: CAD model with mesh representation
2.6 CAD Exchange
Sharing CAD data is one of the most important elements of modern manufacturing practice. Exchange of product models among different CAD systems is important to industry and engineering applications [26, Kim et al.]. CAD designer creates a design and generate a model, which is then sent to analysis and manufacturing processes. Because companies use different CAD systems, and there are collab- orations between these companies, CAD data exchange is essential to complete the whole design process. Each system has its own proprietary format to store design geometry and related data. Different CAD/CAM systems are used by man- ufacturing industry, need for interoperability and data exchange between different engineering platforms has increased. Efficient data exchange is critical to effective collaborative engineering, which is of significant importance in Product Life cy- cle Management (PLM) systems. Ideally, once CAD data is created, it could be reused without any additional modification, CAD file should be transferred easily between different CAD systems, up and down inside the manufacturing organiza- tion. Besides, since 3D CAD model has become the base for many other kinds of engineering application such as CAM (Computer-Aided Manufacturing), CFD (Computational Fluid Dynamics) and FEA (Finite Element Analysis). The inter- operability among CAD packages and its downstream application is also gaining
more and more importance. In order to protect copyright data, only limited in- formation is shared by the company file formats. The intermediate file formats are also limited in what they can describe, and they can be interpreted differ- ently by both the sending and receiving systems. Users therefore need to recreate the model to overcome these inconsistencies and make the model usable. This interoperability issues arises as each system has different kernels and different representation scheme for model definition. However the emerging paradigm of Agile Manufacturing has imposed additional requirements of ”Neutral format”
so that Form-Feature information can be readily shared among multiple partners of a virtual enterprise. The STandard for the Exchange of Product model data (STEP) has emerged as the means for neutral form exchange of product related data . For mechanical parts, the description of product data has been standard- ized by ISO and ISO 10303-21 is informally known as STEP.It is an ASCII file based on Boundary Representation (B-Rep) of solid. STEP is most popular and widely used format in CAD/CAM systems which is defined using EXPRESS lan- guage and has different Application Protocols(AP’s) such as AP203, AP214 etc [21, Hunten et al.]. Neutral file formats can share only limited shape information in fixed application protocol. Unfortunately, in real world often data created in one system, when transferred using neutral file format suffers from information loss, and various other inconsistencies issues. Researchers in the field are trying to over come this interoperability issues by proposing different standards and meth- ods for sharing quality data. The paper [25,Tanaka and Kishinami] highlights the interoperability issues and proposes method quality diagnosis of data shared using STEP files. Researcher in this field are working to develop standards for efficient and quality data transfer with minimum data loss [26, Kim et al.].
2.7 Feature Recognition and Problems
2.7.1 Information Loss In Data Exchange
As explained in earlier section, each CAD system has its own method of describing geometry, both mathematically and structurally. However, there is always some loss of information when translating data from one CAD data format to another . When a CAD model is converted from one data format to another, modelling history and designer intent is lost. But in addition, there are problems due to different representation of same data, incomplete mappings or due to numerical errors. On probing into representational error we found that these errors get em- bedded into either topology or geometry definition of the model [27,Gerbino]. The process of data exchange with neutral files involves extensive entity mapping. The sending system maps native entities to supported neutral entities. The receiving system then has to map/represent the neutral entities from IGES or STEP file into its own native CAD entities. Sometimes this entity mapping/representation can change the definition of the native CAD entity. For example mapping an analyti- cal arc or cylinder to a B-Spline curve or a surface. Figure 2.8 shows an example given by [3, You and Chan] explains how cylinder CAD model can be represented using different representations by different CAD modellers. This throws an addi- tional challenge especially to rule based feature recognition systems. The process of recovering missing data or recovering the original data semantic is referred to as data healing.
2.7.2 Information Loss with Complex Object Design
When two or more features interact geometrically, open into one another, and so on, it produces what is generally termed feature interactions. It is a type of complex feature that is formed by the interactions of two or more generic simple
Figure 2.8: Representational issue as explained by [3,You and Chan]
features. When two or more features interact, it not only results into loss of geometric data but it also manifests to a complex topology which makes it difficult for feature recognition systems to recognize features correctly. Figure 2.9. shows example of complex CAD model with interacting features. Interacting features are a major source of difficulties in feature recognition. Feature interactions alter the face and edge patterns associated with the features. This complicates both the identification of the features in a part, and the derivation of all the data about the features required for automated manufacturing planning. When features interact, ambiguity may arise in design due to the non uniqueness of patterns associated with the topology and geometry because of conflicting, redundant or missing data.
Feature Interaction depends widely upon the type of feature representation i.e.
Figure 2.9: Complex CAD model design with interacting features
some represents the features in terms of volume to be removed [28, Sashiku- mar Venkatraman] or it may be represented as connectivity between groups of topological entities such as faces, edges etc. For volumetric feature definitions, a feature interaction corresponds to an interaction of the volumes of two (or more) features. For topology-based feature definitions, an interaction correspond to mod- ification of the topological elements (faces, edges etc.) Feature interaction may also be classified further as manufacturing plan-level interactions besides the geome- try and topology interactions. Here feature interaction does not deal with the actual topological or geometric level modification but interaction that occur dur- ing actual manufacturing a feature. During manufacturing one feature may affect the neighbouring features, feature interaction is also reflected during planning an operation sequence.
Feature interaction has been an open research problem for the past several years [29, Zhang]. Most of the approaches treat this as a search problem wherein a convergence to a particular solution is achieved by supplying additional informa- tion through hints, or by systematically rejecting possible hypothesis. When one particular method is not found suitable, hybrid methods are employed [30, Sunil et al.]. However till date there is no generic solution to the problem.
2.7.3 Data Reconstruction from Discrete CAD Represen- tation
Mesh model is represented with low level geometry in discrete form in terms of set of connected triangles. The process of extracting high level data from low level geometry such as mesh is done with step by step of abstraction. Recon- structing complete CAD model from triangular mesh into high level B-rep model is very tedious process [31, B´eni`ere et al.]. Mesh reconstruction, segmentation and surface fitting are the fundamental processes which try to associate high level
geometry/topology information to raw 3D data by applying differential geome- try fundamentals. Many ideas in surface reconstruction originate from disciplines such as computational geometry and computer vision. Although the major focus of research till date in 3D shape reconstruction has been to extract primary sur- face geometry from mesh model, recent trend is towards extracting higher level semantic information for shape understanding [32,Attene et al.].
2.8 Summary
Data loss is a common problem with traditional CAD design environment as well as with todays reverse engineering technology. Inaccuracy in data may occur due to data exchange problem in CAD systems, due to data capture or due to approx- imation in reverse engineered objects. Recovery of this missing data or healing inaccuracies with B-rep solid model is still a challenging problem for research com- munity. Many researcher are trying to address this problem in recent years [27, Gerbino]. In case of data exchange issues data healing algorithms are proposed to simplify geometry and topology complexity. There are various commercial trans- lation software’s that have proposed data healing methods but they are limited to certain specific file formats. On reverse engineering front, research on data in- consistencies is an upcoming research area and already interesting methods have been developed to tackle this problem [33, Langbein] using beatification method.
Beatification techniques aim to improve the reconstructed model by solving all geometric and topological as well as numerical errors. In our thesis, we aim to recover lost data for manufacturing feature recognition from lossy or approximated models for both continuous as well as discrete representations.
Related Work
3.1 Introduction
Major focus of this chapter is to explore different techniques and methods de- veloped by computer science community for automated feature recognition and related problems like extracting accurate geometrical data, feature interaction, loss of data etc. We shall also discuss solutions available in literature to tackle the problems when two or more features interact and recognition process fails to recognize underlying features. Towards the end we shall focus on discrete mesh representation and techniques available for semantic level data abstraction from mesh.
3.2 Overview of Feature Recognition Techniques
Automatic feature recognition (AFR) is one of the major research problem for more than two decades in CAD industry and hence literature presents a plethora of algorithms addressing the same. Different methodologies and techniques de- veloped can be found in vast literature, such as[18, Mangesh P. Bhandarkar],[34,
28
J. Gao],[35, P.K. Jain],[36, N. Ismail]. Some of these belong to methods or tech- niques as for example graph Based methods, syntactic pattern recognition, volume based, rule based etc. All these are going to be presented shortly in the next sec- tion. Survey papers by [37,S. Subrahmanyam] presented a survey paper on feature recognition techniques. They discussed on various methods like cell division, cav- ity volume, convex hull, laminae slicing etc. The authors focused on the future needs or scope, in order to integrate CAD/CAM. [10, Marefat] gives a detail sur- vey with definition of features, different representation schemes of geometric data and the application scope for each is discussed. In addition, the problem is ad- dressed from the perspective of information input requirements. Here author also highlights the interacting features issues and mechanisms for attacking the same.
A very recent survey paper on AFR technique is presented by [19, Babic et al.], which gives an excellent survey with novel classification of AFR method and focus on rule-based pattern recognition. Authors has discussed the feature recognition process according to different subtask involved in it,they categorised subtask as (i) extraction of geometric primitives from a CAD model; (ii) defining a suitable part representation for form feature identification; and (iii) feature pattern matching.
Most important and successful AFR techniques from the literature are discussed in detail below.
3.2.1 Syntactic Pattern Recognition
In syntactic pattern recognition a CAD model is represented using semantic prim- itives written in some description language. It is a technique for representing complex patterns in terms of simple sub patterns and relations among sub pat- terns. A set of rules also termed as grammar defines a particular pattern. A model consisting geometric primitives is then described by organizing the primitives into an expression according to grammar rules. Two grammar rules are applied to form the expressions for a model. Some authors give an analogy of an alphabet
in a formal language to the syntactic pattern recognition. As in formal language alphabets are combined into words and sentences similarly sequences of geometric primitives can be combined to form an expression that represents the complex patterns of features. The different combination of sequences can be organized ac- cording to syntactic language rules, just like the grammar for a formal language.
The parser is used for input sentence analysis which apply a grammar to the part description. If the syntax agrees with the grammar, then the description can be classified in a group according to the pattern. Parser checks for input string, se- mantics will be recognized if it can be classified in a group of predefined patterns.
Figure 3.1 shows general architecture of syntactic pattern recognition. The draw- back of this technique is that, it works successfully only to 2D parts, rotational parts with turning features and and axis symmetric volumes.
Figure 3.1: General architecture of syntactic pattern recognition
3.2.2 Graph-based Feature Recognition
In graph-based feature recognition, the topological shape of a part is represented as a graph, generally with nodes of the graph corresponding to the faces of the object and the arcs of the graph corresponding to the edges of the object. Major contribution in Graph based feature recognition was first presented by Joshi and Chang [38, S.Joshi and Chang] as attributed adjacency graph (AAG) for a part.
The AAG uses faces and edges information of a model into graph representation.
An AAG is defined as a triple G (N, A, T), where N is the set of nodes, A is the set
of arcs (links), and T is a set of attribute values for arcs in A. Here every arc takes attribute value as 0, if its nodes have a concave adjacency relation, or 1, if they have convex adjacency relation. Figure 3.2 shows a part (an object with a slot feature) and its AAG as illustrated by Qiang Ji and Marefet in [10, Marefat]. Features in the graph are represented as subgraphs of AAG and these features are recognised as finding such subgraphs that can be matched with the patterns from the database.
Major disadvantage of this scheme is that searching a feature general definitions becomes complicated due to the large number of patterns. Only a limited set of features patterns can be defined in most of the graph based approaches and also AAG cannot be applied on curved surface model. Several variations in the graph based methods are available in the literature which gives better results than AAG such as multi-attributed adjacency graph (MAAG) by Gavankar and Henderson [39, P.S. Gavankar] and also [40, P.K. Venuvinod]etc. All graph-based methods require extensive preprocessing to generate graph and sub graphs of a given part which makes it computationally very complex and expensive.
Figure 3.2: Graph based recognition(a)CAD model with slot feature;(b)Graph representation of entire model;(c) Recognised slot feature as subgraph
3.2.3 Rule-based Feature Recognition
In rule-based methods, rules attempt to specify a set of necessary and sufficient preconditions for the patterns found in a feature. A set of rules, IF R1, R2, R3 . . . Rn THEN A, defining features in a part, if the conditions (R1, R2, R3) defined by some pattern are satisfied then corresponding feature in the part is
