JPH10198811A - Line segment approximating method for tertiary bezier curve - Google Patents

Abstract

PROBLEM TO BE SOLVED: To improve the approximation accuracy and processing speed when a tertiary Bezier curve is subjected to line segment approximation. SOLUTION: When data of a tertiary Bezier curve is given, it is judged whether it is such a rare exception case as the start point and the end point of the curve coincide with each other, and the curve is recursively divided (S20) when it corresponds to the case. It is judged whether a segment of the divided result is in a projecting shape or not, and the segment is recursively divided (S30) until a segment that is not in a projection shape is acquired. Next, it is decided whether the segment that is not in the projecting shape is in a crossing shape or not, and the segment is recursively divided (S40) until a segment that is not in the crossing shape is acquired. An acquired segment of a standard shape is recursively divided until the distance of a straight line that connects the middle point of two controlling points and start and end points becomes an allowable value or less, and when the distance reaches the allowable value or less, the segment is undergone segment approximation.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a method for approximating a cubic Bezier curve as a series of line segments when drawing a graphic represented by a cubic Bezier curve on a bit map or the like.

[0002]

2. Description of the Related Art In computer graphics and drawing software, a free curve is generally approximated by a cubic Bezier curve. A cubic Bezier curve is a parameter curve defined by a start point, an end point, and two control points, and is known to be able to be divided into two cubic Bezier curves without changing its shape. In particular, when a cubic Bezier curve is expressed as a parametric curve of P (t) (0 ≦ t ≦ 1), a method of dividing into two at a point of P (0.5) is easy to calculate and is often used. ing.

For example, as shown in FIG. 14, starting points P0,
A cubic Bezier curve defined by a first control point P1, a second control point P2, and an end point P3 (hereinafter, such a cubic Bezier curve is represented as "cubic Bezier curve P0.P1.P2.P3". ) Is two cubic Bezier curves, ie, cubic Bezier curves P0, P01, P012,
P0123 and cubic Bezier curves P0123 ・ P123 ・ P23 ・ P3
Can be divided into here,

P01 = (P0 + P1) / 2 P12 = (P1 + P2) / 2 P012 = (P01 + P12) / 2 P23 = (P2 + P3) / 2 P123 = (P12 + P23) / 2 P0123 = (P012 + P123) / 2 It is.

As described above, the cubic Bezier curve can be subdivided without limit by repeating the division recursively. The following is known as a cubic Bezier curve drawing algorithm utilizing the property of the cubic Bezier curve. That is, the cubic Bezier curve to be drawn is recursively divided, and when each segment after division (ie, the cubic Bezier curve) is determined to be flatter than the preset allowable value, This algorithm stops the division and approximates the flat segment at this time with a line segment (linear segment) connecting the start point and the end point of the segment. According to this algorithm, one cubic Bezier curve is approximately drawn as a series of line segments.

In this drawing algorithm, the accuracy of approximation depends on a criterion for approximating a segment to a line segment (ie, in the above-described example, an allowable value of flatness).

The following is known as a criterion for this line segment approximation.

(A) As shown in FIG. 15, a line segment P0 P3 connecting a start point and an end point of a segment and control points P1 and P
(2) A method of determining that line segment approximation is possible when distances d1 and d2 to each of them are equal to or smaller than a predetermined allowable value.

(B) A method disclosed in JP-A-2-105979. In this method, when the angle formed by the line segment connecting the start point or the end point of the segment and the predetermined point on the segment and the line segment connecting the start point and the end point is equal to or smaller than a predetermined allowable angle, the line segment can be approximated. Is determined.

(C) A method disclosed in JP-A-2-71384. In this method, when the distance between the midpoint of the start point and end point of the segment and the midpoint of the two control points is equal to or smaller than a predetermined allowable value, it is determined that the line segment can be approximated.

(D) A method disclosed in JP-A-4-223577. In this method, when the distance between the middle point of the start point and the end point of the segment and each control point is equal to or smaller than a predetermined allowable value, it is determined that the line segment can be approximated.

(E) A method disclosed in JP-A-4-266847. In this method, if the difference between one third of the distance between the start point and the end point of the segment and the distance between the start point or the end point and any of the control points is equal to or smaller than a predetermined allowable value, it is determined that the line segment can be approximated. .

[0012]

However, each of the above-described criteria has the following problems.

First, according to the criterion (a), a segment P0.P1.P2.P3 as shown in FIG.
Is approximated by Although the segment shown in FIG. 16 has a portion outside the line segment P0 P3, if it is approximated to the line segment P0 P3, it will be drawn shorter than it actually is, causing a problem.

Further, according to the criterion (b), even if the angles θ1 and θ2 are smaller than the allowable values, as in the case where the distance between the start point P0 or the end point P3 and the control points P1 and P2 is large as shown in FIG. May be distant from the line segment P0 P3, and performing line segment approximation in such a case poses a problem in terms of approximation accuracy. Further, if the allowable angle is set small to avoid this, the number of times of the division processing increases, and the time required for the processing increases exponentially.

According to the criterion (c), even if the segment has a shape that is not flat as shown in FIG.
The distance between the midpoint P03 of the line segment P0 P3 and the midpoint P12 of the line segment P1 P2 becomes small, and there is a possibility that the line segment may be approximated.

According to the criterion (d), as shown in FIG. 19, even if the segment is sufficiently flat, both control points P1, P2
Are too large, the distances d3 and d4 between the control points P1 and P2 and the middle point P03 of the start point and end point are large even though the line segment can be approximated, and it is determined that approximation is impossible. . Therefore, in this case, there is a problem that extra division is required and processing time is required.

