Method and device for generation of quadratic curve signal

A method and system for generation of a quadratic curve signal expressed by f(x, y)=0 nonparametrically on coordinates X, Y, wherein, when linear micro-coefficients in the directions x, y are points (x, y) are given as fx, fy, respectively, the signs of fx, fy are decided and fx, fy are compared for dimensions with each other, thereby limiting the point to be selected next, to two points; then the value of new f(x,y) obtainable through selecting each point, are calculated; absolute values of the new f(x, y) are compared, the point giving the smaller value being selected as the next point; and repeating the aforementioned procedure, thereby to generate a quadratic curve signal expressed by f(x, y)=0.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
This invention relates to method and system for generation of a quadratic 
curve signal to be used effectively for expression of quadratic curves, 
including a straight line, in an aggregate of dots. 
A display unit (e.g. plasma display unit and cathode ray tube (CRT) of a 
raster scan system) expressing patterns in an aggregate of dots and a 
digital plotter are used in electronic computer systems, as a pattern 
output device. In case a human being utilizes a computer in a 
conversational mode through a display unit, such as for example, in 
computer aid design (CAD), a high speed, accurate and easy to observe 
curve, must be generated on the CRT. More particularly, the present 
invention relates to method and system for generation of a quadratic curve 
signal, which satisfies such requirements. The curve herein disclosed 
refers to a conic curve, including a straight line. 
2. Description of the Prior Art 
One method for generating curves at high speed utilizes a device known as 
digital differential analyzer (DDA). This method is described in detail in 
IEEE Transaction on Computers, November 1975, P. 1109-1110, "On Digital 
Differential Analyzer Circle Generation for Computer Graphics" P. G. 
McCrea and P. W. Baker. However, according to the method described 
therein, generation of conic curves leaves open the possibility of 
producing large errors. Furthermore, disadvantageously, such a method 
precludes generating a curve at reasonably high speed and smoothly. 
As an alternative from the foregoing method of generating parametric curves 
using the DDA method, a method for generating conic curves 
nonparametrically is disclosed, for example, in IEEE Transaction on 
Computers, September 1970, P. 783-793, "Incremental Curve Generation", Per 
E. Danielson; or in IEEE Transaction on Computers, December 1973, P. 
1052-1960, "An Improved Algorithm for the Generation of Nonparametric 
curves",, Bernard W. Jordan, et. al.. Insofar as a straight line and 
circle are concerned, a simpler method is disclosed in IEEE Transaction on 
Computers, October 1979 P. 728-738, "A High Speed Algorithm for the 
Generation of Straight Lines and Circular Arcs", Yasuhito Suenaga etal. 
The method disclosed by Jordan et al. is effective for generating curves 
which are accurate, smooth and superior in symmetricalness, in quadratic 
curve generation. However, that method has a shortcoming in that it 
requires a plurality of variable registers which involves a problem prone 
sequence and requires a large amount of time for processing, in the 
hardware carrying out the algorithm. 
Thus, in the prior art, there exists a need for a simple and inexpensive 
method and system for generation of quadratic curves, which can be carried 
out readily by simple hardware and which improves upon the Jordan method, 
on the basis of an algorithm for the quadratic curve generation, suggested 
thereby. 
Prior to describing the invention, the Jordan method of generating a 
quadratic curve will be described. FIG. 1 is an explanatory drawing of 
Jordan's method. FIG. 2 is a flow chart of the algorithm representing such 
method. In FIG. 1, there is shown the case wherein a circle is set forth 
as an example. 
First, a two dimensional curve is given by the below expression (1). 
EQU f(x,y)=0 (1) 
Then, a derived function is given as below expressions (2) through (6). 
##EQU1## 
Assuming z=f(x, y), the curve f(x, y)=0, will be conceived to be an 
intersection with the plane x,y cut with three dimensional curves z=f(x, 
y) and z=0. Since values of x, y are discrete in the curve f(x, y)=0 which 
is expressed as a dot pattern, these do not aways appear on plane z=0, and 
value f(x, y) can be any of f(x, y)&gt;0, =0, &lt;0. Therefore, a dot pattern 
satisfying f(x, y)=0 approximately can be drawn by selecting lattice point 
coordinates of x, y in sequence, so that f(x, y) will be minimized. 
The case wherein a circle is drawn, as an example of a quadratic curve, is 
shown in FIG. 1. Suppose the curve is drawn in the direction indicated by 
arrow from coordinates Ps. In FIG. 1, if the present spot is P, the point 
to move next will be either Px, Pxy or Py. However, in FIG. 1, the point 
present on the plane x, y is Ps only, and those points of P, Px, Pxy and 
Py are not always ones to appear on plane x, y. Now, if a distance from 
f(x, y) to f(x, y)=0, at point P is saved as f.sup..alpha., then the value 
f(x, y) at points Px, Pxy, Py, can be expressed by the below expressions 
(7) through (9). 
EQU f(x+.DELTA.x,y).rarw.f.alpha.+fx.multidot..DELTA.x+1/2fxx(.DELTA.x.sup.2)+ 
. . . (7) 
EQU f(x,y+.DELTA.y).rarw.f.alpha.+fy.multidot..DELTA.y+1/2fyy(.DELTA.y.sup.2)+ 
. . . (8) 
EQU f(x+.DELTA.x,Y+.DELTA.y).rarw.f.alpha.+fx.multidot..DELTA.x+fy.multidot..DE 
LTA.y+1/2{fxx(.DELTA.x).sup.2 +2fxy(.DELTA.x)(.DELTA.y)+fyy(.DELTA.y).sup.2 
}+ . . . (9) 
The above expressions (7) through (9) are calculated, then the absolute 
values .vertline.f.sup.X .vertline., .vertline.f.sup.Y .vertline., 
.vertline.f.sup.XY .vertline. are compared with each other, and then value 
f(x,y) is renewed as f.sup..alpha.. Next, fx and fy are renewed in below 
expressions (10) and (11). 
EQU fx.rarw.fx+fxx.multidot..DELTA.x+fxy.multidot..DELTA.y+ . . . (10) 
EQU fy.rarw.fy+fyx.multidot..DELTA.x+fyy.multidot..DELTA.y+ . . . (11) 
The circle is drawn by repeating the above operation until the end point. 
FIG. 2 is a flow chart giving an algorithm according to the described 
Jordan method. 
The Jordan method comprises selecting from the present spot, the next 
point, from among three points proposed therefor. However, 
disadvantageously, the hardware which is required to carry out this 
method, involves complex circuitry having a large number of variables. 
Thus, the art still is deficient in a method and system for generating 
quadratic curves, which are simple, and inexpensive and which can be 
carried out with simple and inexpensive hardware. 
SUMMARY OF THE INVENTION 
Thus, an object of the invention is to overcome the aforementioned and 
other deficiencies and disadvantages of the prior art. 
The present invention aims to simplify both the circuitry and control 
system for producing quadratic curve signals, by limiting the points to be 
selected next, to two points, and reducing further steps to a comparison 
of absolute values of the two numbers. When linear micro-coefficients in 
the directions x,y at points (x, y) are given at fx, fy, respectively, the 
points to be selected next, are limited to two points by comparing 
.vertline.fx.vertline., .vertline.fy.vertline. for dimensions, besides the 
signs of fx, fy. When each point is selected, new values f(x, y) are 
obtained. Absolute values of the new f(x, y) are compared with each other. 
Then, a point to give a smaller value is selected, as the next point. 
Thus, a quadratic curve signal of f(x, y)=0 is generated nonparametrically 
by repeating the above procedure.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT 
FIGS. 3 and 4 are explanatory drawings illustrating the case wherein a 
circle is drawn according to an illustrative method of the invention. FIG. 
5 is a flow chart representing an algorithm of such method shown in FIGS. 
3 and 4. In FIG. 3, linear micro-coefficients in the directions x, y at 
points (x, y) are given at fx, fy, respectively. The signs of the linear 
microcoefficients are decided first. Then, fx and fy are compared for 
dimensions. Then, the curves are divided into two domains A.sub.1, A.sub.2 
of .vertline.fy.vertline..gtoreq..vertline.fx.vertline. and 
.vertline.fy.vertline..ltoreq..vertline.fx.vertline.. The circle is then 
divided into 8 sectors P.sub.0 through P.sub.7, and the present point is 
decided for which 8 divided circle sector it belongs. In the flow chart of 
FIG. 5, steps 1 to 5 show a flow for the decision. 
In the 8 divided circle sectors P.sub.0 through P.sub.7, the point 
(direction) to select next is prepared in two points G.sub.0, G.sub.1 
beforehand, in each part. The values G.sub.0, G.sub.1 of a new f(x, y), 
when each point is selected, are obtained. Then, the absolute values 
.vertline.G.sub.0 .vertline., .vertline.G.sub.1 .vertline. of these values 
are compared with each other, and the smaller value is selected as the 
next point. Namely, in FIG. 5, step 6 indicates an operation for G.sub.0 
and step 7 for G.sub.1. The absolute values .vertline.G.sub.0 
.vertline., .vertline.G.sub.1 .vertline. are compared at step 8 . The 
smaller one of G.sub.0, G.sub.1 is selected in step 9 . Step 10 is for 
updating the point selected through the abovementioned steps as the 
present point. Then, the procedure returns to step 1 , and the process is 
repeated until the end point is reached. 
At a point P of FIG. 3, a process for selecting the next point will be 
described conceptually. As will be apparent from the drawing FIG. 3, a 
condition .vertline.fx.vertline.&gt;.vertline.fy.vertline. is realized in the 
domain P.sub.0. The point P is not a starting point. Therefore, if 
coordinates of point P are (x, y), z=f(x, y)=0 is not always satisfied 
(not always appearing on the circle). Thus, it has a finite value other 
than zero. For the point to be selected next, P.sub.X is excluded in the 
domain P.sub.0. Two points G.sub.1, G.sub.0 and P.sub.Y and P.sub.XY only 
are compared with each other. Then, point G.sub.1, which will be a smaller 
value (a point coming close by the circle), is selected as the next point. 
Thus, each point (dot) can be made to come close and follow the circle by 
selecting the point coming next in sequence from the two points proposed, 
and thereby drawing the circle. 
FIG. 6 is a block diagram representing one example of a system for carrying 
out the method shown in FIGS. 3 and 4. In FIG. 6, RE1, RE2 are registers 
to store each coefficient and variable (fx, fy, f.sup..alpha., a, b, c, d, 
e), given each data through a data bus and capable of reading and writing 
independently each of them. ALU is an operator to input data from 
registers RE1, RE2 for addition and subtraction. RE3 is a latch circuit to 
hold, temporarily, an operation result transmitted from the operator ALU. 
The operation result is stored in registers RE1, RE2, by way of a bus 
line. CO.sub.X, CO.sub.Y are updown counters for X coordinate and Y 
coordinate, respectively. Coordinates x.sub.o, y.sub.o indicate the 
starting point first set there. The contents of the counter are updated 
thereafter according to the operation results. RE4 is a sign register to 
input the uppermost digit data (sign data) of the operation result 
outputted through latch circuit RE3. LC is a logic circuit to input a 
signal from the sign register RE4, which operates according to programs 
from a microprogram memory ME and gives an operation command signal to an 
arithmetic circuit ALU. CC is a control unit to supervise and control 
registers, latch circuit, updown counters CO.sub.X, CO.sub.Y, etc. Such 
circuit construction enables the operator to carry out the addition and 
subtraction in the main and thus is effective to accelerate the speed of 
operation. 
A sequence for operation is stored in memory ME as a microprogram. By 
combination of an operation command of the microprogram and contents of 
the sign register RE4, the logic circuit LC commands the operator ALU to 
add or subtract, for example, contents of which address of REG1 and those 
of which address of REG2, and also to store the operation result thereat. 
A decision of the linear micro coefficient sign, a comparison of fx,fy for 
dimensions, and an operation for which direction to proceed, G.sub.1 or 
G.sub.0 are carried out thereby. 
The operation result develops information on whether to proceed .DELTA.X to 
+1 or -1, and .DELTA.Y to +1 or -1, according to each domain and also to 
the direction G.sub.1 or G.sub.0, which is impressed on the updown 
counters CO.sub.X, CO.sub.Y. The updown counters CO.sub.X, CO.sub.Y are 
updated consequently to data D.sub.X, D.sub.Y to indicate x,y coordinate 
positions of the next point, and such data are outputted as a pattern 
generating signal. Such decision is made at every updating to the new 
point. 
FIG. 7 represents an example of a pattern obtained through drawing circles 
of radiuses 6 and 10 on a CRT. .DELTA.X, and .DELTA.Y are taken to be 
comparatively large for easy understanding, in this FIG. 7. However, the 
pattern can be more substantially approximated to a circle by using 
smaller .DELTA.X and .DELTA.Y. 
Next, in the inventive method and system for generating a quadratic curve 
signal nonparametrically, there will be described an end point setting of 
the quadratic curve signal and an algorithm for the decision. 
In case the quadratic signal is generated nonparametrically, the end point 
of a quadratic curve is detected in the prior art generally by comparing 
end point coordinates (XE, YE) set beforehand directly with generation 
coordinates (X, Y) of the quadratic curve signal which was being 
outputted. Where the quadratic line is linear, in this case, the end point 
can be detected by deciding either one (selected by the angle normally) of 
X or Y. However, in the case of a circle, ellipse, parabola or other 
quadratic curve, it was necessary to detect a coincidence with the end 
point coordinates XE, YE set beforehand concurrently for both X,Y. The 
above prior art situation inevitably involved certain difficulties, such 
as in setting end point at an arbitrary position, and moreover, the 
algorithm or hardware for carrying out the process for decision became 
unduly complex. 
In contrast, in the inventive system for generating a quadratic curve 
signal nonparametrically, the inventive system structure is such that the 
end point setting of the quadratic curve signal and the decision algorithm 
are substantially simplified. Namely, where micro-coefficients in the 
directions x,y at points (x, y) selected in sequence are given at 
FX(=(.differential./.differential.x)f(x, y)) and 
FY(=(.differential./.differential.y)f(x, y)), the signs at SFX, SFY, 
respectively, and for the end point coordinates (XE,YE) to set similarly, 
the microcoefficients are given at FXE, FYE and the signs at SFXE, SFYE, 
the conditions for end point detection are specified as 
EQU (X=XE).solthalfcircle.(SFY=SFYE) at 
.vertline.FX.vertline..ltoreq..vertline.FY.vertline. (12) 
EQU (Y=YE).solthalfcircle.(SFX=SFXE) at 
.vertline.FX.vertline.&gt;.vertline.FY.vertline. (13). 
When the above conditions are satisfied, generation of the quadratic curve 
signal is stopped as having come to the end point. 
Next will be described the case wherein the quadratic curve is taken at 
f(x, y)=x.sup.2 +y.sup.2 -r.sup.2 =0 (i.e. a circle with the center (0,0) 
and radius r). FIG. 8 represents relation between FX, FY, SFX, SFY in this 
case. Micro-coefficients FX,FY in the directions x,y are FX=2x and FY=2y, 
and SFX, SFY are expressed by S (positive or negative, positive or 
negative, respectively). 
In case, for example, a quadratic curve signal indicating a circular arcto 
a point PE (XE, YE) counterclockwise from a point PO (r,0) is obtained, 
XE, YE (XE only acceptable actually in this case) and SFXE, SFYE are set 
beforehand for the end point PE as an end point coordinate information. 
The process (that of drawing the circular arc), wherein the quadratic curve 
signal indicates the circular arc, is that of selecting the point to come 
next sequentially, from the point PO according to signs or dimensions of 
the slants (FX, FY) in the directions X,Y. The procedure described 
hereinbefore applies. 
A decision on which expression to use, (12) or (13) given hereinbefore, for 
end point detecting conditions, depends on the information from the 
calculating process, wherein the point to come next is selected in 
sequence under the procedure. In the case of FIG. 8, for example, SFX&lt;0, 
SFY&gt;0, and .vertline.FX.vertline.&lt;.vertline.FY.vertline. at the point PE 
(XE, YE). Therefore, the end point is obtained when the conditions of 
expression (12) are satisfied. Namely, any decision will not be made for 
Y, YE, in this case, except the comparison of X with XY (subtraction of 
both signals or coincidence detection by exclusive OR (EX-OR)), and the 
point PE can be detected through discriminating point P1 from P2 in FIG. 
8. 
In generating a quadratic curve signal other than a circle, the criterion 
of the above mentioned expressions (12) and (13) applies for the end point 
detection. This is because, when a pattern signal is generated according 
to information of FX,FY, the common situation is such that it proceeds in 
the direction .vertline.FX.vertline. or .vertline.FY.vertline., whichever 
is smaller, fundamentally. When 
.vertline.FX.vertline.&gt;.vertline.FY.vertline., a dot string is given 
transversely (X direction) but longitudinally (Y direction) when 
.vertline.FX.vertline.&gt;.vertline.FY.vertline.. Therefore, X,Y are 
determined on the spot to XE or YE in such section. Then, where a setting 
of XE, YE includes an error more or less reversely, the end point will be 
detected always in such section. 
FIG. 9 is a block diagram representing one example of a circuit for end 
point detection. In FIG. 9, RE denotes an end point register, to set end 
point data, or end point coordinates XE, YE and signs SFXE, SFYE of the 
end point micro-coefficients, which comprise 4 individual registers 
R.sub.1 through R.sub.4. CC represents a quadratic curve signal generation 
unit and a control unit generally, comprising a plurality of registers, 
adder/subtractor, microprocessor, etc, which are not illustrated 
particularly therein. A quadratic curve signal is generated according to 
signs or dimensions of the quadratic curve slant (linear 
micro-coefficients FX,FY). CUX, CUY denote X counter and Y counter which 
are connected to the quadratic curve signal generation unit CC, and X 
coordinate and Y coordinate data indicating the quadratic curve signal are 
outputted thereat. 
SW1 through SW4 represent data selectors driven on a signal outputted 
according to the status of 
.vertline.FX.vertline..ltoreq..vertline.FY.vertline. or 
.vertline.FX.vertline.&gt;.vertline.FY.vertline. from the control unit CC. 
The data selector SW1 switches an output signal of registers R.sub.1, 
R.sub.2. The data selector SW2 switches an output signal of registers 
R.sub.3 and R.sub.4. The data selector SW3 switches sign data SFX, SFY of 
the linear micro-coefficients obtained through the quadratic curve signal 
generation unit CC. The data selector SW4 switches an output signal from X 
counter CUX and Y counter CUY. EXO1 represents a coincidence detection 
circuit to detect a coincidence of signals from the data selectors SW1, 
SW3. EXO2 represents a coincidence detection circuit to detect a 
coincidence of data signals from the data selectors SW2, SW4. An exclusive 
OR circuit is used for both foregoing circuits. Go then represents a gate 
circuit to input signals from each coincidence detection circuits EXO1, 
EXO2. 
In such circuit configuration, each data selector SW1 through SW4, is 
driven to a contact a or b, as shown in below TAble 1, according to 
dimensions of the quadratic curve slant (linear microcoefficients FX, FY) 
obtained at the quadratic curve signal generation unit CC. 
TABLE 1 
______________________________________ 
SW1 SW2 SW3 SW4 
______________________________________ 
.vertline.FX.vertline. .ltoreq. .vertline.FY.vertline. 
b a b a 
.vertline.FX.vertline. &gt; .vertline.FY.vertline. 
a b a b 
______________________________________ 
The connection shown in FIG. 9 represents the case wherein 
.vertline.FX.vertline.&gt;.vertline.FY.vertline., and the end point is 
detected according to conditions given in expression (13). Namely, under 
the condition .vertline.FX.vertline.&gt;.vertline.FY.vertline. at quadratic 
curve signal generation unit CC, a value Y of the coordinate Y outputted 
to the Y counter CUY coincides with a value YE of the end point coordinate 
set on the end point register R.sub.4, and whether or not SFX value (1 
bit) coincides with a sign SFXE of the end point micro-coefficient set on 
the end point register R.sub.1, is detected on each coincidence detection 
circuit EXO.sub.1, EXO.sub.2. When both coincide, the point is detected as 
an end point. An end signal from the gate circuit Go is given to quadratic 
curve signal generation unit CC. Thus, an output of the quadratic curve 
signal is stopped. 
As described, according to the system illustrated in FIG. 9, the end point 
can be detected accurately by detecting a coincidence of a sign of the end 
point micro-coefficient with a value of either X coordinate or Y 
coordinate. Therefore, an algorithm for the decision is simple. Also, a 
circuit for end point detection can be simplified. When a comparison is 
made for both the coordinates X,Y in this connection, a comparator of 
n+n=2n (n being coordinate bit number) will be required. However, a 
comparator of n+1 bits is enough to work according to this method. 
The foregoing description is illustrative of the principles of the 
invention. Numerous modifications and extensions thereof would be apparent 
to the worker skilled in the art. All such modifications and extensions 
are to be considered to be within the spirit and scope of the invention.