在逆向工程中對適合曲線的數(shù)據(jù)點云的預(yù)處理外文翻譯@中英文翻譯@外文文獻(xiàn)翻譯

附錄 英文原文 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)= ,0 ()ni i ki p N u(0 1)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: , ()ilNu 10 ifotherwise 1i iu u u (2) and 1, ( ) , 1 1 , 111( ) ( )i i ki k u i k i ki k i i k iu u u uN N u N uu u u u (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: , , ,00( , ) ( ) ( )nmi j i p i qijS u v p N u N v (0 1)u (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: ,0( ) ( )nk k i i p kiQ P u p N u ( 0,1,., )kn (5) 12110 12110,ijjjinjjjQQuuQQ (6) Given the parameter values, a knot vector that reflects the distribution of these parameters has the following form: 12110 , 0 , . . . , 0 , , , . . . , , 1 , 1 , . . . , 1nppU V V V 11 jpjiijVup ( 1 , 2 , . . . , )j n p (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. , , 0 ,.,()i p k i k nNu 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 *1()TTP N N N Q (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: 223322221 ( )1dyfdxkfdydx (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): 0 a b cX d 0 e f gY d 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: 2211( ( 0 2 ) ( 0 2 )k r X X Y Y (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 rams. 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 variation of the central cross-sectional curve determined by new points Fig.17.The entir procedure of CAD model reconstruction After the segmentation step, individual groups of data points are separately regressed into explicit non-parametric equations. To eliminate the regression error caused by rough segmentation, remove several points at the start and end of each point group before regression. For example, the segmented points for the top curve are the 28th to 118th point, and the equation, regressing the 31st to the 115th point, can be obtained as 2 3 7 42 5 . 6 3 4 3 0 . 9 7 5 0 . 0 2 0 5 0 . 0 0 0 1 9 6 . 5 0 1 0Z X X X X (12) Depending on Eq. (12), the data points of the top curve can be regenerated with a well-ordered sequence, pre-determined spacing and equal distribution, as shown in Fig. 13(d). The result of pre-processing the original data point measured by the CMM allows smooth curves to be fitted to the regenerated data points. Points on a curve where the curvature is equal to zero are called inflection points. In some situations, there is more than one inflection point on a curve feature which can be applied to construct complex sculptured surfaces. For processing the data points fitting a single curve segment with multiple inflection points, a higher-order regression equation must be used to regress the data points in order to generate the shape of the curve. In applications of CAD, a curve-based modeling technique is widely applied in industry. The part is customarily divided into several cross-sections along a predetermined direction. Spatial curves for individual features are first fitted through the cross-sectional data points. By blending feature curves, the various surfaces can be constructed with the desired shape, using the different categories of surface construction schemes such as ruled surfaces, lofted surfaces, and Coons surfaces. A complex composite surface model is then constructed by combining these surfaces. When the entire pre-processing procedure is completed, the individual sets of regenerated data points can be transferred to a commercial CAD system (Pro/Engineer is applied here) via the IGES format. All of the feature curves on the measured object can be completely created by fitting different data points sets, which are represented in B-spline form, as shown in Fig. 13(e,f). Interpolating the feature curves, the various surfaces can be constructed with the desired shape. Finally, the complete CAD model, as shown in Fig. 17, is achieved by combining the various surfaces, for the further design operation or modification. Conclusion Geometric modeling is a technology that is already used extensively in industrial applications for developing new products. Reverse engineering has become an important tool for CAD model construction for an existing part from the measuring data. A major difficulty in reverse engineering techniques is to fit the irregular data points of an unequal distribution into a B-spline curve. The procedure of the pre-processing of data points for curve fitting in reverse engineering is described in this paper. The method proposed has been developed to process the data points measured from an existing object before curve fitting, and then new data points are regenerated which are suitable for the requirement for fitting into a smooth Bspline curve with a good shape. The entire procedure of this method involves filtering, curvature analysis, segmentation, regressing, and regenerating steps. The proposed method is implemented for practical applications in reverse engineering, and is an effective tool for integrating with current commercial CAD systems for reconstructing the geometric models of physical parts. A broader interpretation of the term “reverse engineering” might perhaps involve deducing the intent of the original designer to some degree. An ideal system of reverse engineering would be able to not only construct a complete geometric model of the source object but also catch the initial design intent. By applying the method proposed above, designers may regroup the data points in order to produce the individual feature curves for reconstructing a complete CAD model of the source object to achieve the original design intent. 中文翻譯 在逆向工程中對適合曲線的數(shù)據(jù)點云的預(yù)處理 逆向工程已經(jīng)成為一種從現(xiàn)存物體通過 CMM 測量的數(shù)據(jù)點重建 CAD 模型的重要工具 .在逆向工程中首要的問題是 :測量到的點具有不規(guī)律形式和不對等分布很難用 B-spline曲線擬合。這篇論文中介紹了一種在逆向工程中用預(yù)先處理數(shù)據(jù)點來擬合曲線的方法。適合 B-spline 形式之前來處理先前測量得到的數(shù)據(jù)點的方法已經(jīng)得到了發(fā)展。通過這種方法產(chǎn)生的新的數(shù)據(jù)點形式，適合建立光滑精確 B-spline 曲線的要求。這種方法的整個的步驟包括：切片，弧度分析，分割，回歸，和再生。在逆向工程中這種方法被實施和用于實踐應(yīng)用。重建的結(jié)果證實了此方法與目前流行的商業(yè) CAD 系統(tǒng)的結(jié)合能力。 隨著計算機(jī)硬件的軟件技術(shù)的發(fā)展，對促進(jìn)產(chǎn)品發(fā)展的計算機(jī)輔助技術(shù)觀念在工業(yè)領(lǐng)域已被廣泛地接受通過新的 CAD 技術(shù)的發(fā)展 ,設(shè)計和制造之間的間隙已逐漸變得越來越密切。在正常的自動化制造環(huán)境下操作順序經(jīng)常是通過用 CAD 系統(tǒng) 創(chuàng)建的幾何模型的產(chǎn)品設(shè)計開始，在幾何模型的基礎(chǔ)上，產(chǎn)生機(jī)器制造指令將原材料轉(zhuǎn)化成最終產(chǎn)品然后結(jié)束。由于意識到現(xiàn)代計算機(jī)輔助技術(shù)在產(chǎn)品發(fā)展和制造中的優(yōu)勢，因此在 CAD 系統(tǒng)著重要求創(chuàng)建物體的幾何模型。然而，在創(chuàng)建 CAD 模型之前，產(chǎn)品發(fā)展的物理模型和樣本先被產(chǎn)生出來。 例如，在設(shè)計汽車主體控制面板時，設(shè)計者和藝術(shù)家關(guān)于控制板的構(gòu)想到底是在什么樣的基礎(chǔ)上制造黏土模型。沒有最初的草圖，確切的記錄模型在哪里？在制造中由于設(shè)計的改變， CAD 模型不得不重新修改的部分哪里？ 在所有這些情形中。物理模型或樣本的建立是為了創(chuàng)建 和建立 CAD 模型。與這些常規(guī)的制造順序相反，典型的逆向工程從測量現(xiàn)存的物理實體開始，這樣推斷出來的 CAD模型可以更好的利用 CAD 技術(shù)的優(yōu)勢。逆向工程經(jīng)?？梢约?xì)分為 3個階段：電子數(shù)據(jù)獲取，數(shù)據(jù)分割，和用 CAD 模型構(gòu)建一個物理模型。樣本起先用 CMM 或激光掃描儀測量以得到以三維坐標(biāo)形式存在的幾何圖案的信息。然后，為了更進(jìn)一步的處理 ,測量結(jié)果被分割成拓?fù)錉?。就重建模型來說，每個小區(qū)域就代表一個簡單的可以用數(shù)學(xué)方面知識描繪其簡單外表的幾何圖案特征。 CAD 模型重建區(qū)域的表面是把這些表面連接成完整的可以描述被測量部分或 樣本的模型。 然而，在實際測量方案中，存在物理樣本或模型的幾何圖案信息不能被完全測量和準(zhǔn)確重建一個好的 CAD 模型的情況。一些表面測量的數(shù)據(jù)可能是不規(guī)律的，還有一些測量誤差或者表面是不要求的。如圖 1所示，測量物體的主要表面可能有這些特征：由于制造的不精確引起的凹坑，凸起，或噪聲點，因此， CMM 探針不能獲取一套完全的數(shù)據(jù)點來重建整個物體的表面。 圖 1.在一個實際測量情況中的一般的問題 在逆向工程中，現(xiàn)存實體的測量，可以通過接觸式測量或非接觸式測量技術(shù)來實現(xiàn)。然而無論用什么技術(shù)，這里都有一系列獲取數(shù)據(jù)的實際 問題，例如，噪聲和不完全數(shù)據(jù)。如果沒有簡單的程序去校對這些數(shù)據(jù)點。這些問題將引起令人不期望的 CAD 模型的重建問題。為了正確和滿意的重建 CAD 模型，這篇論文中介紹了一種先處理數(shù)據(jù)點去擬合曲線的有用和行之有效的方法，用這種方法，數(shù)據(jù)點被按指定的形式重新生成，并適合指定擬合 B-spline 曲線的形式，而沒有先前提到的問題。在擬合了所有曲線之后，模型的表面才可能完全和曲線結(jié)合起來。 B-spline 曲線理論 通過含參數(shù)的方程，絕大多數(shù)外觀基礎(chǔ)上的 CAD 系統(tǒng)都表達(dá)了構(gòu)造模型的要求， 如 Bezier 曲線或 B-spline 曲線形式，最長用的是 B-spline 形式，在目前商業(yè)系統(tǒng)中， B-spline 曲線是標(biāo)準(zhǔn)的代表自由曲線和外表的曲線。 B-spline 曲線和 Bezier 曲線有許多共同的優(yōu)勢。用可預(yù)測的普通方法來移動控制點影響曲線形狀，使它們兩者成了構(gòu)建曲面較好的曲線形式。這兩種不同類型的曲線都具有控制點少，獨立的對稱軸和綜合價值。都表現(xiàn)出了凸凹性。然而，在局部的控制曲線形狀這方面，可能 B-spline 曲線表現(xiàn)出的優(yōu)勢超過了 Bezier 技術(shù)。如增加控制點而沒有增加曲線的度數(shù)的能力?？紤]到現(xiàn)實世界中應(yīng)用 的要求，在這篇論文中 B-spline 技術(shù)被用來代表曲線和曲面。一條 B-spline 曲線設(shè)定了連接 n + 1 個 控點。通過下面的列子給出了一條含參數(shù)的 B-spline曲線： p(u)= ,0 ()ni i ki p N u(0 1)u （ 1） Pi=控制點 n+1=控制點數(shù) Ni,k(u)=B-spline 基本函數(shù) u=參數(shù) 對于 B-spline 曲線，這些變量參數(shù)的度數(shù)經(jīng)常通過參數(shù) K控制，它對應(yīng)控制點的數(shù)量。一條 B-spline 曲線基本功能通過下面的表達(dá)式來定義： (2) 和 1, ( ) , 1 1 , 111( ) ( )i i ki k u i k i ki k i i k iu u u uN N u N uu u u u (3) , , ,00( , ) ( ) ( )nmi j i p i qijS u v p N u N v (0 1)u (4) 擬合 如果從現(xiàn)存的數(shù)據(jù)中測量一些數(shù)據(jù)點，擬合曲線不許經(jīng)過數(shù)據(jù)點。 最新的擬合技術(shù)，用接近的算法規(guī)則，在迭代方法的基礎(chǔ)上，一系列數(shù)據(jù)點形成了 B-spline 曲線。假如一系列數(shù)據(jù)點，在一條不知道參數(shù)值的曲線 P中， K從 1到 N 決定一個準(zhǔn)確加入位置或者是好的擬合曲線 P是必要的。 為了解決這個問題，每個數(shù)據(jù)點的參數(shù)值必須被假定出來。矢量的節(jié)點和曲線的度數(shù)也是要求的。在實際應(yīng)用中度數(shù)一般都是 3，參數(shù)值的確定可以通過下面的方法： ,0( ) ( )nk k i i p kiQ P u p N u ( 0,1,., )kn (5) 12110 12110,ijjjinjjjQQuuQQ (6) 如果給定參數(shù)值，反映這些參數(shù)分布的節(jié)點如下面的形式： 12110 , 0 , . . . , 0 , , , . . . , , 1 , 1 , . . . , 1nppU V V V 11 jpjiijVup ( 1 , 2 , . . . , )j n p (7) 點如下面的形式： Q NP (8) *1()TTP N N N Q (9) 圖 2.曲線與真實測量物體的形狀不符 . 適合 B-Spline 曲線的數(shù)據(jù)要求 為了生成一條光滑準(zhǔn)確的 B-Spline 曲線，還要求一系列數(shù)據(jù)點能適合呈現(xiàn)出的 B-Spline 形 式的曲線特征。首先，數(shù)據(jù)必須有較好的排列順序。當(dāng)應(yīng)用程序為了使一系列數(shù)據(jù)點能適合 -Spline 曲線，這些數(shù)據(jù)點必須以指定的順序讀入。如果數(shù)據(jù)點不是按順序的，這將引起未預(yù)期的曲線或一條失去 B-Spline 曲線形狀控制的曲線。其次，均勻分布數(shù)據(jù)點對擬合曲線來說是比較好的。在實際的測量中，一些因素如機(jī)器的顫抖，系統(tǒng)中的噪音，和被測量物體表面的粗糙，這都將影響測量的結(jié)果。所有這些現(xiàn)象都將引起在經(jīng)過問題點的曲線的局部顫抖。因此，對于產(chǎn)生一個高質(zhì)量的 B-Spline 曲線，光滑有序的點云數(shù)據(jù)是必須的。 獲得均勻分布的數(shù)據(jù) 點，可以提高擬合 B-Spline 曲線參數(shù)的結(jié)果。就象在方程式（ 9）中數(shù)學(xué)方面所展示的那樣，通過和數(shù)據(jù)點分布一致的參數(shù) UI決定的基本函數(shù)和數(shù)據(jù)點，確定了控制點。如果數(shù)據(jù)是不均勻的，這些控點也會分布不均勻還將引起擬合曲線的不平滑。正如上面所提及到的，在實際案例測量中一個物體模型經(jīng)常有一些諸如空洞，內(nèi)凹和小范圍的切片，這些都將阻止 CMM 探針獲得均勻分布的數(shù)據(jù)點。如果一條曲線不是用均勻分布的數(shù)據(jù)點擬合重建的，就像圖 2中所示，產(chǎn)生的曲線會和真實測量物體的形狀不符。圖 3說明了更光滑和更準(zhǔn)確的重建可以通過一系列均勻分布的 空間數(shù)據(jù)點獲得。 圖 3.曲線與真實測量物體的形狀相同 圖 4.數(shù)據(jù)點預(yù)處理 數(shù)據(jù)點預(yù)處理 正如上面所述，為了達(dá)到使一系列數(shù)據(jù)點適合 B-spline 曲線的要求，在擬合曲線之前，對數(shù)據(jù)點進(jìn)行預(yù)處理是非常重要和必須的。在下面的描述中，將介紹有種對擬合曲線有用而且有效的的數(shù)據(jù)預(yù)處理辦法，這種辦法的構(gòu)想是：用絕對的或明確的形式將一系列測量結(jié)果設(shè)為不含參數(shù)的方程式，這些方程式必須滿足曲率的連續(xù)性，對于一個飛機(jī)模型，一個明確的不含參數(shù)方程式的一般形式： 圖 5.曲率是通過在圓里的三個離散的點來計算的 圖示說 明，一個總的逆向工程中預(yù)處理數(shù)據(jù)點的程序。數(shù)據(jù)點的移動第一步是刪除不需要和不規(guī)則的數(shù)據(jù)點。通過 CMM 從物理模型和現(xiàn)存模型測量的原始數(shù)據(jù)點是離散形式的，當(dāng)這些測量的點用圖表示出來時，明顯偏離原始曲線的數(shù)據(jù)點，可通過設(shè)計者的一般處理和可見的搜尋能被有選擇的剔除掉。此外，為進(jìn)一步處理清晰的不連續(xù)的在形狀上急轉(zhuǎn)變化的點，可以很容易的把他們分開。 逆向工程中，從測量點中產(chǎn)生一個 CAD 模型已經(jīng)發(fā)展了很多種途徑。一個復(fù)雜的模型經(jīng)常要通過將完整的模型細(xì)分成單獨的簡單模型來構(gòu)建。在一個 CAD 系統(tǒng)中，每一個單獨的表面定義了一個 簡單的特性。一個完整的的 CAD 模型就可以通過更進(jìn)一步的修整，融合，整合獲得，或者用其他的表面處理工具。當(dāng)一個設(shè)計者把從存在的物體中測量的一系列數(shù)據(jù)進(jìn)行細(xì)分時，要求通過定義單獨的簡單表面來重新構(gòu)建一個完整的模型。 因此，數(shù)據(jù)點的曲率分析被用來將細(xì)分的的數(shù)據(jù)點歸成單獨的小類。 為了提煉出再建的 CAD 模型，在這一步中，依據(jù)曲率推算和數(shù)據(jù)點分析的結(jié)果，數(shù)據(jù)點被歸為不同的類，如一個 2維作標(biāo)的曲線， y=f(x)，曲線被定義如下： 223322221 ( )1dyfdxkfdydx (10) 如果數(shù)據(jù)用離散的形式表示出來，同一架飛機(jī)中任何三個不連續(xù)的點（ X1,Y1），(X2,Y2)(X3,Y3)，這三點形成一平面和一個中心 (X0,Y0)。如圖 5. 0 a b cX d 0 e f gY d a = (X1 + X2) (X2 - X1) (Y3 - Y2) b = (X2 + X3) (X3 - X2) (Y2 - Y1) c = (Y1 - Y3