JPH04195524A - Digital differential analyzer - Google Patents

Abstract

PURPOSE:To attain efficient interpolating processing with simple circuit constitution by generating an interpolating point between two points by using a prescribed set point previously prepared in the case of judging that an amount of travel is less than a previously set threshold. CONSTITUTION:This digital differentiation analyzer is provided with a traveling amount analyzing means 4 for analyzing the amount of travel from a start point up to an end point based upon inputted coordinate information, a parameter computing means 5 for computing a parameter for interpolating processing based upon the inputted coordinate information and an interpolating point generating means 6 for generating an interpolating point between the two points, i.e., the start point and the end point, based upon the computed result of the means 5. When the means 4 judges that the amount of travel is less than the previously set threshold, the means 6 generates the interpolating point between the two points by using the prescribed set point previously prepared without using the computed result of the means 5. Thus efficient interpolating processing can be executed by the simple circuit constitution.

Description

[Detailed Description of the Invention] [Summary] Regarding a digital differential analyzer, the purpose of the present invention is to provide a digital differential analyzer that performs efficient interpolation processing with a simple circuit configuration. A digital differential analyzer for interpolating between two predetermined points, comprising: an information input means for inputting information from the coordinate information of the starting point to the coordinate information of the end point; A movement amount analysis means for analyzing the movement amount from a starting point to an end point, a parameter calculation means for calculating parameters for interpolation processing based on coordinate information input from the information input means, and calculation results of the parameter calculation means. interpolation point generation means for generating an interpolation point between two points, the starting point and the end point, based on the movement amount analysis means, and when the movement amount analysis means determines that the movement amount is smaller than a preset threshold, The interpolation point generation means is configured to generate an interpolation point between the two points using predetermined set values prepared in advance without using the calculation results of the parameter calculation means.

