JPH0120471B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to a high-speed circle drawing method using DDA operations.

[Prior art and its problems]

When drawing a circle on a graphic display such as a personal computer, accurate drawing data can be obtained by performing calculations such as SIN and COS. However, performing the above calculations such as SIN and COS takes too much time, so
Conventionally, an approximate circle is drawn using an inscribed regular polygon with an appropriate angle, or circumference dots are calculated for only 1/4 of the circumference.
For the rest, the drawing speed is improved by finding points that are symmetrical about the x-axis, y-axis, and the origin.

After finding one point as above, if you want to find points that are symmetrical about the x-axis, y-axis, or symmetrical about the origin, if the center of the circle is equal to the origin of the coordinate axes, you can easily do this by reversing the sign, etc. . However, since the origin of the coordinate axes and the center of the circle are usually not equal, in this case it is necessary to store values such as the center coordinates in memory and perform addition/subtraction instructions, which complicates the calculation process and slows down the processing speed. There was a problem with the decline.

[Purpose of the invention]

The present invention has been made in view of the above points, and even when the origin of the coordinate axes and the center of the circle are not equal, it is possible to easily calculate the dots to be drawn on the circumference of the circle, and to create a circle that can be drawn at high speed. The purpose is to provide a drawing method.

[Embodiments of the invention]

