JPH0145105B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to a figure generator for generating figures to be displayed on a graphic display or the like.

[Technical background of the invention and its problems]

Conventionally, in order to display a quadratic curve such as a circle or a parabola on a graphic display, it has been necessary to draw it using software that includes multiplication due to the characteristics of the equation of the quadratic curve. If this was done using ordinary hardware, there would be a drawback that the processing would take a long time because it would involve multiplication calculations. Additionally, hardware that can perform multiplication calculations at high speed is commercially available, but these are extremely expensive.

As a solution to these shortcomings, there is known a ``high-speed circle generation algorithm'' written by Mikio Takagi et al. at the 27th National Conference of the Information Processing Society of Japan. In this method, grid points are selected as if tracing the edge of a circle, and the value of the circular function f(x, y) is added in increments without calculating each time. For this reason, the algorithm included only addition, which had the advantage of shortening processing time. However, this algorithm can only draw 1/8 circle and cannot draw quadratic curves such as parabolas, hyperbolas, and ellipses, so it cannot be applied when you want to draw various quadratic curves. , which was extremely inconvenient.

[Object of the Invention] An object of the present invention is to provide an apparatus that can generate not only straight lines and circles but also quadratic curves such as ellipses, parabolas, and hyperbolas at high speed using an algorithm that does not involve multiplication.

[Summary of the invention]

The present invention provides coordinate values in the X direction and Y direction of a figure to be displayed on the display section, an increment value that increases or decreases the coordinate values in the X direction and Y direction, the true value of the figure, and the coordinate value on the display section. Initializes the error with the value of the figure, the first increase/decrease value in the X and Y directions that increases or decreases the error, and the second increase/decrease value in the X and Y directions that increases or decreases the first increase/decrease value. a setting means for comparing whether the error is positive, negative, or "0"; and a comparing means for comparing whether the error is positive, negative, or "0"; , add a preset step value to the coordinate value, add a second increase/decrease value to the first increase/decrease value, add the added first increase/decrease value to the error, and add it by the comparison means. If the error set in the setting means is determined to be positive or "0", or if the error set in the setting means is determined to be positive or "0", the coordinate value is changed in the other direction of X or Y. A preset step value is added, a second increase/decrease value is added to the first increase/decrease value, and the added first increase/decrease value is determined to be positive or "0" by the comparing means. an addition means for adding the error output from the addition means, coordinate values in the X direction and Y direction,
The step value, the first increase/decrease value, and the second increase/decrease value are initialized again in the setting means, and coordinate values in the X direction and the Y direction are output.

〔Effect of the invention〕

According to the present invention, it is possible to generate a quadratic curve at high speed using an algorithm using addition, which makes it highly practical and improves efficiency.

[Embodiments of the invention]

Hereinafter, one embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a flow diagram of an algorithm according to one embodiment of the invention. In the present invention, the digital 2
Considering that the following curve contains errors in any case, the speed is increased by allowing errors within a practically acceptable range. In other words, when a quadratic curve is given in the form of f (x, y) = 0, the value of f (X, Y) due to the coordinate values (X, Y) on the display section is defined as the error (ERR), If ERR<0, point (X,
Y) exists inside the curve f(x,y)=0,
If ERR>0, the point (X, Y) is the curve f(x,
It can be seen that it exists outside of y)=0. Therefore,
By selecting grid points so as to follow the curve f(x, y)=0, a digital curve that approximates this curve can be obtained. In this case, the algorithm of the present invention includes two judgment steps: ERR<0 and ERR≧0, and based on the judgment result, X>Y The coordinates (X, Y) in the case of , and in the case of X<Y are drawn continuously. In addition, in this algorithm, in order to advance the values of X and Y while ERR always takes a value near 0, DX, DY, DDX,
It uses DDY. DX and DY are the X direction and Y direction, respectively.
This is the value to be added to ERR when the direction value is incremented, and in the algorithm shown in Figure 1, ERR<0
In the case of , the X coordinate is incremented by DLX, but at this time
DX is added to ERR, and the value of ERR approaches 0 (DX>0). If ERR≧0, the Y coordinate is
DLY is incremented, but at this time DY is added to ERR and the ERR value approaches 0 (DY<
0). The values of DX and DY are not constant, and DDX and DDY are added respectively in parallel with the above calculation. In other words, since the increment value and decrement value of ERR are always increasing and decreasing, the value of ERR can always take a value close to 0 at an accelerating rate, and the X coordinate value and Y coordinate value can be stepped. For this purpose, as described later, DX,
By setting the values of DY, DDX, and DDY,
A digital curve that closely approximates this quadratic curve can be obtained.

