CN104238457B - A kind of computation complexity adaptive nurbs curve interpolating method - Google Patents

Abstract

The present invention relates to the interpolated point computing technique of digital control system, specifically computation complexity adaptive nurbs curve interpolating method.By analyzing the de Boor Cox method computation structure when calculating interpolation point, set up the computation complexity formula that interpolated point solves；Abbreviation Basis Function Method calculates computation structure during interpolation point, reduces computation complexity by shared intermediate object program, and sets up the computation complexity formula of Basis Function Method solution procedure；Set up performance judgment formula when de Boor Cox method and Basis Function Method calculating interpolation point, when curve interpolating, dynamically select the method that computation complexity is low to carry out interpolation by described performance judgment formula.Application the inventive method can effectively share the intermediate object program during base function algorithn calculates, and reduces the computation complexity of algorithm, it is possible to the efficient interpolation algorithm of selection of dynamic self-adapting, improves the interpolation efficiency of nurbs curve.

Description

A kind of computation complexity adaptive nurbs curve interpolating method

Technical field

The present invention relates to the interpolated point computing technique of digital control system, the specifically adaptive NURBS of computation complexity Curve interpolating method.

Background technology

1991 International Organization for Standardization (ISO) at the product model data exchange standard of industrial products geometric definition Using NURBS as free type song in (standard for the exchange of product model data, STEP) Line, unique representation of curved surface.Along with STEP-NC(ISO14649) formulation of standard, nurbs curve, song in digital control system The research of face direct interpolation technology gradually increases.Owing to nurbs curve cannot represent with unified analytic expression, thus exist curve, The high problem of computation complexity that curved surface interpolation point calculates, when causing interpolated point to calculate, needs consume a significant amount of calculation time, and affect The raising of working (machining) efficiency.Therefore, reducing the complexity that interpolated point calculates, to improving, process velocity is most important.

Existing interpolated point computational methods are broadly divided into following several: one is to use iterative manner to solve, this side of solving Formula is prone to realize with computer, but average computation complexity is the highest.Two is to be solved by Basis Function Method, each base in solution procedure Function evaluation only need to calculate once, but there is basic function and solve computationally intensive and calculate the problem that intermediate object program is shared. Three is by de-Boor Cox Algorithm for Solving, The method avoids the calculating of B-spline basic function, by control point direct iteration Calculating, the average computation complexity that interpolated point calculates is minimum, but algorithm performance there will be ripple with the change of nurbs curve parameter Dynamic, under extreme case, performance is minimum.

Summary of the invention

For the respective weak point of existing interpolation algorithm, the technical problem to be solved in the present invention is to provide one can root According to the requirement of nurbs curve parameter, by dynamically selecting interpolated point computational algorithm to reduce computation complexity, improve interpolation efficiency Method.

The present invention be the technical scheme is that a kind of adaptive NURBS of computation complexity is bent for achieving the above object Line interpolating method, comprises the following steps:

By analyzing the de Boor-Cox method computation structure when calculating interpolation point, set up the calculating that interpolated point solves multiple Miscellaneous degree formula；Abbreviation Basis Function Method calculates computation structure during interpolation point, reduces computation complexity by shared intermediate object program, and Set up the computation complexity formula of Basis Function Method solution procedure；

Set up performance judgment formula when de Boor-Cox method and Basis Function Method calculating interpolation point, when curve interpolating, logical Crossing described performance judgment formula dynamically selects the method that computation complexity is low to carry out interpolation.

The computation complexity formula that described de Boor-Cox method interpolated point solves is m value when being 1 or 2, curve interpolating institute Need the total degree of multiplication and division computing:

D(k,n,1)=2^k+3-9, m=1 (2)

D(k,n,2)=2^k+3+2^k-12, m=2 (3)

Wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is the high reps of derivative in calculating process.

The computation complexity formula of described Basis Function Method solution procedure is m value when being 1 or 2, multiplication and division needed for curve interpolating The total degree of method computing:

B(k,n,1)=2^k+1+4n²+ 17n+k+11 (4)

B(k,n,2)=2^k+1+10n²+ 42n+8k+20 (5)

Wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is the high reps of derivative in calculating process.

Described performance judgment formula is

F (k, n, m)=D (k, n, m)/B (k, n, m)-1 (6)

