JP2854035B2 - Curve generator - Google Patents

Description

Detailed Description of the Invention [Table of Contents] Overview Industrial application Field of the Invention Prior Art Problems to be Solved by the Invention Means for Solving the Problems Action Embodiment Effect of the Invention [Summary] Curve by using difference matrix method With respect to the generating device, the object of the present invention is to provide a device capable of generating a high-quality curve at a high speed, and to perform a differential operation on a matrix corresponding to any of the points forming the curve and perform a next operation separated from the matrix by a predetermined time interval. The process of calculating the increment amount up to the matrix and obtaining the next matrix by adding the calculated increment amount and the matrix of the calculation reference is performed using the matrix corresponding to the start point of the curve as an initial value and the matrix corresponding to the end point of the curve. In the curve generation device which is repeated until the above is obtained, the errors included in the matrix of the initial values are accumulated by the repetition of the addition up to the end point. Determine the function that indicates the amount to be accumulated and the total number of curve forming points is a variable, calculate the total number of curve forming points where the value of the function is less than or equal to the allowable value, and calculate the time length from the start point to the end point of the curve And calculating the time interval from the selected total number.

[Industrial application field] The present invention relates to an apparatus for generating a curve by using a difference matrix method.

In the fields of CG and CAD, it is necessary to generate high quality curves.

When a high-quality curve is generated by software, the generation speed is low. Therefore, a method of generating a curve by hardware is adopted in a CG device or a CAD device.

[Prior Art] When curves are generated by hardware to which the midpoint division method is applied, it is necessary to convert all curves into Bezier curves, and the configuration of the hardware for performing the conversion is remarkably large. It becomes complicated, and the capacity of the stack for repeatedly storing the midpoint coordinates becomes enormous.

Therefore, a difference matrix method for sequentially obtaining curve forming points by repeating the process of adding the increment amount calculated by the differential operation of the matrix to the matrix is applied to hardware for generating a curve.

According to this difference matrix method, general polynomials, Bezier curves, Spline curves, and the like can be generated at high speed without performing the above-mentioned conversion, and the stack amount does not become enormous.

[Problems to be Solved by the Invention] However, according to the difference matrix method, since the matrix of the curve generation points is obtained in order by the sequential addition of the increments, errors gradually accumulate by repeating the addition.

The present invention has been made in view of the above-described conventional circumstances, and an object of the present invention is to provide an apparatus capable of generating a high-quality curve at high speed.

[Means for Solving the Problems] In order to achieve the above object, the present invention provides a curve (100)
Is computed by differentiating a matrix (M (ti)) corresponding to any of the points (P0... Pi, Pi + 1... Pn) forming the matrix (Pi). Means for calculating an increment (a) up to the next matrix (M (ti)) separated by a time interval (δ), and a calculated increment (a)
Means for adding the matrix (M (t + i)) to the calculation reference matrix, means for performing processing for obtaining a matrix (M (ti + 1)) corresponding to the next curve forming point (Pi + 1) from the added value, With the matrix (M (t0)) corresponding to the starting point (P0) of the curve (100) as the initial value.
Means for repeating until the matrix (M (tn)) corresponding to the end point (Pn) of (0) is obtained, the error (M (t0)) included in the matrix (M (t0)) of the initial value ε) is the end point (P
n) indicates the amount (E) accumulated up to the curve forming point (P0 ...
Means for determining a function (f) in which the total number (n) of (Pi, Pi + 1... Pn) is a variable (step 110); and the function (f)
The total number (nm) of the curve forming points (P0... Pi, Pi + 1... Pn) which becomes maximum when the value (E) of the
ax) (step 120), and the time length (tn to t) from the start point (P0) to the end point (Pn) of the curve (100)
0) and the selected total number (n max) from the time interval (δ
min) (step 130).

[Operation] In the present invention, each curve generation point P0... Pi, Pi + 1.
Matrix M (t0)... M (ti), M (ti
+1)... M (tn) are sequentially obtained by the difference matrix method.