An embodiment of the present invention will be described below with reference to the drawings. The present invention is a DDA (Digital Differential
First, we will give an overview of this DDA. In Figure 1, a point p _o on the circumference of a circle with radius r
When (x _o , y _o ) is being found, the point p _o+1 (x _o+1 , y _o+1 ) on the circumference that has moved counterclockwise by Δθ is x _o+1 = rcos(θ+Δθ) = rcosθcosΔθ−rsinθsinΔθ =x _o cosΔθ−y _o sinΔθ ……(1) y _o+1 = rsin(θ+Δθ) = rsinθcosΔθ+rcosθsinΔθ = y _o cosΔθ+x _o sinΔθ ……(2).

In equations (1) and (2) above, Δθ is a small angle,
If cosΔθ≒1 and sinΔθ≒Δθ, then x _o+1 = x _o −Δθ・y _o y _o+1 = y _o +Δθ・x _o . Furthermore, Δθ=ε=2 ^-m (m is a positive integer)
Then, the above formula becomes x _o+1 = x _o −ε・y _o ...(3) y _o+1 = y _o +ε・x _o ...(4) (However, 2 ^m-1 < r < 2 ^m ). However, if the above equation is used as is, it will diverge, so x _o in equation (4) above is replaced with x _o+1 . If x _o in equation (4) is replaced with x _o+1 in this way, the above equations (3) and (4) become x _o+1 = x _o −ε・y _o ……(5) y _o+1 = y _o + ε・x _o+1 ...(6) It has been confirmed from the past that a value of a substantially perfect circle can be obtained from equations (5) and (6).

The present invention is for drawing a circle at high speed using the above equations (5) and (6), and a specific embodiment thereof will be described below with reference to FIG. In Figure 2, 11 is the x register, which connects the CPU (not shown) to the gate circuit.
X coordinate data specifying user coordinates is input via _G1 . Also, 12 is the y register,
Y coordinate data specifying user coordinates is input from the CPU via the gate circuit _G2 . Furthermore, 13
is the R register, into which data indicating the radius of the circle is input from the CPU via the gate circuit _G3 . The data specifying the radius is given by the number of display dots. The data held in the x register 11 and the R register 13 are sent to the adder circuit 14 via gate circuits G ₄ and G ₅ , and
The signal is sent to the subtraction circuit 15 via G ₆ and G ₇ . The addition output of the addition circuit 14 is sent to the _xR register 16 via the gate circuit _G3 . This x _R register 16 is used to obtain data on the right half of the x coordinate as shown in FIG. 3, and its output is returned to its own input terminal via the gate circuit _G9 and the -1 circuit 17. The signal is also sent to a display processing section (not shown) via the gate circuit _G10 . Further, the subtraction circuit 15 performs subtraction of "x-R",
The result of the subtraction is sent to the x _L register 18 via the gate circuit _G11 . This x _L register 18 is the third
As shown in the figure, it is used to obtain data on the left half of the x coordinate, and its output is returned to its own input terminal via gate circuit G ₁₂ and +1 circuit 19, and is also displayed via gate circuit G ₁₃ . Sent to the processing section.

On the other hand, the data held in the y register 12 is input to the y _OV register 21 via the gate circuit G ₁₄ , and is also input to the y _UD register 22 via the gate circuit G ₁₅ . The above y _OV register 21 is
As shown in Figure 3, it is used to obtain data in the upper half of the y-coordinate, and the output is from the gate circuit.
The signal is returned to its own input terminal via _G16 and the +1 circuit 23, and is also sent to the display processing section via the gate circuit _G18 . In addition, the y _UD register 22
As shown in the figure, it is used to obtain data in the lower half of the y-coordinate, and its output is returned to its own input terminal via gate circuit G ₁₇ and -1 circuit 24, and also via gate circuit G ₁₉ . Sent to the display section.

Further, the data held in the R register 13 is sent to the Δx register ₂₅ via the gate circuit G20. The data held in this Δx register 25 is
is sent to the -1 circuit 26 via the gate circuit G ₂₁ ,
The output of this -1 circuit 26 is input to the Δx register 25. Further, the data held in the Δx register 25 is sent to the “0” judgment circuit 27 via the gate circuit G ₂₂ .
and the judgment result is sent to the CPU. Further, the data held in the Δx register 25 is sent to the adder circuit 28 via the gate circuit _G23 , and the added output is input to the _Rx register ₂₉ via the gate circuit G24. Also, this R _X register 29
In this case, the initial setting value "0.5" is set from the CPU to the gate circuit.
Entered via _G25 . The data held _in this _R
It is sent to the carry discrimination circuit 30 via _G27 .
This carry discrimination circuit 30 is connected to the _R
When the carry signal of G 16 is detected, the gate circuit G ₁₆ ,
Give gate signals to G ₁₇ and G ₂₉ to open the gates.

Further, 31 is a Δy register, to which an initial setting value "0.5" is given from the CPU via the gate circuit _G28 . The output of this Δy register 31 is returned to its own input terminal via the gate circuit G ₂₉ and the +1 circuit 32 which are gate-controlled by the output of the carry discriminator circuit 30, and the gate circuit G ₃₀ ,
The signal is input to the _Ry register 34 via the adder circuit 33 and the gate circuit _G31 . This R _y register 34 has
The initial setting value "0.5" is given from the CPU via the gate circuit _G32 . The data held in the _Ry register 34 is input to the adder circuit ₃₃ via the gate circuit G33, and is also sent to the carry discrimination circuit 35 via the gate circuit _G34 . This carry determination circuit 35 determines the presence or absence of a carry signal in the R _y register 34, and when a carry signal is detected, provides gate signals to gate circuits G ₉ , G ₁₂ , and G ₂₁ to open the gates. Gate circuit as mentioned above
G ₉ , G ₁₂ , G ₂₁ are controlled by the carry discrimination circuit 35, gate circuits G ₁₆ , G ₁₇ , G ₂₉ are gate controlled by the carry discrimination circuit 30, but other gate circuits are controlled by the CPU. gated by the signal.

Next, the operation of the above embodiment will be explained with reference to the flowchart of FIG. First, follow the steps in Figure 4.
At A ₁ , the gate circuit is activated by a command from the CPU.
Open the gates G ₁ to G ₃ and set the x coordinate of the center point Q of the circle to be drawn in the x register 11 and the y coordinate in the y register.
Set the radius R in register 12 and R register 13. For example, when drawing a circle with a radius of 8 dots, as shown in _FIG .
Set the base number to “1000”. Then step
Proceed to _A2 , open the gates of gate circuits _G4 to _G8 , G11, add the contents of the x register ₁₁ and R register 13 in the adder circuit 14, set it in the x _R register 16, and add the contents of the x register 11 and R register 13. R register 13
The contents of are subtracted by the subtraction circuit 15 and x _L register 18
Set to . By the above processing, x _R register 1
The x-coordinate data (maximum value) of the rightmost edge of the circle to be drawn is set in 6, and the x-coordinate data (minimum value) of the leftmost edge of the circle to be drawn is set in the _xL register 18. Also, in step _A2 above, the gate circuit
The gates G ₁₄ and G ₁₅ are opened, and the y coordinate data held in the y register 12 is set in the y _OV register 21 and the y _UD register 22.
After that, proceed to step _A3 , and gate circuit _G10 ,
Open the gates of G ₁₃ , G ₁₈ , G ₁₉ and set x _R register 1
6. Output the x, y coordinate data held in the x _L register 18, y _OV register 21, and y _UD register 22 to the display processing unit, and store the x, y coordinate point in the display memory (not shown). and displayed on a display unit (not shown). At this point, the y coordinate data at the center point Q is set in the y _OV register 21 and the y _UD register 22, so the x coordinate data specified by the contents of the x _R register 16 as shown in FIG. The maximum point p ₁ on the axis and the minimum point p ₂ on the x-axis specified by the contents of the x _L register 18 are plotted. Next, proceed to step _A4 , open the gate of the gate circuit _G20 , and set the radius R held in the R register 13.
is written to the Δx register 25. In step _A4 , the gates of the gate circuits G ₂₅ , G ₃₂ , and G ₂₈ are opened, the R _x register 29 and the _Ry register 34 are set to the initial value "0.5", and the Δy register 31 is set to the initial value "0.5". ”. When setting the above initial value "0.5" to each register 29, 34, set the decimal point position to the 5th bit D _p 2 position to correspond to the radius data as shown in FIG. Write. As a result, each register 25,
34 is the binary number "1000" as shown in Figure 5.
is written. Next, proceed to step _A5 , open the gates of gate circuits _G30 , _G33 , and _G31 , add the data held in the Δy register 31 and the _Ry register 34 in the adder circuit 33, and add the addition result to R. Write to _y register 34. In this case, “0000+1000=
1000'' is performed, and the R _y register 34 is
"1000" is written in. Then step A ₆
Open the gate of gate circuit G ₃₄ as shown in R _y
The contents of the register 34 are read out to a carry determination circuit 35 to determine the presence or absence of a carry. This carry determination is performed by setting the decimal point position to the same D _p 2 position as the initial value is written as shown in Figure 5. As mentioned above, if the content of the R _y register 34 is "1000" No carry detection signal is output. If there is no carry signal, step A ₇
, open the gates of gate circuits G ₂₃ , G ₂₆ , and G ₂₄ , add the contents “1000” of the Δx register 25 and the R _x register 29 in the adder circuit 28 , and add the addition result “10000” to the R _x register 29 write to. Next, proceed to step _A8 , open the gate of gate circuit _G27 , and transfer the contents of R _x register 29 to carry discrimination circuit 3.
It is read to 0 to determine the presence or absence of a carry. This carry discriminating circuit 30 includes the above-mentioned carry discriminating circuit 3.
5, the decimal point position is set to the D _p 2 position, and when the content of the R _x register 29 becomes “10000” and a “1” signal is written to the D _p 2 position, a carry is detected. Output a signal. This carry detection signal opens the gate of gate circuit _G29 , and as shown in step _A9 , Δy register 3
The content of 1 "0000" is increased by +1 in the +1 circuit 32 to become "0001". In addition, the above-mentioned carry discrimination circuit 3
The gates of gate circuits G ₁₆ and G ₁₇ are opened by the carry detection signal output from y _OV register 21 as shown in step A ₁₀ .
+1 by 3, and y _UD register 22
The content of is decremented by -1 by the -1 circuit 24. After that, proceed to step A ₁₁ , and gate circuits G ₁₀ , G ₁₃ ,
Open the gates of G ₁₈ and G ₁₉ , x _R register 16, x _L
Register 18, y _OV register 21, y _UD register 2
The x, y coordinate data held in 2 is output to the display processing section, and the x, y coordinate point is stored in the display memory and displayed on the display section. That is, as shown in FIG. 3, in the first quadrant A ₁ of the x, y coordinates, the contents of the x _R register 16 and the y _OV register 21 are determined, and in the second quadrant A ₂ , the contents of the x _L register 18 and the y _OV register 21 are According to the content of , in the third quadrant A ₃ ,
Due to the contents of the x _L register 18 and the y _UD register 22, in the fourth quadrant, the x _R register 16 and the y _UD
Based on the contents of the register 22, the x and y coordinate points of the circle are plotted in the display memory and displayed on the display section. In this way, we begin plotting a circle based on points p ₁ and p ₂ on the x-axis in FIG. 3 as reference points. After that, proceed to step _A12 , open the gate of the gate circuit _G22 , read the contents of the Δx register 25 to the "0" judgment circuit 27, judge whether it is "0" or not, and output the judgment result to the CPU. . If the contents of the Δx register 25 are not "0", the process returns to step _A5 and the same process is repeated. And step
At A ₅ , Δy register 31 is set to R _y register 34.
If a carry signal is generated when the contents of are added,
Proceed to step _A13 via carry determination step _A6 . In this step _A13 , the carry discrimination circuit 3
The gate of the gate circuit G ₂₁ is opened by the carry detection signal outputted from the Δx register 25, and the data held in the Δx register 25 is set to “−1” by the −1 circuit 26. Further, the gates of gate circuits G ₉ and G ₁₂ are opened by the carry detection signal outputted from the carry discrimination circuit 35, and the contents of the _xR register 16 are changed to -1 circuit 17.
At the same time, the contents of the x _L register 18 are set to "+1" by the +1 circuit 19. Thereafter, proceed to step _A7 and repeat the above process. That is, the Δx register 25, the Δy register 31, the R _x register 29, the R _y register 34, and the adder circuits 28 and 3.
3, a circuit consisting of a +1 circuit 32 and a -1 circuit 26,
For a circle centered at the origin given the radius R of the circle
The DDA calculation, that is, the DDA calculation using the above equations (5) and (6), is performed, and the changes in x and y determined by this calculation are stored in the coordinate registers 16, 18, 21, 22.
The change is made in a circle centered on point Q. In this case, as shown in Figure 3, the arc starts from points _p1 and _p2 on the x-axis, but since the upper and lower points are symmetrical with respect to the x-axis,
When performing one calculation, two symmetrical points can be found at the same time. Thus, the contents of the Δx register 25, in which the radius R was initially set, are sequentially incremented to "-1" by the process shown in FIG. , a "0" detection signal is sent to the CPU, and the process ends.

In the above embodiment, a case where a circle is drawn is shown, but by correcting the carry discrimination timing of the carry discrimination circuits 30 and 35, a horizontally long or vertically long ellipse can be drawn.

Further, in the above embodiment, a case where a circle is displayed graphically is shown, but in other cases, for example, X-Y
The same method can be used when printing on a plotter or the like.

〔Effect of the invention〕

According to the present invention, a circle is drawn from the rightmost end and the leftmost end while simultaneously obtaining vertically symmetrical coordinate data with respect to the X-axis, so any circle can be drawn at high speed.

In addition, a circle can be drawn by calculating 1/4 arc, eliminating the need for conventional symmetric point calculations and troublesome conversion calculations between absolute coordinates and user coordinates.

[Brief explanation of drawings]

The drawings show one embodiment of the present invention, and FIGS. 1a and 1b are diagrams for explaining the arc generating means by DDA, FIG. 2 is a circuit configuration diagram, and FIG. 3 is a drawing state of a circle. 4 is a flowchart showing the operation contents of FIG. 2, and FIG. 5 is a diagram showing the setting state of the decimal point position of the register. 11...x register, 12...y register, 1
3...R register, 14,28,33...addition circuit, 15...subtraction circuit, 16...x _R register, 1
7, 24, 26...-1 circuit, 18...x _L register, 19, 23, 32...+1 circuit, 21...
y _OV register, 22...y _UD register, 27...
"0" judgment circuit, 25...Δx register, 29...
R _x register, 30, 35... Carry discrimination circuit,
31...Δy register, 34... _Ry register.

Claims (1)

[Claims] 1. Means for determining the X-coordinate data of the rightmost end and the X-coordinate data of the leftmost end of the circle to be drawn from the X-coordinate data of the center and radius data, and storing both X-coordinate data determined by this means. An X coordinate data storage means for storing Y coordinate data of the center of the circle to be drawn, and a Y coordinate data storage means for storing Y coordinate data of the center of the circle to be drawn, and each coordinate data of these storage means is A circle drawing method comprising a generation means for generating circle drawing data from the rightmost end and the leftmost end while simultaneously obtaining vertically symmetrical coordinate data with respect to the X-axis.