Wherein, function f (k, n, m) represent de Boor-Cox method algorithm compared with the performance boost amplitude of Basis Function Method, D (k, n, M) being the computation complexity formula that solves of de Boor-Cox method interpolated point, (k, n m) are the calculating of Basis Function Method solution procedure to B Complexity formula；

During m=1, performance judgment formula is:

f(k,n,1)=(2^k+3-9)/(2^k+1+k+4n²+ 17n+11)-1 (7)

During m=2, performance judgment formula is:

F (k, n, 2)=(2^k+3+2^k-12)/(2^k+1+10n²+ 42n+8k+20)-1 (8)

Described the method that computation complexity is low is dynamically selected to carry out interpolation, including following step by described performance judgment formula Rapid:

S1: algorithm starts, reads nurbs curve parameter k, n, m；

S2: read curve and currently put the parameter value u of correspondence；

S3: judge the relation of derivation number of times m and 1 required in Interpolation Process, if m is not equal to 1, forward S5 to；

S4: judge that (k, n, value m), if f (k, n, 1) > 0 sets up, forward S6 to, otherwise forward to performance judgment function f during m=1 S7；

S5: judge that (k, n, value m), if f (k, n, 2) > 0 sets up, forward S6 to, otherwise forward to performance judgment function f during m=2 S7；

S6: with Basis Function Method, use the method sharing calculating process intermediate object program to current interpolation point evaluation, derivation, enter Row interpolation calculates；

S7: by de Boor-Cox method, to current interpolation point evaluation, derivation, carry out interpolation calculation；

S8: judge whether Interpolation Process terminates, returns S2 if not；

S9: interpolation terminates.

The present invention has the following advantages and beneficial effect:

1. application the inventive method can effectively share the intermediate object program during base function algorithn calculates, and reduces algorithm Computation complexity.

2. application the inventive method can dynamic self-adapting select efficient interpolation algorithm, improve nurbs curve Interpolation efficiency.

Accompanying drawing explanation

Fig. 1 is the computation structure of de Boor-Cox algorithm evaluation；

Fig. 2 is the computation structure of de Boor-Cox algorithm derivation；

Fig. 3 is the computation structure before basic function evaluation abbreviation；

Fig. 4 is the computation structure after basic function evaluation abbreviation；

Fig. 5 is the computation structure before basic function derivation abbreviation；

Fig. 6 is the computation structure after basic function derivation abbreviation；

Fig. 7 is algorithm flow chart；

Fig. 8 is computational efficiency comparison diagram.

Detailed description of the invention

Below in conjunction with the accompanying drawings and embodiment the present invention is described in further detail.

1. analyze the de Boor-Cox method computation structure when calculating interpolation point, set up the calculating complexity that interpolated point solves Degree formula.Fig. 1, Fig. 2 respectively de Boor-Cox method carries out computation structure when B-spline curves evaluation, derivation.Make function D (k, n, time m) for using de Boor-Cox method, the total degree of multiplication and division computing needed for curve interpolating, wherein k is nurbs curve Number of times, n is the number of control vertex, and m is the high reps of derivative, 0≤i≤n in calculating process.Due in Practical Calculation mistake In journey, m value is 1 or 2, and in conjunction with the expression formula (1) of nurbs curve, when can obtain m=1, m=2, (k, n, expression formula m) is the most such as D Shown in formula (2), (3).

$c\left(u\right)=\frac{\underset{i=0}{\overset{n}{\mathrm{\Σ}}}{w}_i{P}_i{N}_{i,k}\left(u\right)}{\underset{i=0}{\overset{n}{\mathrm{\Σ}}}{w}_i{N}_{i,k}\left(u\right)}$

D(k,n,1)=2^k+3-9, m=1 (2)

D(k,n,2)=2^k+3+2^k-12, m=2 (3)

2. computation structure during abbreviation Basis Function Method calculating interpolation point, reduces computation complexity by shared intermediate object program, And set up the computation complexity formula of Basis Function Method solution procedure.Fig. 3, Fig. 4 are respectively the basic function computation structure before and after abbreviation, Fig. 5, Fig. 6 are respectively the computation structure of basic function derivation before and after abbreviation.Wherein Fig. 4, Fig. 6 calculated by sharing to take full advantage of Intermediate object program in journey, reduces computation complexity.(k, n, time m) for using Basis Function Method, take advantage of needed for curve interpolating to make function B The total degree of division arithmetic, wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is derivative in calculating process High reps, 0≤i≤n.Then during m=1, k nurbs curve interpolation needs multiplication and division operation times altogether:

B(k,n,1)=2^k+1+4n²+ 17n+k+11 (4)

During m=2, k nurbs curve interpolation needs multiplication and division operation times altogether:

B(k,n,2)=2^k+1+10n²+ 42n+8k+20 (5)

3. set up Performance comparision formula when de Boor-Cox method and Basis Function Method calculating interpolation point, when curve interpolating, Dynamically select the method that computation complexity is low to carry out interpolation by this formula, improve interpolation efficiency.With function f, (k, n m) represent The performance of nurbs curve interpolation algorithm is as follows:

F (k, n, m)=D (k, n, m)/B (k, n, m)-1 (6)

It is meant that the de Boor-Cox algorithm performance boost amplitude compared with Basis Function Method, represents when functional value is more than zero The performance of Basis Function Method is of a relatively high, otherwise the performance of de Boor-Cox algorithm is of a relatively high.Then during m=1, performance judgment function Expression formula is:

f(k,n,1)=(2^k+3-9)/(2^k+1+k+4n²+ 17n+11)-1 (7)

During m=2, performance judgment function expression is:

F (k, n, 2)=(2^k+3+2^k-12)/(2^k+1+10n²+ 42n+8k+20)-1 (8)

When nurbs curve interpolation, de Boor-Cox interpolation algorithm is respectively arranged with quality with the performance of basic function interpolation algorithm, From formula (6), the relative performance of the two is when m value determines, control point number n by parameter curve number of times k, curve is true Fixed, the flow process of algorithm is as it is shown in fig. 7, specifically include following steps:

S1: algorithm starts, reads nurbs curve parameter k, n, m.

S2: read curve and currently put the parameter value u of correspondence.

S3: judge the relation of derivation number of times m and 1 required in Interpolation Process, if m is not equal to 1, forward S5 to.

S4: judge that (k, n, value m), if f (k, n, 1) > 0 sets up, forward S6 to, otherwise forward to performance judgment function f during m=1 S7。

S5: judge that (k, n, value m), if f (k, n, 2) > 0 sets up, forward S6 to, otherwise forward to performance judgment function f during m=2 S7。

S6: with Basis Function Method, use the method sharing calculating process intermediate object program to current interpolation point evaluation, derivation, enter Row interpolation calculates.

S7: by de Boor-Cox method, to current interpolation point evaluation, derivation, carry out interpolation calculation.

S8: judge whether Interpolation Process terminates, returns S2 if not.

S9: interpolation terminates.

4. the implementation effect of the present invention

Work as m=1, n ∈ [3...7], during k ∈ [3...7], according to formula (4) and formula (7), de Boor-Cox algorithm, base The computation complexity of function algorithm and herein algorithm compares as shown in Figure 8.

Figure uses required during calculating take advantage of/division arithmetic number of times to be to represent the complexity of calculating, it can be seen that when When degree of curve k and control point number n change, the computation complexity of de Boor-Cox algorithm or Basis Function Method all can not Remain optimum.Though algorithm adds certain amount of calculation when carrying out adaptively selected herein, but algorithm computation complexity Relatively minima is only increased slightly, and uses algorithm herein, computation complexity can be made to be constantly in reduced levels.

For the method verifying invention further, the nurbs curve representative by machining simulation carries out performance survey Examination, parameter of curve is as follows:

Table 1NURBS curve

Algorithm realizes on Visual C++6.0, and the individual calculus of double-core Pentium (R) 2.2GHz at 2G internal memory Running on machine, operating system is Windows XP Pro SP2, and experimental result is the meansigma methods after being run multiple times, experimental result It is shown in Table 2:

Table 2 algorithm calculates time-consuming contrast

Nurbs curve	Curve one	Curve two	Curve three	Average time
					De Boor-Cox algorithm	10.3us	21.0us	42.4us	24.6us
Basis Function Method	16.5us	19.2us	24.6us	20.1us
					Algorithm herein	10.6us	19.5us	24.9us	18.3us