[Industrial Application Field] The present invention relates to a digital differential analyzer, and more specifically, for example, computer graphics (CG) and CAD (
The present invention relates to a digital differential analyzer suitable for use in the field of computer aided design, which interpolates between two predetermined points when drawing a line segment.

The basis of drawing in graphics processing using a computer is the drawing of a line segment connecting two predetermined points. To draw such a line segment, a predetermined start point and end point are specified, and the drawing between these two points is It is necessary to interpolate.

In recent years, interpolation between two predetermined points has been developed.
Many digital differential analyzers (hereinafter referred to as DDA) have been developed because they can be constructed using only adders and bit shifters without using multipliers with complicated circuit configurations.

However, when interpolating between two points using DDA, it is necessary to calculate parameters from the coordinates of the two points to be interpolated as preprocessing, and in order to simplify the circuit configuration, this preprocessing and interpolation point generation processing If both are processed by the same arithmetic unit, speed will be sacrificed and control will become complicated.

- Therefore, in order to improve processing speed, it is required to perform parameter calculation and interpolation point generation processing separately in pipeline processing.

(Prior Art) In order to improve processing speed, conventional digital differential analyzers of this type are equipped with separate parameter calculation means for calculating parameters and interpolation point generation means for generating interpolation points. Pipeline processing was performed between the means and the interpolation point generating means.

In order to avoid complicating the circuit by providing separate parameter calculation means and interpolation point generation means, the parameter calculation means is generally configured with one calculation unit, and this calculation unit are operated sequentially to calculate all the parameters necessary for the interpolation point generation process.

[Problem to be solved by the invention]

However, in such a conventional digital differential analyzer, since the parameter calculation means is composed of one calculation unit, there are problems as described below.

In other words, the time required to generate an interpolation point by DDA is determined by the two input points, that is, the moving distance from the start point to the end point, whereas the time required to calculate the parameters depends on the parameter calculation means. It is constant depending on the circuit configuration. This means that if the difference between the two input points is larger than a certain value, there is no need to perform parameter calculations quickly, but on the other hand, if the difference between the two points is smaller than a certain value, then the parameter calculations need to be performed quickly. This means that it must be done quickly.

Therefore, due to the nature of the DDA, in order to perform vibration line processing at a high rate, it is necessary to carefully consider the nature of the two input data points and determine the circuit configuration of the parameter calculation means. When configured with one arithmetic unit, as shown in FIG. 6, for example, the parameter calculation means performs calculation in five cycles, and the interpolation point generation means performs interpolation point generation in one cycle per dot. Assuming this, there is a problem in that depending on the two-point data input manually, the processing of the interpolation point generating means goes into a WAIT state until the parameter calculation is completed, resulting in a significant drop in processing efficiency. In addition, in the figure, v
If l is the starting point coordinates (0, O) and ending point coordinates (2, 1) are input, similarly, v2 is the starting point coordinates (2°1), ending point coordinates (3, 1), and V3 is the starting point coordinates (3゜1), end point coordinates (
5,1), V4 is the starting point coordinate (5°1), the ending point coordinate (6,
2) is input.

Furthermore, in order to solve such problems, increasing the number of computing units in the parameter computing means by considering extremely rare data not only violates the prerequisite of simplifying the one-path configuration, but also increases the control However, there was a problem in that the process also became complicated, leading to an increase in costs.

Therefore, an object of the present invention is to provide a digital differential analyzer that performs efficient interpolation processing with a simple circuit configuration.

[Means to solve the problem]

In order to achieve the above object, the digital differential analyzer according to the present invention is a DDAI that interpolates between two predetermined points, a starting point and an ending point, on the XY coordinates, as shown in FIG. Starting point coordinate input means 2 for inputting coordinate information of the starting point
and end point coordinate input means 3 for inputting the coordinate information of the end point.
, the starting point coordinate input means 2, and the end point coordinate input means 3.
movement amount analysis means 4 for analyzing the movement amount from the start point to the end point based on the coordinate information input from the start point coordinate input means 2 and the interpolation processing based on the coordinate information input from the start point coordinate input means 2 and the end point coordinate input means 3; and an interpolation point generating means 6 that generates an interpolation point between the starting point and the ending point based on the calculation result of the parameter calculating means 5. When the amount analysis means 4 determines that the amount of movement is smaller than a preset threshold, the interpolation point generation means 6 uses a predetermined setting prepared in advance without using the calculation result of the parameter calculation means 5. The configuration is such that an interpolation point between the two points is generated using the value.

Further, the interpolation point generating means uses Bresenham's method, and the predetermined setting value is the X coordinate between two points to be interpolated;
ΔX and ΔY (ΔX>
ΔX1 and ΔX1 and ΔX1 and ΔX1 and Δ
2・ΔY−ΔX, 2・ΔY corresponding to Y (ΔX>ΔY)
.

2. It is effective to calculate each value of (ΔY+ΔX) in advance and create a table.

[Effect]

In the present invention, when the movement amount analysis means determines that the movement amount is smaller than a preset threshold value, the input data of the interpolation point generation means is not the calculation result of the parameter calculation means, but a predetermined value prepared in advance. A set value (for example, a table) is used, and an interpolation point between the two points is generated by an interpolation point generation means.

That is, even if the parameter calculation means has a simple configuration, the processing of the parameter calculation means prevents the processing of the interpolation point generation means from entering a waiting state, and the interpolation processing is performed by efficient pipeline processing.

〔Example〕

Hereinafter, the present invention will be explained based on the drawings.

FIG. 2 is a block diagram showing the overall configuration of a first embodiment of the DDA according to the present invention.

First, the configuration will be explained.

The DDA 1 of this embodiment is roughly divided into a starting point coordinate input section 2 which is a starting point coordinate input means, an end point coordinate input section 3 which is an end point coordinate input means, a movement amount analysis section 4 which is a movement amount analysis means, a parameter calculation unit 5, which is a parameter calculation means;
It is composed of an interpolation point generation section 6, which is an interpolation point generation means, and a table 7 stored in a ROM or the like.

In the movement amount analysis section 4, a number one cycle less than the processing cycle of the parameter processing section 5 is set in advance as a threshold value.

In addition, 8 is an arithmetic circuit, and the arithmetic circuit 8 calculates the amount of movement M from the start point to the end point based on the coordinates of two points input from the start point coordinate input section 2 and the end point coordinate input section 3. The interpolation point generating section 6 of this embodiment includes Bresenh
Line segment interpolation processing is performed using the am method.

FIG. 3 is a diagram showing an example of set values tabulated in this embodiment.

In DDA using Bresenham's method, if ΔX1 and ΔY (ΔX>ΔY), which are the differences between the X and Y coordinates between two points, are given as the amount of coordinate movement, The coordinates of the interpolation point are generated by sequentially determining whether or not to move in the X direction based on the calculated parameters.

Based on this, Table 7 of this embodiment has ΔX and Δ
Information on whether or not the Y coordinate moves in response to Y (ΔX>ΔY) is compiled into a table in advance. The table value 0 indicates no movement, l indicates movement, and each bit position is We are looking at the number of times we should move.

Next, the effect will be explained.

First, it is assumed that the calculation by the parameter calculation unit 5 is performed in 5 cycles, and the generation of interpolation points by the interpolation point generation unit 6 is performed in 1 cycle for each dot.
It is assumed that the threshold value of the movement amount analysis section 4 is set to 4.

First, when (0, O) is input as the starting point coordinate to the starting point coordinate human input unit 2 and (6, 5) is input as the ending point coordinate to the ending point coordinate input unit 3, the arithmetic circuit 8 calculates the X coordinate between the two points, and Differences in Y coordinates, ΔX and ΔY, are calculated.

In this case, the amount of movement M in the X direction is 6, and the amount M of movement in the Parameter calculations are performed, and interpolation point generation processing is performed by the interpolation point generation section 6 based on the calculated parameters.

Next, when (0, O) is input as the starting point coordinate to the starting point coordinate input section 2 and (2, 1) is inputted as the ending point coordinate to the ending point coordinate input section 3, the amount of movement M in the X direction is 2, and the amount of movement M in the X direction is 2. The amount of movement M
is 1, and these values are determined by the movement amount analysis unit 4 to be smaller than the threshold value, so the values in the table 7 are referred to, as shown in FIG. In this case, the value of Table 7 is 0010, which means that there is no movement in the X direction during the first movement in the X direction, and there is no movement in the X direction during the second movement in the X direction. This shows that there is movement. Then, the reference values of table 7 are input to the interpolation point generation section 6, and the interpolation point generation section 6 performs interpolation point generation processing based on the values of table 7.

Therefore, as in the conventional example, vl is the starting point coordinate (0
, O), the end point coordinates (2, 1), and the starting point coordinates (2, 1) as V2.
, 1), end point coordinates (3, 1), and starting point coordinates (3, 1) as v3.
, 1), end point coordinates (5°1), an example of operation when the start point coordinates (5, 1) and end point coordinates (6, 2) are input as V4 is shown in Fig. 4, and is similar to the conventional example. Processing is faster compared to . FIG. 5 is a diagram showing an example of tabulated setting values according to the second embodiment of the present invention, and table 7 of the present embodiment is 2·ΔY− corresponding to ΔX and ΔY (ΔX>ΔY). The main structure is the same as the first embodiment shown in FIG. 2, except that ΔX, 2·ΔY, and 2·(ΔY+ΔX) are calculated in advance and tabulated.