Next, each step in the flowchart of FIG. 1 will be explained. First, start point (X ₀ , Y ₀ ), end point (X _e , Y _e )
and ERR, DX ₀ , DY ₀ , DDX, DDY, DLX,
Give a desired value as the initial value of DLY as described later. DX ₀ and DY ₀ are values that should be added when ERR is negative or positive, and the initial value of ERR is
Set a value of about DX ₀ + DY ₀ /2. In step 1, it is determined whether ERR is positive or negative or 0. If it is negative, it is calculated in step 2, and if it is positive or 0, it is calculated in step 4.
Perform the calculation. Here, if ERR is negative, the initial values (X ₀ , Y ₀ ) exist inside the true curve, and the X coordinate is incremented (X
=X ₀ +DLX), the addition/subtraction value DX ₀ to be added to ERR is added (DX=DX ₀ +DDX), and the DX of this addition result is added to ERR (ERR=ERR+
DX). As a result, the value of ERR becomes closer to 0 than the initial value, but if this ERR becomes positive or 0, or if it becomes positive or 0 in step 1.
If it is determined that (X, Y ₀ ) exists outside the true curve, the Y coordinate is incremented (Y = Y ₀ + DLY) and added to ERR as shown in step 4. Addition is applied to the exponentiation value DY ₀ (DY=
DY ₀ +DDY), and the result of this addition, DY, is added to ERR (ERR=ERR+DY). If it is determined in step 3 that ERR is negative, the calculation in step 4 is not performed. The coordinates (X, Y) thus stepped are plotted on a display (not shown) as shown in step 5.

1/4 as shown in Figure 2 b, which will be described later here.
If you want to draw a circle, you can do it by repeating steps 1 to 5. However, when drawing a complete circle, four poles parallel to the x-axis or y-axis (p, q,
r, s), it is necessary to invert the sign of several parameters. In other words, as shown in Figure 2c, in order to draw a connected 1/2 circle in the second quadrant, DX and DY must be It is necessary to take symmetrical values. Furthermore, it is necessary to reverse the direction of movement of the X coordinate with respect to point p. Here, in all quadrants ~, in order for ERR to approach 0, DX must always be positive and DY must be negative, but as mentioned above, since they are parameters of a quadratic curve, DX has DDX, DY DDY is added to. For this reason, a point where DX≦0 and DY≧0 occurs. Second
In figure c, DY is p, r, and DX is q, s. In other words, when the step is made to the coordinates of the arrow as shown in Figure 2 a and b, the sign of DY becomes positive, so the signs of DLX, DDX, and DDY are reversed and DY is It is necessary to return it to negative and reduce DX and DY. For this reason, steps 8 and 9 are provided in the flow shown in FIG. In other words, if DY is determined to be positive or 0 in step 8, DDX and DDY have different signs, so for example, when drawing a quarter circle in Figure 2 a and b, DX is increased at the same rate. , when drawing a 1/4 circle (not shown) after the arrow dot, the same ratio is applied to DY.
DX and DY are decreasing. Also, since DLX also has a different sign, the X coordinate is stepped in the negative direction, but the Y
The coordinates will continue to move in the positive direction, so the second
By connecting it to the 1/4 circle in Figure b, you can draw a 1/4 circle that is congruent with this. Step 9 in the flowchart is carried out at two points p and r in FIG. Similarly, regarding DX, the DX of the 1st quadrant and the DX of the 1st quadrant,
The DX of the quadrant must take symmetrical values with points q and s as boundaries. The sign of DX becomes negative at the two points q and s in Figure 2c, but by returning this DX to positive,
Further, steps 6 and 7 are provided to obtain symmetrical values. If DX is determined to be negative or 0 in step 6, DX,
DY has a different sign, and DLY also has a different sign, so Y
Since the advancing direction of is reversed and DX is also returned to positive, drawing can be continued. Thus step 10
The end point (X _e , Y _e ) set in advance is compared with the stepped step (X, Y), and if they match, the flow process ends, and if they do not match, the process returns to step 1.
The process is repeated from