It can be seen that herein average computation de the to be less than Boor-Cox algorithm of algorithm and Basis Function Method from table, Computational efficiency improves about 25% than Boor-Cox algorithm, improves about 9% than Basis Function Method, and along with the adjustment number of times of n, k increases And the increase of analog value, algorithm performance lifting can become apparent from.

During it can be seen that carry out nurbs curve interpolation operation, along with parameters such as degree of curve k and control vertex numbers n Change, de Boor-Cox method be in the algorithm performance quality of Basis Function Method relative change among.But based on answering of calculating Miscellaneous degree carries out the new algorithm that interpolation algorithm is adaptively selected, overcomes in traditional method and causes only with a kind of computational algorithm Performance reduces problem, hence it is evident that improve the average efficiency of nurbs curve interpolation.

Claims (2)

1. a computation complexity adaptive nurbs curve interpolating method, it is characterised in that comprise the following steps:

By analyzing the de Boor-Cox method computation structure when calculating interpolation point, set up the computation complexity that interpolated point solves Formula；Abbreviation Basis Function Method calculates computation structure during interpolation point, reduces computation complexity by shared intermediate object program, and sets up The computation complexity formula of Basis Function Method solution procedure；

Set up performance judgment formula when de Boor-Cox method and Basis Function Method calculating interpolation point, when curve interpolating, by institute Stating performance judgment formula dynamically selects the method that computation complexity is low to carry out interpolation；

The computation complexity formula that described de Boor-Cox method interpolated point solves is m value when being 1 or 2, takes advantage of needed for curve interpolating The total degree of division arithmetic:

D (k, n, 1)=2^k+3-9, m=1 (2)

D (k, n, 2)=2^k+3+2^k-12, m=2 (3)

Wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is the high reps of derivative in calculating process；

The computation complexity formula of described Basis Function Method solution procedure is m value when being 1 or 2, multiplication and division fortune needed for curve interpolating The total degree calculated:

B (k, n, 1)=2^k+1+4n²+17n+k+11 (4)

B (k, n, 2)=2^k+1+10n²+42n+8k+20 (5)

Wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is the high reps of derivative in calculating process；

Described performance judgment formula is

F (k, n, m)=D (k, n, m)/B (k, n, m)-1 (6)

Wherein, (k, n, m) represent the de Boor-Cox method algorithm performance boost amplitude compared with Basis Function Method to function f, and (k, n m) are D The computation complexity formula that de Boor-Cox method interpolated point solves, (k, n are m) that the calculating of Basis Function Method solution procedure is complicated to B Degree formula；

During m=1, performance judgment formula is:

F (k, n, 1)=(2^k+3-9)/(2^k+1+k+4n²+17n+11)-1 (7)

During m=2, performance judgment formula is:

F (k, n, 2)=(2^k+3+2^k-12)/(2^k+1+10n²+42n+8k+20)-1 (8)

Wherein k is the number of times of nurbs curve, and n is the number of control vertex, and m is the high reps of derivative in calculating process.

A kind of computation complexity adaptive nurbs curve interpolating method the most according to claim 1, it is characterised in that Described dynamically select the method that computation complexity is low to carry out interpolation by described performance judgment formula, comprise the following steps:

S1: algorithm starts, reads nurbs curve parameter k, n, m, and wherein k is the number of times of nurbs curve, and n is the individual of control vertex Number, m is the high reps of derivative in calculating process；

S2: read curve and currently put the parameter value u of correspondence；

S3: judge the relation of derivation number of times m and 1 required in Interpolation Process, if m is not equal to 1, forward S5 to；

S4: judge that (k, n, value m), if f (k, n, 1) > 0 sets up, forward S6 to, otherwise forward S7 to performance judgment function f during m=1；

S5: judge that (k, n, value m), if f (k, n, 2) > 0 sets up, forward S6 to, otherwise forward S7 to performance judgment function f during m=2；

S6: with Basis Function Method, use the method sharing calculating process intermediate object program to current interpolation point evaluation, derivation, insert Value calculates；

S7: by de Boor-Cox method, to current interpolation point evaluation, derivation, carry out interpolation calculation；

S8: judge whether Interpolation Process terminates, returns S2 if not；

S9: interpolation terminates.