According to the criterion (e), even if the segment is sufficiently flat, as shown in FIG. 20, both control points P1, P2
2 is close to the center of the start point and the end point, the distance between the start point or the end point and the control point is 1/1/1 of the distance between the start point and the end point, although the line segment can actually be approximated.
The value is far from 3 and it is determined that approximation is impossible. Therefore, in this case, there is a problem that extra division is required and processing time is required.

The present invention has been made to solve such a problem, and it is possible to accurately determine whether or not a line segment can be approximated for each segment of a cubic Bezier curve at a relatively high speed, and to form a smooth approximated curve. It is an object of the present invention to provide a method of approximating a cubic Bezier curve that can be obtained.

[0019]

In order to achieve the above object, a method of approximating a cubic Bezier curve according to the present invention comprises:
A cubic Bezier curve defined by a start point, an end point, and two control points is recursively divided, and when each segment after the division is determined to be flat, the division is stopped. In the method of approximating a cubic Bezier curve, which generates a series of approximate line segment data approximating a given cubic Bezier curve by generating the coordinate data of the start point and the end point as approximate line segment data of the segment, The segment obtained by the division is a standard cubic Bézier curve that is neither a protruding shape protruding outside the start point or end point of the segment nor a cross shape intersecting a line segment connecting the start point and end point of the segment. If it is determined, the representative value related to the thickness of the segment is compared with a preset allowable value, and if the representative value is smaller than the allowable value, the segment Doo is and judging as flat.

Here, the term "the segment protrudes outside the starting point or the ending point" means that a part of the segment which is a cubic Bezier curve is perpendicular to both ends (ie, the starting point and the ending point) of the line segment P0 P3 as shown in FIG. Means a state outside the area between the two.

As described above, when the segment has a protruding shape, even if the segment is flat, it is inconvenient if the segment is approximated by a line connecting the start point and the end point. However, there is a possibility that a line segment approximation may be performed. On the other hand, in this configuration, when the segment is a standard form having a good property, erroneous approximation can be avoided by determining flatness and performing line segment approximation.

In a preferred aspect of the present invention, the midpoint of the two control points of the segment, the starting point of the segment, The distance from the line connecting the end points is used.

In this embodiment, when the segment is in the standard form, each point of the segment always goes between a line connecting the start point and the end point (hereinafter referred to as a "base line") and the midpoint of the two control points. Pass (the proof of this will be described later).
Therefore, if the distance between the baseline and the midpoint is equal to or less than a predetermined allowable value, the thickness of the segment viewed from the baseline is always equal to or less than the allowable value, and the segment can be determined to be flat. According to this aspect, it is not necessary to perform the distance calculation twice to determine the flatness as in the above-described related art (a), and the calculation time can be reduced. The calculation of the distance between a point and a straight line is a relatively complicated calculation, and considering that the cubic Bezier curve usually created has many such standard forms, the reduction in the number of times of this calculation means that the processing speed is reduced. The effect is extremely large from the viewpoint.

The method according to the present invention is a first step of recursively dividing a cubic Bezier curve defined by a start point, a first control point, a second control point, and an end point. The division is performed until the next Bezier curve becomes a standard cubic Bezier curve in which a square obtained by connecting the start point, the first control point, the second control point, and the end point of the cubic Bezier curve in this order is a convex quadrangle. The first step to be repeated and the distance between the middle point of the two control points of the curve and the line segment connecting the start point and the end point are obtained for the standard cubic Bezier curve obtained by the first step. When the distance is less than a predetermined allowable value, coordinate data of the start point and the end point of the curve is generated as approximate line segment data of the curve, and when the distance is not less than the allowable value, the curve is divided into two cubic Bezier curves. A second step of When the standard cubic Bezier curve is divided by the second step, a series of approximations approximating the given cubic Bezier curve by repeatedly applying the second step to the divided cubic Bezier curve. It is characterized by generating line segment data.

In this method, the standard cubic Bezier curve obtained in the first step has, for example, a convex shape as shown in FIG. 9, and in the second step, such a standard cubic Bezier curve is obtained. The flatness of the curve is determined, and a line segment approximation is performed. The flatness is determined by determining the distance between the baseline and the midpoint of the two control points for the standard cubic Bezier curve,
The determination is made based on whether this distance is equal to or less than a predetermined allowable value. If the original cubic Bezier curve is in the standard form, the division result is also in the standard form.
Only the process of the step needs to be repeated. According to this method, line segment approximation is performed after dividing into a standard cubic Bezier curve (segment). Therefore, erroneous determination of approximation is not performed. Is only required to be performed once, thereby improving the processing speed.

In a preferred aspect of this configuration, the first step is to determine whether or not the given cubic Bezier curve is a protruding shape protruding outside the starting point or the ending point. A protruding shape elimination step of dividing the cubic Bezier curve into two cubic Bezier curves, and recursively repeating the dividing process until it is determined that the divided cubic Bezier curve is not a protruding shape; It is determined whether or not the Bezier curve is an intersecting shape in which a line segment connecting the start point and the end point of the cubic Bezier curve intersects with a straight line connecting the two control points. Is divided into two cubic Bezier curves, and a crossover elimination step of recursively repeating the dividing process until it is determined that the cubic Bezier curve resulting from the division is not a crossover is applied in a predetermined order.

That is, in this embodiment, in order to divide into a standard cubic Bezier curve, the protruding shape eliminating step and the cross-shaped eliminating step are sequentially applied in a predetermined order. Either of the protruding type exclusion step and the cross-type exclusion step may be applied first. For example, if the protruding shape elimination step is applied first, the non-protruding cubic Bezier curve obtained in this step is passed to the next cross-shaped exclusion step.

