Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 UDK - UDC 621.7.012 Kratki znanstveni prispevek - Short scientific paper (1.03) Določanje poti orodja površin nepravilnih oblik z zlepki Tool-Path Generation for Free-Form Surfaces with B-Spline Curves Mohamed Bey1 - Salim Boudjouad2 - Nazim Tafat-Bouzid2 (1Centre de Développement des Technologies Avancées, Algiers, Algeria; 2Université des Sciences et de la Technologie Houari Boumediene, Algiers, Algeria) Deli nepravilnih oblik, ki se uporabljajo pri načrtovanju in izdelavi kalupov, matric in aerodinamičnih oblik itn., so izdelani na 3-osnih ali 5-osnih/rezalnih strojih. Pri običajnem postopku določanja poti površin nepravilnih oblik so gibi orodja izraženi z linearno interpolacijo. S to metodo interpolacije so teoretične krivulje lege orodja aproksimirane z lomljenimi črtami. Gibi orodja so posledično prekinjeni v dotikališčih in v krivinah, kar povzroča vibracije in posledično vpliva na končno obdelano površino. Z razvojem RK interpolatorjev, ki sprejemajo zlepke je še ugodneje , če jih tudi uporabljajo. Pri našem delu o NURBS površinah izdelanih s strategijo paralelnih ravnin na 3-osnih RK frezalnih strojih smo avtomatizirali določanje poti orodja z zlepki z določitvijo najmanjšega števila nadzornih točk, ki podajajo najboljšo aproksimacijo različnih položajev orodja. © 2007 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: strategija vzporednih ravnin, aproksimacije, zlepki, površine nepravilnih oblik) Free-form parts used in the design and manufacture of molds, dies and aerodynamic shapes, etc., are machined on 3-axis or 5-axis milling machines. In the classical approach of tool-path generation for free-form surfaces, the tool movements are expressed as a linear interpolation. For this method oj interpolation, the theoretical curves of the tool positions are approximated with a polygonal line. Consequently, the tool movements are discontinuous in tangency and curvature, which creates vibrations and consequently affects the finish of the surface. With the development of CNC interpolators that accept a B-Spline curve, it has become more advantageous to use them. In our work on the NURBS surfaces machined with a parallel-plane machining strategy on 3-axis CNC milling machines, we automate the generation oj the tool path in terms of B-Spline curves by determining the minimum number of control points that give the best approximation to the different tool positions. © 2007 Journal of Mechanical Engineering. All rights reserved. (Keywords: parallel-plane machining strategy, curve approximation, B-spline, free-form surface) 0 INTRODUCTION Free-form parts are used in the design and manufacture of molds, dies, etc., and are machined on 3-axis or 5-axis milling machines. For machining free-form surfaces, we have to consider many aspects, such as surface definition, machining strategies, machining parameters, etc., with the objective to obtain a good surface finish. Generally, three stages are required to obtain the final part: roughing, semi-finishing and finishing. In the roughing stage, the goal is to remove the most material from the initial workpiece as rapidly as possible, by using a large flat-end mill tool, on sequential horizontal cutting planes and keeping only a small thickness of material that is removed in semi-finishing and finishing, generally using ball-end mill tools. To machine these surfaces we have to generate the tool path by calculating the sequence of tool positions from the design surfaces. Tool-path generation methods are classified as either the CC-based method or the CL-based method, depending on the type of tool-path generation surface [1]. In the cutter-contact (CC) 733 Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 based method, the tool-path generation is done on the design surface and the tool paths are generated by sampling a sequence of CC points from the part’s surface and then each CC point is converted to a cutter location (CL) point. In the cutter location (CL) based method, the offset surface is generated from the design surface, and then it is used as a path-generation surface. For the two methods, to obtain a good surface finish and a minimum machining time, it is necessary to determine the optimum feed-forward step and the side step. Different problems related to the machining of free-form surfaces have been considered by different researchers. In [2] Choi et al. studied interference avoidance and in [3] they looked at the machining of compound surfaces. Duc [4] studied the parameters that affect the surface quality and proposed generating tool paths in terms of planar B-Spline curves. Yang [5] proposed methods for global and local interference checking and then determined the optimal combination of tool sizes that minimizes the machining times. Park [6] optimized the tool path for a Z-constant machining strategy by considering the machining constraints and the tool-path length. OuYang et al. ([7] and [8]) used the Voronoi diagram and Delaunay triangulation to select the optimal ball-end mill tool to be used for finishing free-form surfaces given by a cloud of points. Jerard et al. ([9] and [10]) considered another aspect, which is the determination of the optimal cutting conditions and in particular the feed rate. Recent research has focused on the machining of free-form surfaces directly from a cloud of points, without the reconstruction of the CAD model of the surfaces. Different methods have been developed for 3-axis machining ([11] to [14]) and for 5-axis machining ([15] and [16]). Jerard et al. ([17] and [18)] proposed methods for the simulation and verification of the generated machining programs. Among the fields of research is the quality of the finished surfaces. For machining these surfaces, different machining strategies are used: isoparametric, Z-constant, parallel plane, etc. The parallel-plane machining strategy permits the machining of multiple adjoining surfaces and guarantees the continuity of the machining. In the classical approach of tool-path generation, the tool movements are expressed as linear interpolations. For this method of interpolation, a polygonal line is used to approximate the theoretical curves of the tool positions. Consequently, the tool movements are discontinuous in the tangency and in the curvature because at each point there is an abrupt change in the direction that creates vibrations and this consequently affects the finish of the surface. With the development of CNC interpolators that accept the B-Spline curve; it is more advantageous to use these interpolators because they minimize vibrations, allow a good surface finish and permit the reduction of the size of the machining program. In our work, from the NURBS surfaces machined with a parallel-plane machining strategy on 3-axis CNC milling machines using the CC-based method, we automate the generation of the tool path with B-Spline curves by determining the minimum number of control points that gives the best approximation to different tool positions with a given accuracy. 1 DEFINITION OF NURBS CURVES AND SURFACES Different parametric formulations are used in the description of curves, such as Bezier, Rational Bezier, B-Spline and NURBS. However, the most powerful version is the NURBS. A NURBS curve is defined by (n+1) control points Pi with their weight Wi, (0?i?n), knot vector U and degrees p. If all the weights are equal, a NURBS curve becomes a B-Spline curve. A NURBS curve is given by YJNip{u)wi Generally, the free-form parts are designed by the junction of an important number of complex surfaces. To describe the shape of these surfaces, the parametric formulation is used with regard their advantages relative to the other formulations. Different parametric formulations are used, such as the Bezier, the Rational Bezier, the B-Spline and the NURBS. However, the most powerful formulation is the NURBS. A NURBS surface is defined by (Fig. 1): • A network of (m+1)x(n+1) control points Pi, with their weight Wj (0) = ÎÎA<„KW-e, (5). To control the form of the curve, we constrain the curve so it must pass by the first and the last of the data points for each curve. This condition is given by: fa=ß0 \Pn=Qm (6). To obtain a linear system of equations and to calculate the coordinates of the control points, we need to choose methods for calculating the nodal value uk for each data point and the knot vector U. The values of the parameters uk are calculated using the uniformly spaced method, the centripetal method or the chord-length method, and the knot vector is calculated using the uniform method or the average method [19]. With this parameterization, we can generate six different B-Spline curves and consequently, we must choose the best one in terms of their quality. To qualify the quality of the generated curve, two criteria of accuracy are used [21]: • The superior error C1: measures the gap to the less approached point: C1 = Max Qi - C(ui i=0,... m (7). The average quadratic error C2: measures the average error committed at a point: C2 = ,Z(ô,-c(M,))2 V ;=0 m + 1 (8). The criteria of precision C1 and C2 are both necessary to judge the precision of the obtained curve, but these criteria do not allow us to validate the curve between data points. It is also possible to calculate the deviation between the middle of each segment of data points and the approximated curve. 3 SOFTWARE DEVELOPMENT AND RESULTS To automate the generation of the tool path with the B-Spline curves and the determination of the minimum number of control points that give the best approximation with an imposed accuracy, we have developed object-oriented software running under Windows using the C++ Builder and the graphics library OpenGL [22]. Fig. 3 shows the flowchart of the developed software. The generation of the tool path with the B-Spline curves is divided into two stages. In the first stage, the user selects the surfaces to machine and introduces a set of parameters: machining parameters, approximation parameters and methods of parameterization. These parameters are as follows: tool dimensions, feed rate, the distance between two planes, the number of triangles for each surface, the sweeping strategy (zig-zag, one-way), orientation of the vertical plane, points to approximate with the B-Spline curves (cutter contact, tool center, cutter location), degree of the curve, accuracy of the approximation and finally the methods used for the calculation of the nodal values and the knot vector. Generally, the degree is chosen to be equal to 3 in order to obtain a continuity of the curvature and to avoid the problem of oscillations of the curve. Once these parameters are introduced, the software automatically finds the correct orientation for each surface and triangulates it. In the next step, the intersection points between all the positions of the vertical planes and the triangles are calculated with the associated tool-center points and cutter-location points. In the second stage, for each data point, we fix the initial number of control points and the increment value, which are both equal to five because we have found in our tests that generally the approximation converges with a small number of control points. After this, we calculate the nodal values and the knot vector for all the possible combinations, one after another in this order (uniformly spaced method, uniform method), (uniformly spaced method, average 2 m 736 Bey M. - Boudjouad S. - Tafat-Bouzid N. Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 - Machining parameters - Degree of the curve - Accuracy of the approximation - Parameterization methods Orientation and triangulation of the surfaces Determination of intersection points Number of control points = 5 Calculate nodal values, knot vector and errors C1 and C2 (six possible combinations) No Accuracy is not verified for all combinations Yes Increment the number of control points by 5 Number of control points < number of data points Yes No Degree = 1 and number of control points = number of data points Generate the B-Spline curve Generate the tool path with B-Spline curves Fig. 3. Flow chart of tool-path generation with B-Spline curves method), (centripetal method, uniform method), (centripetal method, average method), (chord-length method, uniform method), (chord-length method, average method) and simultaneously the errors C1 and C2. If the accuracy is verified at least for one combination, a new B-Spline curve is generated and we pass to the next data points. But, if the accuracy is not verified for all the combinations, we increment the number of control points by 5 and we repeat the same steps until verification of the accuracy for at least one combination. In the worst case, if the number of control points is greater than the number of data points, the degree is set to 1 and the number of control points equal to the number of data points. In the end, we obtain a set of B-Spline curves with a minimum number of control points, which are used in the generation of the tool path. To demonstrate the automatic generation of the tool path in terms of B-Spline curves, we have considered two different surfaces (Fig. 4). The dimensions of the first surface are 44 mm x 51 mm x 16 mm and the minimum principal radius of curvature is equal to 4.634 mm. To avoid the problem of interference we have chosen a tool radius equal to 4 mm. The selected parameters for this surface are as follows: feed rate = 50mm/min, distance between two planes = 2 mm, number of triangles in each direction = 200, orientation of the vertical plane = 90°, and degree = 3. For the accuracy we have considered three values, 0.1, 0.05 and 0.01, and the results for the cutter-contact points, the tool-center points and the cutter-location points are given in Table 1, Table 2 and Table 3, respectively, and Fig. 5 represents the a- First surface b- Second surface Fig. 4. The two considered surfaces Surface Model (NURBS) Določanje poti orodja površin nepravilnih oblik - Tool-Path Generation for Free-Form Surfaces 737 Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 Table 1. Results of the approximation with the B-Spline curves for the first surface with an accuracy of 0.1 CC points CE points CL points Points of intersection 9023 9023 9023 Total number of control points 225 230 230 Percentage of reduction 97.5 97.45 97.45 Error C1 0.0952 0.0947 0.0947 Error C2 0.0029 0.002 0.002 Table 2. Results of the approximation with the B-Spline curves for the first surface with an accuracy of 0.05 CC points CE points CL points Points of intersection 9023 9023 9023 Total number of control points 240 230 230 Percentage of reduction 97.34 97.45 97.45 Error C1 0.0479 0.0497 0.0497 Error C2 0.0013 0.0014 0.0014 Table 3. Results of the approximation with the B-Spline curves for the first surface with an accuracy of 0.01 CC points CE points CL points Points of intersection 9023 9023 9023 Total number of control points 375 355 355 Percentage of reduction 95.84 96.07 96.07 Error C1 0.0098 0.0099 0.0099 Error C2 0.0004 0.0002 0.0002 generated curves. The obtained results show a good approximation of the data points with the B-Spline curves and an important reduction in the number of points that exceeds 95 percent. The running times for the three cases are 1 min, 1 min 30 sec, and 2 min 30 sec, respectively, and the maximum number of control points are 10, 15 and 20, respectively. The dimensions of the second surface are 102 mm x 160 mm x 51 mm and the minimum principal radius of curvature is equal to 12.844 mm. To avoid the problem of interference we have chosen a radius of the tool equal to 10 mm. The parameters for this surface are as follows: feed rate = 50mm/min, distance between two planes = 5mm, number of triangles in each direction = 200, orientation of the vertical plane = 0°, accuracy = 0.1 mm, and degree = 3. The obtained results from these data are given in Table 4, and Fig. 6 represents the generated curves for the cutter-contact points, the cutter-center points and the cutter-location points. For this example, the maximum number of control points is equal to 10 and the software takes 1 min 30 sec to generate the curves. The results show a good approximation with the B-Spline curves and an important reduction in the number of points that exceeds 97 percent. It is very important to mention that the percentage of the reduction in the number of control points depends on the number of data points, the distance between these points, the shape of the data points and on the imposed accuracy of the approximation. We must also mention that the maximum number of control points increases with the imposed accuracy. For the generation of the B-Spline curves, the software takes a time that depends on the following parameters: the shape complexity and the dimensions of the surfaces, the distance between two planes, the number of curves and the data points 738 Bey M. - Boudjouad S. - Tafat-Bouzid N. Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 c- Tool-center curves d- Cutter-location curves Fig. 5. The first considered surface and the generated B-Spline curves a- Intersection points b- Cutter-contact curves c- Tool-center curves d- Cutter- location curves Fig. 6. The second considered surface and the generated B-Spline curves Določanje poti orodja površin nepravilnih oblik - Tool-Path Generation for Free-Form Surfaces 739 Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 Table 4. Results of the approximation with the B-Spline curves for the second surface CC points CE points CL points Points of intersection 13033 13033 13033 Total number of control points 330 320 320 Percentage of reduction 97.47 97.54 97.54 Error C1 0.095 0.1 0.1 Error C2 0.0026 0.003 0.003 for each curve, the imposed accuracy and the CPU of the computer. 4 CONCLUSION In this paper we have presented a method that enables us, from CAD models of surfaces, to machine with a parallel-plane machining strategy on 3-axis CNC milling machines, the automatic generation of the tool path with B-Spline curves that satisfy a given accuracy and with a minimum number of control points. These curves make it possible to obtain a good surface finish and an important reduction in the size of the machining program and consequently the necessary memory. The presented method can be used for other machining strategies without much difficulty. In terms of this work, and in order to accelerate the generation of B-Spline curves, it is very important to develop a distributed application because the calculations for each curve can be done on separate computers or a computer with several processors can be used. In the next step of our work, we would like to verify the obtained results by machining a real part on a CNC machine equipped with this interpolation. 5 REFERENCES [1] D. V.Sundararajan, K. P. Wright (2003) Zig-zag tool path generation for sculptured surface finishing, Workshop on Computer Aided Design and Manufacturing, October 7-9, DIMACS Center, Rutgers University, USA. [2] B. K. Choi, C. S. Jun (1989) Ball-end cutter interference avoidance in NC machining of sculptured surfaces, Computer Aided Design, Volume 21, pages 371-378 [3] B. K. Choi, C. S. Lee, J. S. Hwang and C. S. Jun (1988) Compound surface modeling and machining, Computer Aided Design, Volume 20, pages 127-136 [4] E. Duc (1998) Usinage de formes gauches contribution a` l’amélioration de la qualité des trajectoires d’usinage, These de doctorat, École Normale Supérieure de Cachan, France [5] D. C. H. Yang, Z. Han (1999) Interference detection and optimal tool selection in 3-axis NC machining of free-form surfaces, Computer Aided Design, volume 31, pages 303-315 [6] S. C. Park (2003) Tool path generation for Z-constant contour machining, Computer Aided Design, Volume 35, pages 27-36 [7] D. OuYang, B. A. Van Nest, H. Y. Feng (2004) Automatic ball-end milling tool selection from 3D point cloud data, Flexible Automation and Intelligent Manufacturing, FAIM2004, pages 253-260, Toronto, Canada. [8] D. OuYang, B. A. Van Nest, H. Y Feng (2005) Determining gouge free ball-end mills for 3D surface machining from point cloud data, Robotics and Computer Integrated Manufacturing, volume 21, pages 338-345 [9] R. B. Jerard, B. K. Fussell, J. G., Hemmett, M. T, Ercan (2000) Toolpath optimization: A case study, Proceedings of the NSF Design & Manufacturing Research Conference, Vancouver, British, Columbia, Jan 3-6. [10] R. B. Jerard, B. K., Fussell, M. T Ercan (2001) On-line optimization of cutting conditions for NC machining, Proceedings of the 2001 NSF Design, Manufacturing & Industrial Innovation Research Conference, Tampa, Florida , Jan 7-10. 740 Bey M. - Boudjouad S. - Tafat-Bouzid N. Strojniški vestnik - Journal of Mechanical Engineering 53(2007)11, 733-741 [11] Lin and Liu (1998) Automatic generation of NC cutter path from massive data points, Computer- Aided Design volume 30, pages 77-98. [12] J. W. Choi, S. M. Hur1 and S. H. Lee (2002) Free-form surface generation from measuring points using laser scanner, International Journal of the Korean Society of Precision Engineering, Vol. 3, No. 4, pages 15-23. [13] C. Park (2003) Tool path generation from measured data, Computer-Aided Design, volume 35, pages 467-475. [14] H. Y. Feng, Z. Teng (2005) Iso-planar piecewise linear NC tool path generation from discrete measured data points, Computer-Aided Design, volume 37, pages 55-64. [15] P. Breteau, F Thiébaut, P. Bourdet, C. Lartigue (2006) Towards an approach for rapid copying of free form surfaces in 5 axis machining, IDMME 2006 Grenoble, France, May 17-19. [16] K.L. Chui, W.K. Chiu, K.M. Yu (2007) Direct 5-axis tool-path generation from point cloud input using 3D biarc fitting, Robotics and Computer-Integrated Manufacturing. [17] R. B. Jerard, S. Z. Hussaini, R. L. Drysdale, and B. Schaudt (1989) Approximate methods for simulation and verification of numerically controlled machining programs, The Visual Computer, Volume 5, no. 6. [18] R. B. Jerard, R. L. Drysdale, K. Hauck, B. Schaudt, J. Magewick (1989) Methods for detecting errors in sculptured surface machining, IEEE Computer Graphics and Applications, Volume 9, pp 26-39, 1989. [19] J. C. Léon (1991) Modélisation et construction des surfaces pour la CFAO, Edition Hermes, France [20] G. Farin (1992) Courbes et surfaces pour la CGAO, Edition Masson, France [21] M. Daniel (1989) Modélisation de courbes et surfaces par des B-Spline, Application a la Conception et a la visualisation de formes “, These de Doctorat, Université de Grenoble, France [22] M. Dixon, M. Lima (1997) OpenGL programming guide, Addisson-Wesley Publishing Company Authors’ Addresses: Mohamed Bey Centre de Développement des Technologies Avancées - CDTA Cité 20 Aout 1956 BP N°17 Baba Hassen Algiers, Algeria bey_mohamed@yahoo.com Salim Boudjouad Nazim Tafat-Bouzid Université des Sciences et de la Technologie Houari Boumediene Algiers, Algeria Prejeto: Sprejeto: Odprto za diskusijo: 1 leto 22.12.2006 28.9.2007 Received: Accepted: Open for discussion: 1 year Določanje poti orodja površin nepravilnih oblik - Tool-Path Generation for Free-Form Surfaces 741