As described above, in this embodiment, when the movement amount determined by the movement amount analysis means is smaller than a preset threshold value, the input data of the interpolation point generation means is not the calculation result of the parameter calculation means, but is prepared in advance. Using a predetermined set value, the interpolation point generation means can generate an interpolation point between two points, and even if the parameter calculation means has a simple configuration, the processing of the interpolation point generation means waits for the processing of the parameter calculation means. You can do it without any trouble.

Therefore, with a simple circuit configuration, interpolation processing can be performed by efficient pipeline processing, and the interpolation processing speed can be increased.

(Effects of the Invention) In the present invention, when the movement amount calculated by the movement amount analysis means is smaller than a preset threshold value, the input data of the interpolation point generation means is not the calculation result of the parameter calculation means, but is prepared in advance. Using the predetermined settings,
The interpolation point generation means can generate an interpolation point between two points, and even if the parameter calculation means has a simple configuration, the processing of the interpolation point generation means can be performed without waiting for the processing of the parameter calculation means.

Therefore, interpolation processing can be performed using efficient pipeline processing with a simple circuit configuration.

[Brief explanation of the drawing]

Fig. 1 is a diagram explaining the principle of the DDA of the present invention, Figs. 2 to 4 show a first embodiment of the DDA according to the invention, Fig. 2 is a block diagram showing its overall configuration, and Fig. 3 is its table. 4 is a diagram for explaining an example of the operation of the first embodiment. FIG. 5 is a diagram illustrating an example of tabulated setting values of the second embodiment. FIG. 6 is a diagram for explaining an example of the operation of the conventional example. 1...DDA (digital differential analyzer), 2.
...Starting point coordinate input section (starting point coordinate input means), 3.
... End point coordinate input section (end point coordinate input means), 4.
...Movement amount analysis unit (means movement amount analysis means), 5.
...parameter calculation section (parameter calculation means),
6... Interpolation point generation section (interpolation point generation means), 7.
...Table, 8...Arithmetic circuit. Figure 3 shows an example of tabulated setting values in the first embodiment.
Figure 5 shows an example of tabulated setting values of the second embodiment.
figure

Claims (4)

[Claims] (1) A digital differential analyzer that interpolates between two predetermined points, a starting point and an ending point on the XY coordinates, and an information input means for inputting information from the coordinate information of the starting point to the coordinate information of the ending point; a movement amount analysis means for analyzing the movement amount from the starting point to the end point based on the information inputted to the information inputting means; and calculating parameters for interpolation processing based on the coordinate information inputted from the information inputting means. comprising a parameter calculation means, and an interpolation point generation means for generating an interpolation point between the starting point and the end point based on the calculation result of the parameter calculation means, and the movement amount is preset by the movement amount analysis means. If it is determined that the interpolation point is smaller than the set threshold, the interpolation point generation means generates an interpolation point between the two points using a predetermined set value prepared in advance without using the calculation result of the parameter calculation means. A digital differential analyzer characterized by: (2) The digital differential analysis according to claim 1, wherein the information input means includes: a start point coordinate input means for inputting coordinate information of a starting point; and an end point coordinate input means for inputting coordinate information of an end point. vessel. (3) The interpolation point generating means uses Bresenham's method, and the predetermined setting value is the X coordinate between two points to be interpolated;
ΔX and ΔY (ΔX>
3. The digital differential analyzer according to claim 2, wherein information on whether or not the Y coordinate moves in response to ΔY) is prepared in advance in a table. (4) The interpolation point generating means uses Bresenham's method, and the predetermined setting value is the X coordinate between two points to be interpolated;
ΔX and ΔY (ΔX>
2・ΔY−ΔX, 2・ΔY, 2・(Δ
3. The digital differential analyzer according to claim 2, wherein each value of Y+ΔX) is calculated in advance and tabulated.