In a further preferred aspect of this configuration, the determination as to whether or not the object is a protruding shape in the protruding shape eliminating step includes determining an inner product of a vector connecting the starting point and the ending point and a vector connecting the starting point and the first control point, and the starting point and the Vector connecting end point and second
This is performed based on the inner product of a vector connecting the control point and the end point.

The cubic Bezier curve has an angle of 90 ° between a straight line connecting the starting point and the ending point and a straight line connecting the starting point and the first control point.
If the angle between the straight line connecting the start point and the end point and the straight line connecting the second control point and the end point is 90 ° or less,
Does not protrude. Whether the angle is 90 ° or less can be determined by the sign of the inner product of the vector, and the inner product of this vector can be obtained by a simple combination of the product and sum of each component of the vector. It is possible to determine whether or not it is a protruding type in a short processing time.

In another preferred aspect, when the cubic Bezier curve is determined to be a cross shape in the cross elimination step, whether the cubic Bezier curve can be approximated by a line segment is further determined according to a predetermined criterion. It is determined whether or not the line segment approximation is possible. When the line segment approximation is determined to be possible, the division of the cubic Bezier curve is stopped, and only when the line segment approximation is determined to be impossible, the tertiary Bezier curve is determined. Divide the curve into two cubic Bezier curves.

Generally, a crossed cubic Bezier curve can be divided into a combination of non-intersecting cubic Bezier curves by dividing it to some extent. In some cases, it may happen. In such a case, there is a risk of falling into an infinite loop. However, according to this aspect, the line segment approximation is independently determined for the crossing shape, and if possible, the line segment approximation is performed at the stage of the crossing shape. , Such an infinite loop can be prevented.

Further, according to the present invention, the starting point, the first control point, the second
A first step of recursively dividing a cubic Bezier curve defined by a control point and an end point, wherein the cubic Bezier curve resulting from the division is a start point, a first control point, and a second control point of the cubic Bezier curve.
A first step of repeating division until a quadrangle obtained by connecting the control point and the end point in this order becomes a standard cubic Bezier curve that becomes a convex quadrangle, and a standard cubic Bezier curve obtained by the first step The distance between the middle point of the two control points of the curve and the line segment connecting the start point and the end point is calculated,
If the distance is equal to or smaller than a predetermined allowable value, coordinate data of the start point and the end point of the curve is generated as approximate line segment data of the curve. If the curve is not equal to or smaller than the allowable value, the curve is divided into two cubic Bezier. A second step of dividing into curves,
When a standard form cubic Bezier curve is divided by the second step, a program for causing a computer to execute the third step of repeatedly applying the second step to the cubic Bezier curve resulting from the division is recorded. A recording medium is provided.

When the program recorded on the recording medium is executed by the computer system, the method of approximating the cubic Bezier curve according to the present invention can be realized. The concept of the recording medium includes all machine-readable media on which programs are recorded, such as a flexible disk, a hard disk, a CD-ROM, a magneto-optical disk, a ROM (Read Only Memory), and a flash memory. Note that a method of providing and recording the above program via a communication medium is also included in the aspect of the present invention.

[0034]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Preferred embodiments of the present invention will be described below with reference to the drawings.

[Explanation of Principle] The principle of the line segment approximation process of the cubic Bezier curve in this embodiment will be described. In the present embodiment, a cubic Bezier curve is recursively divided, and when a segment resulting from the division (this segment is also a cubic Bezier curve) satisfies a predetermined condition, a line connecting the start point and the end point of the segment And a cubic Bezier curve to be drawn is approximated as a series of a plurality of line segments. Here, in the present embodiment, in determining whether or not the line segment approximation is possible, the shape of the segment is determined at any time, and a segment having a poor shape that causes deterioration in the approximation accuracy has a good shape by repeating the division. Return to segments.

Shapes having poor properties include a protruding shape and a crossed shape. The projecting shape is, as shown in FIG. 7 (or FIG. 16 described above), a start point P0, an end point P3, and two control points P1,
Cubic Bezier curve P0, P1, P2, P3 defined by P2
In this case, when perpendicular lines are drawn to the line segment P0 P3 at the start point P0 and the end point P3, a part of the cubic Bézier curve protrudes outside the region sandwiched by both perpendicular lines. Regardless of how flat the protruding cubic Bezier curve is, if the line segment is approximated by the line segment P0 P3 connecting the starting point and the ending point, the protruding portion is not drawn because the protruding portion is not drawn, and the approximation accuracy This is a problem.
The term "intersecting" refers to a state in which the cubic Bezier curve intersects a straight line connecting the start point P0 and the end point P3, as shown in FIG. Such an intersecting cubic Bezier curve may be subjected to line segment approximation even though it is not flat.
The definition of the cross shape is not limited to this, and a case where a line segment connecting the start point P0 and the end point P3 intersects with a straight line connecting the two control points may be defined as a cross shape.

In the present embodiment, such a protruding or intersecting cubic Bezier curve is reduced to a group of segments of the standard type having good properties as shown in FIG. It is determined whether minute approximation is possible.

