英文資料.pdf

Int J Adv Manuf Technol (2000) 16:635642 2000 Springer-Verlag London Limited The Pre-Processing of Data Points for Curve Fitting in Reverse Engineering Ming-Chih Huang and Ching-Chih Tai Department of Mechanical Engineering, Tatung University, Taipei, Taiwan Reverse engineering has become an important tool for CAD model construction from the data points, measured by a coordi- nate measuring machine (CMM), of an existing part. A major problem in reverse engineering is that the measured points having an irregular format and unequal distribution are diffi - cult to fi t into a B-spline curve or surface. The paper presents a method for pre-processing data points for curve fi tting in reverse engineering. The proposed method has been developed to process the measured data points before fi tting into a B- spline form. The format of the new data points regenerated by the proposed method is suitable for the requirements for fi tting into a smooth B-spline curve with a good shape. The entire procedure of this method involves fi ltering, curvature analysis, segmentation, regressing, and regenerating steps. The method is implemented and used for a practical application in reverse engineering.Theresultof thereconstructionprovesthe viability of the proposed method for integration with current commercial CAD systems. Keywords: Curve fi tting; Pre-processing ofdatapoints; Reverse engineering 1.Introduction With the progress in the development of computer hardware and software technology, the concept of computer-aided tech- nology for product development has become more widely accepted by industry. The gap between design and manufactur- ing is now being gradually narrowed through the development of new CAD technology. In a normal automated manufacturing environment, the operation sequence usually starts from product design via geometric models created in CAD systems, and ends with the generation of machining instructions required to convert raw material into a fi nished product, based on the geometric model. To realise the advantages of modern com- Correspondence and offprint requests to: Ming-Chih Huang, Depart- ment of Mechanical Engineering, Tatung University, 40 Chungshan N Road, 3rd Section, Taipei 104, Taiwan. E-mail: mindyKmgher. .tw puter-aided technology in the product development and manu- facturing process, a geometric model of the part to be created in the CAD system is required. However, there are some situations in product development in which a physical model or sample is produced before creating the CAD model: 1. Where a clay model, for example, in designing automobile body panels, is made by the designer or artist based on conceptual sketches of what the panel should look like. 2. Where a sample exists without the original drawing or documentation defi nition. 3. Where the CAD model representing the part has to be revised owing to design change during manufacturing. In all of these situations, the physical model or sample must be reverse engineered to create or refi ne the CAD model. In contrast to this conventional manufacturing sequence, reverse engineering typically starts with measuring an existing physical object so that a CAD model can be deduced in order to exploit the advantages of CAD technologies. The process of reverse engineering can usually be subdivided into three stages, i.e. data capture, data segmentation and CAD modelling and/or updating 1,2. A physical mock-up or prototype is fi rst measured by a coordinate measuring machine or a laser scanner to acquire the geometric information in the form of 3D points. The measured results are then segmented into topological regions for further processing. Each region represents a single geometric feature that can be represented mathematically by a simple surface in the case of model reconstruction. CAD modelling reconstructs the surface of a region and combines these surfaces into a complete model representing the measured part or prototype 3. In practical measuring cases, however, there are many situ- ations where the geometric information of a physical prototype or sample cannot be measured completely and accurately to reconstruct a good CAD model. Some data points of the measured surface may be irregular, have measurement errors, or cannot be acquired. As shown in Fig. 1, the main surface of measured object may have features such as holes, islands, or roughness caused by manufacturing inaccuracy, consequently the CMM probe cannot capture the complete set of data points to reconstruct the entire surface. 636M.-C. Huang and C.-C. Tai Fig. 1. The general problems in a practical measuring case. Measurement of an existing object surface in reverse engin- eering can be achieved by using either contact probing or non- contact sensing probing techniques. Whatever technique is applied, there are many practical problems with acquiring data points, for examples, noise, and incomplete data. Without extensive processing to adjust the data points, these problems will cause the CAD model to be reconstructed with an unde- sired shape. In order to rebuild the CAD model correctly and satisfactorily, this paper presents a useful and effective method to pre-process the data points for curve fi tting. Using the proposed method, the data points are regenerated in a specifi ed format, which is suitable for fi tting into a curve represented in B-spline form without the problems previously mentioned. After fi tting all of the curves, the surface model can be completed by connecting the curves. 2.The Theory of B-spline Mostofthe surface-basedCAD systemsexpress shapes required for modelling by parametric equations, such as in Be zier or B-spline forms. The most used is the B-spline form. B-splines are the standard for representing freeform curves and surfaces in current commercial CAD systems. B-spline curves and Be zier curves have many advantages in common 4. Control points infl uence the curve shape in a predictable, natural way, making them good candidates for use in an interactive environment. Both types of curve are variation diminishing, axis independent, and multivalued, and both exhi- bit the convex hull property. However, it is the local control of curve shape which is possible with B-splines that gives the technique an advantage over the Be zier technique, as does the ability to add control points without increasing the degree of the curve. Considering the real-world applications requirement, the B-spline technique is used to represent curves and surfaces in this research. A B-spline curve is a set of basis functions which combines the effects of n + 1 control points. A parametric B-spline curve is given by p(u) =O n i=0 piNi,k(u)(0 # u # 1)(1) Pi= control points n + 1 = number of control points Ni,k(u) = the B-spline basis functions u = parameter For B-spline curves, the degree of these polynomials is controlled by a parameter k and is usually independent of the number of control points, and the B-spline basis functions are defi ned by the following expression: Ni,1(u) =H1 if u i# u # ui+1 0 otherwise (2) and Ni,k(u) = u ui ui+k ui Ni,k1(u) + ui+k+1 u ui+k+1 ui+1 Ni+1,k1(u)(3) Where k controls the degree (k1) of the resulting poly- nomials in u and thus also controls the continuity of the curve. A B-spline surface is defi ned in a similar way to a tensor product in a B-spline curve. It is also possible to defi ne a B-spline surface having different degrees in the u- and v-direc- tions: S(u,v) =O n i=0 O m j=0 pijNi,p(u) Ni,q(v)(0 # u # 1)(4) 3.Curve Fitting Given a set of data points measured from existing object, curve fi tting is required to pass through the data points. The least-squares fi tting technique is the most used algorithm which aims at approximating, based on an iterative method, a set of data points to form a B-spline 57. Given a set of data points Qk, k = 0,1,2,. . .,n, that lie on an unknowncurvePforcertainparametervaluesuk, k = 0,1,2,. . .,n; it is necessary to determine an exact interp- olation or best fi tting curve, P. To solve this problem, the parameter values (uk) for each of the data points must be assumed. The knot vector and the degree of the curve are also determined. The degree in practical applications is generally 3 (order = 4). The parameter values can be determined by the chord length method: Qk P(uk) =O n i=0 piNi,p(uk)(k = 0,1,. . .,n)(5) u0= 0,ui= O i j=1 uQj Qj1u. O n j1 uQj Qj1u. (6) Given the parameter values, a knot vector that refl ects the distribution of these parameters has the following form: U = 0,0,. . .,0, V1,V2,. . .,Vn,1,1,. . .,1 p+1 p+1 Vj= 1 p O j+p1 i=j ui(j = 1,2,. . .,np)(7) Pre-Processing of Data Points for Curve Fitting637 Fig. 2. Curve fi tting with unequal distribution of data points. It can be proved that the coeffi cient matrix is totally positive and banded with a bandwidth of less than p, therefore, the linear system can be solved safely by Gaussian elimination without pivoting. Ni,p(uk) ui,k=0,. . .,n Equation (5) can be written in a matrix form: Q NP(8) where Q is an (m + 1) 1 matrix, N is an (m + 1) (n + 1) matrix, and P is an (n + 1) 1 matrix. Since m . n, this equation is over-determined. The solution is P* = (NTN)1NTQ(9) 4.The Requirement for Fitting a Set of Data into a B-Spline Curve In order to produce a B-spline curve with a “good shape”, some characteristics are required to fi t the data point set into a curve presented in B-spline form. First, the data points must be in a well-ordered sequence. When applying the program to fi t a set of data points into a B-spline curve, the data points must be read one by one in a specifi ed order. If the data points are not in order, this will cause an undesired twist or an out-of-control shape of the B-spline curve. Secondly, an even dispersion of the data points is better for curve fi tting. In the measuring procedure, some factors, such as the vibration of the machine, the noise in the system, and the roughness of the surface of the measured object will infl uence the result of the measurement. All of these phenom- ena will cause local shakes in the curve which passes through the problem points. Therefore, a smooth gradation of the location of the data points is necessary for generating a “high quality” B-spline curve. Having the data points equally distributed is important for improving the result of parameterisation for fi tting a B-spline curve. As the mathematical presentation shows in Eq. (9), the control points matrix P is determined by the basis functions N and data points Q, where the basis functions N are determined by the parameters uiwhich are correspond to the distribution of the data points. If the data points are distributed unequally, the control points will also be distributed unequally and will cause a lack of smoothness of the fi tting curve. As mentioned above, in practical measuring cases, the main surface Fig. 3. Curve fi tting with equal distribution of data points. Fig. 4. The procedure of data points pre-processing. of a physical sample often has some features such as holes, islands, and radius fi llets, which prevent the CMM probe from capturing data points with equal distribution. If a curve is rebuilt by fi tting data points with an unequal distribution, as shown in Fig. 2, the generated curve may differ from the real shape of the measured object. Figure 3 illustrates that a smoother and more accurate reconstruction may be obtained by fi tting an equally spaced set of data points. 5.The Pre-Processing of Data Points To achieve the requirements for fi tting a set of data points into a B-spline curve as mentioned above, it is very important and necessary that the data points must be pre-processed before curve fi tting. In the following description, a useful and effective method for pre-processing the data points for curve fi tting is presented. The concept of this method is to regress a set of measuring data points into a non-parametric equation in implicit or explicit form, and this equation must also satisfy the conti- nuity of the curvature. For a plane curve, the explicit non- parametric equation takes the general form: y = f(x). Figure 4 638M.-C. Huang and C.-C. Tai Fig. 5. Curvature is calculated by three discrete points on a circle. illustrates an overview of the procedure to pre-process the data points for reverse engineering. Data point fi ltering is the fi rst step in displacing the unwanted points and the noisy points. The original data points measured from a physical prototype or an existing sample by a CMM are in discrete format. When the measured points are plotted in a diagram, the noisy points which obviously deviate from the original curve can be selected and removed by a visual search by the designer for extensive processing. In addition, the distinct discontinuous points which apparently relate to a sharp change in shape may also be separated easily for further processing. Many approaches have been developed for generating a CAD model from measured points in reverse engineering. A complex model is usually constructed by subdividing the com- plete model into individual simple surfaces 8,9. Each of the individual surfaces defi nes a single feature in a CAD system and a complete CAD model is obtained by further trimming, blending and fi lleting, or using other surface-processing tools. When the designer is given a set of unorganised data points measured from an existing object, data point segmentation is required to reconstruct a complete model by defi ning individual simple surfaces. Therefore, curvature analysis for the data points is used for subdividing the data points into individual groups. In order to extract the profi le curves for CAD model recon- struction, in this step, data points are divided into different groups depending upon the result of curvature calculation and analysis of the data points. For each 2D curve, y = f(x), the curvature is defi ned as: k = d2y dx2 F1 +Sdy dxD 2G3/2 = f 1 + (f)23/2 (10) If the data is expressed in discrete form, for any three consecutivepointsinthesameplane (X1,Y1) (X2,Y2) (X3,Y3), the three points form a circle and the centre (X0,Y0) can be calculated as (see Fig. 5): X0 = a b + c d Y0 = e f + g d where a = (X1 + X2) (X2 X1) (Y3 Y2) b = (X2 + X3) (X3 X2) (Y2 Y1) c = (Y1 Y3) (Y2 Y1) (Y3 Y2) d = 2(X2 X1) (Y3 Y2) (X3 X2) (Y2 Y1) Fig. 6. The fi llet of the model. Fig. 7. The curvature change of the fi llet. e = (Y1 + Y2) (Y2 Y1) (X3 X2) f = (Y2 + Y3) (Y3 Y2) (X2 X1) g = (X1 X3) (X2 X1) (X3 X2) And, the curvature k of (X2, Y2) can be defi ned as: k = 1 r = 1 (X0 X2)2+ (Y0 Y2)2) (11) Figure 6 illustrates an example in which the curvatures of a plane curve consisting of a data point set are calculated using the previous method. The curvature of the curve determined by the data point set changes from 0 to 0.0333, as shown in Fig. 7. This indicates that there is a fi llet feature with a radius 30 in the data points set. Thus, these points can be isolated from the original data points, and form a single feature. By curvature analysis, the total array of data points is divided into several groups. Each of these groups is a segmented form of the original data points which is devoid of any sharp change in shape. After segmentation, individual groups of data points are separately regressed into explicit non-parametric equations, and then the data points can be regenerated from the regression equation in a well-ordered sequence, with appropriate spacing and an equal distribution so that better fi tting can be achieved. The format of the new data point set is valid for fi tting into a single simple B-spline curve without inner constraints, which can be applied for further editing and modifying, such as trimming and extending. By combining individual curves to construct all of the surfaces, designers may effortlessly achieve a complete CAD model conforming to the design intent. Additionally, some regression errors are introduced by the regression operation between the measured points and the regression equation. In the following example, the order of the regression equation is discussed, because it bears a close relationship to the regression errors. Given a set of existing data points, the set is regressed using a different order of the regression (order = 2,3,4,5). Figure 8 illustrates the relationship between the order of the regression equations and the regressed errors calculated by the root-mean-square (r.m.s.) method. This Pre-Processing of Data Points for Curve Fitting639 Fig. 8. The relationship between the order and the r.m.s. error. Fig. 9. The procedure of implementation. fi gure shows that increasing the equation order causes a decrease of the r.m.s. error. However, in most cases, when the 5th-order of the regression equation is used, the coeffi cient of the 5th-order item becomes zero. i.e. the r.m.s. error of the 4th-order equation is equal to the 5th-order equation. This means that the designer only has to regress the data points into a 4th-order equation. In practice, a 4th-order equation has already satisfi ed the demand for curvature continuity in CAD model construction for industrial applications. 6.Implementation In order to prove the effectiveness and feasibility of the proposed method the pre-processing of data points for curve fi tting, an implemented case is developed following the steps of the fl owchart (Fig. 9). A Mitutoyo BN706 coordinate measuring machine equipped with a Renishaw PH9 touch probe and SAS statistics software is used as a tool for system implementation. The measurement of the part surface is performed via standard CMM control and measurement software (Geopak 2800). To ensure that the proposed method is useful for practical appli- cations, a commercial CAD system, Pro/Engineer, is integrated Fig. 10. Confi guration of system components for implementation. Fig. 11. The physical m