Computer-Aided Design 36 (2004) 1219–1229 www.elsevier.com/locate/cad A new format for 5-axis tool path computation, using Bspline curves Jean Marie Langerona, Emmanuel Ducb,*, Claire Lartiguec,d, Pierre Bourdetd a Machining Solutions, Dassault Systèmes, 9 quai Marcel Dassault, BP 310, 92156 Suresnes, Cedex, France b LaRAMA, IFMA, Campus de Clermont Ferrand/Les Cézeaux, BP 265, 63175 Aubière, Cedex, France c IUT de Cachan, 9 av Division Leclerc, 94234 Cachan, Cedex, France d Lurpa, ENS de Cachan, 61 av du président Wilson, 94235 Cachan Cedex, France Received 22 July 2003; received in revised form 3 December 2003; accepted 10 December 2003 Abstract This article presents a new format of tool path polynomial interpolation in 5-axis machining. The linear interpolation usually used produces tangency discontinuities along the tool path, sources of decelerations of the machine tool whereas polynomial interpolation reduces the appearance of such discontinuities. The new format involves a faster tool path and a better surface quality. However, it imposes a modification of the process so as to take the interpolation format and the inverse kinematics transformation (necessary to 5-axis machining) into account. This article deals with the geometrical problem of tool path calculation. Validation tests are detailed. They show that profits concern the reduction of machining time as well as the quality of the machined surfaces. Indeed, the trajectory continuity avoids the appearance of marks and facets. q 2004 Elsevier Ltd. All rights reserved. Keywords: High speed milling; 5-axis machining; Bspline interpolation; Tool path computation 1. Introduction The purpose of the machining of free-form surfaces is to carry out complex shapes according to a given level of quality, while minimising machining time. This method of machining relates to mould and dies, aeronautics, or car industries. The manufacturing process consists of four main activities. The first one relates to the design of part surfaces using a CAD system in order to respect design requirements. The second activity consists in calculating the machining tool trajectory, according to the chosen machining strategy by means of a CAM system [1]. The machining strategy defines the geometrical characteristics that are necessary to carry out the machining. In addition to the geometry of the part surfaces and that of the tool, one chooses the machine tool, 3 or 5 axis, the machining type, point milling or flank milling, the machining direction and the longitudinal * Corresponding author. Tel.: þ33-4-73-28-80-96; fax: þ 33-4-73-2880-85. E-mail addresses: Jean-marie_langeron@ds-fr.com (J. M. Langeron); emmanuel.duc@ifma.fr (E. Duc); claire.lartigue@lurpa.ens-cachan.fr (C. Lartigue); pierre.bourdet@lurpa.ens-cachan.fr (P. Bourdet). 0010-4485//$ - see front matter q 2004 Elsevier Ltd. All rights reserved. doi:10.1016/j.cad.2003.12.002 and side step values. The latter are calculated according to the geometrical specifications, essentially form deviation and surface roughness. Then, the calculation algorithm calculates a set of tool positions defining the tool path by calculating tangent tool locations at the surface and by arranging them according to the longitudinal and side steps. The tool path is calculated considering the given type of tool path description format, to be read by the Numerical Control unit (NC unit). During the third activity, the post-processor ensures the translation of the APT program file to the ISO program file, in order to be treated by the NC unit. The last activity is the realisation of the part on the machine by the movement of the cutting tool. The machine tool is a mechanical system, generally using 3 or 5 axis of displacement. A NC unit controls the machine. In particular, the NC unit ensures the reading of the program, the calculation of movement and speed orders of each axis of the machine tool. The communication between these four activities goes through the definition of geometrical languages for the surface description (IGES, STEP, geometrical model of surfaces) and for the machining tool path (APT, ISO, interpolation format of the tool path). 1220 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 To improve part quality and to decrease machining time, the process must henceforth be adapted to High Speed Machining (HSM). In particular, the tool path calculation and its communication to the NC unit must take the dynamical behaviour of the machine tool and the real-time behaviour of the NC unit into account. Heisel and Feinauer indicate that the form of the calculated tool path and the interpolation format used generate constraints on the realtime follow-up of the tool path and may cause decelerations of the machine tool or appearance of chatters during machining [2]. If the tool path calculation and its communication to the NC unit are optimised, machining time is thus minimal while respecting quality requirements. To solve this problem, we consider that the CAM system must compute a C2 continuous tool path using polynomial curves. This improvement should increase the effective speed of the tool during machining in 3-axis as well as in 5axis machining of free-form surfaces. To evolve in this direction, NC units now propose to read polynomial or Bspline curves in 3-axis milling (Heindenhain, Siemens, Fanuc and Num for example). It is thus necessary to define a dedicated format for the communication of the tool path between the CAM system and the NC unit, for the APT format only considers linear and circular interpolation formats. CAM systems must evolve to propose tool path computation methods well adapted to this new format. However, in 5-axis the problem is more difficult since calculation methods must integrate the problem of the inverse kinematics transformation. This article presents a new format of tool path computation and interpolation for 5-axis machining, based on the Bspline interpolation of the tool path in the part coordinate system, respecting accuracy requirements. The goal is to define a 5-axis tool path description format, adapted to the communication between the CAM software and the NC unit. In this case, the CAM output is directly expressed through Bspline curves. We propose a calculation method allowing solving the computation problem. Generally the Bspline interpolation is used to build curve for CAD systems. Some works are related to the curve interpolation for NC machining, such as papers presented by Erkorkmaz, Cheng, Xu, Yeh, and Yong [3 –7]. Authors suggest to use tool path described as polynomial curves, to enhance the acceleration, speed and chord error control, during the real-time NC follow-up of the tool path. The main results consist in a smoother variation of the speed axis, a reduction of machining time and a diminution of the chordal error. Our approach does not consider real-time interpolation but it is only located at the CAM stage, and concerns the geometrical calculation of the tool path. To ensure the follow-up of the tool path, we use an adapted NC unit Siemens 840D. Many papers study the computation of tool path with curves in 5-axis milling. Only Fleisig and Spence presents an off line interpolation of the tool path [8]. In Section 3, we study the main difference between our both approaches. Section 2 exposes problems linked to 5-axis machining. Section 3 is dedicated to the presentation of the interpolation format we propose, and the method of calculation adopted. Section 4 relates comparison tests, which show that polynomial interpolation leads to important profits in terms of quality and machining time. 2. 5-Axis machining Five axis machining is carried out on machine tools which have two rotation axes (A; B or A; C or B; C) allowing the tool to be oriented relatively to the part in addition to the usual axes of translation X; Y; Z: Bohez presents the various types of machine structures [9]. In the present work, we are only interested in continuous 5axis machining, the most generally used for aeronautics parts. Continuous 5-axis machining is used for the surface milling with ball end or toroı̈dal cutter, and flank milling with cylindrical or conical cutter. Five axis machining poses two different types of problems. The first one can be described as geometrical. It relates to the tool path calculation in the part coordinate system (P-system) and also to the inverse kinematics transformation that is necessary to calculate position instructions of the 5-axis from the calculated tool path. The second type is mechanical and relates to both speed and acceleration calculation and control of the 5-axis using adapted laws. The most usual interpolation format of the tool path in 5-axis machining is the linear one. The tool path calculated using the CAM system is expressed in APT format and is transformed into ISO format by means of a post-processor. 2.1. Geometrical problem associated to the 5-axis tool path computation As the geometrical problem is concerned, the computing process of position instructions of the 5-axis can be divided in four stages. (1) Initially, the tool path is calculated as a set of tool positions and tool axis orientations in the given interpolation format. The tool path is expressed in the part coordinate system (P-system). To perform this step, various calculation algorithms are available in literature. Li, Takeuchi and Choi present such methods [10 –12]. Let us call Pi ; the ith tool position and Ai the ith tool axis orientation expressed in the P-system. If we consider two successive couples ðPi ; Ai Þ and ðPiþ1 ; Aiþ1 Þ; the tool is supposed to be moving in J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 straight line in the P-system. PðuÞ ¼ Pi þ uðPiþ1 2 Pi Þ AðuÞ ¼ Ai þ uðAiþ1 2 Ai Þ ; for 0 # u # 1 ð1Þ Successive couples are computed in order to respect a given deviation named machining tolerance. The distance between the computed tool path and the theoretical perfect tool path must be closer than the machining tolerance, along the tool path. (2) Instructions of the rotation axes are calculated from the previous set of tool axis orientations [13]. This calculation leads to solve a trigonometrical system, which can have zero, one, or several solutions in the space of authorised situations of the machine. (3) Next step is the calculation of the coordinates of the tool TIP in the machine coordinate system (M-system). The ISO program is generated. (4) The NC unit interprets the programmed locations of the 5-axis and axis orders are calculated according to dimensions of the tools and adjustments of the machine (Fig. 1). The inverse kinematics transformation relates to stages 2 and 3. Bohez presents a complete analysis of the inverse kinematics transformation [14]. The post-processor usually performs the inverse kinematics transformation during the translation stage of the APT file. The geometrical analysis of this transformation shows that the transformation is not linear from the P-system to the M-system. A linear movement of the tool expressed in the P-system is not transformed into a linear movement of the tool in the M-system. The same effect can be observed on the real speed of the tool relatively to the part. The speed of the tool relatively to the part is the subtraction of that of the tool relatively to the M-system minus that of the part relatively to the M-system (Eq. (2)). Vtool=part ¼ Vtool=M-system 2 Vpart=M-system ð2Þ To solve both problems, post-processors generally add tool locations on the initially calculated tool path so that 1221 the movement of the tool in the M-system is as close as possible to the ideal movement. The really treated tool path is thus computed at two stages: first, in the P-system by the CAM system, and second, in the M-system by the postprocessor. In the same way, the speed of each axis is programmed according to time inverse so that the programmed tool feedrate is respected. In this case, we consider that the post-processor is of major importance in the geometrical calculation of the tool path. As a result, the final error between the real tool path and the ideal one is the addition of the CAM computation error, the post-processor error and the NC follow-up error. Note that, the calculated tool path is adapted to a dedicated machine tool, with its own kinematics and its own NC unit. The change of machine tool involves a new calculation program. Furthermore, when changing interpolation format, it is necessary to modify the CAM calculation, the treatment of the NC unit, and the kinematics transformation carried out by the postprocessor. Henceforth, all these problems can be avoided with the use of new NC units for they can perform all tool path treatments in the P-system. Indeed, NC units carry out in real-time the tool path interpretation and the inverse kinematics transformation just after the tool location calculation (TRAORI function for Siemens 840D) [15]. The tool path calculated by the CAM system is directly transmitted to the NC unit. The role of the post-processor is only limited to the translation of the APT format into the ISO format. In this case, the geometrical transformation takes place for each calculation of a tool location order. Therefore, any interpolation format is seen the same way as regards the geometrical transformation. At this point, two complementary activities can be defined: † the CAM system calculates the tool path according to the specified machining tolerance in the P-system, † the NC unit carries out the interpretation and the follow-up of the tool path in the P-system, and calculates displacement and speed orders of the motion axes. Note that this configuration is well known in 2.5- or 3axis machining where the post-processor just ensures the necessary translation of languages. The integration of the inverse kinematics transformation at the level of the NC unit makes coherent the 5-axis machining with the 3-axis machining process, and makes also coherent the NC unit of the machine tools with that of robots. 2.2. Mechanical problems associated to the 5-axis tool path follow up Fig. 1. Tool path transformation from P-system to M-system. At the mechanical level, the problem relates to the performance of the rotation axes comparatively to 1222 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 the translation axes. For machines for which rotation axes are located on the table, axes have to move important masses and also support significant efforts during machining. As a result, they have low capacities of acceleration. When the machine has to slow down or to stop the tool movement, the speed reduction involves significant times of deceleration and re-acceleration. This effect appreciably increases machining time, and is amplified in HSM, because rotation axes must reach greater speeds. Therefore, it can be economically more interesting to machine in 3-axis at high speeds and a minimal number of decelerations, than in 5-axis. Decelerations generally appear when the tool path presents tangency or curvature discontinuities, or when the speed of the rotation axes abruptly evolve. To avoid producing marks on the part or generating a too large contour lag error, the NC unit decides to slow down, even to stop. Bloch details some aspects of the NC units well adapted to HSM [16]. Erkorkmaz shows that discontinuities are source of high frequency vibrations, which can excite the natural modes of the machine tool structure [3]. Contrary to machining with 3-axis, 5-axis machining at high speeds imposes good clockwork of all the axes, i.e. the most constant variation of the 5-axis movements between two programmed successive positions. The number of tool locations is increased to obtain the same distance between two successive positions, even if the machining tolerance is already respected. To remove tangency discontinuities, CAM systems must thus compute C2 continuous tool paths, as smooth as possible, without abrupt variations of the tool orientation. Basically, the linear interpolation commonly used only produces a C0 continuous tool path and seems not well adapted. Previous work showed profits in the part surface quality and in the management of speeds in 3-axis machining when using polynomial interpolation [17,18]. Consequently, the use of polynomial interpolation seems a factor of improvement in 5-axis HSM. Section 3 presents the interpolation format we have defined, based on the use of Bspline curves. 3. Polynomial interpolation in 5-axes be carried out in the part coordinate system (problem A before problem B) or in the machine coordinate system (problem B before problem A)? Concerning the case for which the tool path can be computed in the M-system, problem B before problem A, the computation is carried out by the NC unit from the CAM ISO data. Direct calculation in CAM supposes that the CAM system carries out the inverse kinematics transformation. For example, the movements of the axes X; Y; Z; A; C are defined using five polynomial curves expressed in the Msystem. As the other case is concerned, problem A before problem B, the CAM system fits a curve to a sub-set of ideal tool path positions. In other words, P and A are expressed in P-System, using Bspline Curves (Eq. (1)). At this stage, tool path discontinuities may simply be detected. The curve is directly transmitted to the NC unit, which interprets it before performing the inverse kinematics transformation. Therefore, this case seems well adapted to 5-axis machining using polynomial tool path. In Section 3.1, we consider that problem A is solved before problem B. The movement of the tool TIP and the tool axis orientation are expressed as polynomial curves in the P-system. The NC unit interprets the tool path, samples the tool path in the P-system and calculates the tool movement orders for each sampling period. 3.1. Description of the interpolation format: the 5xNurbs format We propose to describe the tool movement as follows. The tool movement is defined using the two parametric curves PðuÞ and QðuÞ: † PðuÞ ¼ ðXtðuÞ; YtðuÞ; ZtðuÞÞ; defines the locus of the tool TIP locations, † QðuÞ ¼ ðXhðuÞ; YhðuÞ; ZhðuÞÞ; defines the locus of a second point belonging to the tool axis. Note that this description is generic and allows the expression of the tool path for all types of machining 3- or 5axis, machining in point or flank milling and for all interpolation formats (Fig. 2). When using polynomial interpolation in 5-axis machining, two geometrical calculations are necessary, at the CAM and Post-processor stages: † problem A: computation of the tool path using a polynomial curve, † problem B: calculation of the inverse kinematics transformation. Here, the essential difficulty concerns the relative position of these two problems within the general process. In other words, does the calculation of the tool path have to Fig. 2. Definition of the tool path using the 5xNurbs format. 1223 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 The tool path is thus expressed like a polynomial function C of R towards R6 : C : R ! R6 0 XtðuÞ 1 0 1 C C B B C C B B B YtðuÞ C B PðuÞ C C C B B C C B B C C B B C B ZtðuÞ C B C C B B u ! CðuÞ ¼ B C with PðuÞ [ R3 C¼B C C B B C B XhðuÞ C B C C B B C C B B B YhðuÞ C B QðuÞ C C C B B A A @ @ i¼0 and QðuÞ [ R ð3Þ The calculation of the tool location relatively to the surface is led by a usual calculation of distance in metric space. By gathering the coordinates, we construct two curves PðuÞ and QðuÞ in the P-system. The two curves are computed so that their relative distance is equal to a length H: ’H [ R so that ;u; llQðuÞ 2 PðuÞll ¼ H ð4Þ The tool axis AðuÞ is thus calculated for each value of the u parameter by subtraction of the two curves: AðuÞ ¼ ðQðuÞ 2 PðuÞÞ=llQðuÞ 2 PðuÞll ð5Þ H corresponds to the height of the tool in flank milling and the diameter of the tool in point milling. It defines the size of the hull containing the tool. The direct computation of PðuÞ and AðuÞ curves can introduce gouging due to the size of the tool, whereas the computation of PðuÞ and QðuÞ take that into account. Considering a point located on the cutting area of the tool surface, for a given parameter u* ; its distance to the ideal tool location is less than the distance of the point Qðu* Þ to the ideal curve Q: Using this format, one can thus quantify the maximal distance between the side of the tool and the surface or the distance between the back of the tool and the part, when the use of PðuÞ and AðuÞ as defined in Eq. (1) does not permit them. Indeed, the length of AðuÞ is equal to 1. If the computation of the tool path gives an error equal to 0.01 mm for Aðu* Þ; then the real error is multiplied by H: Polynomial interpolation curves are non-uniform cubic Bsplines. Each one is defined by a set of ðn þ 1Þ control points and a knot sequence mj representing the variation of the parameter u along the curve. The degree m is equal to 3. Both curves P and Q present the same parameter setting in order to synchronise the two trajectories. n X Ni;m ðuÞPi with u [ ½m0 ; mnþmþ1  and Ni;mþ1; PðuÞ ¼ i¼0 spline functions QðuÞ ¼ n X ð6Þ Ni;m ðuÞQi with u [ ½m0 ; mnþmþ1  i¼0 and Ni;mþ1; spline functions i¼0 with u [ ½m0 ; mnþmþ1  ZhðuÞ 3 For each parameter u; the unit vector of the axis is obtained using the following relation  n n  X X   Ni;m ðuÞðQi 2 Pi Þ= Ni;m ðuÞðQi 2 Pi Þ AðuÞ ¼   ð7Þ ð8Þ Fleisig proposes a different method, for curve interpolation from a set of tool locations and orientation, using quintic spline and Bézier curves [8]. The tool path is then C3 continuous. The goal is to produce a constant feed and to reduce the angular acceleration. To compare with our method, PðuÞ is the position curve and ðQðuÞ 2 PðuÞÞ=llQðuÞ 2 PðuÞll is the orientation curve. Fleisig uses a near arc length parameterised quintic polynomial spline for the position curve and a near arc-length parameterised quintic spherical bezier curve for the orientation curve. A third spline is necessary for the re-parameterisation of both curves and the synchronization of the position and the orientation splines. In our method, both curves are defined with the same parameterisation and using the same Bspline format, and are calculated using the same algorithm at the same level. The use of the parameterisation curve is thus not necessary. The realtime computation of the tool location and the speed is ensured by the NC Unit Siemens 840D. However, the main difference consists in the choice of the initial tool location set. Fleisig has not concentrated on this issue, considering that the set of tool locations is given. With our approach, we select a set of tool locations from the whole theoretical tool path, defining an initial curve that fits the theoretical tool path while respecting a specified machining tolerance. Our algorithm is thus located at the CAM stage dedicated to the tool path computation. Section 3.2 details the calculation method of tool path as Bspline curves. 3.2. Method of tool path calculation The tool path calculation is carried out by interpolation of a set of particular positions of C2 continuous portions of the tool path. The tool path calculation is divided into four steps. (1) Whatever the tool geometry and the type of machining, the first step relates to the calculation of a tangent location of the tool on the surface. Calculation can be led according to algorithms proposed by Yu, Lee and Li in Refs. [19 –21]. (2) The second step relates to the organisation of the successive tool locations so as to respect the machining tolerance and according to the given interpolation format [22]. When using the polynomial interpolation, the tool path is calculated from a set of sampled positions belonging to the theoretical tool path. The tool path is thus calculated 1224 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 as polynomial curves so that the distance between the calculated tool paths to the theoretical one is lower than the specified machining tolerance while minimising the geometrical information sent to NC unit. (3) The next step concerns the tool path planning in the transversal direction according to the respect of the maximum transversal step or the maximum scallop height allowed. Lee proposes a calculation algorithm of the maximum step in 5-axis machining [23]. (4) The last step is dedicated to the detection of tool path discontinuities, which becomes essential in polynomial interpolation. Indeed, polynomial interpolation permits to associate C2 continuous curves to tool path portions. As a result, those portions must be at least C2 continuous, and tangency or curvature discontinuity points must be detected. Choi presents a method based on the comparison of the relative position of the tool centre’s points and contact points in 3-axis machining [24]. Duc proposes to isolate the portions from tool path having soft variation of curvature radius [25]. If the discontinuity point is not precisely detected, the CAM system must add interpolating points or control points in order to respect the machining tolerance. In this case, the calculated curve may present oscillations of great frequency and curve arcs of low lengths, which disturbs the follow-up of the tool path by the NC unit. Consequently, a tool path calculated and optimised for linear interpolation is not a good support for an accurate and optimal calculation of a tool path in polynomial interpolation. The method we develop relies on the interpolation of tool path portions using non-uniform cubic Bsplines. Each portion of the calculated tool path is a curve C of R6 (see Eq. (3)). C is solution of the problem of interpolation of a set of tool locations belonging to the theoretical tool path that exactly machines the surface. We use the method suggested by Piegl [26]. Note that the tool path interpolation problem is not the same than the curve interpolation problem, defined in CAD software. Our problem is not to compute a curve passing trough a set of points, but to compute a curve in a given format, which is an approximation of a theoretical curve. The calculated curve must be located in a pipe centred on the theoretical curve. The distance between both curves must be evaluated along the whole curve and be less than the given machining tolerance, which defines the radius of the pipe. In addition, the number of passing points must be minimal, in order to simplify the NC unit treatment. Let us consider a C2 continuous portion T of the theoretical tool path. In fact, T corresponds to two portions of C2 continuous curves, T1 and T2, describing the movement of the tool TIP and of another point of the tool axis, distant by H distance of the tool end (see Eq. (4)). Fig. 3 presents an example of such curve T1 or T2 (1). From T; we Fig. 3. Computation of the tool path. define a very fine sampling of tool locations, which implies the calculation of a great number of Mi positions of the tool along T (2). Each, position Mi is defined by six coordinates (Xti, Yti, Zti, Xhi, Yhi, Zhi). This sampling less than 0.1 mm is too fine to be directly sent to the NC unit. From the initial set, we select a sub-set of n Mi positions (3). The Mi positions are regularly distributed so as to minimise the number of interpolating points and in order to take curvature variations of the tool path into account. The selected set of Mi positions defines a broken line (4), which is an approximation of the theoretical tool path, respecting a given maximal chordal error. The maximal chordal error is greater than the machining tolerance, so that the number of chosen points is very small. The number and the locus of the Mi interpolating points depend on the form of the theoretical curve and on the given machining tolerance. Several distributions are possible, but the best one minimises the number of Mi positions and avoids the appearance of oscillations on the calculated curve. The calculated tool path (5) is computed by interpolation of the Mi points. The curve is accepted, when it is located in the pipe (6) centred on the theoretical curve (1), and which radius is equal to the machining tolerance (7). To ensure at least a C0 continuity at the junction points of the different curves, we impose that extremities must coincide. The problem of interpolation is solved according to the following steps [26]: † Parameter setting of the curve: the parameter ui of each Mi position is equal to the arc length of the Mi position on the curve T1; in order to obtain a near arc length parameterisation, † Calculation of the knot sequence: the knot sequence includes n þ 5 knots, which verify: m0 ¼ m1 ¼ m2 ¼ m3 ¼ 0; mnþ1 ¼ mnþ2 ¼ mnþ3 ¼ mnþ4 ¼ l; mjþ3 ¼ jþ2 1X u for j ¼ 1; …; n 2 3; 3 j i where l indicates the length of T1; † Construction of the problem of interpolation: for each Mi (Xti, Yti, Zti, Xhi, Yhi, Zhi) position, Mi belongs to the searched C curve and verifies: Mi ¼ n X j¼0 Nj;m ðui ÞPj ; for i ¼ 0; …; n ð9Þ J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 Eq. (9) leads to a linear problem of 6·ðn þ 1Þ equations for 6·ðn þ 1Þ unknowns (coordinates of the Pj control points). † Inversion of the problem and calculation of the control points of the curve C, † Checking the respect of the machining tolerance by calculation of the distance between the calculated curve and T: If the machining tolerance allowed is not respected, a refining of the sampling of the Mi positions is carried out. The verification of the respect of the machining tolerance is led by analysing the distance between a sampling of C and T, distance which is calculated according to the norm 1225 defined on the set of the functions of R in R6 : The computation is based on the calculation of the distance between a tool location X (X1ðx1; y1; z1Þ; X2ðx2; y2; z2Þ) of R6 (belonging to C) and the ideal curve. d6 ðX; TÞ ¼ MinðMaxðllX1; T1ðutÞll; llX2; T2ðutÞllÞ; ð10Þ for ut covering the interval of definition of T, ll ll indicates the Euclidean distance in R3 : The distance between the curves C and the T is thus obtained by Eq. (11) DðC; TÞ ¼ Maxðd6 ðCðucÞ; TÞ; for uc covering the interval of definition of C: Fig. 4. 5xNurbs format, example of program. ð11Þ 1226 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 This method we expose easily computes interpolation curves. However, the most significant interpolation errors are located at the extremities. To decrease error, tangents at the extremity points must be imposed. In the case of smooth aeronautic parts, this algorithm describes a 270 mm length tool path, using only one Bspline with six control points and three arcs, with a machining tolerance equal to 0.02 mm. This algorithm is integrated to the Catia CAD/CAM Software. Siemens has developed the Oricurve function to treat such curves. Fig. 4 presents an example of a tool path generated using the polynomial format. XT, YT, ZT and XH, YH, ZH are the coordinates of the control points, solution of the problem defined in Eqs. (3) and (9). The parameters DK and PL identify the variation of the knot sequence for each arc of the curve and W indicates the weight of the control point, which is equal to 1 for Bspline curves. 4. Applications Several test parts were defined and machined in order to estimate benefits brought by the polynomial interpolation. They are representative of different type cases in five continuous axes machining: † machining of a smooth surface with a toroidal cutter to maximise the covering rate, † machining of a cavity with a hemispherical tool to avoid collisions with the part, † machining of surfaces having the shape of a turbine blade. Machining was carried out on the Mikron UCP710 milling centre of Lurpa, equipped with a Siemens 840D NC unit adapted by Siemens to treat 5xNurbs tool paths. Cutting tools are carbide tools authorising a spindle speed of 15 000 rpm and feedrates variable between 2000 and 4000 mm/min. Due to the functionality of the Siemens NC unit, we have compared various modes of interpolation, the linear interpolation G1, the linear format interpolated in a polynomial curve in real-time by the NC unit (function compcad of the Siemens 840D) and the 5xNurbs interpolation. Two preliminary analyses were conducted. One concerns the length of elementary tool paths and the second one relates to the evolution of interpolation errors along the tool path. Following, real machining was carried out, and we have compared machining time and analysed real speed of the axes. Finally, the quality and the visual aspect of the machined parts were studied. Fig. 5. Part PM5X: computed tool path (Bspline/linear). for the 5xNurbs interpolation. All the tests showed that the polynomial interpolation makes it possible to decrease the number of geometrical information necessary to control the tool. Generally, a tool path portion not having discontinuity is expressed as only one C2 continuous Bspline curve from the beginning to the end of the portion. The elementary arc length is longer than that in linear interpolation. In Fig. 5, segment ends are represented as lines on the right for the linear interpolation (A). The ends of the 51 interior arcs of Bspline (1) are represented on the left for the Bspline tool path (B). The number of segments is strongly reduced. Fifty-four control points (2) define the curve, whereas 129 points are necessary for linear interpolation. The length of each arc is varying between 2 and 8 mm. The length of the arcs is reduced when the curvature radius of the tool path is reduced. The NC unit can thus read longer segments. The error between the computed curve and the theoretical one lies between 2 0.006 and 0.005 mm. The quality of the calculated tool path depends on the geometry of the surfaces to be machined and on the accuracy of the tool path calculation. When the surface presents tangency discontinuities, this may imply a non-optimised tool path calculation and may alter the performance of the NC unit. Initial surface must be C2 continuous. If a loss of accuracy during the interpolation is authorised at the points of connection is authorised, this may lead to a smoother movement and improve the performance of the NC unit. 4.1. Distribution of the arcs of curves 4.2. Kinematic analysis For this analysis, the length of each elementary tool path segment is evaluated. The elementary segment is a line segment for the linear interpolation and an arc of the Bspline The problem of the axis speed results from the treatment of the tool path by the NC unit. Indeed, NC must calculate J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 a speed law according to the motorization of each axis, taking the acceptable variations of contour lag error into account, and considering the response in vibration of the machine tool structure. The C1 continuity of the tool path and the interpolation format play a significant role. Theoretically, it is impossible to cross a C1 discontinuity with a non-null speed while ensuring a weak contour lag error. When the linear interpolation is chosen, either due to the form to be machined or to the tool path calculation, C1 discontinuities between successive elementary tool paths exist and the NC unit must use algorithms to detect such discontinuities and to smooth them. Considering the adaptation of the algorithm to the tool path, this treatment is more or less powerful. For our testing machine tool, rotation axes are less dynamic than translation axes. The machine is set with weak gain for the position control loop and a low value of the jerk to smooth the speed orders and to avoid marks on the parts. Similarly, each speed variation causes a significant increase of machining time essentially due to the significant deceleration time. The polynomial interpolation allows an important benefit in machining time, by eliminating C1 discontinuities of the tool path present in linear interpolation. As the tool path is C2 continuous, it is not necessary to slow down. The NC unit better interprets the tool path and only orders slow-downs when it is really necessary. Generally, the machine is more dynamic and the tool presents a more continuous, fast and smooth movement. The rotation axes can reach the ordered speed more quickly and maintain it for a longer period of time. The benefit is particularly significant on complex C2 continuous shapes that present great variations of curvature. Fig. 6 presents the evolution of the actual mean feedrate of machining in function of the interpolation format and the programmed feedrate. The use of Bspline curve multiplies the average feedrate by two. The polynomial interpolation, computed in real-time (function compcad) also allows a gain of approximately 300 mm/min. 1227 surface and the nominal surface) according to methods suggested by Jerard and Lartigue [27,28]. A grid of points is computed on the surface of the part. For each point, the straight line normal to the surface is computed and oriented outer of the part. A sampling of the tool path simulates the machining. The intersection between each line and each tool location and the associated distance are computed. For each line, the minimum value is kept. The variation of geometrical errors is more continuous when using the polynomial interpolation. Even if maximum error values are of the same magnitude order, the error is more homogeneous on great portions of the tool path. In case of the PM5X test, which presents the machining of a cavity (see Figs. 7 and 8), errors are concentrated on the connection between two surfaces. The interpolation of a tool path by a Bspline curve with a tolerance equal to 0.01 mm involves significant errors at the ends of the curves. The surfaces of the machined parts present the same defects. Marks due to the decelerations in linear interpolation and the A-blows speeds of the rotation axes are eliminated as for the facets appearing on large curvature radius (see Fig. 7). 4.3. Quality analysis To compare the two interpolation formats, we have simulated the machined surface and then evaluated geometrical deviations (deviations between the simulated Fig. 6. Part AI5X: measured average feedrate. Fig. 7. Part PM5X: simulation of the machining errors G1/5xNurbs. 1228 J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 dimensions into account. The model suggested in this article contains all geometrical information that is necessary to define algorithms for compensation (in particular the normal to the tool path for each tool position). In flank milling, it is sufficient to know if the part is on the left or on the right of the tool, and to develop algorithms for compensation of tool diameter variations. Further work will focus on this point. Acknowledgements The work presented in this article relates to the 5xNurbs project, which gathered Dassault Systèmes, Siemens, Cenit and Lurpa about the development of a new format of interpolation in 5-axis machining. References Fig. 8. Parts PM5X and AI5X: machined part, elimination of facets and marks. 5. Conclusion and prospects HSM requires to guarantee a high speed of the axes of the machine tool all tool path long. This depends on both the numerical controller capacities to calculate laws of optimal accelerations and the CAM system capacity to calculate accurate tool paths that are adapted to the NC unit treatment. This article presents a new description format of the tool path in 5-axis machining. This format uses non-uniform cubic Bspline curves and expresses the tool movement in the part coordinate system (P-system). The C2 continuity introduced by the interpolation format ensures a continuous evolution of the speed of rotation axes, which have lower capacities of acceleration. Test parts are machined, and permit to conclude on significant benefits in the reduction of machining time as well as on the quality of the machined surfaces. Indeed, the smoothness of the tool path avoids the appearance of marks or facets. Today, the part PM5X was machined on different 5axis machine tools, such as Mikron, Hermlé, Huron and Forest liné. In all cases, machining time is reduced. The reader can evaluate directly the performance and the interest of this method, using the CAM software Catia V5R12 SP2, from Dassault Systèmes and the NC software 840D 6.3 from Siemens. New research is now necessary to improve calculation of the curve of interpolation by decreasing the number of control points and by clearly identifying the points of discontinuity. Finding the best tool path, which respects the required quality and simplifies the dynamical treatment of the NC, is still an issue to be addressed. In addition, it becomes necessary to propose a method of tool compensation in order to take variations of tool [1] Choi B, Jerard R. Sculptured surface machining-theory and applications. Dordecht: Kluwer Academic Publishers; 1998. [2] Heisel U, Feinauer A. Dynamic influence on workpiece quality in high speed milling. CIRP Ann. Manuf Technol 1999;48(1):321–4. [3] Erkorkmaz K, Altintas Y. High speed CNC system design. Part I: jerk limited trajectory generation and quintic spline interpolation. Int J Mach Tools Manuf 2001;41:1323–45. [4] Cheng M-Y, Tsai M-C, Kuo J-C. Real time Nurbs command generators for CNC servo controllers. Mach Tool Manuf 2002;42: 801 –13. [5] Xu HY. Linear and angular feedrate interpolation for planar implicit curves. Comput-Aided Des 2003;35(3):301 –17. [6] Yeh S-S, Hsu P-L. The speed-controlled interpolator for machining parametric curves. Comput-Aided Des 1999;31(5):349–57. [7] Yong T, Narayanaswami R. A parametric interpolator with confined chord errors, acceleration and deceleration for NC machining. Comput-Aided Des 2003;35(13):1249–59. [8] Fleisig RV, Spence AD. A constant feed and reduced angular acceleration interpolation algorithm for multi-axis machining. Comput-Aided Des 2001;33(1):1 –15. [9] Bohez E. Five-axis milling machine tool kinematic chain design and analysis. Int J Mach Tools Manuf 2002;42:505–20. [10] Li F, Wang C, Ghosh SK, Kong DZ, Lai TQ, Wu XT. Tool-path generation for machining sculptured surface. J Mater Process Technol 1995;48:811–6. [11] Takeuchi Y, Watanabe T. Generation of 5 axis control collision free tool path and postprocessing for NC data. Ann CIRP 1992;41(1): 539 –42. [12] Choi BK, Park JW, Jun CS. Cutter-location data optimization in 5-axis surface machining. Comput-Aided Des 1993;25(6): 377 – 86. [13] Lin RS, Koren Y. Ruled surface machining on five-axis CNC machine tools. J Manuf Processes 2000;1(2). [14] Bohez E. Compensating for systematic errors in 5-axis NC machining. CAD 2002;34:391–403. [15] SINUMERIK 840D/840Di/810D Description of functions special functions (FB3). 09.01Edition. [16] Bloch S, Deneuville E, Tan L. Innovative feed rate optimisation technique, 3eme international congres on metal cutting and high speed Milling, Metz France. ; 2001. 10 p. [17] Valette L, Duc E, Lartigue C. A method for computation and assessment of NC tool-paths in free form curve format. Second Seminar of Improving Machine Tool Performance, La Baule; 2000. 18 p. J.M. Langeron et al. / Computer-Aided Design 36 (2004) 1219–1229 [18] Duc E, Lartigue C, Laporte S. Assessment of the description format of tool trajectories in 3-axis HSM of sculptured surfaces. In: Dudzinski D, Molinari A, Schluz H, editors. Metal cutting and high speed machining. Dordecht/New York: Kluwer Academic Publishers/ Plenum Press; 2002. [19] Yu D, Deng J, Duan Z, Liu J. Generation of gouge-free cutter location paths on freeform surfaces for non-spherical cutters. Comput Ind 1996;28:81–94. [20] Lee YS, Ji H. Surface interrogation and machining strip evaluation for 5-axis CNC die and mold machining. Int J Prod Res 1997;35(1): 225–52. [21] Li SX, Jerard RB. 5-axis machining of sculptured surfaces with a flatend cutter. Comput-Aided Des 1994;26(3):165–78. [22] Cho HD, Jun YT, Yang MY. Five-axis CNC milling for effective machining of sculptured surfaces. Int J Prod Res 1993;31(11): 2559–73. [23] Lee YS. Non isoparametric tool path planning by machining strip evaluation for 5 axis complex surface machining. Comput-Aided Des 1998;30(7):559–70. [24] Choi BK, Jun CS. Ball-end cutter interference avoidance in NC machining of sculptured surfaces. Comput-Aided Des 1989;21(6): 371–8. [25] Duc E. Usinage de formes gauches, contribution à l’amélioration de la qualité des trajectoires d’usinage. thèse de doctorat de l’ENS de Cachan-1998. [26] Piegl L, Tiller W. The Nurbs book. New York: Springer; 1997. [27] Jerard RB, Drysdale RL, Magewick J. Methods for detecting errors in numerically controlled machining of sculptured surfaces. IEEE Comput. Graphics Appl. 1989;26–39. [28] Lartigue C, Duc E, Tournier C. Free-form machining and geometrical specifications. J Engng Manuf 1999;13B:21–7. Jean Marie Langeron, graduated in 1986 of the French Aerospace Engeneering school of ENSMA (Ecole Nationale Supérieure de Mécanique et d’Aérotechnique) he joins the (Numerical Control) NC department of DASSAULT SYSTEMES in 1987. In charge of the Tool Path generator development team of CATIA NC for a long time, he is now Consultant Research and Development, directly attached to the Director Research and Development of the DELMIA and CATIA Machining Solutions. 1229 Emmanuel Duc is Assistant Professor at the French Institute for Advanced Mechanics (IFMA-Institut Français de Mécanique Avancée) of Clermont Ferrand. His research interests include the tool path computation for High Speed Milling, particularly in 5-axis machining and pocket machining. Computational methods are developed using Bspline curve, and experimental validations are tested on various machine tool. He has conducted many studies in aeronautics aera. Claire Lartigue is Professor at the department of Mechanical Engineering of IUT CachanUniversity of Paris XI. She is in charge of research activities in the fields of CAD/CAM and inspection of sculptured surfaces. These activities focus in particular on the assessment and the improvement of the geometrical quality of machined parts. An experimental laboratory consisting of a 5-axis HSM center and digitizing means contributes to the success of this research. Pierre Bourdet member of CIRP is a Professor at Ecole Normale Superieure in Cachan. This institution is a main place in France, which educate new teachers. Pierre Bourdet is doing researches at University Research Laboratory in Automated Production (LURPA). The domain of research concerns the tridimensional geometry for activities of design, manufacturing and inspection. The team’s research activities concerning three topic areas: algorithms for the assessment of measured points in co-ordinate metrology, geometrical quality of machined parts and model functional tolerancing for mechanism design.