The determination of the approximation of the line segment with respect to the segment of the standard form is made based on the distance between the middle point between the control points P1 and P2 and the line segment P0 P3 connecting the start point and the end point. That is, as shown in FIG. 10, it is determined whether or not the distance d12 between the midpoint P12 of the control points P1 and P2 and the line segment P0 P3 is equal to or smaller than a predetermined allowable value δ. In some cases, line segment approximation is performed. Here, as the allowable value δ, for example, a bitmap device (also referred to as a raster output device, which is a drawing destination of a curve; a bitmap memory, a display device,
(Including a printer or the like).

The segment of the standard form has a starting point P0 and an ending point P
Since there is no outward projection from between the three points, there is no problem even if approximated by the line segment P0 P3 connecting the start and end points, and there is no intersection with the line segment P0 P3. Even if the approximation of the line segment is determined based on the distance from the line segment P0 P3 connecting the start point and the end point, the erroneous determination (see FIG. 18) as in the prior art (c) does not occur.

Next, the validity of judging the possibility of line segment approximation based on the distance from the midpoint P12 of the control points P1 and P2 to the line segment P0 P3 connecting the start point and the end point will be described with reference to FIG.

It is well known that a cubic Bezier curve is composed of a starting point, an ending point and two control points and does not protrude from the inside of a convex area (square) (convex hullness). In the cubic Bezier curve, the distance between the point and the line segment P0 P3 exceeds the distance d12 from the midpoint P12 of the control points P1 and P2 to the line segment P0 P3 regardless of the point selected on the curve. Never. The proof is as follows.

In the standard cubic Bezier curve, the control point P1
, P2 are on the same side of the straight line P03. Therefore, in FIG. 10, when the points P01, P12, P23, P012, P123, and P0123 are defined in the same manner as in the case of FIG. 14 described above, these points are all controlled points P1, P2 with respect to the straight line P03.
On the same side as P2. Here, assuming that the distances between the control points P1 and P2 and the line segment P03 are d1 and d2, respectively, each point P0
1, P12, P23, P012, P123, P0123, the line segment P03 and the distance can be expressed as follows using d1 and d2, respectively.

[0043]

D01 = d1 / 2 d12 = (d1 + d2) / 2 d23 = d2 / 2 d012 = (d01 + d12) / 2 = (2d1 + d2) / 4 d123 = (d12 + d23) / 2 = (d1 + 2d2) / 4 d0123 = (d012 + d123) / 2 = (3d1 + 3d2)
/ 8 From these equations, the distances d01, d23, d012, d123,
d0123 is a distance d12 or less between the midpoint P12 of the control points P1 and P2 and the line segment P03. In other words, the point P12 is the point P0
It can be said that it is a point farthest from the straight line P0 P3 among 1, P12, P23, P012, P123, and P0123.

Here, the cubic Bezier curve P0.P1.P2
P3 is two cubic Bezier curves P0 without changing the shape
P01 ・ P012 ・ P0123 and P0123 ・ P123 ・ P23 ・ P3
As described above, it can be divided into
Next Bezier curves P0, P01, P012, P0123 and P0123
P123, P23, and P3 are four points P0, P01, and P01, respectively.
2, the convex hull formed by P0123 and the four points P0123, P123,
Passing through the inside of the convex hull formed by P23 and P3 is guaranteed by its convex hull property. Therefore, the original cubic Bezier curves P0, P1, P2, P3 are represented by points P0, P01, P012.
, P0123, P123, P23, and P3 do not protrude from the convex polygon.

In addition, the point P12 is divided into points P01, P12, P23,
Considering that it is the farthest point from the straight line P0 P3 among P012, P123, and P0123, any point of the cubic Bezier curve P0, P1, P2, P3 can be selected.
The distance between that point and the straight line P0 P3 is the point P12 and the straight line P0 P
3 or less. Therefore, the point P12 and the straight line P0
If the distance d12 to P3 is equal to or less than a predetermined allowable value δ, the distance between the point and the straight line P0 P3 is equal to or less than the allowable value δ, regardless of the point selected on the cubic Bezier curve P0. .

In the first place, the line segment approximation of the cubic Bezier curve is 3
Line P0 connecting all points on the next Bezier curve to the start point and end point
It is based on the fact that if the drawing is performed within the allowable value δ (for example, one pixel) from P3, the drawing result is the same as that of drawing the line segment P0 P3 even if drawing is performed according to the definition formula of the curve. In the standard cubic Bezier curve,
As described above, the midpoint P12 between the control points P1 and P2 and the line segment P0
If the distance to P3 is equal to or less than the allowable value δ, it is guaranteed that all points on the curve are within the allowable value δ when viewed from the line segment P0 P3. In such a case, it can be said that performing line segment approximation is appropriate.

As described above, according to the present embodiment, the cubic Bézier curve is divided into segments of a standard form without protrusions and intersections, and it is determined whether or not line segment approximation is possible. There is no deterioration in accuracy.

[Explanation of Specific Example] An apparatus configuration and a processing procedure of the present embodiment for specifically realizing the method according to the above principle will be described.

FIG. 1 is a diagram showing a schematic configuration of a graphic drawing apparatus according to the present embodiment. FIG. 1 shows a configuration in which a drawing instruction is input in the form of a PDL (page description language).

In FIG. 1, a PDL interpreter 10 interprets input PDL data in order. Where P
If the DL data instructs the drawing of a line segment,
The PDL interpretation unit 10 passes the data of the line segment (the coordinates of the start point and the end point) to the straight line drawing unit 12 and
Draws a line segment in the drawing buffer 14 based on this data.

On the other hand, if the PDL data instructs the rendering of the cubic Bezier curve, the PDL interpreter 10
From the PDL data, the coordinate data of the start point and end point of the cubic Bezier curve and two control points are extracted, and the coordinate data of these four points is passed to the curve processing unit 16. In the curve processing unit 16, the approximation determination unit 18 determines whether the cubic Bezier curve can be approximated by a line segment based on the coordinate data of these four points. The details of this determination processing will be described later in detail. If the approximation determining unit 18 determines that the line segment cannot be approximated, the data of the four points defining the cubic Bezier curve is passed to the curve dividing unit 20. Curve division unit 20
Divides the cubic Bezier curve into two cubic Bezier curves (segments) based on the data of these four points.
This dividing method may be the same as the method described in the related art. The curve division unit 20 compares the data of the start point, the end point, and the control point defining each segment with the approximation determination unit 1.
8, the approximation determination unit 18 determines whether or not line segment approximation is possible for each segment based on these data. The curve processing unit 16 repeats the above processing recursively until it is determined that the segment can be approximated by a line segment.

When it is determined that the segment can be approximated by a line segment, the approximation determining unit 18 passes the coordinates of the start point and the end point of the segment to the straight line drawing unit 12 as data representing an approximate line segment of the segment. Then, the straight line drawing unit 12 draws a line segment connecting the start point and the end point on the drawing buffer 14. In this way, each recursively divided segment is drawn by the line segment connecting the start point and the end point, and the drawing by the line segment approximation of the cubic Bezier curve is completed.

Next, the processing procedure of the curve processing section 16 will be described in detail with reference to a flowchart. (1) General Description FIG. 2 shows a general flow of the processing of the curve processing unit 16. In FIG. 2, when the curve processing unit 16 acquires the definition data of the cubic Bezier curve (that is, the coordinates of the start point P0, the end point P3, and the control points P1, P2) from the PDL interpretation unit 10 (S10), first, P0 = P1. An extremely rare exceptional case such as the case where P = P2 = P3 or the case where P0 = P3 is eliminated (S20). In S20, it is determined whether or not the given cubic Bezier curve corresponds to such an exceptional case.
The curve is divided, and the same determination is repeated for each segment obtained by the division. In S20, such determination and division processing is performed recursively. If a segment that does not correspond to an exceptional case is obtained at each stage of the recursive processing, the definition data of the segment is changed to the next protruding form. It is passed to the step of exclusion processing (S30).

At S30, the given segment is
It is determined whether or not it is a protruding shape as shown in (1). If the protruding shape is determined, the segment is divided, and the same processing is recursively repeated for each segment as a result of the division. When a segment that is not protruding is obtained at each stage of the recursive processing, the definition data of the segment is passed to the next cross-shaped exclusion processing (S40).

In S40, the given segment is
It is determined whether or not it is an intersecting shape as shown in (1). If the intersecting shape is determined, the segment is divided, and the same processing is recursively repeated for each segment as a result of the division. When a segment that does not intersect is obtained at each stage of such recursive processing, the definition data of the segment is passed to the next approximation processing (S50).

The segment passed to S50 is a standard segment as shown in FIG. 9 as a result of the processing up to S40. In S50, for such a segment of the standard form, the midpoint P12 of the two control points and the baseline P0
Whether or not line segment approximation is possible is determined based on the distance to P3. If it is determined that line segment approximation is not possible, the segment is divided, and the same processing is recursively repeated for each segment as a result of division. When a segment that can approximate a line segment is obtained at each stage of such recursive processing, the curve processing unit 1
6 passes the coordinate data of the start point and the end point of the segment to the straight line drawing unit 12, and approximately draws the segment as a line segment (base line) connecting the start point and the end point. By such processing, the cubic Bezier curve to be drawn is finally approximated as a series of line segments.

Hereinafter, a more specific processing procedure will be described for each of the exception exclusion processing (S20), the protruding shape exclusion processing (S30), the cross-shaped exclusion processing (S40), and the approximation processing (S50).

(2) Exception Exclusion Process FIG. 3 is a flowchart showing a specific procedure of the exception exclusion process (S20). First, in the exception elimination process, the approximation determination unit 18 starts the starting point P0 of the target cubic Bezier curve.
It is determined whether the coordinates of the end point P3 and the control points P1 and P2 match, that is, whether P0 = P1 = P2 = P3 (S202). If the determination result is true, the start point P0, the end point P3, and the control points P1 and P2 have been reduced to one point. In such a case, for example, the one point is drawn and the processing ends. If the determination result in S202 is false, the approximation determination unit 18 further determines whether P0 = P3 (S204). When the result of this determination is true, the target cubic Bezier curve has a starting point P0 as shown in FIG.
And the end point P3 match. In such a case,
Since the start point P0 and the end point P3 are the same point, a line segment connecting the start point and the end point cannot be formed, which is not suitable for line segment approximation. Therefore, in this case, the target cubic Bezier curve is divided into two segments by the curve dividing unit 20 (S206), and the processing from S202 onward is repeated for each of the two segments (S20-1, S20-2). ). That is, the curve division unit 20 returns the data of the start point, the end point, and the control point of each of the two segments obtained by the division to the approximation determination unit 18, and the approximation determination unit 18 performs the processing of S202 and S204 for each of these two segments. Perform determination processing. In this case, the approximation determination unit 18
The processing of the first segment may be performed in advance by stacking the segment data, and the processing of the second segment may be performed when the processing of the first segment is completed. In general, the cubic Bezier curve is divided once, so that the start point and the end point do not coincide with each other. Therefore, the number of divisions performed in the exception exclusion process is at most one. In this manner, the segment determined not to be an exception case proceeds to the next protruding shape elimination process (S30).

