【溫馨提示】 dwg后綴的文件為CAD圖，可編輯，無水印，高清圖，，壓縮包內(nèi)文檔可直接點開預覽，需要原稿請自助充值下載，請見壓縮包內(nèi)的文件及預覽，所見才能所得，請細心查看有疑問可以咨詢QQ：414951605或1304139763
附錄
英文原文
The Pre-Processing of Data Points for Curve Fitting in Reverse Engineering
Reverse engineering has become an important tool for CAD model construction from the data points, measured by a coordinate 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 difficult to fit into a B-spline curve or surface. The paper presents a method for pre-processing data points for curve fitting in reverse engineering. The proposed method has been developed to process the measured data points before fitting into a B-spline form. The format of the new data points regenerated by the proposed method is suitable for the requirements for fitting into a smooth B-spline curve with a good shape. The entire procedure of this method involves filtering, curvature analysis, segmentation, regressing, and regenerating steps. The method is implemented and used for a practical application in reverse engineering. The result of the reconstruction proves the viability of the proposed method for integration with current commercial CAD systems.
Introduction
With the progress in the development of computer hardware and software technology, the concept of computer-aided technology for product development has become more widely accepted by industry. The gap between design and manufacturing 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 finished product, based on the geometric model. To realize the advantages of modern computer-aided technology in the product development and manufacturing 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 definition.
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 refine 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 modeling and/or updating .A physical mock-up or prototype is first 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 modeling reconstructs the surface of a region and combines these surfaces into a complete model representing the measured Part or prototype.
In practical measuring cases, however, there are many situations 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.
Fig. 1. The general problems in a practical measuring case
Measurement of an existing object surface in reverse engineering 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 undesired 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 fitting. Using the proposed method, the data points are regenerated in a specified format, which is suitable for fitting into a curve represented in B-spline form without the problems previously mentioned. After fitting all of the curves, the surface model can be completed by connecting the curves.
The Theory of B-spline
Most of the surface-based CAD systems express shapes required for modeling by parametric equations, such as in Bezier 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 Bezier curves have many advantages in common. Control points influence 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 exhibit 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 Bezier 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)= （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 defined by the following expression:
{ (2) and
(3)
Where k controls the degree (k-1) of the resulting polynomials in u and thus also controls the continuity of the curve.
A B-spline surface is defined in a similar way to a tensor product in a B-spline curve. It is also possible to define a B-spline surface having different degrees in the u- and v-directions:
(4)
Curve Fitting
Given a set of data points measured from existing object, curve fitting is required to pass through the data points. The least-squares fitting 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.
Given a set of data points Qk, k = 0,1,2,. . .,n, that lie on an unknown curve P for certain parameter values uk, k = 0,1,2,. . .,n; it is necessary to determine an exact interpolation or best fitting 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:
(5)
(6)
Given the parameter values, a knot vector that reflects the distribution of these parameters has the following form:
(7)
Fig.2. Curve fitting with unequal distribution of data points.
It can be proved that the coefficient 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.
Equation (5) can be written in a matrix form:
(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
(9)
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 fit 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 fit a set of data points into a B-spline curve, the data points must be read one by one in a specified 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 fitting. 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 influence the result of the measurement. All of these phenomena 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 parameter for fitting 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 ui which 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 fitting curve. As mentioned above, in practical measuring cases, the main surface of a physical sample often has some features such as
holes, islands, and radius fillets, which prevent the CMM probe from capturing data points with equal distribution. If a curve is rebuilt by fitting 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 fitting an equally spaced set of data points.
The Pre-Processing of Data Points
To achieve the requirements for fitting 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
Fig.3. Curve fitting with unequal distribution of data points.
Fig.4.The procedure of data points pre-processing
fitting. In the following description, a useful and effective method for pre-processing the data points for curve fitting 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 continuity of the curvature. For a plane curve, the explicit nonparametric equation takes the general form: y = f (x). Figure 4 illumination an overview of the procedure to pre-process the data points for reverse engineering.
Fig.5. Curvature is calculated by three discrete points on a circle.
Data point filtering is the first 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 complete model into individual simple surfaces. Each of the individual surfaces defines a single feature in a CAD system and a complete CAD model is obtained by further trimming, blending and filleting, or using other surface-processing tools. When the designer is given a set of unorganized data points measured from an existing object, data point segmentation is required to reconstruct a complete model by defining individual simple surfaces. Therefore, curvature analysis for the data points is used for subdividing the data points into individual group.
In order to extract the profile curves for CAD model reconstruction, 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 defined as:
(10)
If the data is expressed in discrete form, for any three consecutive points in the same plane (X1,Y1) · (X2,Y2) · (X3,Y3), the three points form a circle and the centre (X0, Y0) can be calculated as (see Fig. 5):
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)]
e = (Y1 + Y2) (Y2 - Y1) (X3 - X2)
f = (Y2 + Y3) (Y3 - Y2) (X2 - X1)
g = (X1 - X3) (X2 - X1) (X3 - X2)
Fig.6. The fillet of the model
Fig.7.The curvature change of the fillet
And,the curvature k of (X2,Y2) can be defined as:
(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 fillet 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 fitting can be achieved. The format of the new data point set is valid for fitting 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 figure 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 coefficient of the 5th-order item becomes zero. i.e. the ram’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 satisfied the demand for curvature continuity in CAD model construction for industrial applications.
Fig.8.The relationship between the order and the r.m.s. error.
Implementation
In order to prove the effectiveness and feasibility of the proposed method – the pre-processing of data points for curve fitting, an implemented case is developed following the steps of the flowchart (Fig. 9). A Mitutoyo BN706 coordinate measuring machine equipped with a Reni Shaw 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 applications, a commercial CAD system, Pro/Engineer, is integrated in the implementation. The overall configuration of the system components is shown in Fig. 10.
First, the cross-sectional curves describing the shape of the implemented sample are measured by the CMM. The physical object which is typically of symmetric geometry, as shown
Fig.9. The procedure of implemnation
in Fig. 11, is used in the implemented case. The CAD model of a symmetric object can easily be constructed by mirroring the symmetric features about the centerline. Therefore, some cross-sectional curves which are symmetric require only data for half the curve and then the other half can be mirrored to generate the complete curve. The result of the measurement is shown in Fig. 12.
When the measurement is completed, the individual data point sets representing different cross-sectional curves are processed separately. In this implemented case, the central cross-sectional curve is processed as an instance to demonstrate the procedure for pre-processing
Fig.10.Configuration of system components for implementation.
Fig.11.The physical model implementation
Fig.12.The result of measurement.
the data points, where 144 points are obtained in this curve, as shown in Fig. 13(a). In the data points filtering step, the noisy points and distinct discontinuous points, which obviously deviate from the group of data points, are removed directly for pre-processing. After filtering, the residual data consist of 132 points, as shown in Fig. 13(b). In order to segment the data points, the curvatures of the curve representing the residual data points are calculated and plotted in Fig. 14. As the surface of the implemented physical object is unrefined, the curvature determined by these measured points may greatly deviate from the original curve so that it is difficult to achieve curve segmentation. To obtain the apparent curvature variation, the measured points must be smoothed by the median method before curvature calculation. Figure 15 describes the algorithm
of the median method in which point x1￠, the new coordinate of point x1, is the average of point x0, x1 and x2, x1￠ = (x0 + x1 + x2)/3. The result of the curvature calculation of the new points, shown in Fig. 16, may be used to segment the curve roughly. Observing the change of curvature and considering the scheme of surface construction, these filtered points are divided into several groups which represent individual feature curves, including the top curve, the side curve, and the fillet curve, as shown in Fig. 13(c) (refer to Fig. 16).
Fig.13.The steps of pre-processing the data points of the central cross-sectional curve.
Fig.14.Curvature variation of the central cross-sectional
curve determined by original points.
Fig.15.Smoothing the distribution of points by the media method.
Fig.16.Curvature variati