The time interval δ min used in the difference matrix operation
Is the time length tn to t from the start point P0 to the end point Pn of the curve 100
.., Pi + 1,..., Pn (step 130).

Further, the total number n max of the curve forming points P0... Pi, Pi + 1... Pn used for obtaining the time interval δ min is obtained by selecting the solution of the function f (step 12).
0).

This function f is represented by curve forming points P0... Pi, Pi + 1.
Is a variable, the final accumulated error E is obtained by giving the initial error ε, and the function value E is
The total number n max is selected as a solution that maximizes the variable n under the condition that it is equal to or less than E max.

Then, the function f is defined as a matrix M (t0), M (ti), M (ti
+1)... M (tn). Therefore, the maximum total number n max can be selected by using the difference matrix method, and therefore, the curve forming points P0... Pi, Pi + 1.
The time interval δ min together with n can be obtained at high speed by hardware.

Further, since the minimum time interval δ min at which the final accumulated error E becomes equal to or smaller than the allowable value E max is obtained, the curve 100 can be accurately expressed.

Hereinafter, preferred embodiments of the method according to the present invention will be described with reference to the drawings.

FIG. 2 illustrates the configuration of a curve generator to which the present invention is applied. This curve generator includes a data input unit 20, a cumulative error calculation unit 22, a difference matrix calculation unit 24, an interval determination unit 26,
It comprises an increment value adding section 28 and a curve output section 30.

In the present embodiment, a three-dimensional curve 100 (for example, a uniform B-spline function) is to be generated, and the curve control points Qi, Qi + in a section with a certain temporal length t0 to tn.
Data of 1, Qi + 2 and Qi + 3 are taken in from the data input unit 20.

These control points Qi, Qi + 1, Qi + 2, Qi + 3 and time interval δ
And the initial value matrix M (t0) = [A, B, C, D] is calculated as follows: A = (1/6) Qi + (2/3) Qi + 1 + (1/6) Qi + 2 B = ｛(− 1/6) δ ² + (1/2) δ-1/2｝ Qi + ｛1/2) δ ^2- δ｝ Qi +1 + ｛(-1/2) δ ² + (1/2) δ + 1/2｝ Qi + 2 + (1/6 ) Δ ² Qi + 3 C = (− δ + 1) Qi + (3δ−2) Qi + 1 + (− 3δ)
+1) Qi + 2 + δQi + 3 D = −Qi + 3Qi + 1−3Qi + 2 + Qi + 3 (Expression 1), and the matrix M (t0) = [A, B, C,
D] is calculated by the difference matrix calculation unit 24.

