JP2538645B2 - Curved line approximation device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] A curved line approximation device for use in, for example, a computer graphic display device, for the purpose of approximating a curved line with a polygonal line without increasing the processing time and the amount of data. A curve dividing means for dividing a curve in one range into two curve sections, and an error calculating means for calculating a distance between a midpoint of a line segment connecting a start point and an end point of the curve and a dividing point of the curve as an error. If the error is less than a predetermined value, a polygonal line data generating means for generating a line segment connecting the start point and the end point of the curve section as polygonal line data of the curve, and if the error is a predetermined value or more, the curve section Is further divided into two curve sections, and a repeating means for repeating the operation of the curve dividing means is provided.

[Industrial applications]

The present invention relates to a curved line approximation apparatus used in, for example, a computer graphic display device.

[Problems to be Solved by Conventional Techniques and Inventions]

Generally, in a graphic device, if a curve is directly generated and displayed, a complicated process is required. Therefore, a plurality of line segments are generated by approximation with polygonal lines and displayed.

Conventionally, as a method for approximating a curved line of a curve, for example, the curve is divided into a predetermined number of divisions, only the coordinates of the points on the curve at the division points are calculated, and the obtained coordinates of the points on the curve are drawn. It was approximated by the broken line connecting the minutes.

However, in order to represent a curve having a large curvature with a polygonal line with high accuracy, it is necessary to increase the number of divisions. As a result, the processing time and the amount of data are increased, while an excessive accuracy is required for a curve having a small curvature. There is a problem that becomes.

Therefore, an object of the present invention is to approximate a curve with a broken line without increasing processing time and data amount.

[Means for solving the problem]

In order to solve the above-mentioned problems, according to the present invention, as shown in FIGS. 1 and 2, the curves P _{01 to} P ₀₂ in one range of inflection points are divided into two curve sections P _{01 to} P _{01. 11,} P ₁₁ ~P
A curve dividing means for dividing into ₀₂ , an error calculating means for calculating a distance between a midpoint of a line segment connecting a start point P ₀₁ and an end point P ₀₂ of the curve and a dividing point P ₁₁ of the curve as an error e, and the error Is less than a predetermined value, a polygonal line data generating means for generating a line segment connecting the starting point and the end point of the curve as polygonal line data of the curve; and if the error is a predetermined value or more, further dividing each curve section by 2 There is provided a polygonal line approximation device for a curve, comprising: a repeating unit that divides into one curve section and repeats the operation of the curve dividing unit.

[Work]

According to the above means, as shown in FIG. 2, the curves P _{01 to} P ₀₂ in the range of one inflection point are divided into two curve sections P _01.
Divided into ~P _11, P ₁₁ ~P _02, the distance between the dividing point P ₁₁ of the line segment at the midpoint and the curve connecting the start point P ₀₁ and the end point P ₀₂ of the curve is calculated and the error e. As a result, when the error e is small, the above line segment is used as polygonal line data, and when it is large, the above-described division processing is repeated to approximate the curved line. As a result, the number of divisions increases for a curve having a large curvature, but the number of divisions decreases for a curve having a small curvature.

〔Example〕

FIG. 3 shows a graphic display device to which the curved line approximation device according to the present invention is applied. In FIG. 3, 1 is a graphic data input device, 2 is a coordinate conversion device, 3 is a curve generation device, 4
Is a drawing processing device, and 5 is a display control device for controlling the CRT 6. The curved line approximation apparatus according to the present invention is a curve generation apparatus 3
Used as.

FIG. 4 is a block circuit diagram showing an embodiment of a curved line approximation apparatus according to the present invention. In FIG. 4, the data input circuit 401 has four coordinates Q ₁₁ ~ representing a cubic Bezier curve.
Q ₁₄ is input and sent to the curve dividing circuit 402. The curve division circuit 402 divides the curve of the input coordinates from the data input circuit 401 or the curve of the curve data returned from the error determination circuit 404 by ts: 1-ts. The error calculation circuit 403 calculates the error between the divided curve and the line segment that approximates it.
The error determination circuit 404 compares the error calculated by the error calculation circuit 403 with a preset error threshold value. If the error is within the threshold value, the data is output to the data output circuit 40.
When it is not within the threshold value, the data is returned to the curve dividing circuit 402 again. The data output circuit 405 performs a process of outputting curved line-approximated curve data.

 Hereinafter, each of the circuits 402 and 403 will be described in detail.

