JPH0248780A - Straight line generator - Google Patents

Abstract

PURPOSE:To prevent the increase of an error, to obtain a prescribed accuracy and to shorten a calculating time by executing a prescribed operation and calculating respective intermediate values between the starting point and an end point of third data based on the parameter for the third data concerning the third coordinates for X and Y coordinates. CONSTITUTION:A parameter processing part 4 divides the difference between the starting point and the end point of the third data concerning the Z coordinates for X and Y coordinates of the starting point and the end point stored in an input register group 1 based on control signals S4-S7 from a sequencer 3 with respective input register groups R8-R14 of a plotting register group 5 together with arithmetic circuits 6 and 7, with the difference of the larger absolute value of the difference of X and Y coordinate axis directions and divides it into an integer part and a decimal part. The intermediate value between the starting point and the end point of the third data is obtained by the addition (or subtraction) of the integer part and the digital differential analyzing method (DDA) operation at the decimal part side. Consequently, processing is executed by the addition (or subtraction) of the integer and DDA. Thus, it is prevented that the error is increased, a prescribed accuracy can be obtained and the calculation time can be shortened.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a straight line generation device, and in particular, to smooth generation of straight lines on three-dimensional coordinates and color information on straight lines in information processing devices that generate and display figures. The present invention relates to a straight line generator that can express a three-dimensional object by changing the straight line to a three-dimensional object.

[Conventional technology]

Techniques for displaying three-dimensional objects on computer displays, so-called three-dimensional graphics, are rapidly becoming popular these days.

In order to make a 3D object look like it appears on a 2D flat display, there are hidden surface removal methods that prevent surfaces hidden by objects in the foreground from being displayed, and shading methods that make objects with curved surfaces look like they appear. has been considered.

Among the various methods, the methods with the simplest algorithm and the most suitable for speeding up are the Z-buffer algorithm for hidden surface elimination, and the Gouraud method for shading.

In addition to the memory that stores normal display data, the Z-buffer algorithm has a memory called a Z-buffer that corresponds one-to-one to that data. Calculate the value Z already written to the Z buffer. Read the value and compare it with this, and only when it is in front (Z < Zo) data and Z
This method involves rewriting the value. By repeating this process, hidden surface removal can be achieved.

Gouraud's method attempts to make a curved surface appear smooth by smoothly changing the color information itself of the data to be written. The generation of color values is done using the Z
The method of generating values and the generation of straight lines are basically the same; the only difference is that the generated values are used directly as color values rather than as depth information.

Now, both formulas are basically used when a straight line is generated. Digital differential analysis (hereinafter referred to as DDA) is a well-known technique for generating two-dimensional straight lines. This accurately multiplies the X and Y coordinates of the line point sequence,
Since it can be determined without performing division, it is a widely used technique that has been applied to many graphics display devices.

Next, DDA will be briefly explained.

First, the difference D in the X coordinate axis direction from the starting point and ending point coordinates of the straight line
Find the difference DY in the X and Y coordinate axis directions.

Then, using the larger absolute value of the differences DX and DY as a reference coordinate axis, the unit coordinate value "1" is added (or subtracted) using the coordinate value of the starting point of the reference coordinate axis as an initial value.