In FIG. 3, the difference matrix calculation unit 24 and the increment value addition unit 28
Is explained, and the matrix M (t0) = [A, B,
[C, D] corresponds to the start point P0 of the curve 100.

Then, an initial value matrix M (t0) = [A, B, C, D]
Is given to the increment value adding section 28, and the first element A = S (t0) indicating the starting point P0 is given from the increment value adding section 28 to the curve output section 30 and outputted to the outside.

In addition, in the incremental adding unit 28, the second element B = ΔS (t0) of the current matrix M (t0) is first-order differentiated, and the third element C =
Δ ² S (t0) is secondarily differentiated, and the fourth element D = Δ ³ S
(T0) is third-order differentiated.

A matrix [B, C, D,
0] = [ΔS (t0) , Δ 2 S (t0), Δ 3 S (t0)] is calculated, the increment value addition unit 28 in increments of a matrix [B, C,
[D, 0] is added to the previous matrix M (t0) = [A, B, C, D].

The resulting matrix M (t1) = [A + B, B
+ C, C + D, D] is sent to the curve output unit 30 as data indicating the next curve forming point P1.

Further, a new matrix M (t1) = [A + B, B + C, C
+ D, D] to the previous matrix M (t0) = [A, B, C, D]
Is updated.

The above processing is repeated in the same manner. As a result, data A, A + B, A + 2B indicating the curve forming points P0, P1, P2,.
+ C ... A + nB + n (n-1) C / 2 + n (n-1)
(N-2) D / 6 is sequentially output to the outside.

The matrix M (t0) obtained at this time = [A, B, C,
D], M (t1) = [A + B, B + C, C + D, D], M (t2) = [A +
2B + C, B + 2C + D, C + 2D, D] ... M (tn) = [A + nB +
n (n-1) C / 2 + n (n-1) (n-2) D / 6, B + nC +
n (n−1) D / 2, C + nD, D], each element S (ti + 1), Δ
S (ti + 1), Δ 2 S (ti + 1), Δ 3 S (ti + 1) is represented by the following the equation (2).

S (ti + 1) = S (ti) + ΔS (ti) ΔS (ti + 1) = ΔS (ti) + Δ 2 S (ti) Δ 2 S (ti + 1) = Δ 2 S (ti) + Δ 3 S (ti) Δ 3 S (Ti + 1) = Δ ³ S (ti) Equation (2) Their matrices M (t0), M (t1), M (t2) ...
The time interval δ at which M (tn) is obtained is represented by δ = ti + 1−ti... (3), and the number n of the differential operation and the addition of the increment amount is n = (tn + t0) / δ. 4) Formula:

Here, when calculating the difference matrix, the error ε included in the initial value D of the tertiary differential increment Δ ³ S (ti) and the allowable value E max of the error E to be finally accumulated are taken in from the data input unit 20 in advance. It is.

The error E finally accumulated at the end point Pn of the curve 100 is
As understood from the first element S (tn) of the matrix M (tn) in the figure, E = n (n−1) (n−2) ε / 6...

The equation (5) uses the maximum total number of forming points n max at which the interval δ between the curve forming points Pi + 1 is the densest, and E = n max (n max−1) (n max−2) ε / 6 · .Times..times..times..times..times..times..times..times..times..times..times..tim- es..times..times..times..times..times.

The condition that the accumulated error E is equal to or larger than the allowable value Emax is represented by nmax (nmax-1) (nmax-2)> 6Emax / ε (8). Expression) is generated by the accumulation calculating unit 22.

Then, the value of the left side in the expression (8) is obtained by the difference matrix method by the difference matrix calculation unit 24 and the increment addition unit 28, and the maximum total number of formed points n max satisfying the expression (8)
Is selected.

That is, since the maximum forming point total number n max is an integer of 0 or more, the process of substituting 0, 1, 2,... .

The values on the left side are added to the accumulated error calculation unit 22 and the increment value addition unit 28.
, And a total number n max satisfying the expression (8) is selected.

Further, the total number n max is given from the accumulated error calculating unit 22 to the interval determining unit 26, and the interval determining unit 26 calculates the maximum total number n max of forming points according to the following equation (9). Determined.

As described above, in the present embodiment, the solution on the left side of the equation (8) is a cubic curve equation similar to the curve 100 and the solution satisfying the equation is 0.
Paying attention to the above integers, the maximum total number n max is obtained by hardware using the difference matrix method.

Therefore, there is no problem in terms of the convergence of the solution and the time required for the calculation, unlike the Newton method or the like.
The solution of the equation is calculated at high speed.

In addition, since the operation by the difference matrix method is an integer operation, there is no error, and an accurate solution can be obtained.

 In the increment value adder 28, S (nmax) = nmax (nmax-1) (nmax-2) (Equation (10)) is treated as the target curve equation.

At this time, the matrix elements indicated by the values A, B, C, and D in FIG. 3 are: S (n maxi + 1) = S (n maxi)... Equation (11) ΔS (n maxi + 1) = ΔS (N maxi) + Δ ² S (n max
i) · · · No. (12) Δ2S (n maxi + 1) = Δ 2 S (n maxi) + Δ 3 S (n max
i) ··· Expression (13) Δ ³ S (n maxi + 1) = Δ ³ S (n maxi) ··· Expression (14), and values A, B and C from expression (10) , D equivalent value An, B
n, Cn, and Dn are obtained from the following equation (15).