The curve division circuit 402 obtains a point on the curve that divides the curve at a ratio ts: 1-ts from the property of a cubic Bezier curve (reference: Fujio Yamaguchi, “Shape processing engineering by computer display (2 ) ”Nikkan Kogyo p10〜1
(5, Showa 57) is used to divide the curve. As shown in FIG. 5, the curve division circuit 402 includes registers 501 to
504, coordinate division circuits 505 to 510, and registers 511 to 518. That is, as shown in FIG. 6, if Q _{11 to} Q ₁₄ are given as coordinates representing a curve, these coordinates are stored in the registers 501 to 504. Coordinate Q ₁₁ ,
Q ₁₄ is stored in registers 511 and 518 as it is. The coordinate division circuit 505 divides the coordinates Q ₁₁ and Q ₁₂ with the ratio ts: 1-ts.
Generates Q ₂₁ and stores it in register 512, then the coordinate division circuit 506
Generates a coordinate Q ₂₂ which is obtained by dividing the coordinates Q ₁₂ and Q ₁₃ by the ratio ts: 1-ts, and the coordinate dividing circuit 507 calculates the ratio ts: 1-ts between the coordinates Q ₁₃ and Q _14.
The coordinate Q ₂₃ divided by is generated and stored in the register 517.
Further, the coordinate division circuit 508 calculates the ratio ts: 1−ts between the coordinates Q ₂₁ and Q _22.
The coordinate Q ₃₁ divided by is generated and stored in the register 513, and the coordinate division circuit 509 generates the coordinate Q ₃₂ obtained by dividing the coordinate Q ₂₂ and Q ₂₃ by the ratio ts: 1−ts and stored in the register 516. . further,
The coordinate dividing circuit 510 generates the coordinate Q ₄₁ by dividing the coordinates Q ₃₁ and Q ₃₂ by the ratio ts: 1−ts and stores them in the registers 514 and 515. At this time, as shown in FIG. 6, the coordinate Q ₄₁ is Q ₁₁ , Q ₁₂ , Q ₁₃ , Q ₁₄
Is the coordinate on the curve that divides the curve given by the ratio ts: 1-ts, and at the same time the curve is
It is divided into two curves (Q ₁₁ , Q ₂₁ , Q ₃₁ , Q ₄₁ and Q ₄₁ , Q ₃₂ , Q ₂₃ , Q ₁₄ ).

The input coordinates Q of the registers 501 to 504 in FIG.
_{11 to} Q ₁₄ data input circuit 401 or error determination circuit 404
The switch to is performed by a switch (not shown).

The coordinate division circuits 505 to 510 shown in FIG.
As shown in the figure, it is composed of multipliers 701 and 702 and an adder 703.

When calculating the error (distance) between a curve such as Q ₁₁ and Q ₁₄ and a line segment ▲ ▼, as shown in FIG.
Q ₁₁ and coordinates Q ₁₄ are the start and end points of the curve section, coordinates Q ₄₁ are the coordinates on the curve that further divides the curve sections Q ₁₁ and Q ₁₄ , coordinate M is the midpoint of line segment ▲ ▼, and point D is the coordinate Q. Straight line from _41
It shows the intersection of the perpendiculars drawn on ₁₁ Q ₁₄ . The distance between the line segment obtained by connecting the start point and the end point of the curved section and the coordinate on the curve that divides the curved section one more time is the coordinate Q _41.
Is the distance d _{2 from the} coordinate D. However, it is not practical to find the intersection D of the perpendicular line drawn from the coordinate Q ₄₁ to the line segment ▼. Therefore, the line segment ▲
The distance d ₁ between the midpoint M and the coordinate Q ₄₁ is used as an error. By doing this, the line segment ▲ ▼
The middle point M is easily obtained, and the distance d ₁ obtained by this calculation is always longer than the actual distance d ₂ . Therefore, when the obtained distance d ₁ is compared with the error for judgment, the accuracy of the approximated curve does not decrease,
The approximated curve is smooth.

In this case, the distance between the two points will be obtained. Two
Assuming that the coordinates of the points are (X ₁ , Y ₁ ), (X ₂ , Y ₂ ), the calculation of the distance between the two points is expressed as shown in equation (1).

Distance = In ^{_{{(X 1 -X 2) 2}} + (Y 1 -Y 2) 2} 1/2 ... (1) Equation (1), since it requires multiplication and division, if required high-speed processing Is at a disadvantage. In order to perform this processing only by addition and subtraction, the coordinate difference between two points is used as shown in equation (2).

Distance = | X ₁ −X ₂ | + | Y ₁ −Y ₂ |… (2) By doing this, the operation can be executed simply and at high speed. The distance is always longer than the distance calculated by the equation (1).
Therefore, when the obtained distance is compared with the error for judgment, the accuracy of the approximated curve does not decrease,
The approximated curve is smooth.

Details of the error calculation circuit 403 of FIG. 4 for calculating the error shown in FIG. 8 are shown in FIG. In FIG. 9, 9
01, 902, 903, and 906 are registers, 904 is a midpoint arithmetic circuit for finding the midpoint of the two input coordinates, and 905 is the input 2
It is a coordinate difference calculation circuit that calculates a coordinate error obtained from the two coordinates by the calculation formula shown in Formula (2).

First, of the curves divided into two curves output from the curve dividing circuit 402, Q ₁₁ , Q ₁₄ , and
Q ₄₁ is stored in the registers 901 to 903, respectively. Where Q ₁₁ is the beginning of the curve, Q ₁₄ is the end of the curve, and Q ₄₁ is Q ₁₁
Ratios curves for the starting point Q ₁₄ of the curve and the end point of the curve ts: 1-t
A point on the curve that divides into s. As a result, Q ₁₁ and Q ₁₄ are input to the midpoint arithmetic circuit 904, and the midpoint M of the line segment connecting the curve start point Q ₁₁ and the curve end point Q ₁₄ is obtained as the output of the midpoint arithmetic circuit 904. To be In addition, the coordinate difference calculation circuit 905 includes the midpoint M of the line segment connecting the curve start point Q ₁₁ and the curve end point Q ₁₄ obtained by the midpoint calculation circuit 904, and Q ₁₁ as the curve start point Q ₁₄ . The point Q ₄₁ on the curve that divides the curve that is the end point of the curve into the ratio ts: 1-ts is input, and the difference between these two coordinates is obtained as the output of the coordinate difference calculation circuit 905. The calculation result is stored in the register 906 as the error e.

The midpoint arithmetic circuit 904 of FIG.
As shown in the figure, it is composed of an adder 1001 and a divider 1002.

The above error e is compared with the threshold value by the error determination circuit 404 in FIG. 4, and if the error is smaller than the threshold value, the line segment ▲
▼ is output from the data output circuit 905. If the error is larger than the threshold value, the curves Q ₁₁ , Q ₂₁ , Q ₃₁ ,
Q ₄₁ is again input to the curve division circuit 402 and divided. At this time, the other curves Q ₄₁ , Q ₃₂ , Q ₂₃ , and Q ₁₄ are temporarily stored in the error determination circuit 404, and the curves Q ₁₁ and Q
_When the division of ₂₁ , Q ₃₁ and Q ₄₁ is completed, the curve division circuit 402
Is input to and processing is performed.

Through this series of processing, the cubic Bezier curve is approximated to a broken line and output.

The above-described embodiment can be realized as a program using a general-purpose microcomputer. For example, as shown in FIG. 11, at step 1101, cubic Bezier curve data Q _{11 to} Q ₁₄ are input, and at step 1102, 3
The curve is divided by generating the next Bezier curve data, and in step 1103, eight Q ₁₁ , Q ₂₁ , ..., Q ₁₄ are stored in the memory. In step 1105, the distance e between the midpoint of the curves Q ₁₁ , Q ₂₁ , ..., Q ₁₄ and the line segment ▼ is calculated, and in step 1105 it is determined whether or not the distance e is less than or equal to a threshold value. As a result, if the distance e ≦ threshold value, the line segment ▲ ▼ is output as broken line data in step 1106, and otherwise, steps 1102 to 1104 are repeated. That is, the curve is further divided. Further, steps 1102 to 1106 are repeated until all the broken line approximations of the curves are completed in steps 1107 and 1008.

〔The invention's effect〕

As described above, according to the present invention, since the number of divisions, that is, the number of approximate polygonal lines, changes according to the curvature of the curve, the curve is efficiently and smoothly approximated to the polygonal line without increasing the processing time and the data amount. be able to.

[Brief description of drawings]

FIG. 1 is a diagram showing a basic configuration of the present invention, FIG. 2 is a diagram for explaining the operation of the present invention, and FIG. 3 is a block circuit showing a graphic display device to which a curved line approximation device according to the present invention is applied. FIG. 4, FIG. 4 is a block circuit diagram showing an embodiment of a curved line approximation apparatus according to the present invention, FIG. 5 is a block diagram showing the curve dividing circuit of FIG. 4, and FIG. 6 is a cubic Bezier curve. FIG. 7 is a circuit diagram showing an example of the coordinate division circuit shown in FIG. 5, FIG. 8 is a graph showing error calculation, and FIG. 9 is a circuit diagram showing the error calculation circuit shown in FIG. FIG. 10 is a circuit diagram showing the central arithmetic circuit of FIG. 9, and FIG. 11 is a flow chart showing another embodiment. 401 ... Data input circuit, 402 ... Curve division circuit, 403 ... Error calculation circuit, 404 ... Error determination circuit, 405 ... Data output circuit.

Claims (2)

(57) [Claims] 1. A curve (P _{01 to} P) in which the inflection point is within one range.
₀₂ ) is divided into two curved sections (P _{01 to} P ₁₁ , P _{11 to} P ₀₂ ) and a line segment (▲) connecting the starting point (P ₀₁ ) and the ending point (P ₀₂ ) of the curve.
▼) error calculating means for calculating the distance between the midpoint of the curve and the dividing point (P ₁₁ ) of the curve as an error, and if the error is less than a predetermined value, the line segment connecting the start point and end point of the curve A polygonal line data generation unit that generates curved line data, and a repeating unit that divides each curve segment into two curve segments and repeats the operation of the curve segmentation unit when the error is a predetermined value or more. An apparatus for approximating a curved line, comprising: 2. The curved line approximation apparatus according to claim 1, wherein the error calculating means calculates a coordinate difference as a distance between a midpoint of the line segment and a dividing point of the curve.