(3) Projection-type exclusion processing FIG. 4 shows a specific procedure of the projection-type exclusion processing. In this protruding shape exclusion processing, the approximation determination unit 18
First, the start point P0 to the end point P3 of the segment to be processed
Product of the vector P0 P3 going to the first control point P1 from the starting point P0 is calculated (S3
02), it is determined whether or not the inner product is negative (S30).
4). If the inner product is negative, the angle between the vector P0 P3 and the vector P0 P1 is larger than 90 °, and the target segment has a protruding shape as shown in FIG.

On the other hand, if it is determined in S304 that the inner product is 0 or more, the vectors P0 P3 and P0 P1
Is less than 90 °, the inner product of the vector P3 P0 from the end point P3 to the start point P0 and the vector P3 P2 from the end point P3 to the second control point P2 is further calculated (S306). Is determined (S308). If this inner product is negative, the vector P3
This means that the angle between P0 and the vector P3 P2 is greater than 90 °, and the target segment has a protruding shape. In this processing, the inner product of the two vectors (x1, y1) and (x2, y2) can be obtained by a simple combination of multiplication and addition of (x1 x2 + y1 y2). Can be executed with a small number of operations.

If the result of the determination is true in either S304 or S308, that is, if the target segment is determined to be a protruding shape, the segment is divided by the curve dividing section 20, and
S30 for each of the two segments resulting from the division
2 is recursively repeated (S30-1, S30
-2). Also here, the approximation determination unit 18 sequentially performs processing of each segment using, for example, a stack.

If the judgment results in S304 and S308 both become false during such a recursive process, the segment is not a protruding type, and the segment proceeds to the crossing type elimination process (S40). That is, according to this protruding type elimination processing, a protruding segment as shown in FIG. 7 can be eliminated, but a cross-shaped segment as shown in FIG. 8 still remains. Perform processing to eliminate the crossover.

(4) Crossover Elimination Process FIG. 5 shows a specific procedure of the crossover exclusion process. In this cross-shaped exclusion processing, the approximation determination unit 18
First, a straight line P0 P3 connecting the start point P0 and the end point P3 of the segment to be processed, a first control point P1 and a second control point P2
Are calculated at the intersection with the straight line P1 P2 connecting
2). This is, for example, the straight line P0 P3 and the straight line P1 P2
, And solving these simultaneous equations. And this intersection is the starting point P0 and the ending point P
Then, it is determined whether or not the line segment is located on the line segment P0 P3 connecting to the line 3 (S404). For example, a straight line P0 P3 and a straight line P1 P2
Is expressed in a parameter display format, the equations of these straight lines can be obtained very easily, and their intersections can also be obtained by simple matrix calculation. Further, it is determined whether or not the intersection is on the line segment P0 P3. Is also easy.

If the result of the determination in S404 is false, that is, if the straight lines P0 P3 and P1 P2 are outside the line segment P0 P3, the control points P1 and P2 are set to straight lines as long as the segment is not protruding. It is guaranteed to be on the same side as viewed from P0 P3. Therefore, in this case, it is found that the segment is not the crossed one but the standard one as shown in FIG. 9, and the process proceeds to the next approximation processing (S50).
If there is no intersection between the straight line P0 P3 and the straight line P1 P2, that is, if both straight lines are parallel, the control point P1
, P2 are guaranteed to be on the same side as viewed from the straight line P0 P3. In this case as well, it is determined that the segment is not a crossing (that is, a standard), and the approximation processing (S5) is performed.
Go to 0).

Further, not only in the case shown in FIG. 8 but also in the case shown in FIG. 12, the determination result of S404 is true, so according to S404, the starting point P0, the control points P1, P2 and The case where the end point P3 forms a concave square as shown in FIG. 12 can also be eliminated. Therefore, the segment that proceeds to the approximation processing (S50) is the start point P0
, And the control points P1, P2 and the end point P3 form a convex square as shown in FIG.

When the result of the determination in S404 is true, it is determined that the segment is a cross. Here, an intersecting cubic Bezier curve is generally divided into a combination of non-intersecting cubic Bezier curves by dividing the curve several times. The worst case is considered to fall into a loop.
Therefore, in the present embodiment, in order to avoid such an infinite loop, when the segment is determined to have an intersecting shape,
The same determination processing as in the above-described conventional technique (a) is performed on the segment, and if possible, the line segment is approximated at the stage of the crossing. That is, referring to FIG. 13, the approximation determining unit 18 first obtains a distance d1 between the baseline P0 P3 and the first control point P1 (S406), and compares this distance d1 with a predetermined allowable value δ. (S408). Here, the distance d1 can be obtained by a known distance formula between a point and a straight line. If the distance d1 is larger than the allowable value δ, it is determined that the line segment cannot be approximated, the segment is divided into two by the curve dividing unit 20, and the processing of S402 and subsequent steps is performed recursively on each segment as a result of division. (S40-1, S40-2). On the other hand, if it is determined in step S408 that the distance d1 is equal to or smaller than the allowable value δ, the distance d2 between the baseline P0 P3 and the second control point P2 is further obtained (step S408).
410), and compares this distance d2 with a predetermined allowable value δ (S412). If the distance d2 is larger than the allowable value δ, the segment is divided into two, and the processing after S402 is recursively applied to the division result (S40-
1, S40-2). If the determination result in S412 is true, that is, if both d1 and d2 are equal to or smaller than the allowable value δ, the segment is determined to be flat, and the segment is approximated by the baseline P0 P3. That is, the approximation determination unit 1
8 passes the coordinates of the start point P0 and the end point P3 of the segment to the straight line drawing unit 12 to draw the line segment P0 P3 (S
414).

By such a process, even if the crossing is made, if the line is sufficiently flat, the line segment is approximated, so that it is possible to avoid falling into an infinite loop.

The steps from S406 to S414 are provided in order to avoid the infinite loop in the processing, and have the property that the target cubic Bezier curve does not fall into such an infinite loop. If it ’s good,
These steps may be omitted. That is, in this case, the segment is divided as soon as it is determined to be the cross shape in S404 (S416), and the cross shape elimination process may be applied recursively to each segment.

In the above description, it is determined that the line segment can be approximated when both d1 and d2 (see FIG. 13) are equal to or smaller than the allowable value δ. However, instead of this criterion, d1 + d2 is changed to the allowable value δ.
The following may be used as a criterion for approximating a line segment.

(5) Approximation Processing For the segment for which the determination in S404 is false (that is, the segment of the standard form), the processing of the procedure shown in FIG. 6 is performed.

That is, the approximation determining unit 18 determines whether the control point P1
, P2 the distance d1 between the midpoint P12 and the baseline P0 P3
2 (see FIG. 10) (S502), and this distance d12 is calculated.
Is compared with the allowable value δ (S504). This distance d12 can also be obtained from a formula for the distance between a known point and a straight line.
If the distance d12 is larger than the allowable value δ, it is determined that the approximation is impossible, and
Divide into two. Here, the segment to be subjected to the approximation processing includes the start point P0, the control points P1, P2
2 and the end point P3 are convex cubic Bezier curves forming a convex square as shown in FIG. Therefore, the result of dividing such a segment into two is a similar convex cubic Bezier curve. Therefore, since each segment of the division result is also guaranteed to be in the standard form, the processing of S502 and subsequent steps may be applied recursively to each division result (S
50-1, S50-2).

If it is determined in step S504 that the distance d12 is equal to or less than the allowable value δ, the segment is determined to be flat, and the segment is determined to be the baseline P0 P3.
Approximation. That is, the approximation determination unit 18 passes the coordinates of the start point P0 and the end point P3 of the segment to the straight line drawing unit 12, and draws the line segment P0 P3 (S508).

As described above, if the segment is recursively divided in the approximation processing (S50), each segment can be approximated by a line segment without fail.
The next Bezier curve is finally approximated as a series of line segments.

The control points P 1, P 1,
Properties of the midpoint P12 of P2 (ie, baseline P0 P3
(The property that the distance from the point is greater than any point on the segment) is the start point P0, the control points P1, P2, and the end point P
Since 3 also holds when a concave quadrangle as shown in FIG. 12 is formed, it is not always necessary to eliminate such segments in the cross-shaped exclusion processing. However, in the case as shown in FIG. 12, if the relevant segment is divided in S506 of the approximation processing, there is a possibility that a crossed form will appear in the divided result. In this case, the process returns to the crossed form elimination processing for each segment of the divided result. Must be processed.

As described above, in this approximation processing,
Whether or not line segment approximation is possible is determined only from the distance between the midpoint P12 of the control points P1 and P2 and the baseline P0 P3. The calculation of the distance between a point and a straight line is a relatively complicated calculation. For example, in the prior art (a), such a complicated calculation had to be performed twice after each segment, but in the present embodiment, Only one such complicated calculation is required. Further, in this embodiment, once the segment is divided into the standard form (convex) (that is, if the process proceeds to S50), the division result becomes the standard form no matter how much the segment is divided thereafter. It is only necessary to repeat the determination of S50 with a small amount. Considering that many cubic Bezier curves that are usually created have such a standard form, it can be said that this embodiment has an extremely large effect of reducing the amount of arithmetic processing.

The preferred embodiment of the present invention has been described above. As described above, according to the present embodiment, 3
By dividing the next Bezier curve into segments of the standard form and determining whether or not the line segment can be approximated, erroneous determination or deterioration of approximation accuracy can be prevented, and the time required for approximation processing can be significantly reduced. .

This embodiment can be realized in a computer system by loading a program describing each of the above-described processes into a memory and executing the program by a CPU. Such programs are:
It is provided in a state recorded on a recording medium. As the recording medium, for example, a flexible disk, a CD-ROM, a memory card, or the like can be used. The program recorded in the recording medium is installed in a storage device incorporated in the computer system, for example, a hard disk device, to execute the program to implement an apparatus that realizes each processing described in the present embodiment. Contribute. In addition, it is also possible to realize each of the above-described processes as a logic circuit and implement the present embodiment in hardware.

In the above embodiment, the process of approximating a cubic Bezier curve as a series of line segments has been described as an example, but the present invention is not limited to this. The present invention provides a method for filling a region having a cubic Bezier curve in at least a part of a contour, determining whether a point is inside such a region (internality determination), or multiplying such two regions. Can be used as a pre-process of various processes related to a graphic including a cubic Bezier curve, such as the calculation process of.

In the present invention, the criterion for judging the protruding shape or the cross shape in the protruding shape exclusion process or the cross shape exclusion process is
The invention is not limited to those described in the above specific examples. Further, the order of application of the protruding shape elimination process and the cross-shaped exclusion process may be reversed from that in the above specific example. However, from the viewpoint of processing speed, the order of the above specific example is more desirable.

[0080]

As described above, according to the present invention,
If the cubic Bezier curve has a shape that causes misjudgment, such as a protruding shape or a crossed shape, the division is further repeated. To perform line segment approximation, it is possible to prevent approximation accuracy from deteriorating. Further, the flatness determination criterion is that the distance between the midpoint of the two control points of the cubic Bezier curve (segment) and the baseline is equal to or less than a predetermined allowable value, and thus the flatness determination is performed. Can be reduced.

[Brief description of the drawings]

FIG. 1 is a diagram showing a schematic configuration of a graphic drawing apparatus according to an embodiment of the present invention.

FIG. 2 is a flowchart showing an overall flow of a method for approximating a cubic Bezier curve in the embodiment.

FIG. 3 is a flowchart showing a specific procedure of an exception exclusion process.

FIG. 4 is a flowchart showing a specific procedure of a protruding shape exclusion process.

FIG. 5 is a flowchart showing a specific procedure of crossover exclusion processing.

FIG. 6 is a flowchart illustrating a specific procedure of an approximation process.

FIG. 7 is a diagram illustrating an example of a protruding cubic Bezier curve.

FIG. 8 is a diagram illustrating an example of an intersecting cubic Bezier curve.

FIG. 9 is a diagram showing an example of a standard cubic Bezier curve.

FIG. 10 is a diagram for describing a criterion for determining the flatness of a cubic Bezier curve according to the present invention.

FIG. 11 is a diagram illustrating an example of a cubic Bezier curve in which a start point and an end point match.

FIG. 12 is a diagram showing a start point, an end point, and a control point of one type of a cubic Bezier curve eliminated by the cross-shaped exclusion process.

FIG. 13 is a diagram for explaining a method for determining whether or not line segment approximation of an intersecting cubic Bezier curve is possible.

FIG. 14 is a diagram for explaining a method of dividing a cubic Bezier curve.

FIG. 15 is a diagram for explaining a determination criterion for approximation of a line segment of a cubic Bezier curve in the related art (a).

FIG. 16 is a diagram for explaining a problem of a criterion in the conventional technique (a).

FIG. 17 is a diagram for explaining a problem of a criterion of the conventional technique (b).

FIG. 18 is a diagram for explaining a problem of a criterion in the conventional technique (c).

FIG. 19 is a diagram for explaining a problem of a criterion of the conventional technique (d).

FIG. 20 is a diagram for explaining a problem of a criterion in the conventional technique (e).

[Explanation of symbols]

10 PDL interpretation unit, 12 straight line drawing unit, 14 drawing buffer, 16 curve processing unit, 18 approximation determination unit, 20
Curve division.

Claims (7)

[Claims] 1. A cubic Bezier curve defined by a start point, an end point and two control points is recursively divided, and when each of the divided segments is determined to be flat, the division is stopped. A line of a cubic Bezier curve that generates a series of approximate line segment data that approximates a given cubic Bezier curve by generating coordinate data of the determined start point and end point of the segment as approximate line segment data of the segment. In the minute approximation method, the segment obtained by the division is a standard form that is neither a protruding shape protruding outside the start point or end point of the segment nor a crossed shape intersecting a line segment connecting the start point and end point of the segment. If it is determined that the segment is a Bezier curve, the representative value related to the thickness of the segment is compared with a preset allowable value, and if the representative value is smaller than the allowable value, Line approximation method of a cubic Bezier curve, characterized in that said segments are determined to be flat. 2. The method according to claim 1, wherein the representative value relating to the thickness of the segment is a distance between a midpoint between two control points of the segment and a line segment connecting a start point and an end point of the segment. A line approximation method for a cubic Bezier curve. 3. A first step of recursively dividing a cubic Bezier curve defined by a start point, a first control point, a second control point, and an end point, wherein the cubic Bezier curve obtained as a result of the division is the three-dimensional Bezier curve.
A first step of repeating division until a quadrangle obtained by connecting the start point, the first control point, the second control point, and the end point of the next Bezier curve in this order becomes a standard cubic Bezier curve that is a convex quadrangle; For the standard cubic Bezier curve obtained in one step, the distance between the middle point of the two control points of the curve and the line segment connecting the start point and the end point is obtained, and this distance is equal to or less than a predetermined allowable value. Generating the coordinate data of the start point and the end point of the curve as approximate line segment data of the curve, and dividing the curve into two cubic Bezier curves if the distance is not smaller than the allowable value; In the case where the standard form cubic Bezier curve is divided by the second step, the given cubic Bezier curve is approximated by repeatedly applying the second step to the divided cubic Bezier curve. Series approximation line approximation method of a cubic Bezier curve and generates a line segment data that. 4. The method according to claim 3, wherein in the first step, it is determined whether or not the given cubic Bezier curve has a protruding shape protruding outside a start point or an end point, and is determined to be a protruding shape. In the case, a protruding shape eliminating step of dividing the cubic Bezier curve into two cubic Bezier curves and recursively repeating the dividing process until it is determined that the resulting cubic Bezier curve is not a protruding shape, It is determined whether or not the cubic Bezier curve is an intersecting shape in which a line segment connecting the starting point and the end point of the cubic Bezier curve intersects with a straight line connecting the two control points. Divide the Bezier curve into two cubic Bezier curves,
A crossover rejection step of recursively repeating the dividing process until it is determined that the cubic Bezier curve resulting from the division is not a crossover, and applying in a predetermined order: . 5. The method according to claim 4, wherein the determination as to whether or not the object is a protruding shape in the protruding shape eliminating step includes an inner product of a vector connecting the starting point and the ending point and a vector connecting the starting point and the first control point, and the starting point. And a vector connecting the end point and a vector connecting the second control point and the end point. 6. The method according to claim 4, wherein when the cubic Bezier curve is determined to be a cross shape in the crossing elimination step, the cubic Bezier curve can be approximated to a line segment according to a predetermined criterion. And if it is determined that the line segment can be approximated, a line segment approximation is performed to
The division of the second-order Bezier curve is stopped, and the cubic Bezier curve is divided into two
A line approximation method for a cubic Bezier curve, which is divided into a second-order Bezier curve. 7. A first step of recursively dividing a cubic Bezier curve defined by a start point, a first control point, a second control point, and an end point.
A first step of repeating division until a quadrangle obtained by connecting the start point, the first control point, the second control point, and the end point of the next Bezier curve in this order becomes a standard cubic Bezier curve that becomes a convex quadrangle; For the standard cubic Bezier curve obtained in one step, the distance between the middle point of the two control points of the curve and the line segment connecting the start point and the end point is obtained, and this distance is equal to or less than a predetermined allowable value. Generating coordinate data of the start point and the end point of the curve as approximate line segment data of the curve, and dividing the curve into two cubic Bezier curves if the curve is not smaller than an allowable value; When the standard form cubic Bezier curve is divided by the two steps, a third step of repeatedly applying the second step to the cubic Bezier curve resulting from the division. Recording medium recording a gram.