An = Bn = Cn = 0 Dn = 6 Expression (15) Thus, the minimum time interval δ min in the interval determination unit 26 is obtained.
Is obtained, the values A, B, C, D in FIG. 3 are completely determined,
In the following, the operation of the difference matrix is n ma according to the equation (2).
Repeated x times.

However, in practice, the calculation represented by the following expression (16) is performed using the shift number γ, thereby increasing the calculation accuracy.

S (ti + 1) = S (ti) + γ * (1 / γ) ΔS (ti)
(1 / γ) ΔS (ti + 1) = (1 / γ) ΔS (ti) + γ * (1 / γ2) Δ 2 S (ti) (1 / γ2) Δ 2 S (ti + 1) = (1 / γ2) Δ ² S (ti) + γ * (1 / γ3) Δ ³ S (t
i) (1 / γ3) Δ 3 S (ti + 1) = (1 / γ3) Δ 3 S (ti) ··· first (16) Further, when the distance between the curve forming point Pi is 1 dot, The straight line connecting them can be generated by a straight line generator.

As described above, according to the present embodiment, the final accumulated error E is equal to or less than the error allowable value Emax by giving the initial error ε and the error allowable value Emax. A curve 100 can be generated.

Further, since the minimum time interval δ min is also obtained by the difference matrix method, a high quality curve 100 can be generated at high speed.

For this reason, it is possible to remarkably improve the performance of an apparatus for performing CG and CAD processing.

When the initial error ε and the allowable error value Emax are large, the time interval δmax also increases accordingly.
The production rate of 100 becomes extremely high.

Therefore, by specifying the initial error ε and the error allowable value Emax, it is possible to select which of the generation speed and the generation accuracy of the curve 100 should be prioritized according to the application.

[Effects of the Invention] As described above, according to the present invention, a difference matrix is calculated using a time interval at which the final accumulated error is equal to or less than the error allowable value, and the time interval is also calculated by the difference matrix method. Therefore, it is possible to configure hardware for generating a high-quality curve for navigation.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the invention, FIG. 2 is a diagram illustrating the configuration of an embodiment, and FIG. 3 is a diagram illustrating the operation of a difference matrix calculation unit and an increment value addition unit. 20 data input unit 22 cumulative error calculation unit 24 difference matrix calculation unit 26 interval determination unit 28 increment value addition unit 30 curve output unit

Continuation of front page (56) References JP-A-64-41077 (JP, A) JP-A-62-297984 (JP, A) JP-A-64-82281 (JP, A) (58) Fields investigated (Int) .Cl. ⁶ , DB name) G06T 11/00-11/20

Claims (1)

(57) [Claims] 1. Each point (P0... Pi,
Pi + 1... Pn), the matrix (M (ti)) corresponding to any of (Pi) is differentiated, and the matrix (M (t)
means for calculating an increment (a) from the i)) to the next matrix (M (ti)) separated by a predetermined time interval (δ), and a matrix of the calculated increment (a) and a calculation reference ( M
(T + i)), means for obtaining a matrix (M (ti + 1)) corresponding to the next curve forming point (Pi + 1) from the added value, and starting the curve (100). Means for repeating until a matrix (M (tn)) corresponding to the end point (Pn) of the curve (100) is obtained using a matrix (M (t0)) corresponding to (P0) as an initial value. In the apparatus, an error (ε) included in the matrix of initial values (M (t0)) indicates an amount (E) accumulated up to the end point (Pn) by repeating the addition, and a curve forming point (P0...)・ Pi, Pi
Means for determining a function (f) in which the total number (n) of (+1... Pn) is a variable (Step 110); and a maximum when the value (E) of the function (f) is equal to or less than an allowable value (Emax). Curve forming point (P0 ... Pi, Pi + 1 ... Pn)
Means (step 120) for selecting the total number (n max) of the curves, the time length (tn to t0) from the start point (P0) to the end point (Pn) of the curve (100), and the total number (n max ) And a means (Step 130) for obtaining the time interval (δmin) from the above.