JPH0148593B2 - - Google Patents

Description

[Detailed description of the invention]

INDUSTRIAL APPLICATION FIELD The present invention relates to an apparatus for calculating grid points in an image space divided into a grid. Configuration of conventional examples and their problems In recent years, image processing using electronic computers has become very important, but especially with the spread of ultra-compact computers, processing of images, editing and processing of images, curves and straight lines has become increasingly important. It is becoming very important to use electronic computers to perform processes such as drawing images. For example, a method called digital differential analysis (hereinafter abbreviated as DDA) has been known as a method for calculating drawing points from functional expressions in order to draw straight lines or curves in an image space divided into a grid. There is. FIG. 1, FIG. 2, and FIG. 3 are for explaining this DDA algorithm. below,
A case will be explained in which, for example, a curve expressed by equation (1) is generated by the DDA algorithm. f(x, y)=0...(1) First, by differentiating the above equation (1), we obtain df(x, y)=G(dn, dy, x, y)=0...(2). By introducing a new variable dt into equation (2), it can be rewritten as dx=g ₁ (x, y, dt) dy=g ₂ (x, y, dt) ...(3). From this equation (3), xn + ₁ = xn + dx = xn + g ₁ (xn, yn, dt) yn + ₁ = yn + dy = yn + g ₂ (xn, yn, dt) ... (4). By deriving a recurrence formula regarding xn, yn, it is possible to find the positions of adjacent points one after another from xn, yn and a small constant value dt. If the grid spacing is l, then by drawing a point at the coordinates (xn, yn), the curve of equation (1) can be drawn. (However, xn=[xn/l]yn=
In [yn/l], [x] represents an integer not exceeding x. ) In Figure 1, the coordinates of the true position from point P ₁ to point P ₄ are marked with an x, and the position of an integer (xn, yn) not exceeding (xn, yn) (hereinafter abbreviated as approximate point) .)
is marked with a circle. If the distance between the true position and the approximate point is R _x and R _y , then
In order to obtain the (n+1)th value from the coordinate position of the nth point using the DDA algorithm, processing is performed according to the flowchart shown in FIG. Note that FIG. 3 describes in more detail the part of the process 22 shown in FIG. 2. Further, in the process 23 shown in FIG. 2, the entire processing portion of x shown in FIG. 3 is replaced with y. Now, the process of moving from the approximate point corresponding to P _o in Figure 1 to the approximate point P _o+1 is as follows. That is, first, the increments Δx and Δy of x _o and y _o are determined (process 21 in FIG. 2). This increment is added to the residual R _x (process 31 in FIG. 3). As a result, when R _x becomes larger than l, it means that one vertical line of the grid has been crossed to the right, so R _x is returned to a value smaller than l, and the variable representing the position of the grid line is
1 is added to X _o (processes 34 to 35 in FIG. 3). On the other hand, if △x is negative and R _x becomes smaller than -l as a result of the addition in process 31, this means that the new point is beyond one vertical line of the grid to the left. , reduce the grid line variable X _o by 1, and return R _x to a positive value (Process 37 in Figure 3).
~Processing 39). A conventional method for implementing the above algorithm will be explained in more detail with reference to FIGS. 4 and 5. FIG. 4 explains how to express the position between grids using the above method. Section 41, 42, 4
3 are interlattice numbers N-1, N, N+1, respectively
And from there, it is uniquely expressed as the residual R _X.
Each grid line number _X and residual R
The position on the grid line in the section 42 represented by bit data (16-value notation) is <N, 0000>, and the point immediately before grid line N+1 is <N, FFFF>.
When using this method of notation for the position of a point, △x
The expression requires two words to represent magnitude and direction. That is, the processing of the flow shown in FIG. 3 is processed by calculations as shown in FIG. That is, the residual R _X and the lower part D _XL of Δx are added, and the result is set as a new R _X. The carry information CRY generated during the addition is added at the same time as the grid line number X _o and the upper part D _XU of Δx. This result will indicate the position of the new grid point. Next, with reference to FIG. 6, an example of a device that executes the above processing will be described. According to the apparatus of FIG. 6, the contents of residual register 1
Adder 3 adds R _X and the content D _XL of lower increment register 2.
This result is stored in the residual register 1 again. On the other hand, CRY held by the carry information holding circuit 4 that occurred during addition and the grid line number holding circuit 5
The content X _o of the grid line number in and the content _D In this way, the grid line number of the point to be drawn is calculated. However, since the display method of the residual _R
If the result is negative, and if the residual R _X becomes negative as a result of process 31 in _Figure 3, and if R Processing must be performed to return the difference R _X to a positive value. In other words, since the flow of the program differs depending on the sign of the increment, curves etc. cannot be drawn using the same algorithm, and the control program also becomes complicated. Furthermore, the initial value of residual register 1 is the grid line number.
By fixing the midpoint of 4000 after X ₁ and X ₂ , for example, when drawing an arc, even if the arc has the same center and radius, the
When drawing starts from the axis, the trajectories of the arcs do not necessarily match. Purpose of the Invention The present invention has been made in order to solve the above-mentioned conventional problems, and it is an object of the present invention to extremely easily calculate the position of a point to be drawn when drawing an arbitrary curve on an image space. This provides a lattice point calculation device that can perform Structure of the Invention The present invention includes an increment holding means that holds an increment in two's complement representation, and an increment held by the increment holding means and a residual difference held by itself in two's complement representation. a residual value holding means for adding the result of the addition by a means and again holding the residual as a new residual in two's complement representation; and an initial value setting means for setting an initial value for the residual value holding means. ,
The value of the lattice point held by the lattice point holding means is changed according to the value of the most significant bit of the increment held by the incremental holding means and the new residual held by the residual holding means. In addition to determining whether or not
The above object is achieved by providing lattice point position changing means for changing the value of the most significant bit of the residual holding means when a decision is made to change the value of the lattice point. DESCRIPTION OF EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 7 shows the main block configuration of a grid line calculation device according to an embodiment of the present invention. In FIG. 7, reference numeral 70 denotes an initial value setting means for providing an initial value to a residual register 72, which will be described later, and the initial value is input from a keyboard or the like. Reference numeral 71 denotes an increment register which sequentially holds the increment .DELTA.x in the x-axis direction of the grid in 16 bits using two's complement, and the most significant bit of the data represents the positive or negative of the increment .DELTA.x. 7
2 is a residual register that holds the residual R _X in the _x -axis direction of the grid in 16 bits using two's complement; Hold it again as R _X.
74 is a sign bit detection circuit that detects whether the sign of the most significant bit of the residual register 72 (that is, the sign bit in two's complement representation) is "1" or "0"; When the sign is detected, a signal selection control signal is sent to a signal selection circuit 79, which will be described later, and the sign of the most significant bit of the residual register 72 is changed from "1" to "0". 7
5 is the grid line number N, that is, the grid point in the x-axis direction
With the lattice point pointer that stores X _o , the memory of the lattice points in the x-axis direction is updated every time the addition circuit 73 performs addition. 76 is an addition circuit that adds 1 to the grid point X _o held by the grid point pointer 75;
7 is a subtraction circuit that subtracts 1 from the grid point held by the grid point pointer 75. A signal selection circuit 78 normally passes the output of the adder circuit 76, and passes the output of the subtracter circuit 77 only when the most significant bit of the increment register 71 is negative, that is, the sign represents "1". 79 is a signal selection circuit that normally passes the output of the lattice point pointer 75 and sends the output to the lattice point pointer 75 again, and selects the signal only when the sign bit detection circuit 74 detects a sign "1" indicating a negative value. A signal from the circuit 78 is passed through to cause the grid point pointer 75 to store and update the new grid point. The operation of the above configuration will be explained below with reference to the flowchart of FIG. 8, but first, the method of expressing the position between the grids in this embodiment will be explained with reference to FIG. 9. In FIG. 9, a section 91 is a section from N-1 to N+1 based on the grid line number N held by the grid point pointer 75, and
This is expressed by the residual R _X held in the residual register 72. Note that the initial value of this residual R _X can be arbitrarily set by the initial value setting means 70. The most significant bit in the 16-bit information of the residual _R.sub.X is used as a bit representing the positive/negative sign, and the remaining bits represent the magnitude. Based on the grid line number N, the direction of N-1 is a negative area, so it can be expressed as a two's complement by 〈(N)
8000〉~〈(N)FFFF〉, and since the direction of N+1 is a positive area, 〈(N), 0000〉~〈(N),
7FFF>. Also, the section 72 is expressed based on the grid line number N+1, as described above.
Now, the residual R _X is always treated as a positive number, so
If you want to set a negative area, use the initial value setting means 70.
By subtracting the grid line number by 1 and returning the residual R _X to positive, the initial value can be set arbitrarily.
The remaining range in this case is 0 to 7FFF. Note 2
As is generally known, the complement of is the top 4
If you limit the information to bits, it will look like the table below.
Positive or negative is indicated depending on whether the most significant bit is "0" or "1".

【table】

【table】

[Table] Now, the operation of the lattice point calculation device shown in FIG. 7 will be explained below along with the flowchart shown in FIG. Note that the flowchart in FIG. 8 corresponds to the flowchart shown in FIG. (a) First, the residual _R
is added to the increment △x held by
The added value is stored again in the increment register 72 as the residual _R.sub.X. At this time, carry information is ignored. (b) Next, the sign bit detection circuit 74 checks the sign of the most significant bit of the increment register 72. When the sign bit detection circuit 74 detects "0", that is, a positive sign, the signal selection circuit 7
9 control is not performed. Therefore, the signal selection circuit 79 selects the a-side signal, that is, the lattice point pointer 75
passes the information about the grid point X _o in the x-axis direction held by
X _o memorize information. On the other hand, when the sign bit detection circuit 74 detects "1", that is, a negative sign, the residual difference register 72
The signal selection circuit 79 is controlled by changing the sign of the most significant bit from "1" to "0" and sending a signal selection control signal to the signal selection circuit 79. Therefore, the signal selection circuit 79 is controlled so that the signal on the b side is passed through and the new grid point X _o is stored in the grid point pointer 75. (c) In addition to the control described in (b) above, the signal selection circuit 78 is also controlled in accordance with the information "0" and "1" of the most significant bit in the increment Δx of the increment register 71. (d) That is, when the most significant bit information of the increment Δx is “0”, the signal selection circuit 78 selects the signal on the a side, and the addition circuit 76 selects the signal at the lattice point X sent from the lattice point pointer 75. _o plus 1 is sent. (e) On the other hand, when the most significant bit information of the increment Δx is "1", the signal selection circuit 78 selects the signal on the b side, and the subtraction circuit 77 moves the lattice point pointer 7
The value obtained by subtracting 1 from the grid point X _o sent from 5 is sent. (F) By the control in (D) or (E) above, the information sent from the addition circuit 76 or the subtraction circuit 77 is sent to the grid point pointer 75 by the signal selection circuit 77.
The data is stored and updated in the lattice point pointer 75 via 8 and 79. As is clear from the controls in (a) to (e) above, regardless of the value of the most significant bit of the increment register 71,
If the most significant bit of the residual register 72 is “0” as a result of _R
Information on X _o is input again via the signal selection circuit 79 and stored. On the other hand, when the most significant bit of the residual register 72 becomes "1" as a result of R _X +Δx, this means that a change has occurred in the grid point in the x-axis direction. At this time, if the most significant bit of the increment register 71 is "0", it means that the grid point has moved by one in the positive direction, so the addition circuit 76 receives the grid point X sent from the grid point pointer 75. 1 is added to _o , the signal selection circuit 78,
A new grid point is added to the grid point pointer 75 via 79.
Memorize X _o +1. On the other hand, if the most significant bit of the increment register 71 is "1", this means that the grid point has moved by one in the negative direction, so the subtraction circuit 77
is the grid point sent from the grid point pointer 75
1 is subtracted from X _o , and a new grid point (X _o
-1) is memorized. The table below shows the storage update state of the lattice point pointer 75 caused by the above operation.

[Table] As described above, according to this embodiment, the signal selection circuits 78 and 79 are controlled by the values of the most significant bits of the increment register 71 and the residual register 72, which are expressed in two's complement numbers. By simply doing this, you can easily calculate the changes in the grid points that occur at a certain small constant value dt. In this embodiment, the signal selection means 79 sends information from either the lattice point pointer 75 or the signal selection circuit 78 to the lattice point pointer 75 in response to the signal selection control signal sent from the code bit detection circuit 74. Although the memory is being updated, the grid point pointer 7
The signal selection means 78 is used only when it is necessary to change the memory in step 5.
It may be configured such that the output sent from the lattice point pointer 75 is sent to the grid point pointer 75 to update the memory. Furthermore, by providing the initial value setting means 70,
Since it is possible to set even a delicate position that is less than the grid line interval of the starting point, the position of the entire curve can be set more accurately. Effects of the Invention As described above, the present invention provides an increment holding means that holds an increment in two's complement representation, and an increment held by the increment holding means and the remainder held by itself in two's complement representation. and a residual holding means for adding the difference by an adding means and holding the residual of the addition result as a new residual again in two's complement representation; and an initialization for setting an initial value for the residual holding means. a value setting means, and a grid held by the grid point holding means according to the value of the most significant bit of the increment held by the increment holding means and a new residual held by the residual holding means; and lattice point position changing means for determining whether or not to change the value of a point, and also changing the value of the most significant bit of the residual holding means when a decision is made to change the value of the lattice point. When drawing an arbitrary curve on the image space,
The position of the point to be drawn can be calculated extremely easily, and even delicate drawings can be performed accurately, which is highly effective.

[Brief explanation of drawings]

Figure 1 is a schematic diagram explaining digital differential analysis.
Figures 2 and 3 are flowcharts of the same analysis, and Figure 4
The figure shows a representation of the position between grids, Figure 5 is a diagram explaining the calculation process shown in Figure 3, and Figure 6 is a block diagram of the main parts of a conventional grid point calculation device that executes the calculation process shown in Figure 5. 7 is a block wiring diagram of the lattice point calculation device according to an embodiment of the present invention, FIG. 8 is a flowchart of the lattice point calculation device, and FIG. 9 is a diagram showing the positions between lattices in the lattice point calculation device. It is a figure showing an expression. 70... Initial value setting means, 71... Increment register, 72... Residual register, 73... Addition circuit,
74... Sign bit detection circuit, 75... Grid point pointer, 76... Addition circuit, 77... Subtraction circuit,
78, 79...Signal selection circuit.

Claims (1)

[Claims] 1. An increment holding means that holds an increment in two's complement representation, and adding the increment held by the increment holding means and the residual held by itself in two's complement representation. a residual difference holding means for adding the difference by means of a residual difference holding means and again holding the residual difference of the addition result as a new residual in two's complement representation; and an initial value setting means for giving an initial value to the residual difference holding means; The value of the lattice point held by the lattice point holding means is changed according to the value of the most significant bit of the increment held by the incremental holding means and the new residual held by the residual holding means. 2. A lattice point calculation device comprising lattice point position changing means for determining whether or not the lattice point value is changed, and also changing the value of the most significant bit of the residual holding means when a decision is made to change the value of the lattice point. 2. The lattice point position changing means includes an addition means for adding 1 to the lattice points held by the lattice point holding means, a subtraction means for subtracting 1 from the lattice points held by the lattice point holding means, and an incrementing means for adding 1 to the lattice points held by the lattice point holding means; a first signal selection means for selecting the output of either the addition means or the subtraction means according to the value of the most significant bit of the increment held by the holding means; and a residual held by the residual holding means. determining means for determining whether or not to change the lattice point held by the lattice point holding means to the information selected by the first signal selection means, according to the value of the most significant bit of the lattice point holding means. A lattice point calculation device according to claim 1, characterized in that: 3. The determining means may cause the grid point holding means to re-store the grid points held by the grid point holding means in accordance with the value of the most significant bit of the residual held by the residual holding means; a second one for storing and updating the information selected by the first signal selecting means in the grid point holding means;
3. The lattice point calculation device according to claim 2, wherein the lattice point calculation device is a signal selection means.