Now, change the initialized parameters to the coordinate values (X ₀ ,
Y ₀ ), ERR=0 for convenience, first increase/decrease value DX ₀ ,
Let DY ₀ be the second increase/decrease value DDX, DDY, and the parameter after being stepped an appropriate number of times will be the coordinate value (X,
Y), ERR (≠0), and the first increase/decrease values DX and DY, DX=DX ₀ + (X-X ₀ )*DDX...(A) DY=DY ₀ + (Y-Y ₀ )*DDY... (B) ERR= _x-x0 〓 1DX+ _y-y0 〓 1DY...(C) holds true. Here, by substituting equations (A) and (B) into equation (C) and expanding it, ERR=(X-X ₀ )*DX ₀ +DDX/2*(X-X ₀ )* (X-X ₀ +1 ) +(Y-Y ₀ )*DY ₀ +DDY/2*(Y-Y ₀ )* (Y-Y ₀ +1) = DDX/2(X-X ₀ ) ² +(DX ₀ +DDX/2(X- X ₀ ) +DDY/2 (Y-Y ₀ ) ² + (DY ₀ +DDY/2) (Y- Y ₀ ) ...(D) Here, ERR is always considered to be near 0, so ERR = 0, equation (D) corresponds to the equation expressing an arbitrary quadratic curve: ax ² +by ² +cx+dy+e=0.In other words, the equation of the quadratic curve to be drawn can be matched with equation (D). The parameters DX ₀ , DY ₀ , DDX, and DDY can be determined by transforming the equation into

For example, when DDX=DDY=0, equation (D) becomes DX ₀ (X−X ₀ )+DY ₀ (Y−Y ₀ )=0, which represents a straight line passing through the point (X ₀ , Y ₀ ).

DDX = DDY = 2, DX ₀ = -1, DY ₀ = -201
Then, equation (4) becomes (X-X ₀ ) ² + (Y-Y ₀ -100) ² = (100) ² , which represents a circle with a center (X ₀ , Y ₀ +100) and a radius of 100.

DDX = 2, DDY = 0, DX ₀ = -1, DY ₀ = -
When it is set to 100, equation (D) becomes (X-X ₀ ) ² -100(Y-Y ₀ )=0, which represents a parabola at the apex (X ₀ , Y ₀ ).

DDX = 2, DDY = -2, DX ₀ = 1, DY ₀ = -
199, equation (D) becomes −(X−X ₀ ) ² +(Y−Y ₀ −100) ² =100 ² and represents a hyperbola at the vertex (X ₀ , Y ₀ +100).

DDX=5000, DDY=20000, DX ₀ =-2500,
When DY ₀ = -1010000, equation (D) becomes (X - X ₀ ) ² /100 ² + (Y - Y ₀ -50) ² /50 ² = 1, and the center (X ₀ , Y ₀ +50), length Axis 100, short axis 50
represents the inertia circle of

Figure 2 a and b are circles X ² + (Y-10) ² as mentioned above.
This is a table of coordinate values calculated using this algorithm when drawing =10 ² and a digital curve shown by the corresponding dots. As the initial value (X,
Y) = (0, 0), DDX = 2, DDY = 2, DX ₀ =
-1, DY ₀ = -21, DLX = 1, DLY = 1 and
Set ERR=INT(DX ₀ +DY _0/2 )=-11.

This is because ERR changes while always taking a value near 0 by adding DX and DY, and an intermediate value between DX ₀ and DY ₀ seems to be appropriate as an initial value. It is. This figure 2b
As shown in , by using this algorithm, a digital circle approximated to a circle with a center point (0, 10) and a radius of 10 can be obtained.

Note that it is not always necessary to start the step from (0, 0) as in this example; for example, if you want to draw the step in the opposite direction from the arrow dot in Figure 2b,
The initial settings can be made by setting DLX=-1 and DLY=-1 and calculating DX, DY, and ERR at the coordinates of the arrow dot. Although FIGS. 2a and 2b show examples of drawing circles, parabolas, hyperbolas, and ellipses can also be drawn using the flow shown in FIG. In this case, step 1~
5 is a parabola, and a hyperbola is 1/2 bordering the vertex.
The part is a 1/4 circle drawn in the inertia circle, and step 6~
9, all desired parts can be drawn.

3 and 4 are configuration diagrams of hardware for processing the algorithm flow according to the present invention. The hardware shown in Figure 3 is built into the image data output device connected to the display, and 11 is
DDX, 13 is a register that holds DDY,
12 is a register that holds DX ₀ and 14 is a register that holds DY ₀ . Adders 15 and 16 add the contents of 11 and 12, and 13 and 14, respectively. 17 is ERR
This is a register that holds the value of ERR, and outputs this ERR to an adder 18 and a selector 19, which will be described later.If the sign bit in the register is 1, that is, if ERR<0, a signal "1" is sent to the signal line. Output to 23. 18 is an adder that adds the output contents of the adder 15 and the contents of the error register 17;
A selector 19 switches between the contents of the register 17 and the output contents of the adder 18 depending on whether the ERR held in the register 17 is positive or negative. 20
An adder 21 adds the output contents of the adder 16 and the output contents of the selector 19, and 21 switches the output contents of the selector 19 and the output contents of the adder 20 depending on whether the output contents of the selector 19 are positive or negative. Selector 22 is a positive signal detection circuit that outputs a signal "1" when a positive signal is input, 23, 24,
25 is a signal line, 26, 27 is an AND circuit, 28,
29 is set in advance to be incremented by +1 (DLX=1, DLY=1), and the AND circuit 26,
These are an X counter and a Y counter that count up each time the output from 27 is input.

Next, the operation in this configuration diagram will be explained. The CPU (not shown) has registers 11, 12, 13, and 14.
Set DDX, DX, DDY, and DY, respectively, set the initial value of ERR in error register 17, and set X,
The initial values of (X, Y) are set in the Y counters 28 and 29. (Set in error register 17
ERR is assumed to be negative).

The circuit shown in FIG. 3 performs steps 1 to 5 in the flow shown in FIG. 1, and when drawing a circle, it can draw up to 1/4 of a circle. In other words, every time a clock signal is input,
8. X coordinate stored in Y counter 29, Y
The coordinate values are incremented, but when drawing a complete circle, the DX stored in registers 12 and 14,
Depending on the sign of DY, the CPU (not shown) sets register 1.
DDX and DDY codes stored in 1 and 13, step number (DLX) set in X counter 28
Alternatively, this can be achieved by inverting the sign of the step number (DLY) set in the Y counter 29. Now, in FIG. 3, the clock signal advances the coordinates (X, Y) in the X counter 28 and Y counter 29, stores the error in the error register 17, and transfers it to the DX register 12 and DY register 14.
It is input to store DX and DY, and the following operations are performed at the input interval of the clock signal. The adder 15 adds the DDX output from the register 11 and the DX output from the register 12, and outputs the addition result (DX) to the adder 18. Since ERR<0 from the error register 17, the signal “1” is sent to the signal line 23.
It is input to the selector 19 and the AND circuit 26 through the input signal. The adder 18 outputs the output from the adder 15.
DX and the ERR output from the error register 17 are added and output, but since the selector 19 receives the signal "1", it takes in and outputs the ERR output from the adder 18.

Here, the sign bit in the error register 17 is 0.
If this is the case, that is, if the ERR output from the error register 17 is positive or 0, the selector 19 indicates that the signal “1” is not output from the error register 17.
Enter ERR as is. Next, the ERR output from the selector 19 is output to the adder 20 and selector 21 through the signal line 24.
If ERR≧0, a signal “1” is output from the positive signal detection circuit 22 to the selector 21 and the AND circuit 27 through the signal line 25. The adder 16 adds the DDY output from the register 13 and the DY output from the register 14, and outputs this addition result (DY) to the adder 20, which adds the ERR output from the selector 19. The selector 19 adds the DX output from the adder 16 and outputs the result. However, if the selector 19 inputs the signal "1", it takes in and outputs the ERR output from the adder 20, and outputs the signal "1". If not input, the ERR output from the selector 19 is input as is. In this way, as a step before the clock signal is input, a signal "1" is input to the AND circuits 26 and 27 according to the positive or negative sign of ERR, ERR is output from the selector 21, and the adder 15,
16 outputs the addition results DX and DY. A new ERR is stored in the error register 17 by inputting a clock signal thereto.
Also, since a signal is output from the AND circuit to which the signal "1" is input, for example, the AND circuit 26
At this time, the X counter 28 is incremented by 1 and a new DX is stored in the register 12. Coordinate values X and Y are output from the X counter 28 and Y counter 29, and an image data processing device (not shown) displays the corresponding dot on a display or the like based on the coordinates (X, Y).

FIG. 4 is a block diagram of the hardware for processing steps 1 to 5 in the algorithm of FIG. 1, which is different from the circuit of FIG. 3. This hardware outputs a set of coordinate values (X, Y) by inputting signals of about 8 clocks. 30 is an octal counter, and the numbers 0 to 7 counted are the 8-format additions in steps 1 to 4 in Figure 1 (in steps 1 and 3, ERR=
(replaced with ERR+0). or,
This counter also outputs an output enable signal to a register to be described later. 31 is the address
It is a ROM, and stores addresses where each of parameters stored in a register file 32, which will be described later, is stored. It also outputs clock signals individually to the flip-flop, X, and Y registers, which will be described later. A register file 32 holds parameters necessary for addition. 33 is an adder that adds the two parameters (addend, summand) output from the register file 32, and if the addition result is negative (as long as the sign bit in the adder is set to 1), If so), a signal “1” is output to the flip-flop 34. 34 is a T flip-flop which turns on the write enable signal connected to the register file 32 by inputting the signal "1" and the clock signal. 35 and 36 are for taking in the X and Y coordinates of the addition result output from the adder 33 using a clock signal output from the address ROM 31. Next, the operation in this configuration diagram will be explained. First, when the first clock is input to the counter 30, the counter 30 outputs a count of 1 to the address ROM 31. In other words, the first addition (ERR
=ERR+0). address
The ROM 31 sends the address where "ERR""0" is stored to the register file 32 through address buses AS and BS. Based on this address, the register file 32 outputs "ERR""0" to the adder 33 through data buses A and B. Adder 3
3 performs addition, and if the addition result (ERR) is negative, a signal "1" is output to the flip-flop 34. The address ROM 31 outputs a clock signal to the flip-flop 34 at the interval between the first and second clock inputs. Now, assuming that the addition result (ERR) is negative, the flip-flop 34 turns on the write enable signal to the register file 32 using this signal "1" and the clock signal. (The clock output from the address ROM is output at the first and second, and fifth and sixth clock intervals.) The ERR output from the adder 33 is returned to D of the register file 32 through the data bus. is written to the original address by the write enable signal that is turned ON. Next, when the second clock enters the counter 30, it outputs a count of 2. In response to this address
The ROM outputs the address of “X” and “DLX”, and the register file 32 outputs the address of “X” based on this address.
"DLX" is output to the adder 33, and this addition result (X) is sent to the D, X register 35, and Y register 36 of the register file 32 through the data bus. In the register file, X is written to the original address by the write enable signal that is turned ON. Also, from the address ROM, the X register 3
A clock signal is output only to the register 35, and the addition result X is stored in the register 35. Below, in synchronization with the third and fourth clocks, the third addition (DX=DX+DDX) and the fourth addition (ERR=
ERR+DX), fifth addition (ERR=ERR+
0) is performed, and after this fifth clock, a clock signal is output from the address ROM 31 to the flip-flop 34. At this time, the fifth addition result
If ERR (=ERR+0) is positive or 0, adder 3
3 does not output a signal "1" to the flip-flop 34. Therefore, even if a clock signal is input to flip-flop 34, the write enable signal remains ON.
It remains as it is. At this time, the following 6th addition result (Y=Y+DLY), 7th addition result (DY=DY+DDY), and 8th addition result (ERR
=ERR+DY), and the ninth (first) addition result (ERR=ERR+0) is written to the corresponding address in the register file 32. Furthermore, if the fifth addition result ERR is negative, a signal "1" is input to the flip-flop 34, thereby turning off the write enable signal. For this reason, the 6th, 7th,
The addition results of numbers 8 and 9 are not written, and the ninth (first) addition result ERR is naturally negative, so the signal "1" and the clock signal are input to the flip-flop 34 again, and the write enable signal is activated. Turned on. By the way, after the sixth clock, the address ROM 31 to Y register 36
By inputting the clock signal to the register 36, the addition result Y (=Y+DLY) is stored in the register 36. After the 8th clock (that is, after the counter 30 changes from "111" to "000"), the counter 3
From 0, output enable signals are simultaneously output to the X register 35 and Y register 36, and a set of coordinates (X, Y) is output. In this way, if the hardware shown in FIG. 4 is used, one set of (X, Y) can be output in about 8 clocks, and only one adder is required, so the amount of hardware can be reduced.

As explained above, by using the algorithm of the present invention, it is possible to generate a quadratic curve only by determining whether the error is positive or negative and adding steps, so even a cheap microcomputer without a multiplication instruction can generate a quadratic curve at high speed. This is very convenient in practice.

[Brief explanation of drawings]

Fig. 1 is a flow diagram of the algorithm of the present invention, Fig. 2 is a diagram of coordinate values and graphs of a quadratic curve using the algorithm of the present invention, and Figs. 3 and 4 show the operation of the algorithm of the present invention. FIG. 2 is a configuration diagram of hardware. 11, 12, 13, 14... register, 15,
16, 18, 20... Adder, 17... Error register, 19, 21... Selector, 22... Positive signal detection circuit, 23, 24, 25... Signal line, 26,
27...AND circuit, 28, 29...Up-down counter.

Claims (1)

[Claims] 1 Coordinate values in the X and Y directions of a figure to be displayed on the display, step values that increase or decrease the coordinates in the X and Y directions, and figures based on the true value of the figure and the coordinates on the display. Setting to initialize the error with the value of means, a comparison means for comparing whether the error is positive, negative, or "0", and if the error is determined to be negative by this comparison means, a coordinate value is determined in one direction of X or Y. A preset step value is added to the step value, a second increase/decrease value is added to the first increase/decrease value, the added first increase/decrease value is added to the error, and the error added by the comparison means is is determined to be positive or "0", or if the error set in the setting means is determined to be positive or "0", the coordinate value is set in advance in the other direction of X or Y. the second increase/decrease value is added to the first increase/decrease value, and the added first increase/decrease value is added to the error determined to be positive or "0" by the comparison means. The error output from the addition means, the coordinate values in the X direction and the Y direction, the step value,
A graphic generation device characterized in that the first increase/decrease value and the second increase/decrease value are initialized again in the setting means, and coordinate values in the X direction and the Y direction are output.