On the other hand, the coordinate values of the coordinate axes that did not become the reference coordinate axes are synchronized with the increase or decrease of the reference coordinate axes, and in principle the slope of DX/DY (or D Y/D Instead of increasing or decreasing D X/D Y, the increase or decrease is determined based on a modified formula so that there is no need to directly add or subtract D X/D Y.

Regarding three-dimensional straight lines, straight lines on the X-Y plane are generated by DDA, but the third-dimensional Z values and color values are calculated directly by calculating the slope of the straight line on the X-Z plane or Y-Z plane. They adopted a method of asking for additional information. This is because the basics of DDA is to use coordinate axes with large differences as a reference, but the starting points of straight lines on mutually independent XYZ coordinate systems,
This is because the difference in the end point coordinates varies in size, so the Z value cannot be directly determined by DDA.

[Problem to be solved by the invention]

The conventional straight line generator described above generates a straight line on the X-Y plane by DDA, but because the third-dimensional value cannot be generated by DDA, it directly adds the slope between the starting point and the ending point. Since the configuration is such that the slope D Z/
When calculating D X or D Z/D Y by division, the precision is determined by the number of bits used to calculate it, and since they are sequentially added, there is a drawback that errors increase. Conversely, if the number of bits below the decimal point is increased in order to improve precision, the computation time required for division will increase, resulting in a deterioration in performance.

SUMMARY OF THE INVENTION An object of the present invention is to provide a straight line generator that can prevent errors from increasing, obtain a predetermined accuracy, and reduce calculation time.

[Means to solve the problem]

The straight line generator of the present invention has a starting point and an ending point.

an input register group that stores third data including the Y coordinate and at least one of third coordinates and attached data for these X and Y coordinates, and X, Y coordinates stored in the input register group; The difference between the starting point and the ending point in the direction of the X coordinate axis is calculated, and the starting point on the XY plane is determined from these differences by using the coordinate axis with the larger absolute value of these differences as the reference coordinate axis.

means for generating and storing parameters for calculating the intermediate linear coordinates between the end points; and means for determining the difference between the start point and the end point of the third data stored in the input register group, and converting this difference into the reference coordinate axis. A parameter for determining the integer part and decimal part of the value divided by the difference in direction, and calculating the intermediate value between the start point and the end point of the third data from these integer part and decimal part and the difference in the reference coordinate axis direction. and a means for generating and storing a unit coordinate value, which sequentially monotonically increases (or decreases) by a predetermined unit coordinate value in the direction of the reference coordinate axis from the starting point on the X-Y plane.
At the same time, in synchronization with the monotonous increase (or decrease) of this unit coordinate value, predetermined calculations are performed based on the parameters for the X-Y plane to determine each coordinate in the direction of the coordinate axis paired with the reference coordinate axis, means for calculating each intermediate linear coordinate between the starting point and the ending point on the X-Y plane; and calculating intermediate values between the starting point and the ending point of the third data.

[Effect]

The present invention introduces the following idea in order to calculate an accurate third-dimensional Z value at high speed.

First, the Z value is basically generated using DDA. For this purpose, the slope of a straight line on the X-Z plane or the Y-Z plane is separated into an integer part and a decimal part less than 1.

For example, the starting point (0, O, O) and the ending point (1o.

7.23> is interpolated by a straight line.

The reference coordinate axis becomes the X coordinate axis with a large difference.

On the X-Y plane, coordinate values in the X-coordinate axis direction are calculated while sequentially adding unit coordinate values "1" in the X-coordinate axis direction.

On the other hand, the Z value is determined by generating a straight line on the X-Z plane. In this case, the slope is 23/10, so the integer part is 2,
The decimal part is 3/10.

From these values, a straight line of Z values, Z = (23/10)・X
is expressed as Z=2・X+(3/10)・X. In other words, when calculating the Z value, for 2.X, it is sufficient to add "+2" for the increase of ゛+1 pa in X, and for (3/10).X, conventional DDA can be applied. .

This method is simple because the Z value can be calculated in complete synchronization with the calculation of the X and Y locus values, and the DD
Since it uses A, it is possible to calculate an accurate Z value, and it also has the feature that it can be simplified by simply finding the integer part and decimal part of the result of division.

〔Example〕

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. This embodiment has a function of generating a straight line connecting a starting point (Xs, Ys, Zs) and an ending point (XE, YE, ZE), and shows an example when color data is fixed.

Before explaining the embodiment shown in FIG. 1, an overview of the overall process flow will be first explained based on the flowchart shown in FIG.

Based on the given start point and end point coordinates, the amounts of change in the X, Y, and X coordinate axis directions, that is, the differences DX, DY, and DZ are determined. Parameters required for DDA are calculated based on the differences DX and DY in the X and X coordinate axis directions.

On the other hand, regarding the X coordinate axis direction, the integer part and decimal part are obtained by dividing the difference in the X coordinate axis direction by the larger value of the difference in the X coordinate axis or the X coordinate axis direction. Parameters required for DDA for Z value generation are calculated based on the decimal part. The steps up to this point (procedures P1 to P4) are so-called pre-processing.

Next, actual drawing processing, that is, straight line generation is performed.

First, point X that corresponds to a straight line on the X-Y plane.

color data already written to the Z buffer from Y) and Z. The calculated z value is compared with the Ze value, and Z (if Zo, new color data and z
The value is written back to the point (X, Y) of a display memory such as a Z buffer. If Z≧Zo, do nothing (steps P5 to P7
).

Next, the x, y, and z values are updated. This is calculated by DDA based on the DDA parameters generated in preprocessing (procedure P8).

Finally, check whether you have drawn to the end point coordinates and repeat the above operation until the end point coordinates (step p9.
P9).

Next, the hardware of this embodiment will be explained.

In Fig. 1, 1 is a group of input registers that stores the starting point and end point data required to generate a straight line, 2 is an input control unit that performs read/write control of input register group 1, and 3 is a control unit that controls the flow of processing. 4 is a parameter processing unit that converts input data into a format suitable for drawing operations, 5 is a drawing register group, 6 and 7 are arithmetic circuits that process the contents of the drawing register group 5, and 8 is a color data processing unit. A data selection section that processes binary values; 9 is an address output section that outputs an address for a display memory such as an external Z buffer; R1 and R18 are each 16-bit registers; D1 to Dll
is data, S, ~sit is a control signal.

First, the coordinates (Xs, Ys, Zs) of the start point and end point are stored in each register R1 to R7 of the input register group 1 from the host system located at the upper level.

(Xi, Yt, Ze) and attached data, straight line color data CRL, are stored. Selection of these registers R1 to R7 is performed by a control signal SKI decoded by the input control section 2 based on the control signal S1. After storing the necessary data, the host system starts the operation of the sequencer 3 by means of a control signal S1.

The parameter processing unit 4 uses the registers R8 to R14 of the drawing register group 5 together with the arithmetic circuit 6.7 to calculate the starting point stored in the input register group 1 based on the control signals S4 to S7 from the sequencer 3. and the coordinates of the end point (Xs,
Ys, Zs), (Xi.

YE, Zs) to the starting point in the x, y, z coordinate axis direction.

Find the differences DX, DY, and DZ between the end points, and calculate the differences DX, D
Using the coordinate axis with the larger absolute value of Y as the reference coordinate axis, from these differences DX, DY, and DZ, a DDA parameter is generated for calculating the intermediate linear coordinate between the starting point and the ending point on the X-Y plane, and The difference DZ is the difference in the direction of the reference coordinate axis (
Calculate the integer part and decimal part of the value of DZ/DX divided by (temporarily assumed to be DX), and calculate the intermediate coordinate between the start point and end point in the Z coordinate axis direction from these integer part, decimal part, and the difference DX in the reference coordinate axis direction. Generate DDA parameters for

The drawing register group 5 stores each DDA parameter generated by the parameter processing unit 4 and the arithmetic circuits 6 and 7 in a register R.
8 to R14, and register R15.
~R18 First of all, X, Y.

The initial values of Z and color data (starting point values) are stored.

After the above-mentioned DDA parameters are generated, the arithmetic circuit 6.7 uses each register R8 to R17 of the drawing register group 5 to perform the X-Y
Sequentially monotonically increase (or decrease) the unit M target value "1" from the starting point on the plane in the direction of the reference coordinate axis (X coordinate axis), and in synchronization with this monotonous increase (or decrease), Perform DDA calculations based on the DDA parameters to obtain each coordinate in the direction of the coordinate axis (Y coordinate axis) that pairs with the reference coordinate axis, calculate each linear coordinate intermediate between the starting point and end point on the X-Y plane, and use the results. Sequentially stored in registers R, 6, R, , and in synchronization with the monotonous increase (or decrease) in the reference coordinate axis direction, the D is
DA calculation is performed to calculate intermediate coordinates between the starting point and the ending point in the Z coordinate axis direction, and the results are sequentially stored in the register R15.

The address output unit 9 outputs an X value from registers R16 and R17 in synchronization with a monotonous increase (or decrease) in the direction of the reference coordinate axis, that is, each time the X and Y coordinates are updated.

Read and output the Y coordinate.

The data selection section 8 inputs the Zo value and color data read from the address corresponding to the X and Y coordinates from the address output section 9 in a display memory such as a Z buffer, and selects the Z value and the Zo value of the register R15. If Z<Zo, the values of registers R, 4, and R18 are written back to the display memory,
If Z≧Zo, do nothing and proceed to the next step.

In this way, the starting point in the XYZ coordinate system.

Generation of a straight line connecting end points, Z coordinate axis direction and color
Hidden surface erasure processing of the data is performed.

FIG. 3 shows steps P, ~ of the flowchart shown in FIG.
It is a flowchart which shows the detailed flow of P4.

In FIG. 3, DXYI to DXY3 are DDA parameters for the XY plane, and are stored in registers R8 to R1o of the drawing register group 5, respectively. Also, DZ1
~DZ3 and S are DDA parameters for the Z coordinate axis direction, and are stored in registers RI4 to R1 of the drawing register group 5, respectively.

FIG. 4 is a flowchart showing the detailed flow of step P8 in the flowchart shown in FIG.

DDA parameters DX\1 to DxY3 for the X-Y plane and Z coordinate axis direction. A DDA operation is performed using DZ1 to DZ3 and S, and the X, Y, and Z coordinates stored in registers R15 to R17 are sequentially updated.

The reason why two systems of arithmetic circuits are provided is to improve performance, and also because step P of the flowchart in FIG.
19+ The branching of processing in the sequencer 3 based on whether R21 is positive or negative is determined by the control signal S output from the arithmetic circuit 6.
It is executed based on IO.

In the above embodiment, the color data is fixed and the XYZ
We have described the case of generating a straight line in the coordinate system, but
Starting point (Xs, Ys) and ending point (XE, Yv,
), color data can be defined for each of the starting point and the ending point, and the color data of the intermediate point between the starting point and the ending point can be obtained by linear interpolation. This is a necessary function to implement shading using Gouraud's method.

This process can be easily realized using the hardware of the above embodiment.

First, the flow of processing will be explained with reference to FIG.

In this process, "Z" in FIG. 2 is replaced with color data, and steps P5 to P7 are changed as follows.

There is no need to read data from the point (X, Y) on the memory or compare Z values; it is sufficient to simply write the obtained Z value (color value) to the point (x, y).

Therefore, the operation of the data selection unit 8 shown in FIG. 1 is simplified, and the Z value input from the register R15 is
It should be output as O. The above-mentioned operation instruction to the data selection section 8 can be given by the control signal S8.

Note that the address generation for the display memory in the above embodiment was a combination of the X coordinate value and the Y coordinate value, but
It can be generated independently of the calculation of the Y coordinate, or it can be generated by the data selection section 8.
Even if hardware is added to write the result of calculating the data read from the display memory and the newly written color data, this does not depart from the gist of the present invention.

Further, although the embodiments of the present invention have shown the generation of three-dimensional straight lines and the generation of shading straight lines separately, it is also possible to easily generate three-dimensional straight lines while performing shading by combining them. In addition, by processing not only one type of color data but multiple color data, so-called RGB (RE
D. GREEN.

Shooting processing can also be realized in correspondence with the three primary colors of BLLE.

〔Effect of the invention〕

As explained above, the present invention calculates the difference between the starting point and the ending point of the third data with respect to the X, Y coordinates of the starting point and the ending point.
Divide by the larger absolute value of the difference in the direction of the Y coordinate axis, divide it into an integer part and a decimal part, and add (or subtract) the integer part and add (or subtract) the intermediate value between the start point and end point of the third data to the decimal part. By adopting a configuration in which the calculation is performed using the DDA operation on the part side, instead of directly adding (or subtracting) the slope of the third data as is in the conventional method, it is possible to calculate the slope by adding (or subtracting) an integer and using the DDA calculation.
Since the calculation is performed by However, in the present invention, this is not necessary, so there is an effect that the calculation time can be shortened.

Register group, 6, 7... Arithmetic circuit, 8... Data selection section, 9... Address output section, P1 to P24... Procedure, R1 to R18... Register.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a τ embodiment of the present invention;
3 is a flowchart showing in detail a part of the procedure of the flowchart shown in the figure.

Claims (1)

[Claims] an input register group that stores the X and Y coordinates of the start point and the end point, and third data including at least one of the third coordinates and attached data for these X and Y coordinates, and the X stored in this input register group; , calculate the difference between the starting point and the ending point in the X and Y coordinate axis directions from the Y coordinate, and using the coordinate axis with the larger absolute value of these differences as the reference coordinate axis, use these differences to calculate the intermediate point between the starting point and the ending point on the X-Y plane. means for generating and storing parameters for calculating the linear coordinates of;
Find the difference between the start point and end point of the third data stored in the input register group, divide this difference by the difference in the reference coordinate axis direction, find the integer part and decimal part, and calculate the integer part and decimal part. means for generating and storing a parameter for calculating an intermediate value between the start point and the end point of the third data from the difference in the direction of the coordinate axis and the reference coordinate axis;
From the starting point on the Y plane, the unit coordinate values are sequentially monotonically increased (or decreased) in the direction of the reference coordinate axis, and in synchronization with the monotonous increase (or decrease) of the unit coordinate values, the
means for calculating each coordinate in a direction of a coordinate axis that pairs with the reference coordinate axis by performing a predetermined calculation based on parameters for the plane, and calculating each linear coordinate intermediate between the starting point and the ending point on the X-Y plane; Means for performing predetermined calculations based on parameters for the third data in synchronization with the monotonous increase (or decrease) in the direction of the reference coordinate axis, and calculating intermediate values between the start point and the end point of the third data. A straight line generator comprising: