JPH0363891A - Bezier curved surface approximation circuit - Google Patents

Abstract

PURPOSE:To make the linear approximation of a Bezier curved surface into hardware and to accelerate a processing by simplifying the decision of a convergence condition by considering the resolution of a device which performs the display of the Bezier curved surface. CONSTITUTION:The above circuit is equipped with first and second register files 21, 22 which store coordinate points (x), (y), respectively, and first and second ALUs 11, 13 which receive data from the register files 21, 22 and perform the calculation of midpoint of the coordinate point. Also, it is equipped with a third ALU 12 with performs an addition arithmetic operation from the computed results of those two pairs of ALUs 11, 13, and a control circuit 3 which controls the register files 21, 22 and the ALUs 11-13. Then, the Bezier curved surface can be obtained by approximating with a straight line. In such a way, it is possible to perform a fast processing by realizing the making of the linear approximation of the Bezier curved surface into the hardware by simplifying a process to find the convergence condition of the linear approximation.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a Bezier curve generation circuit, and particularly to a circuit that approximates a Bezier curve with a straight line.

[Conventional technology]

Generally, a Bezier curve is expressed by approximating one Bezier curve with several straight lines, and the method for finding this straight line has conventionally been done using software.

The conventional technique will be explained with reference to a flowchart in FIG. 3 and a coordinate diagram of a Bezier curve in FIG. 4. There are two methods for linear approximation of a Bezier curve: a functional method and a geometric method, but the geometric method is often used in terms of processing speed. FIG. 4 is a coordinate diagram explaining the geometric method. Point P. l pHP2゜P3 is the Huntroll point that uniquely defines the Bezier curve B, and the Bezier curve B is defined by the control point P o "P3. In the geometric method, it is created by the control points P. to P3. Each midpoint m of the line segment.

rnl, m2. seek. Furthermore, these midpoints m. ~
The midpoint n of each line segment made by m2. Find rnl, then line segment n. , nl, find the midpoint Oo.

0° found in this process coincides with the - point on the Bezier curve B. The line segment ``;, σJ1 becomes a straight line when the Bezier curve B is approximated by a straight line.

Next, in the geometric method, line segment P. Oo.

It is determined whether the approximation is sufficient using Oo P 3. Starting point P. The Bezier curve from the end point O6 is a trapezoid P. 2mo
, no, Oo, and the line segment P o Oo and the point m0 or n. If the distance ', K is within a certain range, then the line segment P. It is determined that Oo and 0oP3 are sufficient to linearly approximate the Bezier curve B. If the distance ', K is greater than the defined value, then the point Pa.

mo, nog The Bezier curve redefined by Oo is recursively approximated by a straight line. Similarly, the point Oo+ n++ mz+
Linear approximation is also performed for P3. In other words, line segment P. P3
and the distance 42. between the control points P2 and P3. ! ! If ' is larger than a certain value, the process of starting the process of finding the point Oo is performed recursively.

This will be explained using the flow diagram shown in FIG. When approximating Bezier curves using geometric methods using software, first,
In step 101, a process of finding a series of midpoints is performed, and the point m
Find o, mlz l11z+ no+ nl+ oo. Next, in step 102, a convergence condition is determined to determine whether this linear approximation is sufficient, and the condition is satisfied (step 103).
). In this example, line segment Pooo and point m. +
Find K at the distance nO. At this time, quite complicated processing including multiplication is required.

[Problem to be solved by the invention]

In the conventional Bezier curve generation method described above, the convergence condition is determined by determining the distance between the approximated straight line and the control point of the new Bezier curve, which requires extremely complicated processing. For this reason, it is difficult to implement with hardware and has the disadvantage that it cannot be made faster.

SUMMARY OF THE INVENTION An object of the present invention is to provide a Bezier curve generating circuit which can be implemented as a node and which can perform high-speed processing by simplifying the process of determining convergence conditions for linear approximation.

[Means to solve the problem]

The configuration of the Bezier curve approximation circuit of the present invention includes first and second register files that respectively store X and y coordinate points from the CPU, and receives data from these register files and calculates the midpoint of the coordinate points. It is equipped with first and second ALUs that perform the respective operations, a third ALU that performs addition operations from the operation results of these two sets of ALUs, and a control circuit that controls each register file and each ALU described above, and converts the Bezier curve into a straight line. It is characterized in that it can be obtained by approximating.

〔Example〕

Next, the present invention will be explained with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention, and FIG. 2 is a coordinate diagram illustrating the processing of this embodiment.

First, FIG. 2 will be explained. Point P0+Pl+P21
P3 is the control point of the Bezier curve B, and the point m0.
m1. m2 is the line segment P OP ! , P IP 2. P
2P is the midpoint of 3, and is the point n. +nl is line segment m. ml
, m1m2, and point Oo is the line segment n. It is the midpoint of nl.

These midpoints are the same as in FIG. 3, and the point m3 is the line segment P
3 It is the midpoint of P o.

Next, Bezier curve B is line segment P. In order to find a convergence condition for determining whether the approximation of Oo, 0OP3 is sufficient, the distances Q and Q' are found. The sum of distances Q and Q' is
It increases in proportion to the distance S between the line segment P 3 P o and the point Oo. If the device for displaying the Bezier curve is a CRT or a printer, the resolution is relatively low, so the pixels that display the points are discrete, and it is possible to determine whether the convergence condition is met based on the size of the distance S. Therefore, it is not necessary to calculate the distance Q as shown in FIG. 3 of the prior art.

By determining Q', it is possible to equivalently determine whether the convergence condition is met.

Next, FIG. 1 will be explained. 21 and 22 are register files that store coordinate points, and register file 2
1 stores the X coordinate of the coordinate point, and the register file 22 stores the Y coordinate of the coordinate store.

Control point P that defines Bezier curve B. ,Pl.

P2. P3 is connected to the host CP via data lines 31 and 32.
It is assumed that it is given by U. ALUII.

13 has functions of addition, subtraction, and right 1-bit shift. This ALU II, 13 uses addition and right 1-bit shift to find the midpoint of the X and y coordinates. In other words, A.L.
Process r(PO+Pl)/2-m0 using UII, 13
J is performed.

Processing to find a series of midpoints is performed, and register file 2
1.22 has a midpoint and a control point mar mll
m2.1113. not n, ++ Oar PO
+P3 is stored.

Next, using ALU II, 13, values Q and Q' proportional to the distance S between the point 0° and the line segment D] are obtained, respectively. AL
The values Q found in UII and 13, respectively.

Q' is added by the ALU 12 and the result is given to the control circuit 3. The control circuit 3 determines whether the convergence condition is satisfied based on the result from the ALU 12, and if the convergence condition is satisfied, sends the point Oo to the host CPU via the data lines 31 and 32.

If the convergence condition does not hold, the point 0° host C
Along with sending it to PU, point P is added to the register files 21 and 22 as a new control point of the Bezier curve. , mo+
Reset no and Oo and repeat the above process.

Repeat the same process for one control point 0°, rl, mtr P3.

The control circuit 3 exchanges data with the host CPU, ALU II, 12, 13, and register files 21 and 22.
control.

〔Effect of the invention〕

As explained above, the present invention simplifies the determination of the convergence condition by taking into account the resolution of the device that displays the Bezier curve, thereby making it possible to perform linear approximation of the Bezier curve using hardware, thereby speeding up the processing. There is an effect.

[Brief explanation of drawings]

Fig. 1 is a circuit diagram of an embodiment of the present invention, Fig. 2 is a coordinate diagram explaining the processing of this embodiment, Fig. 3 is a flowchart of the processing of the conventional Bezier curve generation method, and Fig. 4 is a diagram of the conventional Bezier curve generation method. FIG. 2 is a coordinate diagram illustrating a Bezier curve generation method. 3...Control circuit, 5...R/W line, 6
...Control line, 11-13...ALU,
21, 22...Register file, 31.32
...Data line, 101-103...Processing step.

Claims (1)

[Claims] first and second register files that respectively store x and y coordinate points from the CPU; first and second ALUs that receive data from these register files and calculate the midpoint of the coordinate points, respectively; These two sets of ALUs
1. A Bezier curve approximation circuit, comprising: a third ALU that performs an addition operation from the operation results; and a control circuit that controls each register file and each ALU, and obtains a Bezier curve by approximating it with a straight line.