FEATURE-BASED METHODOLOGIES FOR MILLING PROCESS MODELING IN VIRTUAL MACHINING by Jue Wang B.Eng., Wuhan University of Technology, 1989 M.Eng., Huazhong University of Science and Technology, 1996 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in The Faculty of Graduate Studies (Mechanical Engineering) THE UNIVERSITY OF BRITISH COLUMBIA September 2006 ©JueWang, 2006 Abstract Virtual Machining is used to simulate the machining process prior to actual machining, thereby avoiding costly test trials on the shop floor. To realize Virtual Machining, two major methodologies, Geometric Modeling and Process Modeling, are required. In geometric modeling, Cutter/Workpiece Engagements (CWEs) are extracted to support force prediction in process modeling. In process modeling, the physics of the machining process, such as cutting forces, torque and power, are predicted by integrating the laws of the metal cutting process with CWEs generated in geometric modeling. Based on these predictions, process parameters can be optimized for productivity. Methodologies in geometric modeling for CWE extraction require a large number of calculations, however, the robustness and computational stability of these approaches is a significant challenge. In this thesis, methodologies are developed to address these problems in CWE extraction for the milling process. These methodologies achieve computational efficiency and stability by reducing the number of intersections that need to be performed and by parallelizing computational activities in the process of CWE extraction. A featurebased approach is presented for CWE extraction in 2V2D end milling by introducing inprocess machining features into process modeling. In hole milling, an analytical approach is presented for CWE extraction, and a NURBS based approach is developed for generating the swept volume for in-process workpiece modeling. A Multi-Agent System based framework is developed to improve efficiency of the CWE calculation, by parallelizing computational activities and utilizing free resources over a network. Table of Contents Abstract ii Table of Contents iii List of Tables viii List of Figures ix List of Algorithms xii Acknowledgements xiii Chapter 1 Introduction • 1 1.1 Virtual Machining 1 1.2 Process Modeling and Optimization 2 1.3 Geometric Modeling for Virtual Machining 3 1.4 Feature-Based Modeling and Planning 9 1.5 Multi-Agent Systems 11 1.6 Objectives 13 1.7 Organization of Thesis • Chapter 2 Literature Review 14 15 2.1 Introduction 15 2.2 Force Prediction Models in Virtual Machining 15 2.3 Cutter/Workpiece Engagement Extraction 17 2.3.1 B-rep Based Approaches 17 2.3.2 Discrete Vector Approaches 19 2.3.3 Polyhedral Based Approaches 21 2.3.4 Discussion 22 2.4 Feature Recognition 23 2.4.1 Graph Based Recognition 23 2.4.2 Volume Decomposition 25 2.4.3 Convex Hull Decomposition 26 - iii - 2.4.4 Hint Based Recognition 27 2.4.5 Discussion 28 2.5 Swept Volume Generation 28 2.5.1 Jacobian Rank Deficiency Approach 29 2.5.2 Sweep Differential Equation Approach 29 2.5.3 Solid Model Based Approaches 30 2.5.4 Discussion 32 2.6 Distributed, Collaborative and Multi-Agent Systems for Engineering 32 2.6.1 Distributed and Collaborative Systems for Engineering 32 2.6.2 Integration of Multi-Agent Systems and Web Technologies for Engineering 33 2.6.3 Discussion • 2.7 Summary 34 35 Chapter 3 Feature Taxonomy for Process Modeling 36 3.1 Introduction 36 3.2 Machining Features 36 3.3 Feature Taxonomy 37 3.4 Cutter Engagement Machining Features 40 3.5 Removal Volume Machining Features 41 3.6 Geometric Invariant and Form Invariant Machining Features 43 3.6.1 Geometric Invariant Machining Features 44 3.6.2 Form Invariant Machining Features 45 3.7 Summary 46 Chapter 4 A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2ViD End Milling 48 4.1 Introduction • 48 4.2 Overview 50 4.3 Swept Volume Generation 51 4.4 Removal Volume Generation 52 4.5 In-Process Feature Recognition 53 4.5.1 Decomposition Operator 54 4.5.2 Segmentation Operator 57 - iv - 4.5.3 Extraction Operator 68 4.6 Extraction of Cutter/Workpiece Engagement 70 4.7 Implementation and Validation 73 4.7.1 Implementation 73 4.7.2 Validation of Feature Recognition 74 4.7.3 Validation of CWE Extraction 76 4.8 Discussion 78 Chapter 5 Cutter/Workpiece Engagement Extraction for Hole Milling 79 5.1 Introduction 79 5.2 Milled Hole Machining Feature : 80 5.3 Parametrization of Cutter Engagement Feature for a Hole 82 5.3.1 Intersection between Cylinder and Helicoid 83 5.3.2 Constraint 1: Valid Engagement Range 86 5.3.3 Constraint 2: Intersection Point 87 5.3.4 Constraint 3: Connection Point 88 5.3.5 Parametric Representation of Cutter Engagement Feature 89 5.4 Implementation 92 5.4.1 Test Part 92 5.4.2 Results • 5.5 Discussion 93 96 Chapter 6 In-Process Workpiece Modeling in Hole Milling 99 6.1 Introduction 99 6.2 NURBS Curves and Surfaces 100 6.2.1 NURBS Curves 100 6.2.2 NURBS Surfaces 101 6.3 Swept Volume Generation • 102 6.3.1 Overview 103 6.3.2 Silhouette Curves Identification 105 6.3.3 Envelope Surfaces Generation 108 6.3.4 Surface Trimming HI -v- 6.3.5 Surface Stitching 112 6.4 In-Process Workpiece Modeling 113 6.5 Implementation and Validation 113 6.6 Discussion 116 Chapter 7 A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction 118 7.1 Introduction 118 7.2 General Approach to CWE Calculations 119 7.3 Multi-Agent Framework for CWE Calculations 120 7.3.1 Agent Specification in CWE Calculation MAS 121 7.3.2 Agent Collaboration in CWE Calculation MAS 122 7.4 Implementation and Example 134 7.5 Discussion 137 Chapter 8 Conclusion 139 8.1 Contribution 139 8.2 Future Work 140 Bibliography 142 Appendix A Entry and Exit Position Calculations 147 A. 1 Linear Tool Motion/Linear Edge 147 A.2 Linear Tool Motion/Circular Edge 150 A.3 Circular Tool Motion/Linear Edge 153 A.4 Circular Tool Motion/Circular Edge 155 Appendix B Helicoid Equation (5.6) 159 Appendix C Intersection and Connection Point Calculation Equation (5.10) 161 Appendix D Silhouette Curves of End-Mills 163 D. 1 Silhouette Curves of a Flat End-Mill 163 D.2 Silhouette Curves of a Conical End-Mill D.2.1 Calculating P and P 3 164 165 5 D.2.2 Calculating Control Point Q for Silhouette Curve 1 and 2 0 - vi - 167 Appendix E The Sat Files of an Envelope Surface 169 E.l The Sat File by Exact NURBS Representation Method 170 E.2 The Sat File by Skinning Method 173 - vii - List of Tables Table 1-1: Comparison of CWE Extraction Approaches 6 Table 4-1: Labeled Segments 64 Table 4-2: Simulation Times for Feature Recognition 76 Table 5-1: Parameters of mhFs for Roughing Stage 93 Table 6-1: Control Points for Silhouette Curves of a Ball End-Mill 107 Table 6-2: Swept Volume Generation and Verification for a Flat End-Mill 115 Table 6-3: Swept Volume Generation and Verification for a Ball End-Mill 115 Table 6-4: Swept Volume Generation and Verification for a Conical End-Mill 116 Table 7-1: Calculation Time in CWE Calculation MAS 136 - viii - List of Figures Figure 1-1: Virtual M a c h i n i n g 2 Figure 1-2: CWE Formats for Force Prediction M o d e l 3 Figure 1-3: Steps for CWE Extraction in Geometric M o d e l i n g 4 Figure 1-4: Swept V o l u m e from 2YiD Flat E n d M i l l i n g 6 Figure 1-5: In-Process Workpiece Generation 7 Figure 1-6: In-Process Workpiece States during a Machining Operation 8 Figure 1-7: Cutter/Workpiece Engagement Extraction 8 Figure 1-8: M a c h i n i n g Features 10 Figure 1-9: Removal V o l u m e Generation 10 Figure 1-10: Removal V o l u m e Decomposition 11 Figure 1-11: Proposed MAS Based Framework for CWE Extraction 12 Figure 2-1: CWE Zone in the Force Prediction M o d e l 17 Figure 2-2: CWE Calculations for 2'/ D End M i l l i n g : the Spence Approach 18 Figure 2-3: CWE Calculations for 2'/ D E n d M i l l i n g : Y i p - H o i Approach 19 Figure 2-4: N o r m a l Vector Approach 20 Figure 2-5: Extended Z-buffer Approach 21 Figure 2-6: CWE Calculations by Polyhedral Based Approach 22 Figure 2-7: Graph Based Approach to Feature Recognition 24 Figure 2-8: V o l u m e Decomposition Approach to Feature Recognition 26 Figure 2-9: Alternating Sum o f Volumes Decomposition 27 Figure 2-10: Ingress, Egress and Grazing Points on the Boundary o f the Object 30 Figure 2-11: Solid M o d e l Based Approaches 31 Figure 3-1: M a c h i n i n g Feature Classification for Process M o d e l i n g 38 Figure 3-2: Cutter Engagement Machining Features 40 Figure 3-3: Removal V o l u m e Machining Features 43 Figure 3-4: Geometric Invariant Machining Features 44 Figure 3-5: F o r m Invariant Machining Features 45 2 2 Figure 4-1: ceFs Extraction using Advancing Semi-Cylinder 49 Figure 4-2: Removal V o l u m e Decomposition 50 Figure 4-3: Steps in CWE Extraction for 2'/ D End M i l l i n g 51 Figure 4-4: Swept V o l u m e Generation for 2!/ D End M i l l i n g 52 Figure 4-5: In-Process Workpiece and Removal V o l u m e in the /'-th T o o l M o t i o n 53 2 2 - ix - Figure 4-6: In-Process Feature Recognition 54 Figure 4-7: Definition of Minimal Volumes 55 Figure 4-8: Removal Volume Decomposition 56 Figure 4-9: Geometric Invariant and Form Invariant Segments 57 Figure 4-10: A Flowchart of the Segmentation Operator 58 Figure 4-11: Minimal Volume Projection 59 Figure 4-12: Segment Generation 61 Figure 4-13: Entry and Exit Positions of the Segment 62 Figure 4-14: Geometric Invariant Segments 64 Figure 4-15: Segment Combination for One MV 66 Figure 4-16: Segment Combination for Overlapping MVs 68 Figure 4-17: Feature Extraction from a Removal Volume 69 Figure 4-18: Representation of a fiF Figure 4-19: CWE Extraction from a fiF 71 72 Figure 4-20: Steps in CWE Extraction 73 Figure 4-21: Class Diagram in the CWE Extraction System. 74 Figure 4-22: Examples for Feature Recognition 75 Figure 4-23: An Example of CWE Extraction 77 Figure 5-1: Milled Hole Machining Feature 81 Figure 5-2: Toolpaths for Blind Hole and Through Hole 82 Figure 5-3: Intersection between a Cylinder and a Helicoid 83 Figure 5-4: Z coordinate of the intersection curve: (radius of hole: /?=10mm; radius of cylinder: r=7mm; pitch of helix: /?=40mm) 86 Figure 5-5: Valid Engagement Range 87 Figure 5-6: Intersection Point 88 Figure 5-7: Connection Point 88 Figure 5-8: d , d over the 1 Turn from Eq. (5.11) Figure 5-9: d , d over the Middle Turn from Eq. (5.12) min mm st max max Figure 5-10: d , d min max Figure 5-11: d , d min max 90 91 over the Last Turn for a Blind Hole from Eq. (5.13) 91 over the Last Turn for a Through Hole from Eq. (5.14) 92 Figure 5-12: A Test Part: Gearbox 93 Figure 5-13: Test Case 1: ceF on the mhF at the First Turn ((9=120°) 2 Figure 5-14: Test Case 2: ceF on the mhF, at the Middle Turn ((9=60°) Figure 5-15: Test Case 3: ceF on the mhF at the Last Turn (0=240°) 3 -x- 94 95 96 Figure 5-16: Interacting Features 98 Figure 6-1: In-Process Workpiece in Hole Milling 99 Figure 6-2: NURBS Representation of Line and Arc 101 Figure 6-3: NURBS Representation of a Quadric Surface 102 Figure 6-4: Sweeping a Surface 103 Figure 6-5: Swept Volume Generation 104 Figure 6-6: A Flowchart of the NURBS Based Approach 105 Figure 6-7: Silhouette Curves of a General Surface 106 Figure 6-8: Silhouette Curves for a Ball End-Mill 107 Figure 6-9: NURBS Representation of a Silhouette Curve and a Helical Curve 108 Figure 6-10: Control Polyhedron of the Envelope Surface 110 Figure 6-11: NURBS Surface and Control Polyhedron for an Envelope Surface Ill Figure 6-12: Surfaces Trimming 112 Figure 6-13: In-Process Workpiece Modeling 113 Figure 6-14: Data Structures 114 Figure 7-1: Steps in CWE Calculation 120 Figure 7-2: Agents in CWE Calculation MAS 122 Figure 7-3: Agent Collaboration in CWE Calculation MAS 124 Figure 7-4: Parallelism in CWE Calculation MAS 125 Figure 7-5: Slide Window for Results Passing 128 Figure 7-6: FSMModel of a Receiver Agent 130 Figure 7-7: Protocol for Collaboration 1 (Selecting Master Agent) 131 Figure 7-8: Protocol for Collaboration 2 (Allocating Tasks) 132 Figure 7-9: Protocol for Collaboration 3 (Coordinating Results Submission) 133 Figure 7-10: Implementation of CWE Calculation MAS 134 Figure 7-11: Test Part 136 Figure 7-12: CWE Calculation for the 398th Toolpath Segment 137 - xi - List of Algorithms Algorithm 4-1: Removal Volume Decomposition 56 Algorithm 4-2: Minimal Volume Projection 60 Algorithm 4-3: Segment Generation 63 Algorithm 4-4: Segment Classification 65 Algorithm 4-5: Segment Combination 67 Algorithm 4-6: Feature Extraction 70 - xii - Acknowledgements I would like to express my sincere appreciation to my advisor Professor Derek Y i p - H o i for his guidance i n my studies at the University o f British Columbia, and for his many insightful suggestions regarding the development of the ideas in this thesis. I am especially grateful for the many early morning hours he spent discussing my thesis, which helped me complete it. I would also like to thank Professor Y u s u f Altintas for extending me the opportunity to work on the development of the Virtual Machining project. I would like to express many thanks to my colleagues i n the C A D group and the Manufacturing Automation Laboratory ( M A L ) for their friendship and help. I am grateful to my parents and brother for their encouragement and support. Finally, I would like to thank my wife Qing L i u and her parents for their understanding and for taking care of my son Minghan and daughter Helen, who were born during my studies at U B C . Their support allowed me to focus on my education and research. - xiii - Chapter 1 Introduction 1.1 Virtual Machining To produce mechanical parts correctly and optimally in the manufacturing industry, Virtual Machining (VM) is necessary to simulate the machining process prior to actual machining. There are two methodologies in VM: geometric modeling and process modeling. In geometric modeling, NC toolpaths generated by a C A M system are verified to prevent collisions between the cutter and the workpiece or fixture, to eliminate gouges and uncut material on the surfaces of the final part. Verification is done by examining the in-process workpiece, starting with a model of the initial workpiece. As machining progresses, the geometry of the workpiece gets updated by subtracting the volume swept by the cutter during each motion. Cutter/Workpiece Engagements (CWEs) are also extracted in geometric modeling to support force prediction in process modeling. In process modeling, the physics of the machining process, such as cutting forces, torque and power, are predicted by integrating the laws of the metal cutting process with CWEs generated in geometric modeling. Furthermore, process parameters can be optimized for productivity while ensuring that part quality is achieved. Figure 1-1 illustrates the relationship between geometric and process modeling in VM. A CAD model is input into a CAPP system for process planning. A series of machining operations, which include toolpaths and process parameters such as feed rate and spindle speed, are generated. These toolpaths and process parameters are input into geometric modeling for generating the in-process workpiece for NC verification and CWE extraction. In process modeling, cutting forces and chatter stability are predicted using the CWEs provided from geometric modeling. From the results in process modeling, the process parameters are optimized for productivity while respecting process constraints such as the torque and power limits of the machine, strength of the tool, and dimensional tolerances of the part, as well as chatter vibration limits of the machine tool, fixture and workpiece structures. The optimized process parameters and toolpaths are sent to the CNC machine to efficiently produce the part. Chapter I. Introduction Figure 1-1: Virtual Machining 1.2 Process Modeling and Optimization In process modeling, the cutting forces are predicted based on the CWEs extracted using geometric modeling techniques. In order to properly define the input format from CWE for force prediction, a force model must be identified. In this thesis, the force prediction model used is that proposed by Altintas and Spence [4]. This model solves the Cartesian force components by analytically integrating the differential cutting forces along the in-cut portion of each flute. A single engagement zone at a fixed axial depth of cut is defined by flattening the engagement region on the tool envelop cylinder to determine the integration. As shown in Figure 1-2 (a), the CWE from geometric modeling required by this force model in process modeling should be represented as an engagement zone bounded by the entry {(j) i) and exit s angles (<f> ) of the cutter, as well as by the axial location (d , d ) at a given feed step. For ex min max general engagement conditions, the CWE zone can be discretized into a set of single engagement zones to satisfy the requirements of the force prediction model. As shown in Figure 1-2 (b), a general CWE is parametrized by applying a decomposition procedure. -2- Chapter I. Introduction Therefore, the general CWE zone is decomposed into a set of standard formats required by the force prediction model. t d Umax *maxl cm: cm Zone Z o n e C W E l Z o n e 3 cm: Z o n e 2 rf, mini dmin o 0 (j>st <l>ex (f> fall (a) fiexl dmm2 *min3 <j>si2 <t>ex2 </>sl3 <t>ex3 (j) (b) Figure 1-2: CWE Formats for Force Prediction Model Based on the cutting forces, the chatter stability in milling operations can be predicted by an analytical chatter prediction model. The process parameters, such as depth of cut and spindle speed, can be optimized to achieve maximum productivity according to the predicted chatter stability constraints of the milling operation. 1.3 Geometric Modeling for Virtual Machining CWEs are extracted in geometric modeling based on the input format required by process modeling. Figure 1 -3 illustrates the geometric modeling process for VM. The inputs include the initial workpiece, CLData generated by a C A M system for machining the final part from the workpiece, and the cutting tool descriptions. Based on the latter two pieces of information, swept volumes are generated for the tool moving along each toolpath. By subtracting each swept volume sequentially, a series of in-process workpieces are generated. These in-process workpieces play two important roles in geometric modeling: one is to verify NC toolpaths, and the other is in CWE extraction. CWEs can be extracted by identifying the engagement conditions at feed steps along each toolpath. This procedure involves intersecting a representation of the cutting tool with the in-process workpiece then Chapter I. Introduction manipulating the intersection graph to extract entry and exit angles as a function of depth of cut. Three steps are therefore required to extract CWEs in geometric modeling: (1) swept volume generation; (2) in-process workpiece modeling; and (3) CWE extraction. Each step is introduced in the next sections, following an introduction to the different 3D solid modeling representations that can be used in generating CWEs. CAD/CAM System ( Cutter Geometry X Toolpath (CLData) 41 X Initial Workpiece Geometric Modeling Swept Volume Generation 1 In-Process Workpiece Modeling Figure 1-3: Steps for CWE Extraction in Geometric Modeling Approaches to CWE Extraction Based on 3D solid modeling representations of the workpiece, reported research on geometric modeling identifies four major approaches: B-rep, Z-buffer, normal vector and polyhedral based approaches. The B-rep based approach represents the workpiece using a Boundary Representation (B-rep) model that describes the topological relationship among the different level geometric entities of the boundary of the solid model, such as faces, coedges, -4- Chapter 1. Introduction edges and vertices. A B-rep structure is the 3D solid representation model used in solid modelers. The CWE can be extracted by using numerical Surface/Surface Intersections (SSI) between the workpiece and the cutting tool geometry in solid modelers. The Z-buffer based approach characterizes the workpiece using a z-directional vector model, which consists of a set of z-directional vectors (ZDV) emanating from a grid on a workpiece surface. The CWE can be determined by finding intersections between the tool swept volume and these vectors. This procedure involves calculating intersections between surfaces and lines. The normal vector based approach is derived originally from the technique for accurate color shading of sculptured surfaces. In this approach, the workpiece is discretized into arrays containing surface coordinates and the corresponding normal vectors. Similarly, the CWE is extracted by calculating intersections between implicit solid models representing the motions of the cutting tool and surface normal vectors. The polyhedral based approach represents the workpiece with a polyhedral model. The boundary curves of the CWE can be extracted by performing intersections between the cutting tool geometry and the triangular planes that define the boundary of the polyhedral model. Table 1-1 illustrates a comparison of these four CWE extraction approaches. Although Z-buffer, normal vector and polyhedral based approaches require a shorter computational time than does the B-rep based approach, the accuracy of these approaches depends greatly on the resolution of the workpiece. There is always a tradeoff between accuracy and computational efficiency in these approaches. The B-rep based approach can provide an accurate geometric representation for the workpiece. However, the SSI approaches in solid modelers use numerical techniques that are limited primarily by efficiency and robustness. These limitations have great influence on the stability and efficiency of the B-rep based approach. This thesis focuses on a B-rep based approach to providing an accurate geometric representation for the CWE to support process modeling. Methodologies for improving the stability and efficiency of this approach are also studied. The following sections describe the three main steps in this procedure: (1) swept volume generation, (2) in-process workpiece modeling and (3) CWE extraction in a B-rep based approach. Chapter I. Introduction Solid modeling representations Intersection calculations Computational complexity Solutions Robustness B-rep boundary representation Surface/Surface high exact low Z-buffer z-directional vectors Surface/Line low approximate high Normal Vector normal vectors Surface/Line low approximate high Polyhedral triangular mesh Surface/Plane medium approximate high Table 1-1: Comparison of CWE Extraction Approaches Swept Volume Generation In 2V2D end milling, the swept volumes can be generated by a profile curve sweeping approach using a solid modeler. Figure 1-4 illustrates the swept volumes generated by a linear and a circular tool motion. The great challenge in swept volume generation is in 3- and 5-axis machining where the cutting tools with various geometries move along 3D spatial curves and the orientation of the cutter axis changes. Although significant research has been reported on this topic, general swept volume generation is not a component included in today's C A D systems. Some researchers have reported skinning techniques to generate swept volumes. However, only approximate solutions can be provided by these approaches. The stability and efficiency of these methodologies still need to be improved. (a) Linear Tool Motion (b) Circular Tool Motion Figure 1-4: Swept Volume from 2YiD Flat End Milling In-Process Workpiece Modeling An accurate in-process workpiece representation is required for both N C verification and CWE extraction. In the B-rep based approach, the in-process workpieces can be -6- Chapter I. Introduction generated by subtracting a swept volume from the workpiece. Figure 1-5 shows the generation of the in-process workpiece for the i-th tool motion. SV represents the swept t volume in the i-th tool motion, and W .i is the in-process workpiece before the i-th tool t motion. The in-process workpiece W is updated by subtracting SV from W (Wj.r* SVi). For t t t all tool motions, a series of in-process workpiece states are captured when swept volumes are sequentially subtracted from the initial workpiece. Figure 1-6 illustrates a sequence of inprocess workpieces generated by a machining operation with n tool motions. The initial workpiece (Wo) evolves into the final part (W„) by sequentially subtracting n swept volumes from Wo. The in-process workpieces W and Wj represent the in-process workpiece states t after the i-th andy-th tool motions, respectively. The great challenge in in-process workpiece modeling is that the geometry of the workpiece becomes more and more complicated as machining progresses. A B-rep solid representation of the complicated in-process workpiece has a large data structure that leads to slow and unstable Boolean operations in the solid modeler. The in-process workpiece may be replaced by the removal volume, which has a less complicated geometric structure for CWE extraction in the B-rep based approach. This variation will be used in this research. In-Process Workpiece (Wj.,) In-Process Workpiece (WJ Figure 1-5: In-Process Workpiece Generation Chapter I. Introduction Initial Workpiece (W ) 0 In-Process Workpiece (WJ In-Process Workpiece (Wj) Final Part (WJ Figure 1-6: In-Process Workpiece States during a Machining Operation Cutter/Workpiece Engagement Extraction Cutter/workpiece engagements can be extracted by performing Surface/Surface Intersections (SSI) between the advancing semi-cylindrical surface of a cutter and the inprocess workpiece (or removal volume) at a series of consecutive cutter locations along each tool motion. As shown in Figure 1-7, the in-process workpiece (Wj.i) is a workpiece state immediately before the i-th tool motion (Ti). SSIs between the semi-cylinder and W .j are f performed at each feed step along the tool motion (T,) to extract CWEs. It can be seen that a large number of SSIs are needed for machining a complicated part. The robustness and computational efficiency of this approach are therefore primary concerns. Figure 1-7: Cutter/Workpiece Engagement Extraction - 8 - Chapter I. Introduction From the discussion above, it can be seen that methodologies in geometric modeling for CWE extraction require a large number of calculations. Therefore, the robustness and computational stability of these approaches is a significant challenge. To address these problems, this thesis studies the potential of features to characterize regions of the removal volume for reducing the number of intersections that need to be performed. On a parallel track, this thesis also develops a new computational framework for improving the efficiency of the CWE calculation by parallelizing computational activities and utilizing free resources over a network. 1.4 Feature-Based Modeling and Planning Computer Aided Process Planning (CAPP) is a system for automating process planning, and is vital for integration of C A D and C A M . CAPP utilizes features as the link between C A D and C A M systems. A feature is an abstract concept that refers to a region of interest on a component within a specific application domain. Features can be defined with respect to domains such as design, process planning and manufacturing. Machining features capture the manufacturing perspective of a product. A machining feature is defined as a region of interest on a workpiece generated by the removal of material with cutting tools during a sequence of machining operations. In CAPP, one strategy utilizes feature recognition to extract machining features from a C A D model. As shown in Figure 1-8, machining features such as holes, slots and pockets are recognized from the final part. After feature recognition, machining features are mapped to a set of machining operations for creating each feature using knowledge based techniques, e.g., an Expert System. As a result, each machining feature becomes associated with a set of machining operations. For instance, a hole feature might be linked to a center-drill, drill, counter-sink and ream operation sequence. To facilitate CWE extraction, this thesis proposes that in-process machining features be introduced into process modeling to represent regions of interest within the volumes removed during machining operations. To illustrate, in Figure 1-9, the removal volume (RV,) can be generated by performing a Boolean intersection between the swept volume (SVj) and the inprocess workpiece (Wj.i). This approach uses the removal volume to calculate CWE instead of using the in-process workpiece, as it typically has a less complicated geometric structure than the in-process workpiece. As shown in Figure 1-10, a removal volume can be -9- Chapter I. Introduction decomposed into two classes of in-process machining features. Geometric Invariant Machining Features (giF) and Form Invariant Machining Features (fiF) are defined to characterize regions of the removal volume where the CWE is constant or changing in a predicable way. The advantage of defining giFs and fiFs is that CWEs can be analytically extracted from giFs and fiFs without applying repetitive SSI operations. Computational stability and efficiency can thereby be improved significantly. Figure 1-8: Machining Features It can be seen from the above that the introduction of an in-process machining feature into the process modeling domain leads to a comprehensive and unambiguous description of the characterized regions during a machining operation. This description helps develop algorithms to extract these features for facilitating process modeling more efficiently. In-Process Workpiece (W^i) Figure 1-9: Removal Volume Generation - 10- Chapter I. Introduction Figure 1-10: Removal Volume Decomposition 1.5 Multi-Agent S y s t e m s Multi-Agent Systems (MAS) have been developed to provide methodologies for the construction of complex systems involving multiple agents and mechanisms for coordination of independent agents' actions. A n independent agent can be considered as an entity with goals, actions, and knowledge, situated in an environment. MAS can speed up the operation of a system by providing a framework for parallel computing. In particular, the parallelism within a MAS can help mitigate limitations imposed by time-critial requirements. To achieve parallel computing, a MAS breaks tasks into several independent subtasks that can be handled by separate agents. To achieve computational efficiency in CWE extraction, a MAS based framework is proposed to facilitate parallel processing. As discussed previously, the B-rep based CWE extraction approach decomposes the CWE extraction procedure into the following three computational activities: • Swept Volume Generation This activity can achieve full parallelism, since swept volume generation depends only on the toolpath and the associated cutting tool. -11 - Chapter 1. Introduction Removal Volume Generation This activity can only achieve partial parallelism, because the creation of removal volumes requires an accurate in-process model of the workpiece after the previous tool motion. It may be possible to group toolpaths (e.g., on different regions of the part) and to partition the in-process model of the workpiece for parallelism. CWE Extraction This activity can achieve full parallelism since CWE extraction depends only on the removal volume (generated from the previous step), toolpath and cutting tool geometry. Inputs Cutting Tool Toolpath Cicomctn Tool Motion (1-10) SVAgents Group SV Tool 1 Agcntl Motion y " SV Tool (1-3) SV Agcnt2 Motion Tool (4-") Agcnt3 Motion (8-10) Asynchronous RVAgents Group RV R V Agent 1 Tool Motion Tool (1-6) Agcnt2 Motion (~-I0) Asynchronous CWE Agents Group CWE Tool Agintl Motion tl-5) CWE Iool Agent2 Motion (6-8) f id ,v CWE Tool Agcnt3 Motion (9-10) Figure 1-11: Proposed MAS Based Framework for CWE Extraction In the proposed MAS based framework, three computational agents, the Cutter/Workpiece Engagement Agent (CWE Agent), Removal Volume Agent (RV Agent) and Swept Volume Agent (SV Agent), are designed with respect to the corresponding computational activities. - 12- Chapter I. Introduction Figure 1-11 illustrates how these agents achieve parallelism within the framework. It can be seen that computational tasks are shared among agents within each group to achieve parallelism by using the strategy of tasks allocation. In addition, the different groups can also achieve parallelism by using an asynchronous results passing strategy. 1.6 Objectives The objective of this thesis is to develop feature based methodologies that facilitate the extraction of CWE geometry in support of milling process modeling for Virtual Machining. This objective is achieved through methods that reduce the number of intersections that need to be performed and parallelize computational activities in the process of CWE extraction. Toward this objective, the following contributions are presented in this thesis: • A novel in-process machining feature to address the computational complexity and robustness issues in CWE calculations. In-process machining features provide an unambiguous description of removal volume regions during a machining operation. They help in the development of robust and efficient algorithms that extract these features. • A feature-based approach to CWE calculation in 2/4D end milling. Geometric invariant and form invariant machining features are modeled to help analytically represent engagement conditions. Volume decomposition and composition algorithms are described that extract these two types of machining features from the removal volumes generated from each toolpath. CWEs can be analytically extracted from geometric invariant and form invariant machining features without applying repetitive SSI operations. The robustness and computational efficiency of the CWE extraction algorithm are significantly improved. • A n analytical approach to CWE extraction for hole milling. A Milled Hole Machining Feature (mhF) and a milling operation that uses a helical toolpath and a flat end-mill are introduced into the domain of process modeling. A n analytical approach is presented to parametrize the CWEs based on parameters of the mhF. The parametric representation of CWEs provides a closed-form formula to the complicated CWE - 13 - Chapter I. Introduction extraction problem in hole milling, and brings significant advantages with respect to accuracy and computational efficiency. • A n advanced NURBS based approach for swept volume generation for hole features generated by helical milling using flat, conical and ball nose end-mills. This approach generates an exact and efficient NURBS representation for the envelop surfaces of the swept volume given the helical toolpath and tool geometry. Boundary surfaces are trimmed at intersections and internal patches are discarded. The boundary patches are then stitched together to form a closed volume. Reported NURBS based approaches can provide approximate solutions only, while this approach can produce an exact solid model of the swept volume. The generated swept volumes are then used for inprocess workpiece modeling for geometric verification purposes. • A multi-agent system for B-rep based CWE extraction that allows distributed processing of the modeling steps over the Internet. The CWE calculation utilizes distributed agents for performing swept volume and removal volume construction in addition to the extraction of the CWE geometry itself. These distributed agents provide the capability to perform many of the calculations in parallel. The proposed methodology thus makes the best use of available, distributed computing resources, leading to greatly improved efficiency in the CWE calculations. If agents are available to perform these calculations using other non-B-rep approaches the proposed framework facilitates their integration. 1.7 Organization of T h e s i s A review of relevant literature is presented in Chapter 2. Chapter 3 introduces a classification of machining features for process modeling. In Chapter 4, a feature-based approach to CWE extraction in IVJL) end milling is presented. A n analytical approach to CWE extraction in hole milling is developed in Chapter 5. In Chapter 6, a NURBS based approach to swept volume generation and in-process workpiece modeling in hole milling is introduced. In Chapter 7, a multi-agent system for distributed, Internet-enabled CWE extraction is presented. Finally, conclusions and future research directions are given in Chapter 8. - 14- Chapter 2 Literature Review 2.1 Introduction As mentioned in Chapter 1, process modeling in Virtual Machining requires the calculation of CWE from geometric modeling to predict the cutting forces. This is a challenging procedure when the geometry of the workpiece becomes more and more complicated as the machining simulation progresses. A n extensive amount of research has focused on geometric and physical simulations of machining processes. These research achievements have contributed to the important techniques that are integrated in a virtual machining environment. Some of important research contributions in this field will be reviewed in this chapter. Specifically, research into force prediction models, swept volume generation and CWE extraction techniques is reviewed. Since machining features and multi-agent systems are introduced for facilitating CWE extraction in this thesis, an overview of previous research work on feature recognition and multi-agent systems is provided. 2 . 2 Force Prediction Models in Virtual Machining The mechanistic model of cutting forces, first proposed by Tlusty and MacNeil [59], has received much attention over the past two decades. Since this model can be used to estimate instantaneous cutting forces, it is widely used in the physical simulation of machining processes to predict cutting tool deflections and optimize machining parameters. Significant research has addressed the mechanistic model of cutting forces. DeVor et al. [16] and Kline et al. [35] refined and extended Tlusty's model by integrating a discrete model of the cutting tool. Fussell [19] extended this discrete model to handle workpiece geometry changes. One of the most well-known approaches to using the mechanistic model for milling processes is that proposed by Altintas and Spence [4]. - 15 - Chapter 2. Literature Review In Altintas' model, the elemental forces of each flute: feed (F ), normal (F ), and axial x y (F ) forces, can be represented by integrating analytically the differential cutting forces along z the in-cut portion of each flute as: Ffyj{z))=^dFfyj{z))b q = x,y,z where dF (<fo(z)) are the differential cutting forces of the flute j. Zjjffi/z)) q and Zjjffi/z)) are the lower and upper axial engagement limits of the in-cut portion of the flute j. To determine the axial integration limits Zjj and z 2 for each flute, a single engagement zone at a fixed axial jt depth of cut is defined by flattening the engagement region on the tool envelop cylinder. As shown in Figure 2-1, the axial integration limits for each flute are identified based on how the helix representing the cutter flute intersects the boundary of the engagement zone. There are five cases with regard to intersection conditions. Each case provides a set of integration limits for the flute. From Figure 2-1, it can be seen that the CWE from geometric modeling required by this force model in process modeling should be represented as an engagement zone bounded by the entry (<p ) and exit angles st of the cutter, and the axial location {d , min dmax) at a given feed step. Mathematically, the CWE at the cutter location PCL can be represented as CWE = / ( & , , ^ , d m i n ,d max ) - For general engagement conditions, the CWE zone can be discretized into a set of standard formats. Yip-Hoi and Huang [70] parametrized general CWEs by applying a decomposition procedure to meet the requirements of this force prediction model. In this thesis, Altintas' model is used for force prediction in process modeling. Therefore, the CWEs extracted from geometric modeling should follow the standard input format {CWE zone illustrated in Figure 2-1) in order to satisfy the requirements of the force prediction model. As discussed in Chapter 1, a general shape of CWEs has to be decomposed into a set of standard CWE zones to be accepted by the force model. - 16- Chapter 2. Literature Review fat <j) ex Figure 2-1: CWE Zone in the Force Prediction Model 2.3 Cutter/Workpiece Engagement Extraction The purpose of CWE extraction is to identify engagement conditions between the cutter and the in-process workpiece during machining operations for predicting the cutting forces. Research work on CWE extraction can be classified into the following areas: • B-rep based approaches • Discrete vector approaches • Polyhedral based approaches These approaches to CWE extraction are discussed in the following subsections. 2.3.1 B-rep Based Approaches Research into B-rep based methodologies to support modeling machining processes has been reported [4, 51-54, 57, 58, 64]. In these approaches, an in-process workpiece is represented by using a B-rep model. In-process workpiece updating and CWE extraction are performed using geometric and topologic algorithms within the solid modeler system. -17- Chapter 2. Literature Review Spence et al. [52] presented an approach to calculating CWE extraction for 2V2D end milling. Figure 2-2 (a) shows a 2ViD end milling process where a flat end mill engages the in-process workpiece (Wj) at a constant depth of cut d. As shown in Figure 2-2 (b), the CWEs can be determined by performing the intersection between an advancing semi-circle C, moving in the tangential direction of the toolpath and boundary edges of the in-process workpiece on an engagement plane PLzjop- As shown in Figure 2-2 (c), the CWE is identified as entry and exit ($ ) angles in the local coordinates of the cutter by the ex intersection of 2D geometry on the plane PLzjop- Due to an assumed constant depth of cut, this approach is limited to 2V2D end milling where the axial depth of the cutter engagement remains constant during machining. (c) Figure 2 - 2 : CWE Calculations for 2VzD End Milling: the Spence Approach (derived from [70]) - 18- Chapter 2. Literature Review Yip-Hoi et al. [70] extended Spence's approach by applying the intersection operation between a semi-cylindrical surface and surfaces of the in-process workpiece. As shown in Figure 2-3, this approach replaces the advancing semi-circle used in Spence's approach with the advancing semi-cylinder. Surface/surface intersections are performed by the solid modeler to imprint the engagement regions on the surface of the cutter. These engagement regions are then decomposed into a set of simpler regions {CWE = ui?/, i = 1, 2,..MR) to satisfy the CWE format required by the force prediction model. This approach extends the CWE calculation to encompass a wider range of geometries, including conditions when the initial workpiece is non-prismatic and when the tooling and setup changes. a (feed direction) Figure 2-3: CWE Calculations for 2V4D End Milling: Yip-Hoi Approach 2.3.2 Discrete Vector Approaches Research into N C verification has resulted in methodologies for determining the correctness of N C toolpaths generated by C A M applications. The primary concern here is to identify gouges or uncut material on a part's surfaces prior to actual machining, to avoid costly rework. However, these approaches can also be adopted for CWE calculations, since -19- Chapter 2. Literature Review calculations of the intersection of the cutting tool and the workpiece are involved in these approaches. A number of approaches are reported in this area, and can be classified into Solid Modeling [52, 53, 70], Z-Map Model [61, 65] and Discrete Vector Approaches [29-32, 41, 42]. In this section, the dominant approaches in N C verification, Discrete Vector Approaches which include the Normal Vector and Z-buffer approaches will be discussed. The Normal Vector approach has been developed by Oliver [41]. As shown in Figure 24, the approach discretizes the workpiece into arrays containing surface coordinates and the corresponding normal vectors. The discretization of the workpiece is based on a computer graphics image of the workpiece surface. Each pixel on the image is projected onto the workpiece surface, and this set of points becomes the approximation to the surface. The normal vector is then determined at each point on the surface. The CWE can be determined by calculating intersections between implicit solid models that represent the motions of the cutting tool and these normal vectors. The problem in this approach is that the pixel-based discretization generates a large number of vectors on the workpiece surface. The computational complexity is high, since every vector has to be separately intersected with every tool movement envelope. Localization methods have been developed by Chang [8] and Huang [26] to eliminate many of the vectors from consideration. Part Surface Figure 2-4: Normal Vector Approach The Z-buffer based approach was developed by Jerard [29, 30, 31, 32]. This approach provides a more flexible strategy to discretize the workpiece than the pixel-based discretization in the Normal Vector based approach. In this approach, the spacing between -20- Chapter 2. Literature Review points can be determined based on the desired accuracy, tool size and shape and local surface curvature. Fussell and Jerard in their recent research [21] presented an extended Z-buffer approach for CWE calculation for 5-axis sculptured surface machining. This approach represents the workpiece with an extended Z-buffer model and the cutting tool with a discrete axial slice model. The extended Z-buffer model represents the workpiece with a set of evenly distributed discrete vectors, called z-directional vectors (ZDVs), with the length of each vector representing the depth of the workpiece. As shown in Figure 2-5, the CWEs can be determined by finding intersections between the tool swept volume and these vectors. Since the tool swept volume can be modeled as a set of geometric primitives such as planes and quadric surfaces, calculation of the intersections between the cutting tool and the workpiece can be simplified to a set of line/surface intersection calculations instead of expensive surface/surface intersection calculations performed in the solid modeler based approaches. Part Surface Vectors Figure 2-5: Extended Z-buffer Approach 2.3.3 Polyhedral Based Approaches Some research has been reported on polyhedral based methodologies. Peng et al. [43] presented a polyhedral model based CWE calculation method. To improve computational efficiency, in this approach, CWE extraction is based on the calculation of the intersections between the cutter and the polyhedral model of removal volumes instead of on in-process workpieces. Efficiency is improved, since the removal volumes have simpler geometry. To further reduce the number of intersection calculations, an R*-tree based localization -21 - Chapter 2. Literature Review technique is adopted to localize those facets that have potential intersections with the cutter (see Figure 2-6). The intersection points between the facet edges and the cutter are calculated by performing line/surface intersections. A validity checking method based on the kinematics model of the cutter is utilized to remove invalid intersection points. After removing these points, a Mark Circle method is used to generate intersection segments between facets and the cutter. Finally, an undirected graph based method is used to connect all the intersection segments and the boundary curves of the cutter surfaces to generate the resultant intersection lines. This approach aims to improve computational efficiency and robustness for CWE extraction by using a polyhedral model for the removal volumes and through the localization technique. It guarantees that the calculations of CWE boundaries can be performed analytically, thus avoiding numerical calculations and the accompanying problems of stability and robustness. Workpiece (W ) Removal Volume t Localization Result Figure 2-6: CWE Calculations by Polyhedral Based Approach 2.3.4 Discussion From the above discussion, it can be seen that B-rep based approaches can provide accurate mathematical representations for intersections. However, the greatest challenge of these approaches is computational complexity and robustness, since numerical surface/surface intersections are involved. Discrete vector approaches and polyhedral based approaches simplify these calculations into line/surface intersection calculations by using discrete representations for the workpiece or removal volume. Although the simplicity of the model results in a shorter computation time than in the B-rep based approach which performs surface/surface intersections, the accuracy of these approaches greatly depends on the -22- Chapter 2. Literature Review resolution of the workpiece or removal volume model. As such, there is always a tradeoff between accuracy and computational efficiency in these approaches. These problems with the CWE extraction approaches motivate the present research to utilize feature-based techniques for improving the computational efficiency and robustness of B-rep based approaches. 2.4 Feature Recognition Computer-aided process planning (CAPP) plays an important role in C A D / C A M integration. A C A D model is interpreted as a set of machining features in a CAPP system. These machining features are extracted from the C A D model by utilizing feature recognition techniques. Based on these machining features, a sequenced set of machining operations can be generated to produce the final part. A wide variety of techniques have been developed for feature recognition. A comprehensive survey and review of feature recognition methodologies is given by Han et al. [23]. These techniques can be classified as follows: • Graph Based Recognition • Volume Decomposition • Convex Hull Decomposition • Hint Based Recognition The approaches of these three areas are briefly described in the following subsections. 2.4.1 Graph Based Recognition The Graph Based approach was first formalized by Joshi [28]. As illustrated in Figure 27, it consists of the following steps: Step 1. Translation In this step, the boundary representation of the part is translated into a part graph where nodes represent faces and arcs represent edges. The part graph has been represented as a B-rep Graph by Sakurai and Gossard [46], Attributed Adjacency Graphs (AAG) by Joshi [28], Face Edge Graphs (FEG) by De Floriani [15], Face Adjacency Hypergraphs (FAH) by Falcidieno and Giannini [18], Vertex Edge Graphs (V-E) by Chuang and Henderson [9] -23 - Chapter 2. Literature Review and Aspect Face Edge Graphs (AFEG) by Corney [12]. Additional information such as edge-convexity is incorporated into the graph. Step 2. Decomposition The graph is decomposed into sub-graphs by removing all faces that cannot form part of a feature. For example, for a depression a face whose incident edges are all convex will be removed from the part graph since this face cannot form part of this type of feature. Step 3. Matching The resulting sub-graphs are analyzed to determine their feature types by matching some predefined feature patterns such as holes and slots. Part Graph Slot Feature Pattern Figure 2-7: Graph Based Approach to Feature Recognition The Graph Based approach has been quite successful in recognizing features without intersections, but encounters many difficulties in recognizing intersecting features. Marefat and Kashyap [40] observed that the arcs between face nodes in the part graph may be missing when features intersect. They proposed a novel solution to restore highly ranked missing arcs -24- Chapter 2. Literature Review into the part graph. Trika and Kashyap [60] devised algorithms that can compute the exact set of missing arcs. However, their algorithms place strong restrictions on input parts, i.e., they must be polyhedral without inclined faces. 2.4.2 Volume Decomposition Volume Decomposition approaches decompose the C A D model into a set of intermediate volumes which are then manipulated to produce features. One of the most wellknown approaches using volume decomposition is that adopted by Sakurai and Chin [45]. This approach is described in the following steps and illustrated in Figure 2-8. Step 1. Delta Volume Generation The delta volume is the volume that must be removed from a stock piece (initial workpiece) to generate the final part. In this step, the delta volume is generated by subtracting the final part from the stock using a solid modeler. Step 2. Decomposition In this step, the delta volume of the part is decomposed into minimal cells by extending and intersecting all the surfaces or halfspaces of the delta volume. Step 3. Combination The set of minimal cells are combined to generate a volume that can be removed by a machining operation. Therefore, the volume is classified as a machining feature. Cell decomposition may generate a large number of cells. The difficulty is how to combine such cells and produce suitable features. Sakurai and Chin [45] proposed generating all possible features. Coles et al. [11] proposed composing the cells into convex volumes only. Even though some heuristics are used to prune unpromising compositions in their approaches, these composition algorithms still have difficulty avoiding combinatorial explosion. -25- Chapter 2. Literature Review Final Part Figure 2-8: Volume Decomposition Approach to Feature Recognition 2.4.3 Convex Hull Decomposition The Convex Hull Decomposition approach was initiated by Kyprianou in 1980 [37], and formalized by Woo [69]. In this approach, a final part is decomposed by using an Alternating Sum of Volumes (ASV) decomposition. The A S V decomposition recursively performs Boolean difference operations (CHD*(P)) to subtract the part (P) from its convex hull (CH(P)) until the null set is reached. Therefore, a sequenced set of convex volumes {P } are 1 generated. The final part can be represented by summing these convex volumes with alternating signs. As illustrated in Figure 2-9, a final part P is decomposed into a set of convex volumes {P , P , P }. The final part P is represented by an alternating sum of convex 1 2 3 volumes as P = P -* P +* P , where -* denotes a difference operation, and +* denotes a 1 2 3 union operation. The main problem with this approach is that it does not guarantee success and may result in an undesirable machining feature model. Another problem with this approach is that it is inherently based on a polyhedral representation of the part. Parts with curved surfaces must first be mapped to the polyhedral models. Kim [33] has extended the A S V approach by introducing a modified A S V decomposition, Alternating Sum of Volumes with Partitioning (ASVP) decomposition, to provide a remedy for non-convergence in the A S V approach. -26- Chapter 2. Literature Review Figure 2-9: Alternating Sum of Volumes Decomposition 2.4.4 Hint Based Recognition Several Hint Based approaches [22, 62, 63] have been developed to address the difficulty of intersecting feature recognition. A Hint Based approach is a strategy that is based on feature hints rather than on rigid feature definitions such as the part graph used in graph based approaches. The IF (Integrated Incremental Feature Finder) methodology 2 developed by Vandenbrande and Requicha [62] follows these steps: Step 1. Generate In the generate step, a proposed removal volume that is a portion of the delta volume is generated by finding a feature trace such as a floor for a slot feature. Step 2. Test The test step checks the boundary of the proposed volume to identify stock faces that originate from the stock and part faces that originate from the part. If the boundary of the proposed removal volume contains any part faces that have the potential of being removed by -27- Chapter 2. Literature Review the cutter when machining this removal volume, the proposed removal volume is identified as non-machinable as a whole. Step 3. R e p a i r The repair step will be applied to remove a subset of the proposed removal volume such that the machining operation does not intrude into the part faces. After the repair step, the removal volume left is taken as a machining feature. The IF approach can recognize intersecting holes, slots and pockets. However, the 2 problem with the IF approach is that a significant number of traces may not lead to valid 2 features; on the other hand, several traces may lead to an identical volumetric feature. These situations lead to computational inefficiency because of the need to perform expensive geometric reasoning on every trace. 2.4.5 Discussion From the above discussion, it can be seen that a significant amount of research on feature recognition has focused on the domain of process planning. Still, a comprehensive solution has not yet been found in this area. Some problems, such as intersecting feature recognition, computational complexity, and integration of manufacturing information with the recognized features, are still under investigation. On the other hand, process planning is just one feature based application domain. There are other areas in the machining domain that have the potential to benefit from the use of feature based techniques. In this research, feature based approaches are applied to a new application area, process modeling, to facilitate CWE extraction. Since this is a new application area being addressed in terms of features, feature recognition methodologies will be investigated in this thesis to extract in-process machining features. 2.5 Swept Volume Generation A swept volume can be defined as the volume generated by the motion of an arbitrary object along an arbitrary path, possibly with arbitrary rotations. As mentioned in Chapter 1, swept volume generation plays an important role in the field of geometric modeling for Virtual Machining, since in-process workpiece modeling and removal volume generation -28- Chapter 2. Literature Review require swept volumes. Although many studies on this topic have been reported during the last two decades, the problem is still not considered to be sufficiently well solved. AbdelMalek et al. [2] presented a comprehensive survey and review on swept volume generation techniques. In the following sections, some of the dominant techniques will be discussed. 2.5.1 Jacobian Rank Deficiency Approach The Jacobian Rank Deficiency (JRD) approach was first proposed by Abdel-Malek et al. [1]. This approach is based on singularity theory in differential geometry. In singularity theory, a manifold with singularities represents a manifold with boundary parts of lower dimensions. In the JRD approach, a rank-deficiency condition is imposed on the constraint Jacobian of the sweep to determine singular sets. The boundary to the resulting swept volume is generated by substituting the resulting singularities into the constraint equation. One advantage of the JRD approach is that the formulation is applicable to entities of any dimension because of the generality of the rank-deficiency condition. Another advantage is that this approach can generate the exact boundary envelope of a swept volume in closed form. The problem with the JRD approach is that its applications are limited to parametric and implicit sweeping. The resulting swept volumes cannot be directly used in solid modeler based simulations since its analytical representation of the boundary does not directly map to any of the native representation forms. 2.5.2 Sweep Differential Equation Approach The Sweep Differential Equation (SDE) approach was first presented by Blackmore et al. [5]. This approach proposes an algorithm for generating swept volumes using the trajectories of sweep differential equations, which is called the Sweep Vector Field (SVF). As illustrated in Figure 2-10, the SVF decomposes the boundary of the moving object into three sets of points: Ingress Points, Egress Points and Grazing Points. The set of ingress (egress) points are all points on the boundary of the object at which the SVF points into (out of) the interior of the object. The set of grazing points are those points that are neither ingress nor egress points. The full curves of these grazing points at each time step are calculated for constructing the boundary envelope of the swept volume. -29- Chapter 2. Literature Review The main problem with the SDE approach is its computational complexity, since the grazing point curves must be calculated at every time step along the sweep. Blackmore et al. [6] extended the SDE approach by introducing the Sweep-Envelope Differential Equation (SEDE). The SEDE approach only needs to calculate the grazing point set at the initial position of the object; the remaining grazing points can be generated by the flow of the sweep-envelop differential equation. Computational efficiency is thereby dramatically improved. Egress Points Ingress Points S w e e p Vector Field (5>Vr) Grazing Points Figure 2-10: Ingress, Egress and Grazing Points on the Boundary of the Object 2.5.3 Solid Model Based Approaches Mathematical approaches such as JRD and SDE represent the boundary of the resulting swept volume with parametric or implicit equations. It is difficult to integrate these swept volumes into solid modeler based approaches for machining simulations. Attempts have been made to generate swept volumes using a B-rep model for ease of integration. Many researchers have proposed curve-skinning techniques to generate these swept volumes. As illustrated in Figure 2-11, the basic philosophy of these approaches is to interpolate a series of profile curves along the path with parametric surfaces (e.g., B-Spline, NURBS surfaces). These profile curves can be silhouette curves of the moving cutter geometry at a sequence of cutter locations along the path or a set of curves that can be considered on the boundary of the swept volume. These envelope surfaces are then stitched together by solid modeler -30- Chapter 2. Literature Review operators to form a B-rep solid model of the swept volume. In these approaches, the key is how to generate these profile curves. The following approaches use different techniques to construct the profile curves. Sheltami et al. [49] proposed a technique that is based on identifying generating curves along the path and connecting them into a solid model of the swept volume. In this approach, a generating curve is approximated by a circle. It is valid only when the cutter moves along a circular path. For 5-axis motions, this approach has difficulty in achieving accuracy. Roth et al. [44] presented a method to generate swept volumes for a 5-axis toolpath. This method discretizes the cutter into pseudo-inserts and identifies imprint points using a modified principle of silhouettes. A n imprint curve at each cutter location is formed by connecting imprint points that exist for each pseudo-insert. A collection of imprint curves are interpolated by curve-skinning techniques to approximate the swept surface. Chung et al. [10] presents an analytical approach for calculating the silhouette curves of a generalized tool. This approach can provide a closed-form solution, but is limited to 3-axis machining simulations. Envelope Surfaces Figure 2-11: Solid Model Based Approaches Weinert et al. [68] proposed an approach for swept volume generation for 5-axis machining. This approach approximates the silhouette curve of a fillet-end cutter by interpolating a set of points on the surface of the cutter. A set of silhouette curves are calculated when the cutter is located at a sequence of cutter locations along the toolpath. The -31 - Chapter 2. Literature Review advantage of this approach is that the silhouette curve of a fillet-end cutter can always be represented in the form of parametric curves for 5-axis motions. The disadvantage of this approach is that the parametric curve is only an approximation to the silhouette curve. Therefore, only approximate solutions to swept volume generation can be made in this approach. 2.5.4 Discussion From the above discussion, it can be seen that the JRD and S D E approaches generate the exact boundary envelope of a swept volume in the form of parametric or implicit equations, making it difficult to integrate with a solid modeler based simulation. On the other hand, the nature of the curve-skinning technique in solid model based approaches only promises an approximation to the swept volume. For some special cases, for example, the helical toolpath in hole milling, there is a potential for the swept volume to be represented as an exact solid model. Unfortunately these approaches can only provide approximate solutions to these special cases. This limitation motivates research in this thesis into methodologies that provide an accurate solution to the swept volumes generated by special motions such as a helical motion. 2.6 Distributed, Collaborative and Multi-Agent Systems for Engineering As discussed in Chapter 1, Multi-Agent System (MAS) can provide a framework for parallel computing. Reported research in this area focuses on the development of distributed, collaborative systems for engineering analysis, design and process planning. Applications have not been found in the field of process modeling, which inspires research efforts to develop a MAS based framework for facilitating CWE extraction in process modeling. In this section, previous work on distributed, collaborative and multi-agent systems for engineering will be reviewed. 2.6.1 Distributed and Collaborative Systems for Engineering Web technologies stimulate research work on developing distributed and collaborative systems for engineering design and manufacturing. These systems normally are implemented by integrating existing engineering techniques with emerging web technologies. This -32- Chapter 2. Literature Review integration provides the possibility of collaborating among geographically distributed teams to achieve their goals. Cutkosky et al. [13] proposed a real-time collaboration environment based on the Internet and knowledge-sharing agreements to facilitate communication among specialists and their tools. Stori and Wright [55] built an internet-based design and manufacturing environment to provide a networked machining service. L i and Lu [39] developed a web-based process planning system to support distributed design and manufacturing analysis. Wang et al. [66] proposed a scheduled role-based distributed data access control model to support data security management in a distributed environment. CAD-based Application Service Providers (ASP) have also evolved in recent years to offer complete C A D modeling via the Internet on a pay-per-month or pay-per-use basis (e.g., Alibre© [38]). These web-based collaborative systems publish their services on the Internet through web service architectures. The web service architecture decomposes the engineering kernel into a set of software components and distributes them on different machines on the server side. These components are not intelligent; no collaborative behaviors can be conducted among them. Therefore, a control unit is always needed to coordinate their work. This architecture imposes a limitation that software components of the engineering kernel can only be distributed among a limited number of machines on the sever side. The user's machine acts as a thin-client whose job is only to collect user inputs and visualize the results. MAS technologies provide an technique called agent mobility to allow a much wider range of distribution, even including the whole of the Internet if web technologies are integrated. Recent research has demonstrated the trend of integration of web and MAS technologies. 2.6.2 Integration of Multi-Agent Systems and Web Technologies for Engineering Reported research shows that MAS technologies are playing an increasingly important role in developing web-based, intelligent, distributed and collaborative applications. [50] and [67] give a comprehensive survey and review of MAS applications in engineering design and manufacturing. There is significant research on the application of agents in the design field, such as PACT, SHARE, SiFA, DIDE, ICM, Co-Designer, and A-Designer. These earlier applications by different groups reveal the important issue of the interoperability between heterogeneous agents and agent systems. FIPA (Foundation of Intelligent Physical Agents) -33 - Chapter 2. Literature Review [71] has been built to improve the interoperability between heterogeneous agents and agent systems. Following FIPA specifications, agent systems can be designed to interoperate with each other for collaborations. FIPA also stimulates the development of FIPA compliant agent platforms such as J A D E , ZEUS and FIPA-OS. Hao et al. [24] reported a FIPA compliant multi-agent framework called A A D E (Autonomous Agent Development Environment). This framework can facilitate the development of collaborative engineering applications by using its development toolkits. In [24], a web-based design and optimization project is implemented based on the A A D E framework. The authors focused only on the development of the FIPA compliant multi-agent framework. The implemented project demonstrates that the job distributions are created only on the server side, and no collaboration actions taken by agents are observed. Therefore, this framework does not fully take advantage of the capabilities of MAS. Huang et al. [27] presented a web-based framework for collaborative product development. Their framework integrates the concept of agents into workflow management. In their research, the workflow of a project is modeled as a network. The concept of agents is introduced to define nodes and the concept of messages to define edges. Through flow messages, agents can collaborate with each other. The advantage of the agent-based framework is that the same agents may be reused in the workflow of different projects without any changes. 2.6.3 Discussion It can be seen that recent research has focused on the integration of web technologies and multi-agent systems. The attractiveness of the Web for propagating information, and multi-agent systems for their distributed, collaborative and intelligent capabilities, can be integrated to make it more efficient in accessing and manipulating information. However, the challenge is how to build a web-based framework that facilitates integration of related emerging technologies. In this thesis, a distributed, web-enabled, MAS based framework is proposed for CWE extraction. The aim of this research is to develop a framework to facilitate the integration of CWE extraction techniques implemented by using different methodologies such as B-rep, Z-buffer and polyhedral based approaches. -34- Chapter 2. Literature Review 2.7 Summary In this chapter, a review of the literature in force prediction models, CWE extraction, feature recognition, swept volume generation, and multi-agent systems are presented. It has been shown that force prediction models have been well developed for predicting cutting forces. The reported CWE extraction approaches have demonstrated difficulty in computational efficiency and robustness. Feature recognition methodologies for process planning have been well addressed, and feature-based methodologies for process modeling need to be investigated. General swept volume generation approaches have been shown to be deficient in providing exact solutions to swept volume generation with the helical path. Distributed, collaborative and multi-agent systems and their application in the field of engineering have been addressed in this chapter. -35 - Chapter 3 Feature Taxonomy for Process Modeling 3.1 Introduction As mentioned in the previous chapters, machining process modeling requires CWE geometry in order to predict cutting forces. The calculation of these engagements is challenging due to the complicated and changing intersection geometry that occurs between the cutter and the in-process workpiece. B-rep solid modelers can be used to perform these calculations by executing intersection operations between the cutter and the workpiece or removal volume at successive cutter locations. These operations utilize parametric surface/surface intersection algorithms. For the large number of engagements that can occur in machining a complicated workpiece, this can be a time-consuming and sometimes unreliable process. To improve the computational efficiency and stability of B-rep based approaches, in this research, in-process machining features are introduced for reducing the number of intersections that need to be performed in process modeling. One of the primary in-process machining features, the cutter engagement machining feature, was first proposed by Yip-Hoi et al. [70] for characterizing the CWE. In this chapter, several in-process machining features are defined for facilitating CWE extraction in process modeling. First, a definition of machining features is introduced. And then, a classification of machining features for process modeling is presented, followed by formal definitions of related in-process machining features in process modeling: Cutter Engagement Machining Features, Removal Volume Machining Features, Geometric Invariant Machining Features and Form Invariant Machining Features. In this chapter, Removal Volume, Geometric Invariant and Form Invariant Machining Features are assumed to be features that can be created using 2 AT> milling operations. l 3.2 Machining Features There are many definitions of the concept of a feature in the literature. Commonly, a feature is considered to be an abstract concept that refers to regions of interest on a component defined within a specific application domain. Features can be defined from -36- Chapter 3. Feature Taxonomy for Process Modeling different viewpoints, such as design, analysis and manufacturing. Machining features are defined from the manufacturing point of view. A Machining Feature (MF) is defined by Shah as follows: A Machining Feature is a collection of related geometric elements which correspond to a particular manufacturing method or process, or which can be.used to reason about the suitable manufacturing methods or processes for creating that geometry. (Shahetal. [48]) Traditionally, machining features are used in the context of process planning. In this domain, machining features are extracted from a C A D model of the final part to aid in the creation of process plans and toolpaths. However, machining feature-based approaches can be useful in a much broader range of application domains. In the process modeling domain, machining features can be classified into a new category: in-process machining features, to be used for capturing regions of interest within volumes removed during machining operations to facilitate CWE extraction. 3.3 Feature Taxonomy There have been many efforts to classify machining features and create feature taxonomies. No agreement on a canonical set of features for any application has yet been reached by the features technology community. Since features are application dependent, it is more practical to classify features based on the specific application domain. As illustrated in Figure 3-1, a classification of machining features for process modeling is proposed. In this feature hierarchy, final part machining features (fpF) are used in process planning. A large number of feature recognition techniques reviewed in the last chapter address the problem of identifying these machining features from a C A D model of the final part. The result is a set of final part machining features {fpF }. A sequence of machining t operations is then generated by process planning. Each operation in turn when executed leads to the creation of in-process machining features (ipF). -37- Chapter 3. Feature Taxonomy for Process Modeling Figure 3-1: Machining Feature Classification for Process Modeling An in-process machining feature is defined as a set of surfaces generated on the workpiece by a sequence of machining operations that lead to a final part machining feature. Distinct from fpFs, ipFs describe intermediate states of the workpiece before a fpF is completely machined. For the purposes of integrating process modeling into process planning, it is necessary to add an ipF node into the feature hierarchy. As shown in Figure 31, an in-process machining feature is classified into In-Cut (icF) and Out-of-Cut (ocF) -38- Chapter 3. Feature Taxonomy for Process Modeling machining features. A n ocF is defined as the intermediate state of the workpiece when the operation or a step is completed and a new operation or another step of the operation is about to be started. It is obvious that the cutter is not engaged with the workpiece at the moment when an ocF is generated. This class of feature can be used in the field of tooling, fixture and gauging design, and inspection planning. On the other hand, icFs capture characteristics of the workpiece during a machining operation when the cutter is engaged with the workpiece. These features help in describing workpiece states during machining operations in process modeling. In-cut machining features can be classified into three categories. Chip machining features (cF) capture the characteristics of chip geometries generated within a single revolution of the cutter. Cutter engagement machining features (ceF) are used to describe the cutter/workpiece engagement over a single revolution of the cutter. ceFs are the primary concern in this thesis, since parametrizations of ceFs are required to provide geometric inputs to a process model. Removal volume machining features (rvF) represent volumes removed by the cutter as it moves along a predefined toolpath. This feature is significant because each rvF contains engagement information and has much less geometric complexity than the inprocess workpiece being generated concurrently. Therefore, in-process workpieces can be replaced by rvFs for cutter/workpiece calculations in order to reduce computational complexity. To reduce the number of intersection calculations in B-rep based solutions, an rvF is decomposed into two classes: Geometric Invariant Machining Features (giF) and Form Invariant Machining Features (fiF). giFs and fiFs are defined to characterize regions of the rvF where the engagement is constant or changing in a predictable way. The definition of giFs and fiFs helps in improving computational efficiency and robustness. In the following sections, formal definitions and mathematical descriptions of the features described above are provided. -39- Chapter 3. Feature Taxonomy for Process Modeling 3.4 Cutter Engagement Machining Features fc*..= / t o Y X Workpiece ceF Figure 3-2: Cutter Engagement Machining Features In process modeling, the definition of Cutter Engagement Features (ceF) is driven by the requirements of a process model, which dictates the type of geometric input required. ceFs are used to describe the engagement conditions between the cutter and the workpiece in the standard format required by the force model. A ceF is defined as follows: A Cutter Engagement Feature is a collection of one or more connected regions on the envelop surface of a cutting tool that approximates the surface generated on the workpiece during one revolution of the cutter. (Yip-Hoi et al. [70]) In their research, a classification of ceFs is presented to represent CWEs generated in 2XD end milling. In this thesis, ceFs need to be extended to represent CWEs in 3-axis end milling process such as hole milling. In this case, the CWE may be bounded by several free-form curves. Generally, a ceF is expressed as follows: m ceF = \j2one i -40- Chapter 3. Feature Taxonomy for Process Modeling where: Zone is called an engagement zone in the axial depth of cut-engagement angle (d-(f>) t domain. It can be represented as Zone[d , dmaxj, (f> u, 0 i\mini s eX Figure 3-2 illustrates a ceF for a hole milling process based on a helical toolpath. This ceF consists of one connected region on the surface of the cutter which is bounded by the entry (fl ) and exit engagement angles (<fi ) of the cutter and limits on the axial depth of cut st [d mini ex d \. The lower (d ) and upper (d ) engagement limits can be represented as a max min max function of the engagement angle <jr. d min = f(</>) and d = f((/>) respectively, where <f> € [<j> max <j) \. When the region on the surface of the cutter is mapped into the d-tfi domain, the ceF is ex then represented as: ceF'= Zonei[d , minl d i, <f> tu <t>exi\ max s Since CWEs extracted from geometric modeling are required to be represented as ceFs, CWE extraction is alternately called ceF extraction in the following chapters. 3.5 Removal V o l u m e Machining Features The goal of defining Removal Volume Machining Features (rvF) is to improve the computational efficiency of B-rep based approaches for CWE extraction by replacing the inprocess workpiece with the removal volume. A rvF is defined as follows: A Removal Volume Machining Feature is a set of one or more material volumes removed by the action of a cutter as it advances along a linear or circular tool motion. An rvF is generated by a regularized Boolean intersection (D*) between the in-process workpiece and the tool swept volume. The latter is formed by sweeping the cutter geometry along a linear or circular tool motion. An rvF contains all the geometric information about engagement conditions between the cutter and workpiece while machining this portion of the workpiece. Its formal definition is expressed as follows: k -41 - s Chapter 3. Feature Taxonomy for Process Modeling where: Ri c £ : A connected regular closed set in 3D Euclidean space. 3 There are two types of surface geometries in the boundary of each rvF element R . One type t is from the in-process workpiece, the other is from the tool swept volume: m n j=] j=\ where: sWif. Surface geometry which originates from the in-process workpiece, called the WBoundary. sSif. Surface geometry which originates from the tool swept volume, called the SBoundary. Figure 3-3 (a) illustrates an example of a linear rvF. In this example, this rvF is composed of two disjoint volumes: rvF = R vR l 2 The surfaces of Ri includes five W-Boundary and two S-Boundary surfaces: R =\sW ,sW ,sW ,slV ,sW }v{sS ,sS } s l ll l2 x3 l4 l5 u i2 The surfaces of R2 includes seven W-Boundary and two S-Boundary surfaces: sR = {sW ,sW , sW ,sW , sW ,sW ,sW }u \sS ,sS } 2 2l 22 2i 24 25 26 21 2l 22 A circular rvF example is shown in Figure 3-3 (b). A single removal volume Ri in this case has five W-Boundary and three S-Boundary surfaces as follows: rvF = R t R^{SW ,SW ,SW ,SW ,SW }KJ{SS ,SS ,SS } S U U U 14 15 U ]2 U -42- Chapter 3. Feature Taxonomy for Process Modeling Tool Swept Volume Removal Volume Machining Feature In-Process Workpiece (a) Linear Tool Motion Tool Swept Volume In-Process Workpiece Removal Volume Machining Feature (b) Circular Tool Motion Figure 3-3: Removal Volume Machining Features 3.6 Geometric Invariant and Form Invariant Machining Features The motivation to define geometric invariant and form invariant machining features is to improve the computational stability and efficiency of B-rep based CWE extraction approaches. A geometric invariant feature characterizes a portion of a removal volume where CWEs are constant while a form invariant feature characterizes a portion where CWEs have a certain topological shape. The characteristics of these features not only reduce the number of intersection calculations but also eliminate numerical surface/surface intersections. CWEs -43 - Chapter 3. Feature Taxonomy for Process Modeling can be extracted from these features analytically. Computational stability and efficiency can be improved significantly as a result. In this section, formal definitions of geometric invariant and form invariant machining features will be given. 3.6.1 Geometric Invariant Machining Features Removal Volume Machining Feature Geometric Invariant Machining Feature Cutter/Workpiece Engagement Figure 3-4: Geometric Invariant Machining Features Figure 3-4 illustrates an example of a Geometric Invariant Machining Feature (giF). The removal volume machining feature is decomposed into several sub-volumes. Two of them have constant cutter/workpiece engagements while the cutter moves along the toolpath to machine them from the workpiece. This feature type is defined as follows: A Geometric Invariant Machining Feature is a portion of a Removal Volume Machining Feature where the cutter engagement features do not change during machining. The mathematical definition is given as follows: where: /?, <z £ : A connected regular closed set in 3D Euclidean space. -443 Chapter 3. Feature Taxonomy for Process Modeling For any two ceFs in a giF, m . ceF = (JZone [d ,d ,<j> x Xi min M itXi n ,<f> J and ceF = ali 2 {JZone \d 2 ,d min2i J ,<f> \, mm2J sl2i ex2i i=l ;=1 the following constraints should be satisfied: • The number of engagement zones of each ceF is constant: m-n • The corresponding engagement zones are identical: dminl.i ~ dmin2,i 3nd d l,i max fistl.i = ~ d x2,i ma <Pst2,i and fexl.i <t>ex2,i = where: i-\,2,...m. 3.6.2 Form Invariant Machining Features Machining Feature Machining Feature Cutter/Workpiece Engagement Figure 3-5: Form Invariant Machining Features Figure 3-5 illustrates an example of a Form Invariant Machining Feature (fiF). The removal volume machining feature is decomposed into several sub-volumes. Four of them have similar forms while the cutter moves along the toolpath to machine them from the workpiece. This feature type is defined as follows: -45- Chapter 3. Feature Taxonomy for Process Modeling A Form Invariant Machining Feature is a portion of a Removal Volume Machining Feature where the cutter engagements features have similar shapes during machining. The mathematical definition is given as follows: fiF = \jR, /=i where: Rj c E : A connected regular closed set in 3D Euclidean space. 3 For any two ceFs in a fiF, ceF = \JZone \d ,d ,<p ,(/> \and 1=1 x ] minV m!a]i sni ceF = exli {JZone \d 2 2 ,d min2i ,^ ,</> \, mXi2i sl2i ex2i ,=i the following constraints should be satisfied: • The number of engagement zones of each ceF is constant: m-n • The corresponding engagement zones are similar: dmin I, i ~ d i 2,i and d axl,i ~ d x2,i m n <l>stl,i ± <j>st2,i ma m Or <f> exU f (f) 2,i ex where: z-1,2,...m. 3.7 Summary In this chapter, in-process machining features are added into the machining feature hierarchy to capture the characteristics of the workpiece geometry during machining operations. Some related in-process machining features, such as Cutter Engagement, Removal Volume, Geometric Invariant and Form Invariant, are formally defined in this chapter. The definition of these in-process machining features in process modeling helps to improve the computational efficiency and robustness of B-rep based CWE extraction -46- Chapter 3. Feature Taxonomy for Process Modeling approaches by reducing geometric complexity and the number of numerical surface/surface intersection calculations. These definitions are one of contributions of this research. -47- Chapter 4 A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in IViD End Milling 4.1 Introduction As described in the previous chapters, cutting forces are a key input in simulating the vibration of machine tools prior to implementing the real machining process. This simulation can be used to optimize instantaneous process parameters to avoid chatter and improve machining quality. Instantaneous cutting forces are determined by the feed rate, spindle speed, and CWE (which captures the depth of cut). Performing CWE calculations is difficult due to the complex geometry of the in-process workpiece. In 2V2D end milling, a B-rep solid modeler based CWE calculation approach determines engagements by performing Surface/Surface Intersections (SSI) between the advancing semicylindrical surface of a cutter and either the in-process workpiece or the removal volume (see Figure 4-1). Intersecting the removal volume is preferred since the removal volume typically has less complicated geometry than the in-process workpiece. The robustness and computational efficiency of this advancing semi-cylinder approach significantly depends on the solid modeler, since it utilizes the SSI algorithm within the modeler to retrieve CWE boundary curves. The following are several problems in realizing this advancing semicylinder approach: • The SSI approaches in most solid modelers use numerical techniques that are limited by accuracy, efficiency and robustness. These have great influence on the stability and efficiency of the advancing semi-cylinder approach. • Numerical techniques in SSI provide only an approximation to CWE even though the intersecting surfaces are quadric surfaces, which are common in 2'/zD end milling process. Quadric Surface/Surface Intersection can be solved by algebraic or geometric approaches to obtain exact solutions for CWEs. -48- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling • CWEs at a series of consecutive cutter locations may have the same geometry, which leads to duplication of identical SSI computations. As illustrated in Figure 4-1, an advancing semi-cylinder intersects the removal volume at several cutter locations with constant interval 5. There are two groups of consecutive Cutter Engagement Features (ceFs), {ceF2, ceFz, ceF4} and {ceF , ceFy, ceF }, where the 6 8 ceFs are identical. If a subset of volumes with invariant ceFs can be identified from the removal volume, only a single SSI is needed for each sub-volume. Computational efficiency will be significantly improved. Figure 4-1: ceFs Extraction using Advancing Semi-Cylinder In this chapter, a feature-based approach is presented that addresses the above problems in the B-rep solid modeler based approach. This feature-based approach decomposes a removal volume into two classes of features by using a feature recognition technique. As shown in Figure 4-2, volumes with invariant ceF are defined as Geometric Invariant Features igiF), and volumes with invariant form are classified as Form Invariant Features (fiF). The formal definitions of giF and fiF were given in the last chapter. The extraction of giFs and fiFs reduces duplication of the identical engagement calculation. Accurate analytical representations of ceFs based on these features parameters are also presented in this chapter. Formally, ceF can be represented as a closed-form single-variable function ceF(u), where variable u is a parameter representing position along a linear or circular segment of tool motion. As shown in Figure 4-1, P(u) is a cutter location within a segment of a tool motion, -49- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2>/ D End Milling 2 « e [ 0 , l ] . For example, ceF4 is the cutter engagement feature with the cutter located at cutter location P(uA. Geometric Invariant Feature I Form Invariant Feature Figure 4-2: Removal Volume Decomposition Following an overview of this feature-based approach, swept volume and removal volume generation methods are presented. A set of operators used to decompose the removal volume into these feature types are then introduced. A feature recognition algorithm based on these operators is presented to recognize these machining features. After feature recognition, the CWE is retrieved from the recognized machining features. Finally, implementation and validation are presented. 4.2 Overview A feature-based methodology for CWE extraction in 2V£D end milling is illustrated in Figure 4-3. This approach has four major steps: swept volume generation, removal volume generation, in-process feature recognition and CWE extraction. The first step is to generate a swept volume for each tool motion. In the second step, the swept volume is used to create a removal volume by applying a Boolean intersection operation between the swept volume and the in-process workpiece, and to create an in-process workpiece by subtracting the swept volume from the previous in-process workpiece as well. The removal volume is decomposed -50- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling _ into giFs and fiFs in the In-Process Feature Recognition step. After this step, a set of giFs and/or fiFs are generated. The final step is to analytically extract CWEs from both giFs and fiFs. This is significant because analytical CWE extraction reduces the problem of computational efficiency and robustness found in numerical extraction methods. These four steps will be described in the following sections. START ^) Workpiece lool iii'iMiicln Tool Motions -2. Inputs Swept Volume Swept Volume Generation Removal Volume 2. Removal Volume Generation giFs & fiFs 3. In-Process Feature Recognition Figure 4-3: Steps in CWE Extraction for 2V4D E n d M i l l i n g 4.3 Swept Volume Generation In 2/4D end milling, swept volumes are easily generated, since the cutting tool moves on the X Y plane. Figure 4-4 illustrates how swept volumes are generated when the cutting tool moves in linear and circular motions, which happens in 2 / D end milling. A 2D closed 1 2 profile curve on the X Y plane where the tip of the cutting tool is located is created based on the cutting tool geometry and tool motion. The profile curve is then swept along the tool axis 51 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling direction (Z direction in 2VJ) milling) to form a closed volume. Normally, a swept volume is represented as a B-Rep solid to facilitate the CWE calculation using a solid modeler. Figure 4-4: Swept Volume Generation for 2ViD End Milling 4.4 Removal Volume Generation The in-process workpiece is defined as a state of the workpiece during a machining process. These intermediate models are updated as the workpiece is machined by the cutter moving along a series of predefined tool motions. The in-process workpiece can be generated by subtracting a swept volume, which is created by sweeping the geometry of the cutter along the current tool motion from the current workpiece state. A regularized Boolean subtraction is used for this operation in a solid modeler based methodology. The removal volume is the geometry of material removed from the in-process workpiece by a single tool motion. The CWE calculations require accurate removal volume models for each tool motion. Removal volumes can be generated by performing a regularized Boolean intersection operation between the in-process workpiece and the swept volume. Figure 4-5 shows the -52- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling generation of the in-process workpiece and the removal volume for the i-th tool motion. SV, represents the tool swept volume in the i-th tool motion, Wi-i is the in-process workpiece before the i-th tool motion. The in-process workpiece Wj is updated by subtracting SV from t W^i (Wj.i -* SV,). The removal volume MV, is generated by a Boolean intersection operation between SV, and W iA Tool Swept In-Process (SV, D* W ). ul Volume (SVJ Workpiece Removal (W,.,) Volume In-Process (RV) Workpiece (WJ Figure 4-5: In-Process Workpiece and Removal Volume in the i-th Tool Motion 4.5 In-Process Feature Recognition The in-process feature recognition step decomposes a removal volume RV into a set of geometric invariant volumes {giF,} and form invariant volumes {fiF,}. Figure 4-6 illustrates this process and its three operators: Decomposition, Segmentation and Extraction. The decomposition operator decomposes the input removal volume into a set of minimal volumes {MV }. These minimal volumes along with the tool geometry and the associated tool t motion are input into the segmentation operator for generating a set of geometric invariant segments {giS,} and form invariant segments {fiSj}. {giF,} and {fiF,} are then extracted from RV based on {giS,} and {fiS,} in the extraction operator. These three operators will be described in this section. -53 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Removal Volume RV j Decomposition Minimal Volumes {MV,} J Segmentation Geometric Invariant Segment {giSj} Form Invariant Volume Geometric Invariant Feature Form Invariant Feature Figure 4-6: In-Process Feature Recognition 4.5.1 Decomposition Operator A decomposition operator has been defined to decompose a volume into a set of minimal volumes. This operator can be represented as {MVj}=Decompose(RV), where the input is a removal volume RV and output is a set of minimal volumes {MVj}. In 2 AD end milling, a minimal volume is considered to be a solid model in E space. l This solid model for a minimal volume should satisfy the following constraints: • For each horizontal face jhj in the solid model R V, there exists a halfspace h The normal h of the face points to the outside of the corresponding half space. -54- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V2D End Milling • For each halfspace h , all of the geometric entities (vertices v„ edges e and faces t t in the solid model RV should be inside or on the halfspace (i.e. v, e h , e, e h and / , e h,). t t Figure 4-7 illustrates an example of minimal volumes and non-minimal volumes. It can be seen that halfspace /?2 on the horizontal face fli2 in (b) does not satisfy the above constraints. Therefore, this volume is not considered as a minimal volume. (a) A Minimal Volume (b) A Non-Minimal Volume Figure 4-7: Definition of Minimal Volumes The decomposition operator traverses all faces of the input volume RV\o find horizontal faces that do not satisfy the above constraints. Such faces are referred to as splitting-faces. A halfspace h is constructed for each splitting-face. The input volume i?Fcan be divided by t performing Boolean operations between the halfspace h, and the removal volume RV. As illustrated in Figure 4-8, a Boolean difference generates an upper minimal volume MV], and a Boolean intersection creates a lower minimal volume MV2. In some solid modelers, these two Boolean operations can be combined into one for splitting the two volumes at the same time, for example, the routine api boolean chop body in the solid modeler ACIS. Algorithm 4-1 describes how a decomposition operator is implemented to decompose a removal volume into a set of minimal volumes. The first step is to search for all of the horizontal faces by traversing the B-rep of the removal volume. These horizontal faces are inserted into a face list. This list is sorted in an ascending order of z coordinates of each face within the list. The head and tail faces in the face list are then removed. When the face list becomes empty after removing the head and tail faces, the removal volume RVh considered -55 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling as a minimal volume, and is inserted into the output minimal volume list IstMV. Otherwise, the removal volume RVis split by the halfspaces created based on each face within the face list. A set of minimal volumes are generated and added into the minimal volume list IstMV. Removal Volume (RV), Upper Minimal Volume (MVJ Halfspace Splitting-face Lower Minimal Volume (MVi) Figure 4-8: Removal Volume Decomposition Routine: to decompose a removal volume into a set of minimal volumes Input: a removal volume RV Output: a list of minimal volumes IstMV IstMV = Decompose (RV){ A L L O C A T E a horizontal face list: IstFace for (each face f in RV) { if (fi is a horizontal plane) IstFace *— f } SORT IstFace in an ascending order of z coordinate of f e IstFace i R E M O V E head & tail faces in IstFace if (IstFace e</>) IstMV ^RV else { for (each face f in IstFace) { CONSTRUCT a halfspace H at f, SPLIT R into a with //, IstMV +— MV t } } Algorithm 4-1: Removal Volume Decomposition -56- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling 4.5.2 Segmentation Operator The segmentation operator divides a linear or circular tool motion into a set of labeled segments according to the engagement conditions between the tool geometry T and a set of minimal volumes {MVi\ decomposed from a removal volume. This operator can be represented as {Sj}=Segment(S, T, {MV }), where the inputs are a line or circular tool motion t S, a tool geometry T and a set of minimal volumes {MF,}. The outputs are a set of labeled segments {Si}. As shown in Figure 4-9, the outputs include two types of segments: Geometric Invariant Segments (giS) and Form Invariant Segments (fiS), which correspond to Geometric Invariant and Form Invariant Volumes, respectively. The type is determined by the engagement conditions between the tool geometry T and the set of minimal volumes {MF/}. The engagement condition is invariant when the tool is moving along a giS. Otherwise, the engagement condition is changing while the tool is moving along afiS. Geometric Invariant Segment Tool Motion Form Invariant Segment Feed Direction A Minimal Volume Figure 4-9: Geometric Invariant and Form Invariant Segments Figure 4-10 illustrates a flowchart of the segmentation operator. This operator includes four steps: (1) projection, (2) boundary tracing, (3) segment combination for one MVmd (4) segment combination for overlapping MVs. Each minimal volume and the tool geometry are projected onto the X Y plane in order to reduce the segmentation calculation in the following steps to a two-dimensional problem. In the boundary tracing step, a set of giSs -57- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling . and fiSs are generated based on the engagement condition between the tool projection and each edge of the minimal volume projection. Following this step, there are two level segment combination steps. The first level is to combine the overlapping segments generated from a single minimal volume in the boundary tracing step. The second level is to combine the overlapping segments generated from different minimal volumes into a final set of giSs and JiSs. These four steps are described in the following sections. START Minimal Volumes ^ {MV,} Tool (T) "2 Tool Motion (S) X Inputs Projection 2. Boundary Tracing Combination Combination END 2D I 1/ » Segments {Se,}, SeuniLiitN \S Segments {S,} Geometric Invariant {giS,} Form Invariant J//S ! Figure 4-10: A Flowchart of the Segmentation Operator -58- J Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V2D End Milling 4.5.2.1 Projection Both the tool geometry T and each minimal volume MV are projected onto the X Y t plane in order to reduce the segmentation calculation to a two-dimensional problem. As shown in Figure 4-11, tool geometry Tis projected as a circle C and MV as a planar region F, t bounded by a set of linear and circular edges Ei-E^ in the X Y plane. Therefore, a minimal volume MVj can be alternatively represented by its axial limits (d , min in the coordinate system: MVj (d m, m dmax, dmax) and projection F t Fj,). Figure 4-11: Minimal Volume Projection Details of the algorithm to generate the projection are described in Algorithm 4-2. In summary, the algorithm searches for a horizontal face by traversing the B-rep of each minimal volume. A l l of the edges on the horizontal face are inserted into an edge list for output. The Z coordinates of vertices on each edge within the edge list are set to zero. The axial limits (d , min dmax) can be determined by traversing all of the vertices on the minimal volume to find a minimum and a maximum Z coordinate. As shown in Algorithm 4-2, d \n m and dmax are found by the routines FindMaximumZCoordinate, respectively. -59- FindMinimumZCoordinate and Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Routine: to project a minimal volume into a set of edges on the X Y plane Input: a minimal volume MV Output: a list of edges IstEdge, the axial limits (d „, dmax) {1stEdge, ( d , d )} = Project (MV){ for (each face f in MV) { if is a horizontal plane) { for ( each edge Ej in f ) { z coordinate o f the Ej*— 0 IstEdge *— Ej mi min max t t } d = FindMinimumZCoordinate(MF) dmax ~ FindMaximumZCoordinate(MF) return min } } } Algorithm 4-2: Minimal Volume Projection 4.5.2.2 Boundary Tracing The inputs to the boundary tracing step are a minimal volume projection F , t a tool projection C and a tool motion S. A s mentioned in the projection step, the minimal volume projection F consists of a set of edges {Ej} t in the X Y plane. The tool projection C is a circle in the plane. The tool motion S is the toolpath from which the removal volume is generated. The outputs to this step are a set o f geometric invariant and form invariant segments. The boundary tracing step can be divided into the following steps: Step 1. Segment Generation: A segment is generated by identifying the entry and exit positions where the tool projection C starts and ends the intersection with an edge of the minimal volume projection F along the tool motion S. t Step 2. Segment Classification: The segment generated from the last step is classified as either a geometric invariant segment giS or a form invariant segment fiS, based on the intersection condition between the tool projection C and the edge o f the minimal volume projection F . t -60- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Figure 4-12: Segment Generation These two steps are described as follows: -61 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Step 1: Segment Generation A segment is bounded by the entry and exit positions where the tool projection C starts and ends the intersection with an edge of the minimal volume projection. Figure 4-12 illustrates five segments (S i, S 2, S 3, S 4, S i) corresponding to five edges of a minimal e e e e e volume projection (£/, E2, E3, segment S 2 is for the edge E2 and so on. In Figure 4-12, e = [P ntry2, Pexiti] e E4, Es). Segment S j = [Pentryi, Pextti] e is for the edge £ / , P s is an intersection point where C starts the intersection with the edge, and P is an intersection point where C e ends the intersection with the edge. Entry (P try) en and exit (P u) ex positions of each segment can be calculated by performing line/arc or arc/arc intersections between the tool projection C and each edge £, depending on the type of the tool motion and the edge. Figure 4-13 illustrates four cases for calculating entry and exit positions of the segment in 2V2D end milling. The tool projection may intersect a linear or a circular edge when it moves along a linear or circular motion. The calculation for each case is described in Appendix A . CASE1: Linear Tool Motion/Linear Edge CASE3: Circular Tool Motion/Linear Edge CASE2: Linear Tool Motion/Circular Edge CASE4: Circular Tool Motion/Circular Edge Figure 4-13: Entry and Exit Positions of the Segment -62- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling An algorithm to calculate entry and exit positions of each edge is presented in Algorithm 4-3. It can be seen that entry and exit positions of each edge can be calculated based on the tool motion type and the edge type. to generate a set of segments by tracing the edges of a minimal volume projection Input: the edges of a minimal volume projection (IstEdge), tool projection (Q, tool motion (T) Routine: Output: a list of segments IstS IstS = GenerateSegments (IstEdge, C, T) { for (each edge E in IstEdge ) { case ( T is Linear) { case ( Ej is a Line) t S = CalculateLineLine(E C, T) it case ( Ej is a Arc ) S = CalculateLineArc(Ej, C, T) ) case ( T is Circular ) { case ( Ej is a Line) S = CalculateArcLine(E C, T) u case ( Ej is a Arc ) S = CalculateArcArc(E C, T) it } lstS*-S } } Algorithm 4-3: Segment Generation Step 2: Segment Classification A set of segments is generated in the last step. Each segment needs to be classified as either a geometric invariant segment or a form invariant segment. A giS is considered as a segment where the intersection condition between the tool projection C and the edge E is t constant. Figure 4-14 illustrates the geometric invariant segments for a linear tool motion and a circular tool motion. It can be seen that the immersion angles on C at any two positions (Pi, Pi) along the segment are constant (#/= 6i). giSs can be determined by identifying that the linear edge E is parallel to the linear segment in linear tool motion, and the circular edge E t t has the same centre as the circular segment in circular tool motion. On the other hand, a -63 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling . variant intersection condition between the C and £ , along an initial segment leads to a fiS. For the example described in Figure 4-12, the segments can be labeled as in Table 4-1. Segments S4 Si e Inti> & 1 \it Positions Cutting Edge Labels * S e4 \P entryU C \Pentry2> Pec///] Pexit2] XPentryh 4 3 2 0* giS fiS fiS E E E E, Pexi/i]\_Pentry4) PexitA] [Penlry5> Pexit5\ E 5 giS is not labeled because its entry and exit positions are the same Table 4-1: Labeled Segments (a) A Linear Motion (b) A Circular Motion Figure 4-14: Geometric Invariant Segments An algorithm to classify the segments is presented in Algorithm 4-4. For each segment S in the segment list lstS i, its associated cutting edge £ , has been checked. In a linear tool ei e motion, if Ej is parallel to S , S t is labeled as a giS, otherwise S ei e ei is labeled as a fiS. In a circular tool motion, both S and £ , are arcs. If 5 , and £ , have the same center point, S j is ei e labeled as a giS, otherwise S t is labeled as a JiS. e -64- e Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V D End Milling _ 2 Routine: to classify a set of segments asfiSsor giSs Input: a list of segments (lstS ), the associated edges (IstEdge) Output: a list of labeled segments lstS e e lstS = ClassifySegments (lstS , IstEdge) { e e for ( each segment S in lstS ) { case ( S is Linear ) { if ( Ej in IstEdge is parallel to S ) ei e ei ei S *- giS ei else S <-fiS ei } case (S is Circular ) { if (Ej in IstEdge has the same center point as S ) ei el S *- giS ei else S <- flS el } } } Algorithm 4-4: Segment Classification 4.5.2.3 Segment Combination for One MV A set of labeled segments {S } is created in the previous steps. Among these segments, ei there may be some overlap. By combining these overlapping segments, a set of new segments {S,} is generated. These new segments will be classified based on the label of each overlapping segment S , and the following combination rules: e Rule 1.Overlapping geometric invariant segments produce a new geometric invariant segment leading to a geometric invariant feature. Rule 2.0verlapping form invariant segments produce a new form invariant segment leading to a form invariant feature. Rule 3.0verlapping geometric invariant and form invariant segments produce a new form invariant segment leading to a form invariant feature. Figure 4-15 illustrates the combination based on the example described in Figure 4-12. From Figure 4-15, it can be seen that segment S2 is extracted from overlapping segments (S j, e -65 - Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling S 2), segment S3 from overlapping segments (S 2, S s), and segment S4 from overlapping e e e segments (S 3, S s). By applying the rules above, S2 is labeled as a fiS since both S i and S 2 e e e e are fiSs (see the second rule), S3 is labeled as a fiS since S 2 is a fiS and 5 5 is a giS (see the e e third rule), and S4 is labeled as a g/S since both 5 3 and S s are g/Ss (see the first rule). In this e e example, the output contains four segments (Si, S2, S3, S }, where S4 is a giS, and 57, S7, 5j 4 are JiSs. I -Q- -0 'e5 O Segments Classification S, <- fiS S <- fiS 2 S <-fiS 3 s 4 <- giS Figure 4-15: Segment Combination for One MV An algorithm to combine these overlapping segments in the segment list lstS is e presented in Algorithm 4-5. This algorithm extracts entry and exit points from each segment Set in lstS and inserts them into a point list IstPoint. The duplicated points in IstPoint are e removed. The point list IstPoint is then sorted in ascending order by the distance from each point to the start point (see Pstart in Figure 4-12) of the tool motion. A new segment set IstS can be generated by extracting the adjacent point pairs such as [Pi, P2], [P2, Pi] and so on from the point list IstPoint. To classify these new segments, each new segment S in the t segment list IstS is examined to see whether it intersects with each segment S t in the list lstS . e 66 e Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2%D End Milling If multiple intersected segments lstInterS are found, the rules above are applied to determine e the classification of the new segment 5,-. Routine: to combine a set of overlapping segments Input: a list of overlapping segments (lstS ) Output: a list of segments IstS IstS = CombineSegments (lstS ) { A L L O C A T E a point list: IstPoint for ( each segment S t in lstS ) { IstPoint <- EntryPointOf(5" ,) IstPoint « - ExitPointOf(5 ,) e e e e e e } R E M O V E duplicated points in IstPoint SORT IstPoint in an ascending order by the distance | PiPstart] for (each pair [P,, P i ] in IstPoint) { S,= [Pi,P ,] IstS <- St i+ l+ } A L L O C A T E an intersected segment list: lstInterS for (each segment 5, in IstS) { lstInterSe *— FindlntersectSegments^,, lstS ) if ( each intersected segment S t in lstInterSe is giS) S *-giS else S,<-fiS e e e t } } Algorithm 4-5: Segment Combination 4.5.2.4 Segment Combination for Overlapping MVs Since the decomposition operator described in the last section can generate overlapping minimal volumes, the final classification of regions of the removal volume into geometric or form invariant types depends on the length and types of the segments for the overlapping minimal volumes. The combination rules and the algorithm used for overlapping MVs are the same as those used for one MV. As shown in Figure 4-16, a removal volume is decomposed into two overlapping minimal volumes, with which labeled segments (fiSij, giSij,fiSij, -67- giSjj) and (fiS^i, giS2,i) Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling are associated. By applying the combination rules above it can be seen that overlap of fiSij andfiS2,ileads to the form invariant segment fiS/, overlap of giSij and giS^i leads to the geometric invariant segment giS^, overlap of fiSij and giSij leads to the form invariant segment fiS2 and overlap of giSij and giSii leads to the geometric invariant segment giS2- Figure 4-16: Segment Combination for Overlapping MVs In the segmentation operator, the tool motion is divided into a set of Geometric Invariant and Form Invariant Segments based on the intersection condition between the tool and the removal volume. In the following section, an extraction operator will be introduced to extract Geometric Invariant and Form Invariant Features by decomposing the removal volume along the giSs and fiSs. 4.5.3 Extraction Operator The extraction operator is to extract a set of {giF , fiFi) by decomposing a removal t volume RV according to the labeled segment set {giSj,fiSi} generated in the previous steps. This operator can be represented as {giFj,fiFj}=Extract(RV, {giSi,fiSi}), where the inputs are a removal volume RV and a set of Geometric Invariant and Form Invariant Segments {giS/, -68- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling fiSj}. The outputs are a set of Geometric Invariant and Form Invariant Machining Features {giF fiF }' h t Figure 4-17 illustrates an algorithm for extracting giFs and fiFs from a removal volume. It can be seen that a semi-cylinder surface halfspace h is generated at each internal boundary t point Pj of the labeled segment set, starting from the first point P ,. The halfspace h is used star t to split the removal volume into two parts. As shown in Figure 4-17, the first part is the feature fiFi, which is generated by performing a Boolean intersection between the halfspace hi and the removal volume RV (RV 0* hi). The second part is created by subtracting the halfspace hi from the removal volume RV (RV -* hi). The second part will be split by the next halfspace h2 to extract another feature, if possible. Similar to the splitting operation in the decomposition operator, the ACIS routine api boolean_chop body can be used to perform these two Boolean operations at the same time in this operator. Figure 4-17: Feature Extraction from a Removal Volume The feature extraction algorithm is described in Algorithm 4-6. A semi-cylinder halfspace h is generated at the internal boundary point P, of the labeled segment set IstS. The t removal volume RV is split by the halfspaces h . The decomposed volume F is inserted into t IstGIF if the corresponding segment S is a giS. Otherwise, the volume F is a fiF and inserted t into IstFIF. -69- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Routine: to decompose a removal volume into a set of giFs and fiFs Input: a removal volume RV, a list of segments IstS Output: a list of giFs IstGIF, a list of fiFs IstFIF {IstGIF, IstFIF) = Extract (RV, IstS) { for (each segment S in IstS) { Pi = ExitPointOffS,) CONSTRUCT a halfspace H at P SPLIT RV'vnXo a volume F with H if(SiisagiF) { IstGIF <— F } else if (S,is afiF) { IstFIF <— F t t t t } } J Algorithm 4-6: Feature Extraction After recognition of Geometric Invariant and Form Invariant Features, Cutter/Workpiece Engagements can be analytically extracted from giFs and fiFs. In the following section, a CWE extraction algorithm will be presented to do this. 4.6 Extraction of Cutter/Workpiece Engagement A giF or fiF extracted from the feature recognition step may contain several subvolumes originated from minimal volumes. Each sub-volume is represented by its position in the Z direction and projection in the X Y plane. The representation of the giF or fiF is a union of each sub-volume representation. As shown in Figure 4-18, a fiF is composed of subvolume V] and V~2. The upper volume V; can be represented by its position in the Z direction (dmini, dmoxi) and projection (Fi) in the coordinate system: Vi (d i, d i, Fj). The lower min max volume can be similarly represented: V2 (d „2, d 2, F2). Therefore, the fiF is represented as mi (dmini, dmaxi, F]) [j (d in2, d 2, F2). m max -70- maX Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Lower Volume: V (d 2 ,d min2 2> maX F) 2 Figure 4-18: Representation of a fiF In 2'/ D end milling, a CWE in afiF or giF is composed of engagements between the 2 tool and each sub-volume. These engagements can be constructed by entry and exit angles and the depth of cut in the Z direction. Entry and exit angles are determined by calculating the intersection between the tool projection and the volume projection. As shown in Figure 419, the upper volume projection Fj intersects with the tool projection C to determine the entry and exit angles. Entry and exit angles are calculated by finding valid intersection points between C and edges (£/, E ) of Fi. The entry and exit angle fe,,,^], along with the depth 2 of cut [d „i, mi dmoxi], Zone [d , d 2 min2 , max2 are used to construct the engagement zone: Zonei[d „i, (f>st2, ^ 2 ] mi d u max <l>sti, fart]- is constructed from the lower volume V . Both Zonei and Zone 2 are combined into a ceF for the fiF at the cutter location P . u -71 - 2 Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V2D End Milling Entry & Exit Angles Figure 4-19: CWE Extraction from a fiF Generally, the CWE extraction algorithm is described in Figure 4-20. This algorithm includes the following steps: Step 1.Calculate entry and exit angles [ ^ „ , ^ , ] for a sub-volume V by intersecting the tool ( t project C with edges of the sub-volume projection Ft. Step 2. Construct an engagement zone Zonej for the sub-volume F, based on entry & exit angles and the depth of cut represented as Zone\d minh d , maxi [d , mim dmax,]. The engagement </> , (f> ]. sli exi Step 3. Combine the engagement zones {Zonej} into a ceF for giF or fiF. -72- zone is Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling Q I ^d —y/ 01 *// 1. START^) Inputs Calculate Entry & Exit Angles 2. Construct an Engagement Zone no 1 3 . Combine Engagements Q E N D w ceF ^ Figure 4-20: Steps in CWE Extraction 4.7 Implementation and Validation 4.7.1 Implementation The feature recognition algorithm and CWE extraction from giFs and fiFs algorithm described in this chapter were implemented within the Microsoft Windows XP professional edition operating system. Matlab and Visual C++ were used as the development tool. This implementation of feature recognition uses the ACIS 3D modeling kernel as the solid modeling engine, and the HOOP 3dGS as the graphics system. The implementation of CWE extraction uses Matlab to calculate and display engagement angles and engagement zones. This program was tested using a computer with a Pentium 4 processor, with 3GHz/0.99GB. Figure 4-21 illustrates major classes and their relationships in the CWE extraction system. Class GeometricInvariantFeature and FormlnvariantFeature represent giF and fiF -73 Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling . respectively. Class Segment within the above classes is used to stand for the corresponding giS and fiS. In the implementation of the decomposition and extraction operator of the inprocess feature recognition step, limited single-sided open shell Booleans in ACIS are used to perform Boolean operations between the halfspace and the solid model of the removal volume. The ACIS routine apijbooleanchopbody GeometriclnvariantFeature is applied for the decomposition. -Segment Type |-Segment •BrepSolid -IstGII RomovjIVolume -Type -IstGIFs -IstFIFs -IstMinimalVolumes -Toolpath -Cutter -BrepSolid MinimalVolume -IstMinimalVolumes 1..* 1 Type •IstGIFs •IstFIFs -VolumeProjection BrepSolid 0..' -VolumeProjection VolumeProjection -IstEdges Segment -Type -posStartPosition ' -posEndPosition p ^ - -IstFIFs FormlnvariantFeature -Segment |-Type -Segment l-BrepSolid Figure 4-21: Class Diagram in the CWE Extraction System 4.7.2 Validation of Feature Recognition Figure 4-22 illustrates a test part for validating the feature recognition algorithm presented in this chapter. The geometry of the test part and toolpath are presented in Figure 4-22 (a). There are a total of 410 tool motions in the toolpath. 301 out of 410 tool motions are valid tool motions that cut the in-process workpiece. Table 4-2 summarizes the computation times taken to complete the feature recognition for all of the removal volumes. The number of giFs and fiFs involved is also included. Figure 4-22 (b) and (c) show the results of feature recognition for the removal volumes generated by the 47 th (linear) and the 121 (circular) tool motions. It can be seen that the st linear removal volume is decomposed into 1 giF and 2 fiFs, and the circular removal volume into 2 giFs and 3 fiFs. -74- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V2D End Milling 3(*Btf«<<>*«< iff * t (a) A Test Part t^tulSim Client |Ne«ii.>iuljli»nl ilel] g D a! U ff * o i ^ t ' f l Snuuttan Hermiats SaMffiontend*V M M He IA Dtf H & a m ? j 0 l i s * At A T « oft 15 Seomert39 0 Segment 40 0 SegmnHI nut Mil) mil 0 Sagmort 44 0 ScpwnHS 0 SegTjrt« rl^i 8 i F 2 • 0S333H 0 0 0 0 0 0 .:• • ? SegrwnUB 5«gm«it49 5egr*rtS0 Segment 51 5rgrr*rt5? SegmsnlM fi 2 F 1 : Q stgwit) 0 5* growl 55 0 SegmertS* • 0 ^grwr*S7 0 5*grart58 JJUSsd"" (c) A Circular Tool Motion (b) A Linear Tool Motion Figure 4-22: Examples for Feature Recognition 75 Chapter 4. A Feature-Based Approach to Cutter-/Workpiece Engagement Extraction in 2'AD End Milling Inputs Tool Motions Removal Volumes 410 301 M a c h i n i n g Features fiFs g i F s 457 326 T i m e s (seconds) Removal volume Feature Recognition Total 40.248 4.183 44.431 Table 4-2: Simulation Times for Feature Recognition 4.7.3 Validation of CWE Extraction Figure 4-23 illustrates an example of CWE extraction from a fiF. The test part is machined by 117 linear tool motions. The removal volume generated by the 95 tool motion th is decomposed into several giFs and fiFs. A Form Invariant Feature fiF] is selected for the CWE extraction algorithm implemented by the Matlab software. fiF\ is composed of three minimal volumes. Figure 4-23 (c) shows the engagement angle calculation by Matlab for each minimal volume of fiFj. Figure 4-23 (d) illustrates the final ceF at the cutter location w=0.2. -76- Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2'AD End Milling n<* a t? t 9 9 B 9 <9° * '• v 0• t a « # e <* «. a o t i «ft<ft- r> *«» i iwrn 1 tmMB n Eg £: ) NpM« 1 MflMM * < (b) The (a) Test Part 1 r ; ; — Entry Angle fa — Exit Angle fa J 0 0 0.2 I 0.4 0.6 95 TH T U l Motion ! 1 0.8 180 160 m •D IO OJ IQ 120 me rt> 140 100 3r-r 80 : ! <t> — Entry Angle — Exit Angle fa •) st figure No. 1 Na E d t View Tools Window Help Culter.Wdrkpiece Engagement 10 60 ,—, 40 9 20 8 O Insert D'*''0.#P A / / i3 0 O 0.2 04 0.E 1 7 0.8 I 6 O 6 b Entry Angle fa Exit Angle fa 60 ED 100 120 Immersion Angle [deg] 02 0.4 0.6 (d) ceF (u=0.2) 08 Tool Motion Parameter (u) (c) Engagement Angles Figure 4-23: A n Example of CWE Extraction -77- 1 Chapter 4. A Feature-Based Approach to Cutter/Workpiece Engagement Extraction in 2V2D End Milling 4.8 Discussion The feature recognition algorithm is verified based on the removal volumes generated by both the linear and circular tool motions. As shown Figure 4-22, these two types of removal volume can be correctly decomposed into giFs and fiFs. From the results presented in Table 4-2, it can be seen that feature recognition has been done without any computational problem for this intermediary complicated part. Robustness and computational efficiency of this algorithm has been verified. In addition, CWE extraction from a giF or fiF has been tested as shown in Figure 4-23. From Figure 4-23 (c), it can be seen that the entry and exit engagement angles can be calculated analytically. Therefore, it is clear that an exact solution to CWE is provided by this approach. However, this methodology is based on the assumption that a rectangular prismatic initial workpiece is machined by a flat end-mill in 2'/4D end milling. It is possible to extend this methodology to various end-mills, such as ball, cone and bull end-mills if analytical quadric surface/surface intersection calculations are used for the segmentation operator, rather than the calculation among the two-dimensional geometries presented in this algorithm. This methodology can be also extended to different machining operations, such as turning and boring. -78- Chapter 5 Cutter/Workpiece E n g a g e m e n t Extraction for Hole Milling 5.1 Introduction In process planning, a hole is considered as a final part machining feature. To machine a hole feature, two types of machining operation, drilling and milling, can be planned. Since hole milling has a larger material removal rate than hole drilling, a milling operation is normally selected for large-size hole machining during process planning. In a milling operation, a hole is generated by moving an end mill along a helical toolpath. Since the radius of the end mill is greater than the radius of the helical toolpath, the swept volume of the end mill has self-intersections, which leads to the following two difficulties in the areas of geometric verification and process modeling: • In geometric verification, swept volumes are needed for updating the in-process workpiece. The self-intersection in hole milling operations makes swept volume generation difficult. • In process modeling, CWEs are needed for predicting cutting forces. Traditional CWE extraction approaches apply Surface/Surface Intersection between the cutting tool and the removal volume. Since a self-intersected swept volume loses the boundary geometry of common regions, the Surface/Surface Intersection approach cannot extract the correct CWEs when the cutting tool engages these common regions. In this chapter, an analytical approach to CWE extraction for hole milling with a flat end-mill is discussed. This approach provides a closed-form solution without numeric Surface/Surface Intersection calculations. In the next chapter, a self-intersected swept volume generation approach is investigated for in-process workpiece modeling. This approach can generate an exact representation for the self-intersected swept volume for a variety of endmills with helical toolpaths. A definition of a milled hole machining feature will be given in the next section, followed by an overview of its parametrization. This parametrization provides a closed-form representation for the ceF. Finally, examples will be presented to compare the ceFs extracted -79- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling using the analytical approach developed with those generated by the commercial software N C application VERICUT. 5.2 Milled Hole Machining Feature A Milled Hole Machining Feature can be defined as follows: A Milled Hole Machining Feature (mhF) is a cylindrical surface with an optional planar surface on the final part generated using an end mill moving along a helical toolpath. As shown in Figure 5-1, a mhF is machined by a flat end mill moving along a helical toolpath. The cylindrical hole geometry is defined by the following parameters: R: Radius of the hole H: Height of the hole The flat end-mill is defined by the following parameters: r: Radius of the cutting tool h: Height of the cutting tool The helical toolpath is defined by the following parameters: R-r: Radius of the helical toolpath p: Pitch of the helical toolpath In addition, the following two variables are used in defining the CWE: <> /: Engagement angle of the cutting tool (j> e [0, 27i]. &. Rotation angle of the cutting tool 9 e [0 , 9 ], where 0 and 0 are the start and end S e S e rotation angles of the cutting tool to finish machining a hole. 6 = 0 and 0 can be calculated S e byEq. (5.1): e„=2n{— + l] (5.1) -80- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling Milled Hole Machining Feature Figure 5-1: Milled Hole Machining Feature As illustrated in Figure 5-2, there are two types of mhF: Blind Hole and Through Hole. The toolpaths to machine these two types of hole are described as follows: • Blind Hole: The toolpath for a blind hole is composed of two curves: a helix and a circle. The rotation angle range [0 , 0 ] is divided by a rotation angle 6 where the S e B cutting tool reaches the bottom surface of the hole. The toolpath is a helix where 0 e [0 , 6b), and a circle where 0 e [Ob, 0 \ S • e Through Hole: The toolpath of a through hole only contains a helix. Ob is the rotation angle where the cutting tool reaches the bottom surface of the workpiece. For the two types of hole described above, the rotation angle Ob can be calculated as follows: (5.2) -81 - Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling (a) Blind Hole (b) Through Hole Figure 5-2: Toolpaths for Blind Hole and Through Hole 5.3 Parametrization of Cutter Engagement Feature for a Hole A s d e s c r i b e d i n C h a p t e r 3 , a Cutter E n g a g e m e n t Feature (ceF) i s d e f i n e d t o describe the standard engagement f o r m a t required b y the force m o d e l . M a t h e m a t i c a l l y , a ceF c a n b e represented b y its l i m i t s o n the a x i a l depth o f cut [d , dmax] o n the surface o f the c u t t i n g min tool. F o r b l i n d h o l e m a c h i n i n g , the l o w e r engagement l i m i t d min engagement i s a l w a y s z e r o , a n d the upper l i m i t dmax i s represented as a f u n c t i o n o f the parameters d e f i n e d i n the last section as f o l l o w s : P min= (5 3) ° \d =f{R,r,p,0,t) mm F o r t h r o u g h h o l e m a c h i n i n g , d m i s d i v i d e d into t w o p o r t i o n s . d m min i s zero before the cutting t o o l reaches the b o t t o m surface o f the w o r k p i e c e 0 e [6^ 0 ). F o r the segment o f the O h e l i c a l t o o l path after r e a c h i n g the b o t t o m where 0e [Ob, 0 ], d m i s a f u n c t i o n o f the rotation e m angle 0. dmax i s represented as a f u n c t i o n o f the parameters (R, r,p, 0, are defined as: -82- Both d min and dmax Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling From Eq. (5.3) and (5.4), it can be seen that the parametric representation of the ceFs depends on the parameters of the hole geometry, the tool geometry and the toolpath. In other words, the ceF can be determined by the hole, the tool and the toolpath parameters. This is significant, since the ceFs can be obtained from these equations for any size hole, any size tool and different toolpath parameters. 5.3.1 Intersection between Cylinder and Helicoid A CWE is a region on the surface of the cutting tool that engages the in-process workpiece. A CWE is bounded by a set of curves originating from the intersection curves between the surfaces of the cutting tool and the surfaces on the workpiece. In the case of hole milling, a helicoid is generated on the in-process workpiece by the flat bottom of the cutting tool as it moves along the helix. To find the CWE, the intersection curve between this helicoid and the cylindrical surface of the flat end mill needs to be determined. Figure 5-3 illustrates the intersection between a cylinder representing the end mill and a helicoid. I Figure 5-3: Intersection between a Cylinder and a Helicoid A cylinder with height p and radius r at any position along a helix can be parametrically described in Eq. (5.5). x = {R-r)cos6+ rcos(t> ' y = (R-r)s'md + rsm</> (5-5) z=z where z e [-p, 0], 9 e [0,2n] and < > / e [0,27t]. -83- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling A helicoid with a semi-circle profile and pitch p is given by Eq. (5.6) in explicit form. The derivation of Eq. (5.6) is presented in Appendix B. z=— 2K tan V * * (R-rf.-r 2 -1 + COS x +y (5.6) + 2{R-r\[x By manipulating Eq. (5.6) and Eq. (5.5), a parametric form of the cylinder/helicoid intersection is obtained using only the parameters identified in Section 5.2. As a result, Eq. (5.7) is obtained as the equation of the intersection curve. x - (R - r)cos 6 + r cos <j> (5.7) y = ( R - r)sin 6 + r sin <f> in where: a = tan" P = cos (i?-r)sin0 + rsin^ (R - r)cos6 + r cosifi (R-r) + rcos(<f>-0) il(R - rf +2r(R- r)cos(<* - O) + r 2 The z coordinate expression in Eq. (5.7) is used to represent the upper limit of the ceF, i.e. ^max — z (5.8) : IK Figure 5-4 illustrates an example of Eq. (5.8), where the cylinder representing the end mill is located at several positions along the helix (0= 0°, 60°, 120°, 180°, 240°, 300°). It can be seen that Eq. (5.8) describes the intersection curve between the cylinder and the helicoid. It should be noted that this equation represents the full intersection curve. In hole milling, the material behind the cutter has been removed. Hence, to find the true CWE between the flat -84- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling end-mill and the in-process workpiece during a hole milling operation, some constraints have to be applied to the Eq. (5.8). The following are three constraints that must be satisfied: Constraint 1. For a flat end-mill, the valid engagement range is always located on the front semi-cylinder of the cutting tool. This engagement range is changing when the cutting tool is rotating along the helical toolpath. Therefore, the engagement range at any cutter location has to be identified for extracting the valid portion from the intersection curves shown in Figure 5 - 4 . Constraint 2. When moving along the first or last turn of the helical toolpath, the cutting tool intersects with both the helicoid and the top or bottom plane of the workpiece. The upper limit of the CWE is in these cases a composite curve with two segments: one is the intersection curve between the cutting tool and the helicoid, another is the intersection curve between the cutting tool and the top or bottom plane. The intersection point of these two segments needs to be identified in order to construct the complete CWE when the tool is moving along the first or last turns of the helix. Constraint3. Eq. ( 5 . 8 ) represents the intersection curve between a helicoid and a cylinder with a height p (the pitch of the helix). The curve within valid engagement range is disconnected at the intersection point where the bottom edge of the cylinder intersects with the helicoid. To construct a correct CWE from the intersection curve, the curve within valid engagement range must be connected by shifting the segment a pitch distance p upward, since the intersection curve is periodic. The above three constraints will be addressed in the following sections. Eq. ( 5 . 8 ) will be modified to represent the CWE based on these two constraints. -85 - Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling Figure 5-4: Z coordinate of the intersection curve: (radius of hole: l?=10mm; radius of cylinder: r=7mm; pitch of helix: />=40mm) 5.3.2 Constraint 1: Valid Engagement Range Figure 5-5 illustrates a valid engagement range [(/>, s on the surface of an end-mill where the end-mill has rotated an angle 9 along a helical toolpath. <p and <j) can be obtained s e from Eq. (5.9) as follows: +' (5.9) = 0 For example, if the end-mill rotates 60° along the helical toolpath, 0=60°. The valid engagement range should then be ^ e [60°, 240°]. Once the valid engagement range [<p , $>] is identified, the intersection curve portion s within [if , s (f>e\ is considered as a valid intersection curve. -86- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling Valid Engagement ^ Range . -- L k Cutter P Helix Toolpath Workpiece Figure 5-5: Valid Engagement Range 5.3.3 Constraint 2: Intersection Point Figure 5-6 illustrates an end-mill at its first turn in machining a hole. It can be seen that the end-mill has intersections with both the machined area and the non-machined area on the in-process workpiece within its valid engagement range. The machined area is a helicoid generated by the bottom surface of the end mill, and the non-machined area is the top plane of the initial workpiece. A n intersection point (Pb) that lies inside the valid engagement range as identified above joins the two curves that are generated by the cylinder/helicoid and cylinder/plane intersection, respectively. After identifying this intersection point and its angular location fa, it can be seen that the curve at [fa, fa) is from a cylinder/plane intersection, and the curve at [fa,fa]is from a cylinder/helicoid intersection. The intersection point can be calculated by intersecting a circle representing the endmill at the rotation angle 9 along the helix with a circle representing the end-mill at the initial location 9 =0°. The intersection point angle is described in Eq. (5.10). The derivation of this equation is given in Appendix C: + n - sin -r . 9\ r 2) (5.10) — sin — -87- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling Non-Machined Area (Top Plane) Machined Area (Helicoid) Valid Engagement Range Workpiece Cutter Helix Toolpath Figure 5-6: Intersection Point 5.3.4 Constraint 3: Connection Point Figure 5-7 illustrates a connection point Pb that lies inside the valid engagement range. It can be seen that Pb can be identified as the intersection point between the top or bottom edge of the helicoid and the top or bottom edge of the semi-cylinder representing the front surface of a flat end-mill. The upper segment can be connected by shifting the lower segment a distance p upward. Since the connection point is identical to the intersection point in constraint 2, Eq. (5.10) can be used to calculate the connection point. Figure 5-7: Connection Point - 8 8 - Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling 5.3.5 Parametric Representation of Cutter Engagement Feature Based on the constraints above, Eq. (5.8) is adapted to represent the ceFs in the following three cases. A n example with the same input parameters as those described in Figure 5-4 is presented for each case. First Turn For the first turn, the lower limit of the depth of cut of the depth of cut d min is always zero. The upper limit is composed of two curves joined at the intersection point Pb. The d max engagement angle is divided into two portions: [fa,fa)and [fa,fa].As represented in Eq. (5.11), at the interval [fa,fa)is the intersection curve between the end-mill and the top d max plane of the workpiece. Since the cutting tool moves a distance p9/2n in the Z direction after rotating angle 9, d x ma will be p9j2n when (j> e [fa,fa),dmax at the interval [fa, fa] is the intersection curve between the end mill and the helicoid. Figure 5.8 clearly shows the two intersection curves of the C W E for the first turn. d„„ -2-9 2K JL(0-a-fi) = 0. 2K </><</><fa (5.11) S fa<</><fa Middle Turns For the middle turns, dm m is always zero, as with the first turn. d x ma includes only one curve within the valid engagement range [fa,fa],since the end mill only intersects with the helicoid. However, to connect d x ma at the interval [fa,fa)needs to be shifted a pitch distance p upward d x ma at the interval [fa,fa]in order to satisfy constraint 3. The equation for ceFs in the middle turns is described in Eq. (5.12). Figure 5-9 presents an example for these ceFs. £(9-a-fl) +P ( JL(e- -p) IK 5 1 2 ) fa<</><fa a Last Turn For the last turn, d min and d x ma have two different representations, depending on the type of hole being machined. -89- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling Eq. (5.13) represents d and d min for a blind hole. d and d max min max for the interval [fa, fa] are zero since the end-mill has transitioned from moving along the helix to a circular toolpath for generating the planar hole bottom. d max for the interval [fa,fa)is the intersection curve between the end-mill and the helicoid. Figure 5-10 shows the engagement boundary of the ceFs at different locations on the last turn for machining a blind hole. =0, -JL(a + B)+p fa<</><fa Lit ^ max fa^<t>^fa o Eq. (5.14) represents d min (5.13) and d for a through hole. Both d max min and d max interval [fa,fa]are increasing when the cutting tool moves through the last turn. d max over the over the interval [fa,fa)is the intersection curve between the end-mill and the helicoid. Figure 5-11 shows the engagement boundary of the ceFs over the last turn for machining a through hole. •£-(0-a-p)+p in fa<<f><fa (5.14) fa^^ -P-e e [2n : 00 | 20 •a 40 60 ::20:i::-''j'-'.:40:' ; : ; 83 100 120 140 160 180 • •••:..-.:.:l.:-.:::-.-.:,. jhoh•o 9 = 240 -0' •20'. . 40 60. 80 100 . 120 .140. 20 40 60 93 103 .120 140 ,:40 60 80 100 120 1 40 1.60 180 -160. 180 | 20 20.; 1 60 1 80 9 = 300° 20 Figure 5-8: A 3 6 0 d V ' 80;.; . .' 100/:... 120 <l> Immersion Anqle[cieg| • over the 1 Turn from Eq. (5.11) st max 140 ... •:.• 160 90 180 Chapter 5. Cutter-/Workpiece Engagement Extraction for Hole Milling e= o c 6 = 60° 0 = 12O°H 0 = 180° 0 = 24O C 9 = 300° 20; 40 60 ' Figure 5-9: d^n, dmax 00 1 00 .120 <f> Immersion Angle[efeg] ; over the Middle Turn from Eq. (5.12) 0 = 0° 9= 300' 20 J 60 83 100 Y I m m e r s i o n Angle[tteg] Figure 5-10: dmin, dmax over the Last Turn for a Blind Hole from Eq. (5.13) -91 - 190: Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling (ft I m m e r s i o n A n g l e [ d e g ] Figure 5-11: d i„, m d max over the Last Turn for a Through Hole from E q . (5.14) 5.4 Implementation The algorithms described in this chapter are implemented by using the commercial software Matlab. Both the CWE calculation and display are executed within the Matlab environment. In addition, a set of CWEs generated by the commercial machining simulation software VERICUT are compared with the CJ^iss generated analytically by the algorithms presented in this chapter. The computer used was a Pentium 4 processor, 3GHz/0.99GB. 5.4.1 Test Part As illustrated in Figure 5-12, an aerospace gearbox cover is used as a test part to test the parametrization algorithm of the ceFs for the hole milling operation. In this test part, there are three mhFs with different parameters. mhF] and mhF3 are through holes, and mhF2 is a blind hole. Table 5.1 gives the details for each hole, as well as the tool parameters and toolpath parameters for the roughing stage. It can be seen from Table 5.1 that mhF2 and mhF3 have the same diameters. These three holes are machined by a flat end-mill with a diameter of 25 mm into three blind holes in the roughing stage. -92- Figure 5-12: A Test Part: Gearbox Toolpath Hole Machining Feature Tool Radius Pitch Helix Angle Diameter [mm] [mm] l°] [mm] Blind 12 7.92 6 25 24 Blind 7.5 6.62 8 25 21 Blind 7.5 6.62 8 25 Diameter Height [mm] [mm] mhFi 49 24 mhF2 40 mhFi 40 Type Table 5-1: Parameters ofmhFs for Roughing Stage 5.4.2 Results Three test cases are designed to test the ceFs generated in the first, middle and last turns, respectively. These ceFs are compared with the ceFs generated by the commercial software VERICUT. V E R I C U T represents the ceFs using raster bitmaps. These raster bitmaps are generated using the Z-buffer method described in the literature review section, and therefore, produce an approximate solution to the CWE. -93 - Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling In Test Case 1, a ceF is generated when the cutting tool rotates 120° during its first turn to machine the hole mhF2. The middle turn ceF is tested at the cutter location when the cutting tool has rotated 60° when machining the hole mhF] in Test Case 2. In Test Case 3, the ceF is presented where the cutting tool rotates 240° during its last turn to machine the blind hole mhF3. Figures 5-13, 14, 15 (a) illustrate the cutter locations and in-process workpiece geometry where the ceFs are generated. Figures 5-13, 14, 15 (b) show ceFs generated by the analytical solution developed in this chapter, with the engagement angle (f> of the ceFs arranged in an anticlockwise direction. Figures 5-13, 14, 15 (c) show ceFs generated by VERICUT, with tf> arranged in a clockwise direction. It is obvious that V E R I C U T generates an approximation to the exact ceFs. (a) Cutter Location •) F i g u r e N o . 3 Fie Edt m vk Insert took G. Help WlmJ« £> 1 20 r _ 1 .—, 1 :—j— 1 1 — 18 18 14 •j r j i i i | | 12 lo I : : • • 6 A 2 0 } ; ; 20 10 ; ; 60 ; SO j i 120 141 ; 100 i Engagement Ang»|asg] j i 1 90 180 i 9 .» i s » » ia iii HI (c) ceF from VERICUT (b) ceF from Analytical Solution Figure 5-13: Test Case 1: ceF on the mhF at the First Turn (0=120°) 2 -94- m )« wi Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling (a) Cutter Location Fto EdC Hew tnwrt took Dc^ea * A 801 r~ Window Ht4p / jj»ji»o r— 1— 1 1 1 1— 1 1 r (b) ceF from Analytical Solution (c) ceF from VERICUT Figure 5-14: Test Case 2: ceF on the m/iF/ at the Middle Turn (0=60°) -95- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling (a) Cutter Location .» F i g u r e N o . 5 Fte C« View Insert Tools Wtxfaw net. (b) c e F from Analytical Solution (c) ceF from VERICUT Figure 5-15: Test Case 3: ceF on the mhF at the Last Turn (0=240°) 3 5.5 Discussion The CWE calculation approach described in this chapter provides a closed-form solution to process modeling for a hole milling operation. The results are compared with those generated from the commercial software VERICUT, as shown in Figures 5-13, 14, and 15. For hole milling process modeling, the analytical solution presented in this research has the following two advantages over the approach used in VERICUT: • Computational Efficiency: VERICUT uses a discrete workpiece model (Z-Buffer) for geometric verification. CWEs are extracted as a raster bitmap by calculating the -96- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling intersections between the cutting tool and a set of discrete normal vectors on the surface of the workpiece. A number of Line/Surface intersection calculations are involved during the CWE extraction. Moreover, the output raster bitmap needs to be processed into a standard format (described in Chapter 1) in order to satisfy the requirements of the force model. The analytical approach in this research provides a closed-form formula in the standard format. No further processing is needed. • Accuracy: the approach in VERICUT provides only an approximation to the CWE, since the calculation is based on a discrete workpiece model. In particular, the CWE region is wrongly calculated when the surface of the cutting tool has an edge contact with the wall of the hole where no forces exist between them (see Figures 5-15 (b) and (c)). This will introduce significant errors into the force prediction. One advantage of using VERICUT is that it can be applied to CWE calculations across a broad set of machining domains, including complex 5-axis machining. As such, it is a generic methodology for a broad set of machining applications. The analytical approach developed in this research is limited to hole milling using a flat end-mill. A n obvious extension of this research is to include the use of ball and bull nose end-mills in hole milling. The challenges of developing an analytical solution for these cutting tools involves finding closed-form solutions for intersections between surfaces of higher order than those investigated in this research; this in general is known to be a difficult problem. Numerical techniques will likely yield the only feasible solutions. Another challenge to be addressed as future work is the influence on this closed-form technique of interacting features that may be present in a complicated part. As shown in Figure 5-16 (a), a step feature interacts with a hole feature in a part. It can be seen from Figure 5-16 (b) that some surfaces of the hole are trimmed by the step that has been machined previously. The CWE calculation presented in this chapter is affected when the cutting tool engages the surfaces of the machined interacting feature. This problem needs to be investigated to obtain the correct CWEs for the broadest range of hole machining to be properly extracted. -97- Chapter 5. Cutter/Workpiece Engagement Extraction for Hole Milling (b) Wi with Interacting Features (c) W, without Interacting Features Figure 5-16: Interacting Features -98- Chapter 6 In-Process Workpiece Modeling in Hole Milling 6.1 Introduction In geometric verification, in-process workpiece modeling captures the in-process workpiece states during a machining operation. These models are important for verifying the correctness of N C toolpaths. As mention in Chapter 1, the in-process workpiece can be considered as a series of workpiece states, each generated by a machining operation. One or more operations can lead to the creation of a final part machining feature. For example, in Figure 6-1, a hole feature is created by a milling operation. The toolpath data consists of a single helical tool path. As can be seen, W is the workpiece geometry at any cutter location t presented by the parametric value w, along the helix during the hole machining operation. The initial workpiece is represented by Wo prior to performing any cutting. After the tool motion along the helix is completed, a final part hole feature (H) is generated along with the corresponding in-process workpiece W„ (the entire model). Figure 6-1: In-Process Workpiece in Hole Milling In hole milling, the challenge for in-process workpiece modeling is in generating selfintersecting swept volumes that are created as the tool moves along the helix. In this chapter, a Non-Uniform Rational B-Spline (NURBS) based approach is developed to generate an exact solid model of the swept volume. Based on the exact B-rep representation of the swept volume, the in-process workpiece can be modeled by performing Boolean operations between the swept volume and the in-process workpiece generated by the previous tool motion. This is a novel capability, since self-intersecting solids cannot be generated by C A D systems. -99- Chapter 6. In-Process Workpiece Modeling in Hole Milling NURBS curves and surfaces will be described in the next section, since they are used to construct the boundary surfaces of the swept volume. Following this, a NURBS based swept volume generation approach will be presented. This will be followed by in-process workpiece modeling using the Boolean operation between the swept volume and the inprocess workpiece. Finally, examples will be presented to validate the proposed algorithm. 6.2 N U R B S Curves and Surfaces 6.2.1 NURBS Curves A NURBS curve is defined as follows: ZW(«) p(«) = - ^ ( 6 £«>) . 1 } i=0 where: • N k(u) is a blending function, defined as: if M N \ ( fr-f/K^frO i k{ ) = u 1 t —t , (t -u)N _,(u) + i+k Mk ! t —t [0 otherwise • ^-1 degree • H+1 control points • [to, ti, ... ,t„+k] is a knot vector, a knot vector has n+k+l knot values • Pj fa, y z h,) is the /'* position vector or control point, h is a homogeneous coordinate h h t or weight of the /'* control point -100- Chapter 6. In-Process Workpiece Modeling in Hole Milling NURBS Representation of a Line: As shown in Figure 6-2 (a), a straight line bounded with two points (Po, Pi) can be represented by a first degree (k=2) NURBS curve with a knot vector [0, 0, 1, 1] and two control points, Po and Pi. The weights of the two control points are hn=hi=l. NURBS Representation of an Arc: An arc has several representations with NURBS parametrization, a 2 nd curves. To achieve the best degree (&=3) rational Bezier curve is used to represent an arc with a central angle less than 90°. As shown in Figure 6-2 (b), a composite rational Bezier curve is used to represent an arc with central angle greater than 90°. The knot vector, control points and their weights are listed in Figure 6-2 (b). p,o Knot Vector: [ 0 0 1 1 ] Knot Vector: [ 0 0 0 "A / 1 1 1 ] 1 n=1, k=2 n=4, k=3 (a) (b) 2 Figure 6-2: NURBS Representation of Line and Arc 6.2.2 NURBS Surfaces A NURBS surface is defined as follows: m P(«,v) = n ;=0 j=0 m (6.2) n where: • N (u) and N (v) are blending functions in the u and v direction • p-\is iiP Jtq the degree in the u direction, and q-\ the degree in the v direction -101 - Chapter 6. In-Process Workpiece Modeling in Hole Milling • m+\ control points are defined in the u direction and n+\ control points in the v direction • [un, ui, ..., u ] and [vo, vj, ... , v „ ] are the knot vectors in the u and v directions • Pj j (Xjj, ytj, Zjj, hjj) is the i row and j' column control point in the control polyhedron; hjj p+m ? + th h is the homogeneous coordinate (weight) of the control point P y Figure 6-3 illustrates a NURBS representation of a semi-cylinder. The NURBS surface has the following parameters in the u and v directions: • u direction: m=3, p=3, knot vector = [0, 0, 0, A, A, 1,1,1], homogenous coordinates=[l, X X 0.707, 1,0.707, 1] • v direction: n=l, q=2, knot vector = [0, 0, 1, 1], homogenous coordinates=[l, 1] Figure 6-3: NURBS Representation of a Quadric Surface 6.3 Swept Volume Generation A general swept surface is described in Figure 6-4. It is created by sweeping a parametric surface S(w,v) along an arbitrary path *P(f) with a rotation about axis T. Mathematically, a swept volume is described by the sweep equation as: $(u,v,t) = S(u,v)R(t)+V{t) (6.3) where: _{u,v,t): The set of all points inside and on the boundary -102- Chapter 6. In-Process Workpiece Modeling in Hole Milling R ^ ) : 3x3 rotation matrix *P(f): Sweep path S(w, v): Parametric equation of surface or solid In a hole milling operation, the cutting tool moves along a helical toolpath. Therefore, the swept volume is generated by sweeping a quadric surface along a helix without rotations. In this section, a NURBS based approach is developed to generate an exact B-rep model for the swept volume to support in-process workpiece modeling for hole milling. Figure 6-4: Sweeping a Surface 6.3.1 Overview Figure 6-5 illustrates a NURBS based swept volume generation approach. It can be seen that the boundary surfaces of the swept volume can be classified into three categories: Ingress, Egress and Envelope Surfaces. Ingress and egress surfaces are created by splitting the cylinder along its silhouette curves. Envelope surfaces are generated by sweeping the silhouette curves along the helical toolpath. If there are intersections among any of these surfaces, a surface trimming procedure is needed to remove all of the patches located inside the swept volume. Finally, the ingress surfaces at the initial position, the egress surfaces at the final position, and the trimmed envelope surfaces are stitched together to form a solid model of the swept volume. -103 - Chapter 6. In-Process Workpiece Modeling in Hole Milling Cutter & Toolpath Swept Volume Envelope Surfaces Egress Surfaces Figure 6-5: Swept Volume Generation A flowchart of the NURBS based approach is presented in Figure 6-6. This approach includes the following steps: 1. Silhouette Curves Identification'. To identify the silhouette curves of the tool geometry based on the helix angle of the toolpath, and to represent these curves with NURBS. 2. Envelope Surfaces Generation: To generate envelope surfaces by sweeping the silhouette curves along the helical toolpath, and represent these envelope surfaces with NURBS. 3. Surfaces Trimming: To identify the intersecting surfaces among the ingress, egress and envelope surfaces, and trim those patches that are within the boundary of the swept volume. -104- Chapter 6. In-Process Workpiece Modeling in Hole Milling 4. Surfaces Stitching: To stitch all the boundary patches together to construct a B-rep solid model for the swept volume. The topological correctness is verified based on the Euler-Poincare formula. The detail of the above steps will be provided in the following sections. Q START ^) Tool Geometry Inputs -2. Toolpath Silhouette Curves Identification ^" Envelope Surfaces Generation Surfaces Trimming Surfaces Stitching Outputs Swept \ olumc END Figure 6-6: A Flowchart of the NURBS Based Approach 6.3.2 Silhouette Curves Identification Figure 6-7 illustrates a silhouette curve on a general surface from a perspective direction P. A perspective direction is the tangent direction of the path curve during sweeping. A silhouette curve on the surface can be defined as a set of points on the surface where the normal of the surface is perpendicular to the perspective direction. Mathematically, a silhouette curve on a parametric surface S(w,v) can be represented as: G(ii,v) = n ( « , v ) » P = 0 (6.4) where: -105 - Chapter 6. In-Process Workpiece Modeling in Hole Milling ( x as as Surface normal: n{u, v) = — x — Perspective direction: P z Silhouette C u r v e Figure 6-7: Silhouette Curves of a General Surface In this section, the silhouette curves on the surfaces of flat, conical and ball nose endmills are given. The perspective direction P has an angle over the X Y plane that is equal to the helix angle a of the helical toolpath. Figure 6-8 illustrates silhouette curves for a ball endmill that has a cylindrical and spherical surface. The NURBS parameters, such as the number of control points (n), degree (k-I) and knot vector, are given in Figure 6-8. The control points for each silhouette curve are listed in Table 6-1. The reader can refer to Appendix D for silhouette curves of the flat and conical end-mills. -106- Chapter 6. In-Process Workpiece Modeling in Hole Milling Figure 6-8: Silhouette Curves for a Ball End-Mill •-. , Cur\e # Tvpe 1 2 3 4 Arc Arc Line Line <\ : r Control Points , z Point # X Po x +R yo zo+H P, Xo-R yo z +H Q. xo+R y -R z +H Q 2 Xo yo-R zo+H Q 3 Xo-R yo-R zo+H P 3 xo+R yo z P 2 Xo-R yo zo Q. x +R 0 yo+Rsina zo-Rcosa Q 2 Xo yo+Rsina Zo-Rcosa Q 3 xo-R yo+Rsina zo-Rcosa Po xo+R yo zo+H P xo+R yo zo P. xo-R yo zo+H P xo-R yo zo 3 2 0 0 0 0 0 Table 6-1: Control Points for Silhouette Curves of a Ball End-Mill - 107- Chapter 6. In-Process Workpiece Modeling in Hole Milling 6.3.3 Envelope Surfaces Generation Envelope surfaces are generated by sweeping silhouette curves (profile curves) along the path curve. In today's C A D systems, the technique used to generate a swept surface by sweeping profile curves along a path curve is to interpolate a series of profile curves located at calculated intervals along the path curve. This is referred to as skinning. This interpolation is necessary to provide a general solution for a sweep regardless of the mathematical form of the path's geometry. The interpolation of the path curve leads to an approximation of the swept surface to a resolution specified in the modeler. In this thesis, both the profile curve (silhouette curve) and the path curve (helical curve) are represented exactly as NURBS curves. It is therefore possible to construct the NURBS surface to represent the swept surface exactly without the approximation created by interpolation. In order to provide an exact NURBS representation for envelope surfaces, the control polyhedron and associated weights have to be identified based on NURBS representation of the profile and path curves. To assist in the description of the envelope surface generation approach, a NURBS representation of a silhouette curve and a helical curve is illustrated in Figure 6-9. Figure 6-9 (b) presents the top view of the helical curve. m=4, n=4, q=3 p=3 (a) Silhouette Curve (b) Helical Curve Figure 6-9: NURBS Representation of a Silhouette Curve and a Helical Curve Based on the profile and path curves described in Figure 6-9, a control polyhedron of a NURBS surface for the profile curve swept along the path curve is illustrated in Figure 6-10. The control points of the NURBS surface Pjj are calculated by transforming the control polygon of the profile curve Pj along the control polygon of the path curve Qj. This -108 - Chapter 6. In-Process Workpiece Modeling in Hole Milling transformation includes a rotation about the z-axis, a translation along the z-axis and a scaling in the x-axis. This calculation is described in Eq. (6.5). P =P .R(0).T(0).S(9) iJ (6.5) J where: ¥\j(Xjj, y/j, Zjj, 1): The homogeneous coordinates of the control point of the NURBS surface Pj(x,, yj, Zj, 1): The homogeneous coordinates of the control point of the profile curve R(9): The rotation matrix T(0): The translation matrix S(0): The scaling matrix 0: The central angle of the helical curve R(0),T(0) and S(0) are 4x4 matrices represented in Eq. (6.6)-(6.8). cos R f 8\ sin S= 0 0 0 0 0 1 0 0 0 1 cos -sin o o T = .0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 - / pO Inn 1 *, 0 0 0" 0 1 0 0 0 0 1 0 0 0 0 1 (6.6) (6.7) (6.8) where: -109- Chapter 6. In-Process Workpiece Modeling in Hole Milling k, = cos '0^ 1 i= U,5,. / = 0,2,4,. (a) An Envelope Surface and Control Polyhedron Silhouette Curve (b) Top View of the Control Polyhedron Figure 6-10: Control Polyhedron of the Envelope Surface The weights of the control points of the NURBS surface can be calculated using Eq (6.9). -110- Chapter 6. In-Process Workpiece Modeling in Hole Milling Ki = & i' j h 1 = m J = (-) n 6 9 where hj, coi are weights of the control point of the profile and path curve described in Figure 6-9. Figure 6-11 shows an example of the control polyhedron of an envelope surface generated by the top edge of an end-mill based on the above equations. This approach provides an exact and more concise representation compared with the approximate approach used as part of the skinning technique. Figure 6-11: NURBS Surface and Control Polyhedron for an Envelope Surface 6.3.4 Surface Trimming As mentioned in the section overview, the boundaries of a swept volume consist of ingress, egress and envelope surfaces. Ingress and egress surfaces are generated by splitting the boundary surfaces of the cutting tool along its silhouette curves. A surface trimming step will be applied if intersections exist among these surfaces. This step is accomplished by first intersecting the surfaces in question by applying surface/surface intersection algorithms within a solid modeler. Then the resulting patches inside the boundary of the swept volume are detected and removed. The remaining patches form the boundary of the swept volume. Figure 6-12 illustrates how to identify the patched to be removed. The cutting tool sweeps from the initial position P (r, 0) to the final position Y (rcosO, rsinO). The patches to s e be trimmed are always located inside the region defined by the intersection of the initial and final cylinders. Considering the circular projections of these cylinders given any point P(x, y) -111 - Chapter 6. In-Process Workpiece Modeling in Hole Milling on a patch, if F(x, y) satisfies Eq. (6.10), the patch will be trimmed, otherwise the patch will be identified as a boundary surface of the swept volume. (6.10) Figure 6-12: Surfaces Trimming 6.3.5 Surface Stitching The stitching step constructs a B-rep solid model from the trimmed patches that make up the boundary of the swept volume. Solid modelers such as ACIS provide API routines to convert a set of surfaces forming a closed region in 3D space into a B-rep solid model. This operation will be successful only if a closed 3D space is surrounded by these patches. The B-rep of the stitched volume can be verified by the Euler-Poincare formula as: (6.11) V-E+F=2 where: V: Number of Vertices E: Number of Edges F: Number of Faces -112- Chapter 6. In-Process Workpiece Modeling in Hole Milling Only a valid B-rep solid can be used for Boolean operations required by in-process workpiece modeling. 6.4 In-Process Workpiece Modeling In-process workpiece modeling generates a series of in-process workpieces at any cutter location along the toolpath, As illustrated in Figure 6-13, the in-process workpiece W i is i+ generated by a regularized Boolean subtraction operation (-*) between the in-process workpiece W and the swept volume SVj. t W =W -*SV l+x i (6.12) l where: SVj-. Swept volume generated by the /-th tool motion Wj-. In-process workpiece before the /-th tool motion Wj+i: In-process workpiece after the /-th tool motion In-Process Workpiece (W) In-Process Workpiece (W, ) +1 Figure 6-13: In-Process Workpiece Modeling 6.5 Implementation and Validation The algorithms described in this chapter were implemented using the Microsoft Windows X P professional edition operating system. Visual C++ was used as the development tool. This implementation uses the ACIS 3D modeling kernel as the solid - 113 - Chapter 6. In-Process Workpiece Modeling in Hole Milling modeling engine, and the HOOP 3dGS as the graphics system. This program was tested using a computer with a Pentium 4 processor, with 3GHz/0.99GB. Figure 6-14 illustrates data structures designed in this implementation. There are three types of geometry in the data structures. Each type corresponds to a geometric entity such as a volume, surface or curve. The class SweptVolume has a list of egress, ingress and envelop surfaces. The class EnvelopeSurface contains a list of silhouette curves. Each class points to a B-rep data structure of the corresponding geometric element. EgrebsSurfaco -Type -BrepSurface 1 1 -* SweptVolume -Type -Dimension -IstlngressSurfaces -IstEgressSurfaces -IstEnvelopeSurfaces -IstlngressSurfaces Ingreb&Surface -Type -BrepSurface 1 1..* -BrepSolid EnvelopeSurface -IstEnvelopeSurfaces 1..* -Type -IstSilhouetteCurves -BrepSurface -IstSilhouetteCurves A 1 SilhoucttcCurvc -Type -BrepCurve 1..* Figure 6-14: Data Structures Table 6-2 presents an example of the swept volume for a flat end-mill. It can be seen that the swept volume is self-intersecting, since the radius of the cutter is greater than the radius of the toolpath. Table 6-3 shows a swept volume of a ball end-mill having the same radius as the helical toolpath. A n example of the swept volume for a conical end-mill is presented in Table 6-4, where the radius of the cutter is smaller than that of the helical toolpath. This is also the case where the swept volume is self-intersecting. -114- Chapter 6. In-Process Workpiece Modeling in Hole Milling Helical Toolpath Radius [mm] Pitch [ mm] Start Angle [deg] End Angle [deg] 20 40 0 315 Flat End Mill Radius [mm] Height [mm] 30 80 n Swept Volume Workpiece Swept Volume _ Table 6-2: Swept Volume Generation and Verification for a Flat End-Mill Helical Toolpath Radius [mm] Pitch [mm] Start Angle [deg] End Angle [deg] 20 40 0 60 Ball End Mill Radius [mm] Height [mm] 20 50 Swept'Volume Workpiece Swept Volume Table 6-3: Swept Volume Generation and Verification for a Ball End-Mill -115- Chapter 6. In-Process Workpiece Modeling in Hole Milling Helical Toolpath Radius [mm] Pitch [mm] Start Angle [deg] End Angle [deg] 20 40 0 330 Conical End Mill Radius [mm] Height [mm] Cone Height [mm] 10 40 10 Swept Volume Table 6-4: Swept Volume Generation and Verification for a Conical End-Mill 6.6 Discussion As shown in Tables 6-2, 6-3 and 6-4, the swept volumes and in-process workpieces generated by the three types of cutting tool at different cutter locations using the approach outlined in this chapter are verified. The advantage of the algorithms used is that the boundary surfaces of the swept volume are exactly represented with N U R B S . This is because the ingress and egress surfaces are quadric surfaces based on the cutting tool geometry that can be exactly represented with NURBS. Also the envelope surfaces are accurately constructed with N U R B S by calculating control points in the control polyhedron instead of applying the generic sweeping operations provided in solid modelers. In solid modelers, the sweeping operation generates a swept surface by sweeping profile curves along a path, which involves interpolating a series of profile curves located along the path. However, this technique provides only an approximate solution to the swept surfaces. The envelope surfaces generation approach presented in this research provides an exact solution to the envelope surfaces. These envelope surfaces have compact and exact representation. Appendix E - l and E-2 are listed to compare the sat files (ACIS file) of an envelope surface -116- Chapter 6. In-Process Workpiece Modeling in Hole Milling generated by these two different approaches. It can be seen that the NURBS surface generated by the proposed approach has a significantly more compact data structure. Future work will focus on the swept volumes generated by a bull end-mill. The challenge in this future research will be in finding an exact NURBS representation for the silhouette curves of a bull end-mill, since they are not quadric curves. -117- Chapter 7 A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction 7.1 Introduction CWE calculations are an area of growing importance in process modeling. As B-rep models are widely used in the C A D / C A M field, interest in B-rep model based CWE calculations is likewise increasing; However, two difficulties are apparent in the B-rep model based approaches. First, the geometry of the workpiece becomes more and more complicated as the machining simulation progresses, leading to a large data structure with accompanying problems in computational efficiency that grind the simulation to a halt over time. Second, the user who runs the CWE calculation must have access to a solid modeler on their computing system to perform the simulation. To address both of these problems, a distributed, Internet-enabled approach is proposed. Multi-Agent System (MAS) technology is playing an increasingly important role in developing intelligent, distributed and collaborative applications. A comprehensive survey and review of MAS applications in engineering design and manufacturing is provided in Chapter 2. The current chapter presents an approach that utilizes a MAS for the CWE calculations. The MAS based framework accepts requests from a process engineer for CWE calculations for a set of toolpaths (cutter location data). The framework generates one or more CWE agents that in turn initiate requests for removal and swept volume calculations from other agents that reside, or are created as needed, over the Internet. The MAS is managed to maximize the use of free resources in the framework, leading to greatly improved efficiency in the CWE calculation for the job at hand. In addition, because the computational effort is performed by distributed agents instead of on the computer at the user's location, process engineers wanting to perform CWE calculations do not need a resident B-rep solid modeler like ACIS. A user can start the calculation as long as they can find a free CWE agent somewhere on the Internet/intranet able to execute the request. -118- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction The rest of this chapter is organized as follows. Section 2 provides a general description of the key computational steps involved in CWE extraction. Section 3 introduces the architecture of the MAS, including agent specification and agent collaboration. Section 4 illustrates an example that demonstrates the application of the CWE MAS. Section 5 discusses future extensions to this work. 7.2 General Approach to CWE Calculations The strategy for performing CWE calculations is designed to facilitate parallel processing where possible. As shown in Figure 7-1, the inputs to the problem include a B-rep representation of the initial workpiece, CLData generated by a C A M system for machining the final part from the workpiece, and cutting tool descriptions. Based on the latter two pieces of information, swept volumes are generated for the tool moving along each toolpath. These are represented as B-rep solid models. By performing Boolean intersections between each swept volume sequentially with the workpiece, removal volumes are generated. Each removal volume is then processed by a CWE extractor to identify the engagements at feed steps along the associated toolpath. This procedure involves intersecting a representation of the cutting tool with the removal volume, then manipulating the intersection graph to extract entry and exit angles as a function of depth of cut. It can be seen that steps (1) and (3) can be performed for creating each swept volume and processing each removal volume for its CWEs in parallel. Since the creation of removal volumes in step 2 requires an accurate in-process model of the workpiece after the previous tool motion, there are greater restrictions in the ability to perform these operations in parallel. Some research has addressed this issue. In their research, toolpaths are clustered into groups where the in-process workpiece generated by a given group does not affect engagement conditions in other groups, e.g., toolpaths at different Z-levels. Such groups can be processed in parallel. The MAS framework described in the rest of this paper is designed to take advantage of being able to simultaneously perform multiple swept volume and CWE calculations per removal volume. -119- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction Commercial B-rep Solid Modeler CAD/CAM System ACIS Pa.raS.plcl f — - ~ ~ — \ ^ 3 ( Cutting Tool X V Geometric Description J f B-rep Solid of VlnHlalWorMe.ee ^ Swept Volume Generator 2 B^rep Solid of ^\ V Swept Volume J B-rep Solid of In-process Removal Volume Generator < B-rep Solid of Removal Volume CWE Extractor no ^Done^*^ ( \ B-rep Solid Cultlng Tool Figure 7-1: Steps in CWE Calculation 7.3 Multi-Agent Framework for CWE Calculations An agent is an intelligent, autonomous and self-adaptive entity that is able to reason, make decisions and respond accordingly within the application in question. In complicated applications, individual agents may lack the ability to solve a problem. MAS technology has been developed to make agents work together to deliver solutions to problems that are beyond the individual capabilities or knowledge of each agent. MAS technology can also manage agents to achieve parallel computation by breaking tasks into several independent subtasks that can be handled by separate agents. To describe a Multi-Agent framework, it is important to understand the functionality of individual agents and how they interact with each other to reach their individual or shared goals. In this section, a specification is provided for each agent in the CWE calculation MAS. Following this, the collaborative strategy of agents for CWE calculation will be explained. -120- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction 7.3.1 Agent Specification in CWE Calculation MAS Figure 7-2 shows the agents that have been identified for the CWE calculation MAS. Eight agents have been defined. The three primary computational agents are: • Cutter Workpiece Engagement Agent (CWE): This agent is responsible for performing the intersection between the cutting tool and the removal volume geometries to find the actual engagement geometry. To do this, it must coordinate with other CWE agents, since several of them may be created to handle computations in parallel for a large toolpath file. It is also responsible for coordinating with removal volume agents that must provide the solid model of the volume for processing. • Removal Volume Agent (RV): This agent applies solid modeling intersection operations between the swept volumes of the cutter moving along selected toolpaths and the appropriate in-process workpiece state. To do this, it must be able to retrieve or create a model of the correct in-process workpiece state and models of all the selected swept volumes. The latter are generated by interactions with swept volume agents. • Swept Volume Agent (SV): Like the RV agents, these agents apply solid modeling operations to generate the geometry of the swept volume of the cutter along a toolpath In addition to the computational agents, Interface Agents (IA) have been developed for each to facilitate communication with the user of the MAS. These agents are tailored to provide the functionality that the user needs to interact effectively with the computational agent it is associated with. Interface Agents act as a thin-client on the user's computer, collecting user inputs and visualizing the results. For visualizing solid models, the IAs render polyhedral models that are generated from the solid model by faceting functionality within the solid modeler used by the associated computational agent. This thin-client structure makes the user's computer independent of a heavy computational kernel. This feature supports use of the application by users who have not installed a solid modeler or complicated graphics engine on their system. For example, the CWE interface agent requires a graphical user interface to display the results of the engagement calculations. This interface is illustrated in Figure 7-12. As can be seen, through this agent the user can visualize inprocess workpieces, swept volumes, removal volumes and the CWEs themselves. -121 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter-/Workpiece Engagement Extraction The remaining two agents are responsible for data management (DA) and to provide registration/deregistration of the agent with on-line agent services (DF). 1 SV A Pent iH SV A<rent SV Agent DF DBMSj B a o user > File ^systonjr Agent RV Agent 1 Data m FTP/Mail Servers 3 CWF, CWE Figure 7-2: Agents in CWE Calculation MAS 7.3.2 Agent Collaboration in CWE Calculation MAS In this section, we w i l l describe how computational agents interact with each other to achieve parallelism. First o f all a general description for collaboration strategies within the CWE calculation MAS is provided. Agent actions that w i l l be performed during interaction and collaboration i n the MAS need to be identified. Since each computational agent holds several different states, a Finite State Machine (FSM) model is introduced for agents to manage their states during collaboration. Finally, agent collaboration w i l l be discussed by introducing three protocols to explain how agents cooperate with each other to complete tasks in parallel. 7.3.2.1 Overview Requests to CWE, RV or SV agents may be for either a completely new or previously started job. This is significant, since machining is a sequential process. The existence o f swept and removal volumes calculated during a previous j o b for parts o f a tool path file can be used to reduce the computational effort needed when engagements for other tool motions within the same file are required. T o simplify the discussion, it is assumed that the CWE calculation request is submitted for the first time for a given tool path file. Thus, there is no - 122- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction historical data stored in the data agent, and complete CWE, RV and SV calculations are required. As shown in Figure 7-3, computational agents are grouped into several levels. From top to bottom, there are the IA group, CWE group, RV group and SV group. In this layered structure, the calculation requests flow downwards and results are submitted in the upward direction. There are two types of parallelism that can be achieved with this architecture: • Parallelism within a group: To achieve parallelism within a group, agents are divided according to two different roles: one is the master agent, which interacts with one or more slave agents. The master agent is responsible for decomposing and allocating calculation tasks to multiple slave agents. The task scheduling activity that applies a strategy for. allocating tasks among slave agents is performed by the master. • Parallelism between adjacent groups: After sending calculation requests to an agent in a lower-level group, a simple strategy is for an upper-level agent to wait for each result before continuing its calculations. However, to achieve parallelism, agents at lower levels can instead be tasked to submit a set of results at a time so that agents in upper levels can process this result set in parallel. Master agents in each group take the responsibility for collecting results from their slave agents, grouping these into sets and submitting them to the master agent in the upper level. A Result Passing Strategy for determining when results should be transferred to an upper level is defined for each master agent operating on a lower level. The master agent for each group is selected by the master agent that resides in the level immediately above, using a Master Agent Selection strategy. - 123 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction L e v e l l : I A G r o u p L e v e l 2 : C E IA Agent Request CWE Results Task Allocation. Agent (Master) W r\\JV A front i - W l ? A front CWE Results Agent (Slave) Request L e v e l 3 : Results RV Agent (Master) Task Allocation RV Am.nl RV Agent (Slave) Request L e v e l 4 : SV Agent (Master) Task Allocation. Results R V G r o u p A iront B V Results Results G r o u p «iV S V G r o u p Aoi-nt «V A front SV Agent (Slave) Figure 7-3: Agent Collaboration in CWE Calculation MAS To better understand the nature of the collaborations within the CWE calculation MAS, the following scenario is described. First, the user finds a CWE calculation service through the Internet or on a company-wide intranet where the MAS is active. The user must then download a light-weight IA for use to input the calculation parameters and to visualize the calculation results. This IA allows the user to specify the workpiece and toolpaths to be processed with the MAS. The IA also facilitates uploading workpiece and toolpath files to the data agent from the user's computer. When the user broadcasts a calculation request, the interface agent selects a CWE agent that is identified by the DF agent as the master CWE agent and sends the request to this master agent. The master CWE agent accepts the request and extracts the calculation parameters, as well as the addresses of the workpiece and -124- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction toolpath files, from the calculation request message. If the master CWE agentfindsthat RV calculations are necessary, it locates a master R V agent by using the DF agents and sends a request to it. The RV agent in turn checks with the DA to determine if the data it needs is available (i.e., the swept volume and in-process workpiece). If not, its task is delayed until a calculation request to an SV agent is satisfied. When the required geometry for the removal volumes is obtained, the master CWE agent decomposes the CWE calculation task and distributes it to other slave CWE agents in the MAS. Finally, the master CWE agent recombines the calculation results returned by the slave CWE agents and returns them to the interface agent. The user can view the results using the CWE interface agent. The RVand SV agents follow a similar procedure when they receive a calculation request. Figure 7-4 illustrates a comparison between sequential CWE calculation and the parallel CWE process implemented in the MAS framework. Calculation tasks are decomposed and distributed among agents in each group for parallel computation. The overlap between tasks for the different groups is achieved using the results passing strategy. Calculation Time Sequential Calculation SV Calculation RV Calculation ^ ^ ^ > CWE Calculation SV Agent 1 SV Agent 2 C J RV Agent 1 •J-P RV Agent 2 JIB—p CWE Agent 1 — CWK Agent 2 CWE Agent 3 Figure 7-4: Parallelism in CWE Calculation MAS From the above example, three actions can be identified for master agents to achieve these two types of parallelism during collaboration: - 125- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction • Task Scheduling • Master Agent Selection • Results Passing Detailed descriptions of these three agent actions will be provided in the next section. 7.3.2.2 Agent Actions To indicate how busy the system is where the agent is located, an idle factor (K) is defined for each agent. Considering that CPU and memory usage rates are the two most important indications of busyness, they are used to calculate the idle factor as follows: K = 2 (7.1) m where K = 1 - R is the idle factor for CPU usage, with R being the CPU usage rate. c c c Similarly, K = 1 - R is the idle factor for memory usage, while R is memory usage rate. m m m From Eq. (7.1), we can see that K is an average of K and K , and K e [o,l]. The factor K C M will be determined for each agent to indicate its idleness. K plays an important role in the agent collaboration process, since most strategies (such as Task Scheduling, Master Agent Selection, etc.) are based on assigning tasks to agents that are the least active. Task Scheduling To schedule tasks among slave agents in the same group, the master agent broadcasts availability requests to slave agents that are identified by the DF agent based on their availabilities and idle factors. After receiving responses, a master agent maintains an agent list for all available slave agents. Assuming that slave agents {A. \ i = 1,2,..., m} are in an agent list, their tasks {7; |/ = I,2,..JM} can be allocated based on their idle factors {K,\i = \,2,..jn} as described by Eq. (7.2), m (7.2) 7) =7" where -126- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction Tj\ Task allocated to the i-th slave agent K{. Idle factor of the /-th slave agent T: Total tasks to be allocated From Eq. (7.2), it can be seen that a master agent creates a schedule based on the percentage of total idle factors that a given slave agent has. This strategy guarantees that slave agents with larger idle factors will take on more computational tasks. Master Agent Selection Strategy The master agent in each group is determined by the master agent in the immediate upper-level group. The master agent requests availability from all agents in a lower-level group. Based on their idle factors, the agent with the largest idle factor is selected as the master agent. The master agent in the upper-level group then sends all of the calculation requests to the newly designated master agent in the lower-level group. This master agent then decomposes and distributes the tasks to the slave agents in its group. In the CWE calculation MAS, the master CWE agent is selected by an interface agent, the master RV agent by the master CWE agent and the master SV agent by the master RV agent. Results Passing Strategy The results passing strategy is designed to achieve parallelism between adjacent levels. This strategy utilizes a Slide Window to coordinate results submission from a lower level to an upper level. The master agent in a lower level maintains a task queue after receiving calculation requests from the master agent in the upper level. The slide window acts as a 1dimension window sliding along this queue, starting from the first task. A n integer parameter called Slide Window Size (SWS) specifies how many tasks the window spans at any position along the task queue. When the calculations for all the tasks located within the slide window are completed and submitted by slave agents, the results are submitted from the master agent in the lower level to the master agent in the upper level that requested the service. The slide window then slides SWS tasks along the task queue to a new position, where the master agent waits for a new set of results from its slave agents for the next submission. - 127- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction An example of this approach is shown in Figure 7-5. A master RV agent receives six toolpath segments for calculation from the master CWE agent and distributes these tasks to several slave RV agents. Given that a SWS of 3 is used, the slide window first spans from segment 1 to segment 3. After receiving removal volumes 1 and 2 from slave agent 1, the master RV remains in a waiting state, since removal volume 3 is still not available. Once removal volumes 3, 4 and 5 are submitted by slave agent 2, all three removal volumes are now available and can be submitted*to the master CWE agent by the master RV. After the submission is complete, the window slides to a span of the task queue starting at segment 4. The parameter SWS has significant influence on the efficiency of the results passing strategy. The smaller its value, the greater the parallelism is between adjacent groups. However, this comes with a heavier network load. In the CWE calculation MAS, results passing using this approach is performed by the master CWE, RVand SV agents. Master CWE Agent Master RV Agent 1 2 3 4: •;:s,;' 6 J^JRcsiilt (1,2)from Slave Agent 1 J W W 6 J^J_Result (3,4,5) from Slave Agent2 | 1 •' | : .V:'...":-. V : ; ii! 2 3 4 5 6 1 2 3 w 5 6 1 2 3 4 5 6 1 .. 1 1 1 1 ^^jwiiidow Sliding Result 0,2.6) Passing 1 . 2 3 4 5 6 i T i Figure 7-5: Slide Window for Results Passing -128 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction 7.3.2.3 Agent States Each agent manages its state using a Finite State Machine (FSM) model. There are in all five states for an agent: IDLE, WAIT, C A L C U L A T I O N , SUCCESS and ERROR. In each state, only the expected messages are handled; unexpected ones are simply discarded. These states are described as follows: • IDLE: This is the initial status of an agent. A n agent in this state is free and available for queries and calculation requests. • WAIT: When an agent receives a query from another agent, it responds with R E S A V A I L A B L E (Available) and switches to a WAIT state if it is currently IDLE. Otherwise, the query message is simply discarded or a R E S _ U N A V A I L A B L E response is given. A n agent in this state waits for a calculation request from the querying agent. If the request arrives, it switches to a C A L C U L A T I O N state. If the request does not arrive in a specified time, a timeout occurs and it returns to the IDLE state. • C A L C U L A T I O N : When an agent in an IDLE or WAIT state receives a calculation request, it responds with R E S _ A V A I L A B L E and switches to the C A L C U L A T I O N state. At this point, a new session is created. A session that is attached to an agent starts when the calculation request arrives and ends when the calculation finishes. As mentioned above, in the framework there is one agent selected as a master, with the others performing as slaves. For slaves, a session ends when its own job is finished, while for a master a session does not end until all calculations it has distributed over slave agents are finished in addition to any master specific tasks, such as recombining the results from slaves. After a session is created, an agent begins task scheduling, which results in it doing the job by itself, sending calculation requests to other agents or distributing subtasks over slave agents. • SUCCESS: When a session finishes successfully, the agent transfers to a SUCCESS state. Once it reaches this state, it informs the requesting agent of the calculation result and returns to an IDLE state. • ERROR: When there is any error during the calculation or a timeout is caused by a native calculation process or a delayed response from any slave agent, the agent transfers to an -129- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction ERROR state. After reporting the error type and description, it automatically transfers to an IDLE state. Figure 7-6 shows the FSM model of a receiver agent. When the agent is in a C A L C U L A T I O N state and sends requests to other agents, it also doubles as a sender agent. To simplify the state management, its state does not change but remains in the C A L C U L A T I O N state. This means that in the current architecture an agent handles only one session at a time. Figure 7-6: FSM Model of a Receiver Agent 7.3.2.4 Agent Collaborations Based on the agent actions and states discussed above, this section describes how agents collaborate with each other to realize parallel computation. In CWE calculation MAS, three collaborations, Selecting Master Agent, Allocating Tasks and Coordinating Results Submission, are performed to achieve parallelism. Each of these collaborations will be explained with an interaction protocol. Collaboration 1: Selecting Master Agent As mentioned previously, the master agent in each group is selected by the master agent in the immediate upper level group. Each of the three levels in the MAS has a master agent. Initially, the master CWE agent is selected by the interface agent interacting with the end -130- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction user. Following this, the master CWE agent selects the master RV agent, and the master RV agent selects the master SV agent. Figure 7-7 illustrates a scenario that shows how a master RV agent identifies a master SV agent. A master RV agent broadcasts R E S _ A V A I L A B L E messages to all SV agents for their availability. At the time when the SV agents receive this message, SV agent 1 and 2 are in the IDLE state, and S T agent 3 is in the WAIT or C A L C U L A T I O N state. SV agents 1 and 2 respond to the master RV agent with R E S _ A V A I L A B L E messages along with their idle factors, 0.4 and 0.8, respectively. SV agent 3 responds with the R E S J J N A V A I L A B L E message. Master RV agent maintains an available SV agent list that contains SV agent 1 and 2 and their associated idle factors. Master RV agent performs Master Agent Selection (described in previous section) to select SV agent 2 as the master SV agent for the SV agent group. Upon completion of the selection process, the master RV agent sends calculation tasks 1, 2, 3, 4, 5 and 6 to the master SV agent. SV Aaent2 SV Aaentl Master RV Aaent REQJWAILABLE SV Aaent3 , y. REQ_AVAILABLE I REQ_AVAILABI_E I RES AVAILABLE(0.4) fcI I I RES_AVAILABLE(0.8) fe-i 1 Master Agent l Selection ] R E S UNAVAILABLE R E Q _ S V _ C A L C U L A T I O N ( T a s k l ,2,3,4,5,6) I Figure 7-7: Protocol for Collaboration 1 (Selecting Master Agent) -131 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction Collaboration 2: Allocating Tasks The master agent in each group decomposes tasks and distributes them to slave agents according to their idle factors. The master agent at each level broadcasts to all slave agents in the same group for their available state. The master agent forms a list of available slave agents after receiving responses. As shown in Figure 7-8, the agent list includes slave agent 1 with idle factor 0.4 and slave agent 2 with idle factor 0.8. The master agent utilizes the task scheduling strategy discussed in the last section to allocate the six tasks, 1, 2, 3, 4, 5 and 6. Tasks 1 and 2 are assigned to slave agent 1, and tasks 3, 4, 5, 6 are assigned to slave agent 2. Master Aaent REQ Slave A a e n t l Slave Agent2 Slave Aaent3 AVAILABLE -2 REQ_AVAILABLE I I RES_AVAILABLE(0.4) REQ_AVAILABLE I i RES_AVAILABLE(0.8) I k-i I I R E S UNAVAILABLE T a s k Scheduling Task(1,2,3,4,5,6) Task(1,2) -2 Task(3,4,5,6) I -3 Figure 7-8: Protocol for Collaboration 2 (Allocating Tasks) Collaboration 3: Coordinating Results Submission The master agent in each group submits calculation results collected from the slave agents to the master agent in the immediate upper-level group. Starting with the master SV agent, swept volumes are submitted to the master RV agent. The master RV agent sends - 132- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction removal volumes collected from the slave RV agents to the master CWE agent. Finally, the CWEs are submitted by the master CWE agent to the interface agent for visualization. Figure 7-9 shows how a master RV agent, 3 slave RV agents and a master CWE interact with each other for this collaboration. In this example, the master RV agent will use the Results Passing Strategy introduced in the last section to determine when the removal volumes are to be submitted to the master CWE agent. After receiving tasks (1,2,3,4,5,6) from the master CWE agent, the master RV agent distributes tasks 1 and 2 to the slave RV agent 1, tasks 3, 4 and 5 to slave RV agent 2 and task 6 to slave RV agent 3. Since the Slide Window Size for results passing is set to 3, the master RV agent sends results 1,2,3 to the master CWE agent only after slave RV agent 1 completes and submits its tasks (results 1,2) and slave RV agent 1 completes and submits its tasks (results 3,4,5). Once slave RV agent 3 sends its calculation result 6, the master RV agent submits results 4,5,6 to the master CWE agent. Master C W E Aaent RVAaent2 RVAoentl Master RV Agent RVAaent3 Task(1,2) Task(3,4,5) Task(6) -+Result(1,2) £ ] J Result(3,4,5) l«£ ± Window Sliding Result(1,2,3) Result(6) Window Sliding Result(4,5,6) Figure 7-9: Protocol for Collaboration 3 (Coordinating Results Submission) -133 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction 7.4 Implementation and Example To standardize the development of MAS, the Foundation for Intelligent Physical Agents (FIPA) [18] was founded in 1996. The main goal of FIPA is to specify guidelines for agent management and communication. JADE (Java Agent Development Framework) [18] [19] is a FIPA-compliant middle-ware for facilitating FIPA compliant MAS development. Agents developed by J A D E can be easily distributed across machines and different operating systems. The CWE calculation framework is implemented using the J A D E platform. As shown in Figure 7-10, all of the agents in the CWE calculation MAS are implemented using JADE. Ontologies are defined to facilitate the communication among agents. Java Swing and Java 3D are used in interface agent development for user interface and 3D visualization. Computational modules such as those for CWE, RV and SV calculations are built using ACIS R13.0 and implemented as DLLs (Dynamic Link Library) by Visual C++. The corresponding computational agents implemented with Java on the JADE platform call these C++ modules through JNI (Java Native Interface), the Java interface for calling software modules written in languages other than Java. J A D E J a v a ( J a v a ) S w i n g 3D J a v a Data Agent CWE RV Agent Agent DF Agent SV Agent JNI (Java Native Interface) • CWE Calculation Module (dll) A C I S RV SV Calculation Module (dll) i Calculation Module (dll) ( C + + ) Figure 7-10: Implementation of CWE Calculation MAS -134- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction To test the effectiveness of the CWE MAS, a milling process for a spiral part is simulated, as shown in Figure 7-11. Figure 7-11 (a) shows the final part, (b) the initial workpiece, and (c) the toolpaths. There are in total 410 toolpath segments in this milling process. The test was conducted over an Intranet where three workstations (Pentium 4 CPU 1.8GHz and 512MB R A M , 100Mb Network Adaptor) are located. Five test cases were performed on this test part with all of the 410 toolpath segments. The calculation times are shown in Table 7-1. Test case 1 is a sequential CWE calculation where all three calculations are executed on one workstation. In test case 2, six agents (2 CWEs, 2 RVs and 2 SVs) are generated in workstation 1. Each agent has its own process. Compared to test case 1, calculation time is reduced significantly, since parallel computation is performed in test case 2. In test case 3, agents are distributed to different workstations (2 CWEs in workstation 1, 2 RVs in workstation 2 and 2 SVs in workstation 3). The calculation time is further improved since agents have more computational resources to utilize. By increasing the agent numbers in each workstation, additional improvements in the calculation time can be observed. Figures 7-12 (a), (b), (c) and (d) show the visualization within a CWE Interface Agent of the SV, RV, in-process workpiece and the CWE results from the 398th toolpath segment, respectively. -135 - Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction (b) Initial Workpiece ( ) Toolpaths c Figure 7-11: Test Part .— , CWE RV SV Calculation Workstation 3 Workstation 2 Workstation 1 Test# Time CWE RV SV CWE RV SV (Second) 1 1 1 1 0 0 0 0 0 0 68 2 2 2 2 0 0 0 0 0 0 37 3 2 0 0 0 2 0 0 0 2 31 4 3 0 0 0 3 0 0 0 3 27 5 4 0 0 0 4 0 0 0 4 24 Table 7-1: Calculation Time in CWE Calculation MAS - 136- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction (d) Cutter/Workpiece Engagement (c) In-process Workpiece Figure 7-12: CWE Calculation for the 398th Toolpath Segment (from CWE Interface Agent) 7.5 Discussion One of the challenges not addressed in the CWE MAS research to-date is the management of data transfer for the in-process workpiece by the data agent to the RV agent. To correctly generate the removal volume for a toolpath, the swept volume must be intersected with this B-rep model and the model itself updated. The size of this B-rep model and the corresponding memory and data transfer time increase significantly as the simulation progresses. Since several slave RV agents (plus the master), each requiring access to the in- -137- Chapter 7. A Multi-Agent System for Distributed, Internet-Enabled Cutter/Workpiece Engagement Extraction process B-rep model, can exist at any given time, the ability to transfer the model efficiently will greatly impact the overall efficiency of the MAS. A decomposition of the in-process workpiece model is one option for distributing the B-rep model in pieces as needed to different RV agents, reducing the size of the data transferred and further increasing the parallelism of processing. As part of future work, the data agent will be expanded to include this functionality. While the current approach is B-rep based, other computational kernels can be utilized (e.g., Z-buffer or Polyhedral Modeling) for agents in a manner that make them transparent to other agents. Thus, a user can initiate a calculation once a CWE agent employing any kernel can be located on the Internet or an Intranet. A hybrid system of this type can be further leveraged to enhance processing efficiency. As mentioned in the introduction, CWE extraction is part of a Virtual Machining methodology. The other components of VM involve process modeling and optimization. As part of future research, agents for performing these steps will be implemented and integrated into the current MAS. These will include force calculation agents, tool-life prediction agents, chatter and vibration agents and process parameter optimization agents. Many of these process modeling activities are computationally intensive and can benefit greatly from implementation within the current framework. -138- Chapter 8 Conclusion 8.1 Contribution In this thesis, new methodologies are proposed to facilitate the extraction of CWE geometry in milling process modeling. This includes a feature-based approach for CWE calculation in 2V2D end milling and hole milling processes, and a MAS and B-rep model based CWE calculation framework. The feature-based approaches are verified experimentally by conducting a geometric simulation on a test part requiring 2V2D end milling and hole milling processes. The MAS and B-rep model based framework is implemented with a multiagent development toolkit, J A D E , and Java. CWE extraction in the framework is tested on several workstations located in the Intranet. The computational efficiency is verified by observing the processing times with different agent configurations in the framework. The contributions of this thesis are summarized as follows: • Introduced the concept of an in-process machining feature that can be used to address the computational challenges in process modeling. Geometric Invariant Machining Features (giF) and Form Invariant Machining Features (fiF) are defined to represent engagement conditions analytically in 2VTD end milling. A giF characterizes regions of the removal volume where the CWE is identical, and a fiF defines regions where the CWE can be represented in a predictable way. The introduction of giFs and fiFs facilitates CWE extraction and representation. • Developed a feature extraction algorithm for recognizing giFs and fiFs in the removal volumes by applying volume decomposition. • Proposed an analytical approach to extract CWE from giFs and fiFs. This approach provides a closed-form solution. The robustness and computational efficiency of CWE extraction are significantly improved. • Developed a NURBS based swept volume generation method for helical toolpaths with multiple cutting tools to machine hole type features. This approach generates NURBS -139- Chapter 8. Conclusion represented boundary surfaces of the swept volume. A surface trimming procedure is applied to the self-intersected surfaces. This, approach can provide an exact solid model for the swept volume, and the swept volume is used for in-process workpiece modeling for the purposes of N C verification. • Developed an analytical approach to CWE calculation for hole milling. This approach provides a closed-form representation for ceF based on the parameters of the hole geometry and milling operation. • Proposed a MAS and B-rep model based CWE calculation framework. This framework can improve the efficiency of the CWE calculations by parallelizing computational activities. The MAS is managed to maximize the use of free resources in the framework, leading to greatly improved efficiency in the CWE calculation for the job at hand. In addition, because the computational effort is performed by distributed agents instead of on the computer at the user's location, users without a resident B-rep solid modeler can access remote CWE calculations services over the Internet or an Intranet. The proposed framework is also designed to facilitate integration of other non-B-rep based CWE calculation methods. 8.2 Future W o r k The future research work outlined in this thesis is summarized as taking the following directions: • Extending feature-based methodologies to end-mills with more complicated geometry for 2V2D end milling: The feature-based methodologies can be extended to various tool types, such as ball, cone and bull end-mills. • Exploring the possibility of introducing the concept of an in-process machining feature into 3 and 5-axis machining: The feature-based methodologies need to be extended to broader application domains, such as 3 and 5-axis machining. -140- Chapter 8. Conclusion • Expanding feature-based methodologies to different machining operations, such as turning and boring. The feature-based approach detailed in this thesis focuses on process modeling for milling process. Future work will focus on wider types of machining operations, including turning and boring. • Developing a simplified workpiece model to reduce data transfer time in the MAS: Complicated workpiece models in MAS require enormous memory and transfer time in the computer network. Research efforts are needed to develop a simplified in-process workpiece model to improve the efficiency of data exchange. • Developing and integrating new agents into the current MAS for facilitating the calculations in Virtual Machining: More time-consuming calculations are involved in Virtual Machining than the CWE extraction discussed in this research. New agents for performing these computationally intensive activities need to be designed and integrated into MAS. -141 - Bibliography 1. Abdel-Malek, K., Yeh, H.J., Geometric representation of the swept volume using Jacobian rank-deficiency conditions, Computer-Aided Design, Vol.29 No.6, 1997, pp. 457-468. 2. Abdel-Malek, K., Blackmore, D., Joy, K., Swept volumes: foundations, perspectives and applications, International Journal of Shape Modeling, 2004. 3. Altintas, Y., Spence, A.D., End milling force algorithms for CAD systems, Manufacturing Technology CIRP Annals, Vol.40, 1991, pp. 31-34. 4. Altintas, Y . , Spence, A . D . , A solid modeler based milling process simulation and planning system, Transactions of the A S M E , Journal of Engineering for Industry, Vol.116, 1994, pp. 61-69. 5. Blackmore, D., Leu, M . C . , Shih, F., Analysis and modeling of deformed swept volumes, Computer-Aided Design, 1994, Vol.26, 1994, pp. 315-326. 6. Blackmore, D., Leu, M . C . , Wang, L.P., The sweep-envelope differential equation algorithm and its application to NC machining verification, Computer-Aided Design, Vol.29 No.9, 1997, pp. 629-637. 7. Blackmore, D., Samulyak, R., Leu, M . C . , Trimming swept volumes, Computer-Aided Design, Vol.31 No.3, 1999, pp. 215-224. 8. Chang, K., Goodman, E . , A method for NC toolpath interference detection for a multiaxis milling system, A S M E Control of Manufacturing Process, D S C 28/PED 52, pp. 2330. 9. Chuang, S.H., Henderson, M.R., Three-dimensional pattern recognition using vertex classification and vertex-edge graphs, Computer-Aided Design, Vol.22 No.6, 1990, pp. 377-387. 10. Chung, Y . C . , Park, J.W., Shin, H . , Choi, B.K., Modeling the surface swept by a generalized cutter for NC Verification, Computer-Aided Design, Vol.30 No.8, 1998, pp. 581-593. 11. Coles, J., Crawford, R., Wood, K., Form feature recognition using base volume decomposition, Proceedings of A S M E Design Automation Conference, 1994, pp. 281297. 12. Corney, R.C., Graph-based feature recognition, Ph.D. Dissertation, Heriot-Watt University, 1993. 13. Cutkosky, M.R., Tenenbaum, J.M., Glicksman, J., Madefast: Collaborative Engineering over the Internet, Communications of the A C M , Vol.39 No.9,1996, pp 78-87. 14. Dave, P., Sakurai, H . , Maximal volume decomposition and its application to feature recognition, Computers in Engineering A S M E Database Symposium, Vol.29, 1995, pp. 553-568. - 142- Bibliography 15. De Floriani, L., Feature extraction from boundary models of three-dimensional objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.11 No.8, 1989, pp. 785-798. 16. DeVor, R.E., Kline, W.A., Zdeblick, W.J., A mechanistic model for the force system in end milling with application to machining airframe structures, Proceedings of the 8 North American Manufacturing Research Conference, 297-303, 1980, Rolla, Missouri, USA. 17. Drysdale, R . L . , Jerard, R.B., Schaudt, B.,Hauck, K . , Discrete simulation of NC machining, Algorithmica, Vol. 4, 1989, pp. 33-60. th 18. Falcidieno, B., Giannini, F., Automatic recognition and representation of shape-based features in a geometric modeling system. Computer Vision, Graphics, and Image Processing, Vol. 48, 1989, pp. 93-123. 19. Fussell, B.K., Modeling and adaptive force control pf end milling operations, PhD Dissertation, Dept. of Mechanical Engineering, Ohio State University, 1987. 20. Fussell, B.K., Hemmett, J.G., Jerard, R.B., Geometric and mechanistic modeling integration for five-axis milling force prediction, Proceedings of the Japan-USA Symposium on Flexible Automation. Kobe, Japan, Vol. 2, 1994, pp. 747-750. 21. Fussell, B.K., Jerard, R.B.,Hemmett, J.G., Modeling of cutting geometry andforces for 5axis sculptured surface machining, Computer-Aided Design, Vol. 35, 2003, pp. 333-346. 22. Han J., Requicha A . A . G . , Hint generation and completion for feature recognition, Proceedings of International Symposium on Automotive Technology and Automation (ISATA), 1996, pp. 89-96. 23. Han, J., Pratt, M.,Regli, W.C., Manufacturing feature recognition from solid models: A status report, IEEE Transactions on Robotics and Automation, Vol.16 No.6, 2000, pp. 782-796. 24. Hao, Q., Shen, W., Park, S. W., Lee, J. K., Zhang, Z. and Shin, B. C , An agent-based e- engineering services framework for engineering design and optimization, Proceedings of the 17th International Conference on Industrial and Engineering Application of A l and Expert Systems, 2004, Ottawa, Canada. 25. Hemmett, J.G., Fussell, B.K.,Jerard, R.B. Automatic five-axis CNC feedrate selection via discrete mechanistic, geometric, and machine model integration, Proceedings of the Sculptured Surface Machining Conference: Machining Impossible Shapes, Detroit, MI, USA, Vol.1, 1998, pp. 138-146. 26. Huang, H., Oliver, J.H., NC milling error assessment and tool path correction, Computer Graphics Proceedings, Annual Conference Services, 28(4), pp. 287-294. 27. Huang, G.Q., Huang, J., Mak, K.L., Agent-based workflow management in collaborative product development on the internet, Computer-Aided Design, Vol.32, 2003, pp. 133-144. 28. Joshi, S.B., CAD interface for automated process planning, Ph.D. Dissertation, Purdue University, 1987. -143 - Bibliography 29. Jerard, R.B., Drysdale, R.L., Geometric simulation of numerical control machining, Computers in Engineering, Vol. 2, 1988, pp. 129-136. 30. Jerard, R.B., Drysdale, R.L., Hauck, K . , Schaudt, B., Magewick, J., Methods for detecting errors in, sculptured surface machining, IEEE Computer Graphics and Applications, Vol.9 No. 1, 1989, pp. 26-39. 31. Jerard, R.B., Drysdale, R.L., Hauck, K., Schaudt, B., Approximate methods for simulation and verification of numerically controlled machining programs, The Visual Computer, Vol.5 No.6, 1989. 32. Jerard, R.B., Angleton, J.M., Drysdale, R.L., Hauck, K., Su, P., The use of surface points sets for generation, simulation, verification and automatic correction of NC machining programs, Proceedings of NSF Design and Manufacturing System Conference, 1998, SME, USA, pp. 143-148. 33. Kim, Y.S., Recognition of form features using convex decomposition, Computer-Aided Design, Vol.24 No.9, 1992, pp. 461-476. 34. Kimura, K., Development of a high performance end mill based on the analysis of chip flow generated by curved rake face, Cirp Annals, Vol.52 N o . l , 2003 pp. 57-60. 35. Kline, W.A., DeVor, R.E., The prediction of cutting forces in end milling with application to concerning cuts, International Journal of Machine Tools and Manufacture, Vol.22 N o . l , pp. 7-22. 36. Kline, W.A., DeVor, R.E., The effect of runout on cutting geometry and forces in end milling, International Journal of Machine Tool Design and Manufacture, Vol.23, No.2, pp. 123-140. 37. Kyprianou L.K., Shape classification in computer aided design, Ph.D. Dissertation, Cambridge University, 1980. 38. Lacourse, D., Alibre Design 8.0 - Take 3D mechanical design online, Cadalyst, Vol.21 No.l 1, November, 2004, pp. 36-39. 39. Li, W.D., Lu, W.F., Development of a web-based process planning optimization system, Proceedings of A S M E 2004 Design Engineering Technical Conferences and Computer in Engineering Conference, Salt lake City, Utah, September 28-October 2, 2004, DETC2004-57657. 40. Marefat, M . , Kashyap, R.L., Geometric reasoning for recognition of 3-D object features, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.12 No. 10, 1990, pp. 949-965. 41. Oliver, J.H.,Goodman, E.D., Graphical verification on N/C milling programs for sculptured surface parts, Proceedings of the A S M E Winter Annual Meeting, Anaheim, C A , Vol.21, 1986, pp. 247-263. 42. Oliver, J.H.,Goodman, E.D., Direct dimensional NC verification, Computer-Aided Design, Vol.22 N o . l , 1990, pp. 3-9. - 144- Bibliography 43. Peng, X . B . , Yip-Hoi, D., Polyhedral model based cutter workpiece engagements calculation for 2.5 and 3 axis milling, Technical Report, University of British Columbia, 2005. 44. Roth, D., Dedi, S., Ismail, F., Mann, S., Surface swept by a toroidal cutter during 5-axis machining, Computer-Aided Design, Vol. 33 N o . l , 2001, pp. 57-63. 45. Sakurai, H., Chin, C , Definition and recognition of volume features for process planning, Advances in Feature Based Manufacturing, Edited by J.J. Shah, M . Mantyla and D.S. Nau, Elsevier, 1994, pp. 65-79. 46. Sakurai, H., Gossard, D.C., Recognizing shape features in solid models, IEEE Computer Graphics and Applications, Vol.10 No.5, 1990, pp. 22-32. 47. Sambandan, K.,Wang, K . K . , Five-axis swept volumes for graphic NC simulation and verification, Proceedings of the 15th A S M E Design Engineering Technical Conferences, Montreal, QE, Canada, Vol. 19, 1989, pp. 143-150. 48. Shah, J.J., Mantyla, M . and Nau, D.S., Advances in feature based manufacturing, Elsevier, Amsterdam, Netherland, 1994. 49. Sheltami, K., Bedi, S., Ismail, F., Swept volumes of toroidal cutters using generating curves, International Journal of Machine Tools and Manufacture, Vol.38, 1998, pp. 855870. 50. Shen, W., Norrie, D. H . , Barthes, J. P., Multi-agent systems for concurrent intelligent design and manufacturing, Taylor and Francis, London, U K , 2001. 51. Shpitalni, M . , Fischer, A., CSG representation as a basis for extraction of machining features, CIRP Annals, Vol.40, 1991, pp. 157-160. 52. Spence, A.D., Altintas, Y., Kirkpatrick, D., Direct calculation of machining parameters from a solid model, Computers in Industry, Vol.14,1990, pp. 271-280. 53. Spence, A.D., Abrari, F., Elbestawi, M.A., Integrated solid modeler based solutions for machining, Computer-Aided Design, Vol.32 No.8, 2000, pp. 553-568. 54. Spence, A.D., L i , Z., Parallel processing for 2-1/2 D machining simulation, Proceedings of the 6th A C M Symposium on Solid Modeling and Applications, Ann Arbor, MI, 2001, pp. 140-148. 55. Stori, J.A., Wright, P.K., A knowledge-based system for machining operation planning in feature based open-architecture manufacturing, Proceedings of A S M E Design Engineering Technical Conferences and Computer in Engineering Conference, Irvine, C A , August 18-22, 1996, DETC1996/DFM-1286. 56. Subrahmanyam, S., Wozny, M . , Overview of automatic feature recognition techniques for computer-aided process planning, Computers in Industry, Vol.26 N o . l , 1995, pp. 121. 57. Sungurtekin, U.A., Voelcker, H.B., Graphical simulation and automatic verification of NC machining programs, Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, C A , Vol.2,1986, pp. 156-165. - 145- Bibliography 58. Takata, S., A cutting simulation system for machinability evaluation using a workpiece model, CTRP Annals, Vol.38 No.l, 1989, pp. 417-420. 59. Tlusty, J., MacNeil, P., Dynamics of cutting forces in end milling, Annals of CIRP, Vol.24 N o . l , 1975. 60. Trika S.N., Kashyap, R.L., Geometric reasoning for extraction of manufacturing features in iso-oriented polyhedrons, IEEE Transactions on Pattern Analysis and Machine Intelligence, V o l . 1 6 N o . l l , 1994, pp. 1087-1100. 61. Van Hook, T., Real-time shaded NC milling display, Computer Graphics, Vol.20 No.4, 1986, pp. 15-20. 62. Vandenbrande J.H., Requicha A . A . G . , Spatial reasoning for the automatic recognition of machinable features in solid models, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.15, 1993, pp. 1-17. 63. Vandenbrande J.H., Requicha A . A . G . , Geometric computation for the recognition of spatially interacting machinable features, Advances in Feature Based Manufacturing, Edited by J.J. Shah, M . Mantyla and D.S. Nau, Elsevier, 1994, pp. 83-106. 64. Voelcker, H.B., Hunt, W.A., Role of solid modelling in machining-process modelling and NC verification, S A E Preprints, Vol. 810195, 1981. 65. Wang, W.P., Wang, K . K . , Real-time verification of multiaxis NC programs with raster graphics, Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, C A , Vol.2,1986, pp. 166-171. 66. Wang Y . , Ajoku, P.N., Nnaji, B.O., Distributed data access control for lean product information sharing in collaborative design, Proceedings of A S M E 2004 Design Engineering Technical Conferences and Computer in Engineering Conference, Salt lake City, Utah, September 28-October 2, 2004, DETC2004-57748. 67. Wang, L . , Shen, W., Xie, H . , Neelamkavil, J., Pardasani, A . , Collaborative conceptual design: a state-of-the-art survey, Computer-Aided Design, Vol.34 No. 13, 2002, pp. 981996. 68. Weinert, K., Du, S., Damm, P., Stautner, M . , Swept volume generation for the simulation of machining processes, International Journal of Machine Tools and Manufacture, Vol.44, 2004, pp. 617-628. 69. Woo, T., Feature extraction by volume decomposition, Proceedings of Conference C A D / C A M Technology in Mechanical Engineering, 1982. 70. Yip-Hoi, D., Huang, X . , Cutter engagement feature extraction from solid models for end milling, Proceedings of IMECE: A S M E International Mechanical Engineering Congress Novermber 13-19, 2004, Anaheim, California, USA. 71. http://www.fipa.org 72. http://jade.tilab.com -146- Appendix A Entry and Exit Position Calculations A.1 Linear Tool Motion/Linear Edge Figure A - l illustrates a cutter with radius r moving along a linear tool motion P P for s e cutting a linear edge P1P2. The entry (P tty) and exit (P it) position need to be determined en ex based on these parameters. Points P (x*, y ), Pe(*e> ye), Pi(*/, yi) and P2CK2, yi) are shown in s s Figure A - l . Figure A - l : Linear Tool Motion/Linear Edge The equation of a circle with center at Po and radius r is given by |P-P | =r " (A.1) 0 The equation of a line P P is given by s e P = P,+ (P -P .) W e (A.2) s To represent a circle whose center is located on the line P P , replace Po in Eq. (A.1) with P s e in Eq. (A.2). The equation of the circle is represented in implicit form as: [x-{x +u(x -x ))] 2 t e s +b-(y +u(y -yM=r 2 s e (A.3) The equation of a line P1P2 in parametric form is given by (x = x v{x -x ) i+ \y = 2 { ( y +v(y -y,) l 2 Substituting Eq. (A.4) into Eq. (A.3), -147- A 4 ) Appendix A. Entry and Exit Position Calculations [fa -*,)+fa-x,)v-{x - * > ] +[(y,-y )+(y 2 -y,)v-{y -y )uf h Y =y -y 2 e s e = r (A.5) 2 s Introducing the following expressions X =xi-x Js X i=x -xi, X =x -x , Y =y y , s> 2 2 es e s ls r Y =y -y s 2] 2 es e (A.6) s Substituting these expressions into Eq. (A.5), (X + X v - X uf u 2X + (Y + F v - Y uf = r (A.7) 2 es u 21 es Expanding Eq. (A.7), {^+Y ]y-2u[xJX X ,v) e u+ + 2 Y {Y Y v)] + es u+ 2l (X X v) (Y Y v) -r =0 2 Xs+ 2X 2 + u+ 2 2X The roots of Eq. (A.8) is given by the quadratic formula u= -b±ylb -4ac (A.9) 2a where: b= c -2[X (X +X v) Y (Y Y v)] es = u 2l + es u+ 2] (X X v) {Y Y v) -r 2 u+ 2l 2 + u+ 2 2l To determine the entry and exit positions for cutting the linear edge P1P2, the following three cutter positions along the linear tool motion P P need to be calculated. s e Position 1: The cutter position where the cutter has tangential contact with the linear edge. To calculate this position, only one root of Eq. (A.8) exists. In other words, the following equation should be satisfied: A = b -4ac 2 = 4'[X.(Xu ^ v) YjY Y v)] -A_X^Y_\%X X vf 2 2X + u+ 2X u+ (Y lx + = 4 r (x Y )^AYu+Y v)-Y Xx X v)) } 2 2 2 2 s+ e 2X = 4 } (x Y )-((X Y -X Y )y 2 2 u+ 2i (XJ -X X )) ] 2 s+ es 2l 2X es 2 + Xs =0 148- Xs Xs Y v) -r } 2 U + 2X 2 Appendix A. Entry and Exit Position Calculations The above equation can be rewritten as: _(X Y -X Yj±^Xl Yl v es ls u + ( XY es A 1 Q ) -X Y 2i 2l es The parameter v is calculated using Eq. (A. 10). If v e [0, 1] then there is a contact point P t within the linear edge P1P2, otherwise, the cutter does not have a tangential contact with P1P2. If the contact point P exists, the parameter of the cutter location is calculated by t 11, = — ' 2a (A.ll) Position 2: The cutter position where the cutter intersects with point Pi. To calculate this position, set v=0 in Eq. (A. 9), and choose minimum root. The parameter of the cutter position is calculated by b-^b ~4ac 1 (A. 12) 2a where: b= -2(X X +Y Y ) es u es u Position 3: The cutter position where the cutter intersects point P . 2 To calculate this position, set v=l in Eq. (A.9), and choose minimum root. The parameter of the cutter position is calculated by b-4b -Aac (A. 13) 2 2a where: a =X es b= +Y es -2[X„(X +X )+Y„{Y +Y )] u 2l u 2l - 149- Appendix A. Entry and Exit Position Calculations {X +X ) +(Y +Y J-r c= 2 u 2] 2 u 2 Based on the positions calculated using the above equations ( « / , u and u_, the 2 parameters of the entry and exit positions (u , u ) can be determined by following two entry exil rules: Rule 1: If the cutter has tangential contact with the edge, then Uentry u, and u = exil = max(w/, ui) Rule 2: If the cutter does not have tangential contact with the edge, then Uentry min(w/, u ) and u , = max(w/, u ) = 2 exi 2 A.2 Linear Tool Motion/Circular Edge Figure A-2 illustrates a cutter with radius r moving along a linear tool motion P P for s e cutting a circular edge P1P2 with center at O(xo, yo) and radius R. Figure A-2: Linear Tool Motion/Circular Edge The equation of a circle with center at a line P P and radius r is given by s [JC-(x s + u{x -x ))Y e s +[y-(x, + "(y e e -y )ff s = r l (A.14) The equation of arc P1P2 in parametric form is given by (A. 15) where 6 e [ft, 6 \ Substituting Eq. (A. 15) into Eq. (A.14), 2 -150- Appendix A. Entry and Exit Position Calculations K*o -x )+Rcos0-(x -x )uf s e + [(y s r -y )+Rsin0-(y 0 s e 2 (A.16) Introducing the following expressions (A.17) Xos xo-x , X =x -x , Yo =yo-y , Y =y -y = s es e s s s es e s Substituting these expressions into Eq. (A. 16), (X + R cos 0 - X uf 0s (A. 18) + (Y + R sin 0 - Y uf = r 2 es 0s es Expanding Eq. (A. 18), [Xl•+ Yl\ -2[X„{X .+ 2 + (X +Rcos0) 0s Rcos0) + Y {Y + 0s 2 es + (Y +Rsm0) -r 2 0s Rsin^ 0s (A.19) =0 2 The roots of Eq. (A.8) is given by the quadratic formula -b±ylb -4ac 2 u (A.20) 2a where: a = Xl+YZ b = -2[X {X es c = (X 0s + R cos 0) + Y {Y + R sin 0)} es Qs + R cos 0f + {Y + R sin 0f - r 2 0s 0s Position 1: The cutter position where the cutter has a tangential contact with the circular edge. Similar to the calculations described in Section A.1, the following equation should be satisfied: A = /3 -Aac 2 = 4fc (4 Rcos0)+Y (Y s = = :+ es +Rsm0)] -4{x 2 Os +Y ] %X 2 s e 0s +Rcos0f 4[r (xl Yl)-(X (Y Rsin0)-Y (X Rcos0)) ] 2 2 + es Os+ es Os+ {r {x Yl)-((X Y -X Yj X Rsm0-Y Rcos0f] 2 2 s+ es 0s Os + = 0 The above equation can be rewritten as: -151 - es es +{Y Rsm0) -r ] 2 Os+ 2 Appendix A. Entry and Exit Position Calculations '(X„Y -X _Y„)-r (xl+Y__j 2 0 = ±cos" 0t 0 -tan -i Y es (A.21) R^Xl, + Y 2 If 0 e [0i, 0 ] then the parameter of this position is calculated by 2 u, = -b (A.22) 2a Position 2: The cutter position where the cutter intersects with point Pi. To calculate this position, set 0=0i in Eq. (A.20), and choose minimum root. The parameter of the cutter position is calculated by -b-y/b -4ac 2 (A.23) 2a where: a= X +Yes 2 2 es b^^ixJX^+R^^+Y^+Rs^)] c = {X + R cos 0, ) + (F . + R sin 0, ) 2 2 0s 0i - r 2 Position 3: The cutter position where the cutter intersects point P2. To calculate this position, set 0=0 in Eq. (A.20), and choose minimum root. The parameter 2 of the cutter position is calculated by -b-ylb -4ac 2 (A.24) 2a where: a=X + Y 2 2 S b = -2[X es c = {X (X 0s + R cos 9 ) + Y (Y + R sin 0 )] 2 + Rcos0 ) 2 0s 2 es +(Y + 0s 0s 2 Rsm0 ) -r 2 2 -152- 2 Appendix A. Entry and Exit Position Calculations Based on the positions calculated using the above equations (w/, U2 and u ), the t parameters of the entry and exit positions (u tiy, Uextt) en can be determined by following the same rules as described in Section A.1. A.3 Circular Tool Motion/Linear Edge Figure A-3 illustrates a cutter with radius r moving along a circular tool motion P P s with center at O(x , yo) and radius R for cutting a linear edge P1P2. 0 Figure A-3: Circular Tool Motion/Linear Edge The equation of a circle with center at the circular tool motion P P and radius r is given by s [JC e (A.25) - (x + R cos (f)Y + \y - {y + R sin <p)] = r 2 0 2 0 where < > / e [<f> , (j) ]. The equation of a line P i P in parametric form is given by s e 2 (A.26) Substituting Eq. (A.26) into Eq. (A.25), [(*, - x ) + (x - x, )v - R cos 0 2 + [(y, - y ) + (y - y )v - R sin <ff = r 2 0 2 x (A.27) Introducing the following expressions Xio=xi-x , X i=x -xi, 0 2 2 Y =yi-yo, Y =y -yi ]0 21 (A.28) 2 Substituting these expressions into Eq. (A.27), (X + X v - R cos^) + (7,o + Y v - R smtf) = r 2 w 2l 2 2i -153- 2 (A.29) e Appendix A. Entry and Exit Position Calculations Expanding Eq. (A.29), (X xo +X v)cos^ + (7, + 7 v)sin^ = - ^ 21 0 Dividing Eq. (A.30) by J(X + X v) 0,„+* ,v) 2 V(z +x ,v) +(y +r v) 2 2 xo 21 ^ (Y Y v) + ]0+ 2 2] V ^ i o + ^ i ^ + ^ o + ^ i v ) 2l 10 (A.30) ' 2 1 2 2X ^ c Q S ^ V + (Y + F v) . 2 W 10 ' 2 1 21 = (X, 0 + X 2 1 v) 2 + (y, 0 + F ,v) 2 2 /? -/2 + 2/? (x +x v) (r +y v) , 2 2 v l0 2l l0 + 21 (A.31) Introducing angle a as: sin« = X v) +(Y Y v) 2 + X0+ (X, cosa = ,, , 2 2X 0 + 2X X v) , 2 (A.32) 2{ 2 l V(x +x v) +(r + r 10 Yu>+Y v" 21 10 21 v) : Substituting Eq. (A.32) into Eq. (A.31), (A.33) The angle <p can be calculation using Eq. (A.34). \x X v) (Y Y v) +R -r 2 ' = a± cos 1 x0+ 2X 2 + x0+ 2 '21v)Y +(r 2Rj{X X v) +(Y v) 10 + r v) 2 2 x0+ Y +Y v w = tan" 2 2x ' 2l ±cos [x +X v_ x0 2l 2X x0+ 2 j 2I (A.34) \x X v) +{Y +Y v) +R -r x0+ 1 2 2x 2 X0 2X 2 2 : 2X 2R_l{X +X v) +(Y +Y vY i0 2 2] 10 2l Position 1: The cutter position where the cutter has a tangential contact with the linear edg To calculate this position, the following equation should be satisfied: (X X v) +{Y Y v) R -r 2 ]0+ 2 2x X0+ 2X 2 2 + _ ] 2Rj(X X v) (Y Y v) 2 x0+ 2l 2 + x0+ 2X Rewriting Eq. (A.35), -154- ( A 3 5 ) 2 2 Appendix A. Entry and Exit Position Calculations (X xo + X vf + (Y + Y vf 2X l0 R -r 2 2l + = 2R^{X 2 + X v) 2 X0 2X + {Y +7 V) X0 (A.36) 2 21 Solving Eq.(A.36), the roots of Eq. (A.36) can be calculated using Eq. (A.37). - (X X X0 Y Y )±^R±r) (x + 2X 2 XQ v= Y )-(X Y -X Y f 2 2 2X+ 2X 2X X0 x0 2X (A.37) X\ + Y x 2X If v e [0, 1] then there is a contact point within the linear edge P1P2, and the parameter of the cutter location fa can be obtained by substituting Eq. (A.37) into Eq. (A.34). Otherwise, the cutter does not have a tangent contact with P1P2. Position 2: The cutter position where the cutter intersects with point Pi. To calculate this position, set v=0 in Eq. (A.34), and choose minimum root. The parameter of the cutter position is calculated by X +Y +R -r ^ r MO fa = min tan" 2 2 2 2 (A.38) 0 ±cos 2R^X +Y 2 0 X 2 10 ; Position 3: The cutter position where the cutter intersects point P . 2 To calculate this position, set v=l in Eq. (A.34), and choose minimum root. The parameter of the cutter position is calculated by fa = min tan -1 f y y + -MO ^ *2\ yX x0 +X 2X ^ f j ± c o s -1 (*,o + X*) 2 V + (7 o+^ ) +^-^ 2 1 1 2 ^ (A.39) 2RJ{X +X ) +{Y +Y ) 2 X0 2X 2 X0 2X Based on the positions calculated using the above equations (fa, fa and fa), the parameters of the entry and exit positions (fa y, faxit) ntr can be determined by following the same rules as described in Section A.1. A.4 Circular Tool Motion/Circular Edge Figure A-4 illustrates a cutter with radius r moving along a circular tool motion P P s e with center at O (x , yo) and radius R for cutting a linear edge P1P2 with center at Oi(x/, yi) 0 0 0 and radius/?/ -155 - Appendix A. Entry and Exit Position Calculations Figure A-4: Circular Tool Motion/Circular Edge The equation of a circle with center at the circular tool motion P P and radius r is given by s [x-{x +R cosfi + [y - {y + R sin fi\ = r 2 0 e 2 0 Q (A.40) 2 0 where <p e [fa, fa]. The equation of arc P1P2 in parametric form is given by \x = x + i?, cos 0 (A.41) x [y - y\ + ^ 1 s m ^ where 0 e [0,, 6 \ Substituting Eq. (A.41) into Eq. (A.40), 2 [(x, - x ) + /?, cos 0 - R cos fi + [(v, - y ) + R sin 0 - R sin fi = r 2 0 0 0 } 0 (A.42) Introducing the following expressions Xio=xi-xo, Y, =yi-yo (A.43) 0 Substituting these expressions into Eq. (A.42), {X w + fl, cos 0 - R cos fi +(Y + fl, sin 0 - R sin fi = r 0 l0 (A.44) 2 0 Expanding Eq. (A.44), 1 {X +R ]0 ~\ , A, „ • „\ • , (Xo+iJ.cos^y+^o+^.sin^+^o-r cos0)cos</> + {Y +R sintfjsin^-*-* — ^ 2R 5 ] w ! 1 l 0 (A.45) Dividing Eq. (A.45) by ^j(X +R w cos0) +(F 2 l 156 + R, sin0) 2 10 2 Appendix A. Entry and Exit Position Calculations (x + R, cosfl) + (Y, + R sing) + % - r 2 fa + ^sinfl) rCOS0 + " ^sin^ = 2 ]n 0 1 I (A.46) Introducing angle a as: JY +R l0 sin a sin0) x ^{X R cos9) {Y R smef J j o ± R ^ \s n / yX +. i?, COSg 2 ]0+ l + (Z / cosa - l0+ ] r» v iQ + fr + tf, sing) x (A.47) 1 X ^(X +R cos0f xo i 5 +R cosO) 1 0 = a /O \ 2 0 Substituting Eq. (A.47) into Eq. (A.46), (X + R, cos0) + fr + R sm0) 2 m cos 2i? J{X +R, 0 ]0 +R -r 2 0 2 x 2 (A.48) 0 cos g) + fr + sin g) 2 0 2 The angle ^can be calculated using Eq. (A.49). + fl, cosg) + fr + i?, sin^) + R - r 2 (j) - a ± cos 2R j{Xio + 2 cosg) + fr + ( 7 + sing ^ o cosg 10 sin^) 2 0 = tan" 2 2 0 1 0 2 (A.49) (AT.Q + R cosg) + (r, + i?, sing) + R - r 2 2 x ±cos 2 0 2R J(X 0 : Q + R, cos 0) + fr + R sin g) 2 W 0 2 l Position 1: The cutter position where the cutter has a tangential contact with the circular edge. To calculate this position, the following equation should be satisfied: (X w + cos 0) + fr „ + R, sin 0) + R - r 2 2i? V(X + 0 10 2 cosg) + 2 2 + fro 2 sing) _ (A.50) ] 2 Rewriting Eq. (A.50), (i? ±,) -(x o 2 X i0 cosg + F sing = 10 2 n r )-i? 2 + 2 1 27?, Solving Eq.(A.51), the roots can be calculated using Eq. (A.52). -157- (A.51) Appendix A. Entry and Exit Position Calculations 0 = tan X ±cos '{R ±r) -(x \+Y )-Rj 2 2 a (A.52) x 1 2R _IX + Y 2 10; X 0 x If 6 e [ft,ft]then there is a contact point within the circular edge P1P2, and the parameter o f the cutter locationfacan be obtained by substituting Eq. (A.52) into E q . (A.49). Otherwise, the cutter does not have a tangent contact with P1P2. Position 2: The cutter position where the cutter intersects with point P i . To calculate this position, set ft=ft i n Eq. (A.49), and choose minimum root. The parameter of the cutter position is calculated by ( ( Y +R sin0 " ]0 = min tan"' 1^,0 V y$, l + * , i / + cos (A-.Q + R cos 0 f+(Y l X 2R _'(X C O S 0 , , 0 + R sin 0, ) + R - r in 2 2 X + /?, cosfl,) +{Y +R, sin^,) 2 10 (A.53) : 0 2 ]0 Position 3: The cutter position where the cutter intersects point P . 2 To calculate this position, set 0=ft i n Eq. (A.49), and choose minimum root. The parameter of the cutter position is calculated by Y +R w _ = min tan" 1 l X +R 2 K l0 l sin 6 ^ 2 cose 2) + cos~ W +(r cosdj (X +R 1 2Rj(X i0 i0 +R cosej x sint9 ) + i? 2 +R X +{Y L0 AA -r 2 : 2 (A.54) +R sint? ) 2 X 2 Based on the positions calculated using the above equations (fa, fa andfa),the parameters o f the entry and exit positions (fa„ , fa ) can be determined by following the lry same rules as described in Section A . l . -158- xil Appendix B Helicoid Equation (5.6) Figure B - l illustrates a helicoid with a semi-circle profile curve and its parameters. 4Z |Z Figure B - l : A Helicod The equation of the helicoid in parametric form is x = (R - r )cos 0 + r cos <p (B.l) y = (R- r)sin 0 + r sin <f> In where 0 e [0, 2n\ and <f> e [-n, 0]. Combine x and y coordinate expressions as follows: [x-{R-r)cos0f+[y-{R-r)sm0] =r 2 (B.2) 2 Rewriting Eq. (B.2), x +y +{R-r) -r^_ 2 ;ccos0 + ,ysin# =• 2 2 ( Dividing Eq. (B.3) by Jx 2{R-r) 2 +y 2 -159- B 3 ) Appendix B. Helicoid Equation (5.6) 2 2 ( _ )2_ 2 x sin 6 = rCOS0 + +y + R r r 2(R-r)yjx (B.4) +y 2 2 Introducing angle a in Eq. (B.5) as follows: sin y <2 = V a = tan" (B.5) cos a = Substituting Eq. (B.5) into Eq. (B.4), x +y +(R-r) -r cos a cos 6 + sin a sin 9 = • 2(R- yjx +y 2 2 2 2 2 (B.6) 2 r Rewriting Eq. (B.6), {o-a)= l r ?R r x2+yi+ cosi ri (B.7) 2(R-r)y]x +y 2 2 The angle 6* can be calculation using Eq. (B.8). r 2 x 0 - a + cos V \x) {R-r) -r ^ 2 + 2 (B.8) x f + 2 2{R-ryJx +y 2 V = tan 2 + y +y {R-r) -r ^ 2 2 2 2 + COS 2{R-ryJx' +y 2 2 Substituting Eq. (B.8) into the z coordinate expression in Eq. (B.l), the equation of the helicoid in explicit form can be represented as follows: 2n tan V + -1 COS x +y +(R-rf 2 -r 2 : 2(R-r\lx +y 2 (B.9) 2 - 160- JJ Appendix C Intersection and Connection Point Calculation Equation (5.10) As shown in Figure C - l , a cutting tool rotates angle 9 along a helical toolpath from its initial position O i to its final position O2. The intersection and connection point can be determined by calculating the intersection point between Circle O i (initial position) and Circle O2 (final positon). x Figure C - l : Intersection and Connection Point Calculation The equation of Circle 0 2 with center at ((R-r)cos9, (R-r)sin9) and radius r in parametric form is \x = (R-r)cos9+ rcos > ^ r ^ The equation of Circle O i with center at ((R-r), 0) is (C.2) [ -(R-rf y =r> 2 x + Substituting Eq. (C-l) into Eq. (C-2), [(i?-r)cos# + rcos (j)-(R-r)Y +[(R-r)sin9 + rsm<_] = r 2 2 (C.3) Rewriting Eq. (C.3), r[sin 9 sin (f> - (l - cos 0)cos </>] = {R - r){\ - cos 9) -161 - (CA) Appendix C. Intersection and Connection Point Calculation Equation (5.10) Dividing Eq. (C.4) by r j 2 ( l - cos 6), l + cos<9 . . fl^cos? R-r sin^cos^ = 1-cosfl ( v C 5 ) ; A _ . . |i+cos^ li-cos^ . _ ., e , . e . . Replacing J and J m E q . (C.5) with cos— and sin— respectively, + cos—sin^-sin —cos^ = 2 2 sin— r (C.6) 2 Rewriting Eq. (C.6), . (. 6\ R-r sin </>-- \ = 2) y .6 sin- r (C.7) 2 From Eq. (C.7), two intersection points are calculated as follows: , 6 . JR-r . 6\ <j) = ~ + sm 2 \ . 6 0 sin— r . JR-r (j) = — + 7t-sm 2 ,_ , (C.8) 2) . 0\ sin— \ r (C.9) 2) Eq. (C.8) is for calculating intersection point Pi (see Figure C - l ) , and Eq. (C.9) is for P . 2 Since P is within the front semi-circle of Circle 0 , Eq. (C.9) is used to calculate the 2 2 intersection and connection points as Eq. (5.10) in Chapter 5. -162- Appendix D Silhouette Curves of End-Mills D . l Silhouette Curves of a Flat End-Mill Figure D - l illustrates a cylinder representing a flat end-mill and its silhouette curves. Given the center O(xo, yo, zo) of this cylindrical surface, radius R and height H, the control points of the silhouette curves are listed in Table D - l . P, C=1) (i=D P, (1=1) P n=4, k=3 n=4, k=3 Knot Vector: [ 0 0 0 % % 1 1 1 ] Knot Vector: [ 0 0 0 % % 1 1 1 ] (1 • (ft=i) P, -o O a. —( C— n=1, k=2 n=1, k=2 Knot Vector: [ 0 0 1 1] KnotVector:[0 01 1 ] Helix Angle Figure D - l : Silhouette Curves for a Flat End-Mill Curve # " ,„ Control Points Type Point # i 2 Arc Arc , X '.' . Y -- , z Po x +R yo zo+H P. xo-R yo zo+H Q. x +R 0 yo-R zo+H Q 2 Xo yo-R zo+H Q 3 Xo-R yo-R zo+H P 3 x +R yo zo P 2 xo-R yo z Q. Xo+R yo-R Zo Q Xo yo-R zo 2 0 0 -163 - 0 - - Appendix D. Silhouette Curves of End-Mills xo-R yo-R Po xo+R yo zo+H P xo+R yo zo Pi Xo-R yo zo+H P xo-R yo Q Line 3 Line 4 3 3 2 z 0 z 0 Table D-l: Control Points for Silhouette Curves of a Flat End-Mill D.2 Silhouette Curves of a Conical End-Mill A conical end-mill with center at O(xo, yo, zo), radius R, height H and cone height h and its silhouette curves are illustrated in Figure D-2. The control points for each silhouette curve are listed in Table D-2. Q (/> = c o s % ) Q (/, = c o s % ) (1 0 P C=1) (/i=1)P. 3 n=4, k=3 K n o t V e c t o r : [ 0 0 0 "A / 1 1 1 ] 1 d=i) 2 (ft=i) P 2 -o O— K n o t V e c t o r : [ 0 0 0 VS V i 1 1 1 ] (i=D (1=1, O - n=1, k=2 n=1, k=2 Knot Vector: Helix Angle I 7 I (1=0.707)(1=1) Q 3 Knot Vector: [0011] (1=0.707) _ g j ^ Q 1 (i=D (1=D -o O P„(1=D (1=1) P . n=4, fc=3 Knot Vector: [ 0 0 0 V % 1 1 1 ] n=1, k=2 Knot Vector: [0011] (1=1) (1=1, P4 -o O— n=1, k=2 Knot Vector: 2 Figure D-2: Silhouette Curves for a Conical End-Mill - 164- [0011] [0011] || Appendix D. Silhouette Curves of End-Mills • 1 Control Points Type Curve # -. Arc Z Point # P 2 P 3 Qi P 2 Arc 6 Ps Qi 3 4 5 6 7 Line Line Line Line Arc xo-R Yo if if if t t t xo+R Yo * * * t t t P. xo-R yo zo+H P xo-R yo z Po xo+R yo zo+H P xo+R yo zo 6 P * * * 3 P Xo yo z -h 4 P 4 Xo yo z -h if * * Po Xo+R yo zo+H Pi xo-R yo zo+H Qi xo+R yo-R zo+H Xo yo-R zo+H Xo-R yo-R zo+H 2 P 5 Q 2 Q 3 j_ 0 0 0 * see D. 2.1 for*ietails. t see D.2.2 for details. Table D-2: Control Points for Silhouette Curves of a Conical End-Mill D.2.1 Calculating P and P 3 5 A conical end-mill with center at O(x , yo, z ), radius R, height Hand cone height h 0 0 its silhouette curves are illustrated in Figure D-3. The control points for each silhouette a are listed in Table D-2. -165- Appendix D. Silhouette Curves of End-Mills Figure D-3: Calculating P and P 3 5 The perspective direction P is given as: (D.l) P(0, cos a, sin a) The normal n of the conical surface at angle 9 can be calculated as: ( nl cos 9, sin 0,— R (D.2) V The silhouette curve is composed of the points on the surface whose normal n are perpendicular to the perspective direction P. This can be represented in Eq. (D.3). P»n = 0 (D.3) Substituting Eq. (D.l) and (D.2) into (D.3), cos a sin 9 - sin a R (D.4) W+^ =0 2 - 166- Appendix D. Silhouette Curves of End-Mills Rewriting Eq. (D.4), i?tana sin0 (D.5) jR +h 2 2 The cosflcan be obtained from Eq. (D.5) as: i? (l-tan a:)+/? 2 cos 0 = ±Vl-sin 6> = ±, 2 2 2 (D.6) R +h 2 2 Given the center point O(x , yo, z ) of the conical end mill, P and P can be calculated easily 0 0 3 5 by using Eq. (D.5) and Eq (D.6), P (x -Rcos0,y 3 0 + o Rsin0,z ) o )j? (l-tan a:)+ft 2 =P P (jt 5 *°~ i R R 0 2 +Rcos0,y 2 + =P 0 '^VFTF' 2 o /i? (l-tan o;)+^ 2 +R, 2 +Rsin0,z ) o x h (D.7) R tana 2 2 (D.8) i? tang 2 2 D.2.2 Calculating Control Point Qo for Silhouette Curve 1 and 2 Figure D-4 illustrates the calculation of the middle control point Qo for Curve 1 and Curve2. Qi=P , Q =P3 in Curvel, Qi=P , Q =P6 in Curve2. O is the center position of the 2 2 5 2 end-mill. The angle 0, P and P are calculated in D.2.1 (see Eq. (D.5)-(D.8)), and P and P 3 5 2 are calculated in Table D-2. Figure D-4: Calculating the Control Point Q -167- 0 6 Appendix D. Silhouette Curves of End-Mills The unit vector of v can be calculated by adding O Q , and O Q OQ 1 + OQ OQ,+OQ 2 (D 2 2 The vector v = O Q „ can be calculated by multiplying the length of O Q v = OQ OQ, 0 e O Q , + O Q cos- 0 (oQ,+OQ ) 2 : Since O is given, the control point Q can be calculated using Eq. (D.10). 0 -168- (D Appendix E The Sat Files of an Envelope Surface A swept surface generated by sweeping a circle along a helical curve using both the skinning and exact NURBS representation methods is shown in Figure E - l . The parameters of the profile and path curves are list in Table E - l . The sat files of this surface generated by these two different methods are listed in E . l and E.2. The sat file generated by the skinning method has size 20KB, and the file generated by the exact NURBS representation method has size 3KB. It can be seen that the swept surface by the exact N U R B S representation method has a more compact data structures than the skinning method. Profile Curve Path Curve (Helix) Radius Pitch Start Angle End Angle Radius [mm] [mm] [°] [°] [mm] 30 80 0 90 10 Table E - l : Control Points for Silhouette Curves of a Conical End-Mill Figure E - l : A Swept Surface -169- Appendix E. The Sat Files of an Envelope Surface E . l The Sat File by Exact NURBS Representation Method 1000 0 1 0 24 ACIS Test Harness - 10.0 12 ACIS 10.0 N T 24 Thu Apr 07 21:34:53 2005 1 9.9999999999999995e-007 le-010 face $-1 -1 $-1 $-1 $1 $-1 $-1 $2 forward single F F # loop $-1 -1 $-1 $-1 $3 $0 F unknown # spline-surface $-1 -1 $-1 forward { exactsur full nurbs 2 2 both open closed none none 2 5 0 2 12 0 2 0.25 2 0.5 2 0.75 2 1 2 4000 1 40-40 -10 0.70709999999999995 0 -40 -20 1 40 10 0 0.70709999999999995 50-30-10 0.5 10 -40 -20 0.70709999999999995 30 10 0 1 40-20 -10 0.70709999999999995 10-30-20 1 20 10 0 0.70709999999999995 30-10-10 0.5 10 -20 -20 0.70709999999999995 20 0 0 1 20-20-10 0.70709999999999995 0 -20 -20 1 20-10 0 0.70709999999999995 10-30-10 0.5 -10-20 -20 0.70709999999999995 30-100 1 20-40 -10 0.70709999999999995 -10-30-20 1 40 -10 0 0.70709999999999995 30-50-10 0.5 -10-40 -20 0.70709999999999995 4000 1 40-40 -10 0.70709999999999995 0 -40 -20 1 0 0 0 0 3 0.25 0.5 0.75 0 0 F1F0F1F0}IIII# coedge $-1 -1 $-1 $4 $5 $6 $7 forward $1 $8 # coedge $-1 -1 $-1 $6 $3 $-1 $9 forward $1 $10 # coedge $-1 -1 $-1 $3 $6 $-1 $11 reversed $1 $12 # coedge $-1 -1 $-1 $5 $4 $3 $7 reversed $1 $13 # edge $-1 -1 $-1 $14 0 $15 1 $3 $16 forward @7 unknown F # pcurve$-l -1 $-1 1 $16 0 0 # edge $-1 -1 $-1 $15 0 $15 1 $4 $17 forward @7 unknown F # pcurve$-l -1 $-1 1 $17 0 0 # edge $-1 -1 $-1 $14 0 $14 1 $5 $18 forward @7 unknown F # pcurve $-1 -1 $-1 -1 $18 0 0# - 170- Appendix E. The Sat Files of an Envelope Surface pcurve $-1 -1 $-1 -1 $160 1 # vertex $-1 -1 $-1 $7 $19 # vertex $-1 -1 $-1 $7 $20 # intcurve-curve $-1 -1 $-1 forward { parcur full nurbs 2 open 2 0 2 12 40 0 0 1 40-40-10 0.70709999999999995 0 -40 -20 1 0 spline forward { ref 0 } 1111 nullsurface nubs 1 open 2 0 111 00 1 0 nullbs II 0 0 0 surfl } 11 # intcurve-curve $-1 -1 $-1 forward { parcur full nurbs 2 closed 5 0 2 0.25 2 0.5 2 0.75 2 1 2 0 -40 -20 1 10 -40 -20 0.70709999999999995 10 -30 -20 1 10 -20 -20 0.70709999999999995 0 -20 -20 1 -10-20 -20 0.70709999999999995 -10-30-20 1 -10 -40 -20 0.70709999999999995 0 -40 -20 1 0 spline forward { ref 0 } 1111 nullsurface nubs 1 closed 2 0 111 1 0 1 1 nullbs 11 3 0.25 0.5 0.75 0 0 surfl } 11 # intcurve-curve $-1 -1 $-1 forward { parcur full nurbs 2 closed 5 0 2 0.25 2 0.5 2 0.75 2 1 2 4000 1 40 10 0 0.70709999999999995 30 10 0 1 20 10 0 0.70709999999999995 20 0 0 1 20 -10 0 0.70709999999999995 - 171 - Appendix E. The Sat Files of an Envelope Surface 20 -10 0 0.70709999999999995 30-10 0 1 40 -10 0 0.70709999999999995 40 0 0 1 0 spline forward { ref 0 } 1111 nullsurface nubs 1 closed 2 0 111 00 01 nullbs II 3 0.25 0.5 0.75 0 0 surfl } 11 # point $-1 -1 $-1 4 0 0 0 # point $-1 -1 $-1 0 -40 -20 # End-of-ACIS-data Appendix E. The Sat Files of an Envelope Surface E.2 The Sat File by Skinning Method 1200 0 1 0 37 SolidWorks(2004231)-Sat-Convertor-2.0 12 ACIS 13.0 N T 24 Thu Apr 07 13:06:10 2005 1 9.9999999999999995e-007 le-010 -0 body$l -1 -1 $-1 $2 $-1 $-1 F # •1 name_attrib-gen-attrib $-1 -1 $-1 $-1 $0 keep keepkept ignore copy @5 Part2 # -2 lump $3-1 -1 $-1 $-1 $ 4 $ 0 F # -3 rgb_color-st-attrib $-1 -1 $-1 $-1 $2 0.75294117647058822 0.75294117647058822 0.75294117647058822 # -4 shell $-1 -1 -I $-1 $-1 $-1 $5 $-1 $2 F # -5 face $-1 -1 -1 $-1 $6 $7 $4 $-1 $8 reversed single F F # 6 face $-1 -1 -1 $-1 $9 $10 $4 $-1 $11 forward single F F # -7 loop $-1 -1 -1 $-1 $-1 $12 $5 F unknown # -8 spline-surface $-1 -1 -1 $-1 forward { exactsur full nurbs 3 3 both open open none none 2 5 0.5 3 1 3 0 3 0.071428571428571425 3 0.14285714285714285 3 0.21428571428571427 3 0.250000000000000613 19.999999999999996 1.2246467991473531e-015 0 1 19.999999999999993 -19.999999999999996 0 0.33333333333333331 39.999999999999993 -19.999999999999996 0 0.33333333333333331 40 0 0 1 19.999999999999996 -3.0173804715261601 -1.4164293882669949 0.9832852747878823 16.98261952847383 -23.017380471526153 -1.4164293882669949 0.32776175826262749 36.982619528473819 -26.034760943052316 -1.4164293882669949 0.32776175826262749 40 -6.0347609430523219 -1.4164293882669949 0.9832852747878823 19.32856967937445 -5.9591089148893666 -2.86928489744728 0.9832852747878823 13.369460764485078 -25.287678594263813 -2.8692848974472795 0.32776175826262749 32.69803044385953 -31.24678750915319 -2.8692848974472795 0.32776175826262749 38.657139358748914 -11.918217829778738 -2.86928489744728 0.9832852747878823 18.019377358048377 -8.6776747823511595 -4.2857142857142749 1 9.3417025756972176 -26.697052140399538 -4.2857142857142749 0.33333333333333331 27.361079933745593 -35.374726922750703 -4.2857142857142749 0.33333333333333331 36.038754716096761 -17.355349564702326-4.2857142857142749 1 16.710185036722311 -11.396240649812952 -5.7021436739812703 0.9832852747878823 5.3139443869093537 -28.10642568653526 -5.7021436739812703 0.32776175826262749 22.024129423631663 -39.502666336348213 -5.7021436739812703 0.32776175826262749 33.420370073444623 -22.792481299625912 -5.7021436739812703 0.9832852747878823 14.828879084398052 -13.755323697036332 -7.1549991831615554 0.9832852747878823 1.0735553873617152 -28.584202781434378 -7.1549991831615545 0.32776175826262749 15.90243447175977 -42.339526478470717 -7.1549991831615545 0.32776175826262749 29.657758168796111 -27.510647394072674 -7.1549991831615554 0.9832852747878823 12.469796037174671 -15.636629649360593 -8.5714285714285499 1 -3.1668336121859242 -28.106425686535264 -8.5714285714285499 0.33333333333333331 9.3029624249887473 -43.743055335895846 -8.5714285714285499 0.33333333333333331 24.939592074349342 -31.273259298721193 -8.5714285714285499 1 10.11071298995129 -17.517935601684854 -9.9878579596955426 0.9832852747878823 -7.4072226117335642 -27.628648591636132 -9.9878579596955444 0.32776175826262749 2.7034903782177229 -45.14658419332099 -9.9878579596955444 0.32776175826262749 20.22142597990258 -35.035871203369709 -9.9878579596955426 0.9832852747878823 . 7.3921471224894955 -18.827127923010924 -11.440713468875831 0.9832852747878823 -11.434980800521428 -26.21927504550041 -11.440713468875829 0.32776175826262749 -4.0428336780319327 -45.04640296851133 -11.440713468875829 0.32776175826262749 14.784294244978991 -37.654255846021847 -11.440713468875831 0.9832852747878823 4.4504186791262894 -19.498558243636467 -12.857142857142824 1 -15.04813956451018-23.948976922762753 -12.857142857142824 0.33333333333333331 - 173 - Appendix E. The Sat Files of an Envelope Surface -10.59772088538389 -43.44753516639922 -12.857142857142824 0.33333333333333331 8.9008373582525788 -38.99711648727294 -12.857142857142824 1 2.9919506021658848 -19.831444064809034 -13.559388861772048 0.99164263739394098 -16.839493462643151 -22.823394666974913 -13.559388861772053 0.33054754579798035 -13.847542860477263 -42.654838731783954 -13.559388861772053 0.33054754579798035 5.9839012043317679 -39.662888129618075 -13.559388861772048 0.99164263739394098 1.5023058653347638 -20.000000000000004 -14.276646291867323 0.98746395609091164 -18.497694134665242 -21.502305865334762 -14.276646291867323 0.32915465203030386 -16.99538826933048 -41.502305865334769 -14.276646291867323 0.32915465203030386 3.004611730669525 -40.000000000000007 -14.276646291867323 0.98746395609091164 -7.6638049594309347e-014 -19.999999999999996 -15.000000000000002 0.98746395609091175 -20.000000000000078 -19.999999999999911 -15.000000000000002 0.32915465203030392 -20.000000000000153 -39.999999999999915 -15.000000000000002 0.32915465203030392 -1.5591121837237719e-013 -39.999999999999993 -15.000000000000002 0.98746395609091175 0 0 0 0 0 3 0.071428571428571425 0.14285714285714285 0.21428571428571427 0 F1F0F1F0}IIII# -9 face $-1 -1 -1 $-1 $13 $14 $4 $-1 $15 reversed single F F # -10 loop $-1 -1 -1 $-1 $-1 $16 $6 F unknown # -11 plane-surface $-1 -1 -1 $-1 30 0 0 0 0 1 1000 0 0 forward_v 1111 # -12 coedge $-1 -1 -1 $-1 $17 $18 $19 $20 reversed $7 $21 # -13 face $-1 -1 -1 $-1 $-1 $22 $4 $-1 $23 reversed single F F # -14 loop $-1 -1 -1 $-1 $-1 $24 $9 F unknown # -15 plane-surface $-1 -1 -1 $-1 -1.1140577831304493e-013 -30-15 0 0 1 -3.713525943768165e-012-1000 0 forwardv 1111 # -16 coedge $-1 -1 -1 $-1 $19 $19 $25 $26 forward $10 $-1 # -17 coedge $-1 -1 -1 $-1 $27 $12 $28 $29 forward $7 $30 # -18 coedge $-1 -1 -1 $-1 $12 $27 $31 $32 reversed $7 $33 # -19 coedge $-1 -1 -1 $-1 $16 $16 $12 $20 forward $10 $-1 # -20 edge $-1 -1 -1 $-1 $34 -3.1415926535897931 $35 0 $19 $36 forward @7 unknown F # -21 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 2 open 13 0 2 0.26179938779914941 2 0.52359877559829882 2 0.78539816339744828 2 1.0471975511965976 2 1.308996938995747 2 1.5707963267948966 2 1.8325957145940459 2 2.0943951023931953 2 2.3561944901923448 2 2.6179938779914944 2 2.879793265790644 2 3.1415926535897931 2 1 0 0.94611254164616254 0 0.94183174699473993 0 0.93677493932354483 0 0.8943375672974061 0 0.85684756116418259 0 0.85355339059327373 0 0.84995023689285931 2.1337867821239758e-018 0.8169872981077807 2.1654431452783809e-017 0.78586701224058342 1.8772212167380323e-018 0.78291312439676708 0 0.7798739506635517 2.5908894082864976e-018 0.75000000000000022 2.8058371412343862e-017 0.72012604933638202 2.5908894082875245e-018 - 174- Appendix E. The Sat Files of an Envelope Surface 0.71708687560315842 0 0.71413298775934742 3.1880491120183416e-018 0.6830127018922193 3.67753093501905e-017 0.65004976310714069 3.623 76953516684e-018 0.64644660940672627 0 0.64315243883581741 2.8286329116603327e-018 0.60566243270259346 3.5020489078212388e-017 0.56322506067645517 3.7287069478462213e-018 0.5581682530052603 0 0.55388745835383768 0 0.500000000000000110 0.001 0.0107299081764064 spline reversed { ref 0 } 1111 }00# -22 loop $-1 -1 -1 $-1 $-1 $28 $13 F unknown # -23 spline-surface $-1 -1 -1 $-1 forward { exactsur full nurbs 3 3 both open open none none 2 5 0 3 0.5 3 0 3 0.071428571428571425 3 0.14285714285714285 3 0.21428571428571427 3 0.25000000000000178 3 4000 1 39.999999999999993 19.999999999999996 0 0.33333333333333331 19.999999999999996 19.999999999999996 0 0.33333333333333331 19.999999999999996 1.224646799147353 le-015 0 1 40 -6.0347609430523219 -1.4164293882669949 0.9832852747878823 43.017380471526153 13.965239056947674 -1.4164293882669949 0.32776175826262749 23.017380471526153 16.982619528473833 -1.4164293882669949 0.32776175826262749 19.999999999999996 -3.0173804715261601 -1.4164293882669949 0.9832852747878823 38.657139358748914 -11.918217829778738 -2.86928489744728 0.9832852747878823 44.616248273638263 7.4103518495957141 -2.8692848974472795 0.32776175826262749 25.287678594263813 13.369460764485083 -2.8692848974472795 0.32776175826262749 19.32856967937445 -5.9591089148893666 -2.86928489744728 0.9832852747878823 36.038754716096761 -17.355349564702326-4.2857142857142749 1 44.716429498447908 0.66402779334605655 -4.2857142857142749 0.33333333333333331 26.697052140399538 9.3417025756972176 -4.2857142857142749 0.33333333333333331 18.019377358048377 -8.6776747823511595 -4.2857142857142749 1 33.420370073444623 -22.792481299625912 -5.7021436739812703 0.9832852747878823 44.816610723257561 -6.0822962629035953 -5.7021436739812703 0.32776175826262749 28.10642568653526 5.3139443869093563 -5.7021436739812703 0.32776175826262749 16.710185036722311 -11.396240649812952 -5.7021436739812703 0.9832852747878823 29.657758168796111 -27.510647394072674 -7.1549991831615554 0.9832852747878823 43.413081865832432 -12.681768309674615 -7.1549991831615545 0.32776175826262749 28;584202781434378 1.0735553873617178 -7.1549991831615545 0.32776175826262749 14.828879084398052 -13.755323697036332 -7.1549991831615554 0.9832852747878823 24.939592074349342 -31.273259298721193 -8.5714285714285499 1 40.576221723709935 -18.803463261546511 -8.5714285714285499 0.33333333333333331 28.106425686535264 -3.166833612185922 -8.5714285714285499 0.33333333333333331 12.469796037174671 -15.636629649360593 -8.5714285714285499 1 20.22142597990258 -35.035871203369709 -9.9878579596955426 0.9832852747878823 37.739361581587431 -24.925158213418406 -9.9878579596955444 0.32776175826262749 27.628648591636143 -7.4072226117335633 -9.9878579596955444 0.32776175826262749 10.11071298995129 -17.517935601684854 -9.9878579596955426 0.9832852747878823 14.784294244978991 -37.654255846021847 -11.440713468875831 0.9832852747878823 33.611422167989907 -30.262108723532343 -11.440713468875829 0.32776175826262749 26.219275045500417-11.434980800521428-11.440713468875829 0.32776175826262749 - 175 - Appendix E. The Sat Files of an Envelope Surface 7.3921471224894955 -18.827127923010924 -11.440713468875831 0.9832852747878823 8.9008373582525788 -38.99711648727294 -12.857142857142824 1 28.399395601889047 -34.546697808146646 -12.857142857142824 0.33333333333333331 23.948976922762757 -15.04813956451018 -12.857142857142824 0.33333333333333331 4.4504186791262894 -19.498558243636467 -12.857142857142824 1 5.9839012043316719 -39.662888129618089 -13.559388861772076 0.99164263739394076 25.815345269140721 -36.670937527452253 -13.559388861772076 0.33054754579798024 22.823394666974878 -16.839493462643212 -13.559388861772076 0.33054754579798024 2.9919506021658369 -19.831444064809045 -13.559388861772076 0.99164263739394076 3.0046117306693301 -40.000000000000036-14.276646291867369 0.98746395609091131 23.00461173066935 -38.497694134665366 -14.276646291867369 0.32915465203030375 21.502305865334673 -18.497694134665352 -14.276646291867369 0.32915465203030375 1.5023058653346664 -20.000000000000014-14.276646291867369 0.98746395609091131 -4.4928782083082226e-013 -40 -15.000000000000073 0.98746395609091175 19.999999999999549 -40.00000000000022 -15.000000000000071 0.32915465203030392 19.999999999999773 -20.000000000000227 -15.000000000000071 0.32915465203030392 -2.2332635082353182e-013 -19.999999999999993 -15.000000000000073 0.98746395609091175 0 0 0 0 0 3 0.071428571428571425 0.14285714285714285 0.21428571428571427 0 F 1 F 0 F 1 F 0 > 1111 # -24 coedge $-1 -1 -1 $-1 $37 $37 $38 $39 reversed $14 $-1 # -25 coedge $-1 -1 -1 $-1 $31 $28 $16 $26 reversed $22 $40 # -26 edge $-1 -1 -1 $-1 $35 0 $34 3.1415926535897931 $16 $41 forward @7 unknown F # -27 coedge $-1 -1 -1 $-1 $18 $17 $37 $42 forward $7 $43 # -28 coedge $-1 -1 -1 $-1 $25 $38 $17 $29 reversed $22 $44 # -29 edge $-1 -1 -1 $-1 $34 0 $45 0.25000000000000061 $17 $46 forward @7 unknown F # -30 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 1 open 2 0 1 0.25000000000000061 1 0.5 0 0.50000000000000011 0.25000000000000061 0.001 -1 spline reversed { ref 0 } I I 1 1 } 00# -31 coedge $-1 -1 -1 $-1 $38 $25 $18 $32 forward $22 $47 # -32 edge $-1 -1 -1 $-1 $35 0 $48 0.25000000000000061 $31 $49 forward @7 unknown F # -33 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 1 open 2 -0.25000000000000061 1 0 1 1 0.25000000000000061 1 0 0.001 -1 spline reversed { ref 0 } 1111 } 00# -34 vertex $-1 -1 -1 $-1 $20 $50 # -35 vertex $-1 -1 -1 $-1 $20 $51 # -36 ellipse-curve $-1 -1 -1 $-1 30 0 0 0 0 1 10.000000000000002 0 0 1 F -3.1415926535897931 F 0 # -37 coedge $-1 -1 -1 $-1 $24 $24 $27 $42 reversed $14 $-1 # -38 coedge $-1 -1 -1 $-1 $28 $31 $24 $39 forward $22 $52 # -39 edge $-1 -1 -1 $-1 $48 -2.0194839173657899e-030 $45 3.1415926535897931 $38 $53 forward -176- Appendix E. The Sat Files of an Envelope Surface unknown F # -40 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 2 open 13 -3.1415926535897931 2 -2.879793265790644 2 -2.6179938779914944 2 -2.3561944901923448 2 2.0943951023931957 2 -1.8325957145940461 2 -1.5707963267948966 2 -1.3089969389957472 2 -1.0471975511965979 2 0.78539816339744828 2 -0.5235987755982987 2 -0.26179938779914935 2 0 2 0.5 0 0.44611254164616165 3.0391826216922957e-016 0.44183174699473904 3.280613876924436e-016 0.43677493932354422 2.9313198471132126e-016 0.394337567297406710 0.35684756116418265 3.7385529923538775e-019 0.35355339059327379 4.0670520382444336e-019 0.34995023689285948 3.6662924108056502e-019 0.316987298107780810 0.2858670122406527 4.3022305350325433e-014 0.28291312439684152 4.7105913879169037e-014 0.27987395066361792 4.275618838927289e-014 0.25 0 0.22012604933644889 4.2731648028064627e-014 0.21708687560323295 4.7078876947551781 e-014 0.21413298775941622 4.299761224850589e-014 0.18301270189221919 0 0.15004976310714063 0 0.14644660940672627 0 0.14315243883581746 4.9183516869039065e-018 0.10566243270259383 6.089269513339682e-017 0.063225060676456807 2.6800737900841621e-016 0.058168253005262127 2.9268702037714195e-016 0.053887458353839519 2.7114721186238487e-016 00 0.001 0.010729908174256897 spline reversed { ref 2 } 1111 } 00# -41 ellipse-curve $-1 -1 -1 $-1 30 0 0 0 0 1 10.000000000000002 0 0 1 F 0 F 3.1415926535897931 # -42 edge $-1 -1 -1 $-1 $45 -3.1415926535897931 $48 -2.0194839173657899e-030 $27 $54 forward @7 unknown F # -43 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 2 open 13 -3.1415926535897931 2 -2.879793265790644 2 -2.6179938779914944 2 -2.3561944901923448 2 2.0943951023931957 2 -1.8325957145940461 2 -1.5707963267948966 2 -1.3089969389957472 2 -1.0471975511965979 2 • 0.78539816339744828 2 -0.5235987755982987 2 -0.26179938779914935 2 -2.0194839173657899e-030 2 0.5 0.25000000000000061 0.55388745835383824 0.25000000000000039 0.55816825300526085 0.25000000000000033 0.56322506067645561 0.25000000000000033 0.60566243270259346 0.25000000000000061 0.64315243883581752 0.25000000000000056 0.64644660940672638 0.25000000000000056 0.6500497631071408 0.25000000000000056 0.68301270189221941 0.25000000000000056 0.71413298775934742 0.24999999999995826 - 177- Appendix E. The Sat Files of an Envelope Surface 0.71708687560315854 0.24999999999995426 0.72012604933638213 0.24999999999995853 0.75000000000000011 0.25000000000000061 0.77987395066355136 0.24999999999995859 0.7829131243967673 0.24999999999995429 0.78586701224058408 0.24999999999995831 0.81698729810778081 0.25000000000000061 0.84995023689285976 0.25000000000000061 0.85355339059327417 0.25000000000000061 0.85684756116418304 0.25000000000000061 0.89433756729740677 0.25000000000000061 0.93677493932354361 0.25000000000000044 0.94183174699473 826 0.25000000000000039 0.94611254164616077 0.25000000000000039 1 0.25000000000000061 0.001 0.010729908174639924 spline reversed { ref 0 } 1111 } 00# -44 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 1 open 2 -0.25000000000000061 1 0 1 0.49999999999999989 0.25000000000000067 0.5 0 0.001 -1 spline reversed { ref 2 } 1111 } 00# -45 vertex $-1 -1 -1 $-1 $39 $55 # -46 intcurve-curve $-1 -1 -1 $-1 forward { exactcur full nurbs 2 open 5 0 2 0.071428571428571425 2 0.14285714285714285 2 0.21428571428571427 2 0.250000000000000612 19.999999999999996 1.224646799147353le-015 0 1 19.999999999999996 -4.564869487802997 -2.1428571428571379 0.97492791218182362 18.019377358048377 -8.6776747823511595 -4.2857142857142749 1 16.038754716096765 -12.790480076899319 -6.4285714285714119 0.97492791218182362 12.469796037174671 -15.636629649360593 -8.5714285714285499 1 8.900837358252577 -18.482779221821868 -10.714285714285687 0.97492791218182362 4.4504186791262894 -19.498558243636467 -12.857142857142824 1 2.2534587980021841 -20.000000000000007 -13.914969437800982 0.98746395609091153 -7.6198863063682964e-014 -19.999999999999996 -15 0.98746395609091175 0 nullsurface nullsurface nullbs nullbs -1 -1 II 0 3 0.071428571428571425 0.14285714285714285 0.21428571428571427 0 -1 nullbs F 1 F 0 } 11 # -47 pcurve $-1 -1 -1 $-1 0 forward { exppc nubs 1 open 2 - 178- o S3 4iSO so SO SO SO SO so so so SO SO SD SO so 4^ O to Ln o o o o o o o o © © o tO k) tO — © -J © KJ 00 O N ON O OO -fc- ~J so Ln Lo Os LO © OS LO tO LO oo to O Ln oo LO O O to to Ln Ln o o o o o o o o o o o o o o o © © © © © © © © © o © © o — — Ln Os - J OS - J oo Ln Ln Ln to -J to i— © LO oo Ln -a T3 T3 Ln OS O O O LO so SO 5' 5' — to £ _ oo © © © © © © © © © I < ^ 3 © © © 4*. OS )0 LO OS to > — — i > oo Ln J*. 4* © Os Ln Ln 4^ — © © LO to n w w c o v> i . ± K LO O OS LO Ln LO OO LO Ln -4 i— OS to — oo oo so sq SO *o s S - ^ ^ S " — © Ln Os to OS oo -Os 0 SO -O LO LO SD LO ~- © -u to to Ln <*> £• LO I OO ~J to to © to 4*. © OO 4> SO 4^ 4*. 4^ SO -o. so i-n SO OS LO LO OS Ln Ln - J -4 00 00 © - J OS oo to © LO 00 © so 00 -o. i — ~ © -o — OS © 00 -0 OS © LO — so to SO — 4*. — to - j oo LO SO LO © - J © Ln 4i. so © ° —, LO to — Ln so I — to Os Ln © SO — to oo — 4*. © © Ln 00 Ln 4^ CP so Os 4*J OS 00 so so to so Ln — ~J —] LO —] to © so 4^ 3 ° so 4>. to to LO 4^. LO oo to Os so © OS _ Os - J ~J LO to pj SO to LO 42. © ^ SO to O © *> © © so - J tO P Ln - J © o SO SO to to © © Ln to P to P •o Ln LO ^ SO Ln Ln to to © Ln to Ln to O <=> a so © © Ln Ln © © Ln © Ln to SO ~J — to X © Ln —J © © © o © © © © so " SO © © © SO © o © © SO © © LO LO OS to o © © © SO © o © © © © © © © © © o © © SO © to ^° J£ © © Os * 0 © o © © © o © Os © Os © © Ln © © © © © © -J ^ © © © © © -J © © © so Os © © © OS © © © to © © © © © © © 4^ to © © © to © © so © © OO © © © © © © -U © © © © © © © © so © © © Os © © © © OS Os © © © © — © © 4^ 4*. LO K> Os — © o © © Ln © © © — OS 4^ © © Os Ln — Ln © © OS OS © -J oo o © © to Os SO - a — Ln Ln Ln OS LO - J -a so LO Os OS OO -4^ J 0> LO 4^ 3 —1 SO to Ln LO Ln so to SO to Ln Ln © OS -J Ln Ln I LO £ to Ln Ln LO © oo so Ln so 4*. so Ln -4 © oo SO © -J LO Ln -J Ln so Ln to SO to 00 to o so SO 00 4^ 00 LO SO to Ln © to LO SO LO S rr J°, P3 3 SO Ln LO to © LO © © © 4*. to 00 Ln -J it to oo Ln -J 4^ to *. to 00 Ln -J it to 00 Ln -o it to oo Ln © to it to 00 Ln •o it to 00 Ln —i it to -J Appendix E. The Sat Files of an Envelope Surface 0.27987395066361787 0.25000000000000167 0.28291312439684146 0.25000000000000178 0.28586701224065253 0.25000000000000167 0.31698729810778065 0.25000000000000061 0.34995023689285931 0.25000000000000061 0.35355339059327368 0.25000000000000061 0.35684756116418248 0.25000000000000061 0.39433756729740643 0.25000000000000061 0.43677493932354428 0.25000000000000089 0.44183174699473909 0.25000000000000089 0.44611254164616176 0.25000000000000089 0.49999999999999994 0.25000000000000061 0.001 0.010729908176226099 spline reversed {ref 2 } 1111 } 00# -53 ellipse-curve $-1 -1 -1 $-1 -1.1140577831304493e-013 -30 -15 0 0 1 -3.7135259437681647e-01410.000000000000002 0 1 F -2.0194839173657899e-030 F 3.1415926535897931 # -54 ellipse-curve $-1 -1 -1 $-1 -1.1140577831304493e-013 -30-15 0 0 1 -3.7135259437681647e-01410.000000000000002 0 1 F -3.1415926535897931 F-2.0194839173657899e-030 # -55 point $-1 -1 -1 $-1 -7.6198863063682964e-014 -19.999999999999996 -15 # -56 point $-1 -1 -1 $-1 -1.4854103775072659e-013-40-15# End-of-ACIS-data - 180-
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Feature-based methodologies for milling process modeling...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Feature-based methodologies for milling process modeling in Virtual Machining Wang, Jue 2006
pdf
Page Metadata
Item Metadata
Title | Feature-based methodologies for milling process modeling in Virtual Machining |
Creator |
Wang, Jue |
Date Issued | 2006 |
Description | Virtual Machining is used to simulate the machining process prior to actual machining, thereby avoiding costly test trials on the shop floor. To realize Virtual Machining, two major methodologies, Geometric Modeling and Process Modeling, are required. In geometric modeling, Cutter/Workpiece Engagements (CWEs) are extracted to support force prediction in process modeling. In process modeling, the physics of the machining process, such as cutting forces, torque and power, are predicted by integrating the laws of the metal cutting process with CWEs generated in geometric modeling. Based on these predictions, process parameters can be optimized for productivity. Methodologies in geometric modeling for CWE extraction require a large number of calculations, however, the robustness and computational stability of these approaches is a significant challenge. In this thesis, methodologies are developed to address these problems in CWE extraction for the milling process. These methodologies achieve computational efficiency and stability by reducing the number of intersections that need to be performed and by parallelizing computational activities in the process of CWE extraction. A feature-based approach is presented for CWE extraction in 2 1/2 D end milling by introducing in-process machining features into process modeling. In hole milling, an analytical approach is presented for CWE extraction, and a NURBS based approach is developed for generating the swept volume for in-process workpiece modeling. A Multi-Agent System based framework is developed to improve efficiency of the CWE calculation, by parallelizing computational activities and utilizing free resources over a network. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080728 |
URI | http://hdl.handle.net/2429/18346 |
Degree |
Master of Applied Science - MASc |
Program |
Mechanical Engineering |
Affiliation |
Applied Science, Faculty of Mechanical Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2006-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2006-0696.pdf [ 30.76MB ]
- Metadata
- JSON: 831-1.0080728.json
- JSON-LD: 831-1.0080728-ld.json
- RDF/XML (Pretty): 831-1.0080728-rdf.xml
- RDF/JSON: 831-1.0080728-rdf.json
- Turtle: 831-1.0080728-turtle.txt
- N-Triples: 831-1.0080728-rdf-ntriples.txt
- Original Record: 831-1.0080728-source.json
- Full Text
- 831-1.0080728-fulltext.txt
- Citation
- 831-1.0080728.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080728/manifest