JPH1131232A - Method and device for plotting polygon - Google Patents

Abstract

PROBLEM TO BE SOLVED: To attain high speed plotting by successively generating pixel data along a scan line by using an anti-aliasing technique. SOLUTION: Line cross point data to be generated includes first outside cross point XLe and inside cross point XLi corresponding to the upstream edge of the scan direction of a scan line N, second outside cross point XRe and inside cross point XRi corresponding to the downstream side edge, the increase ratio of a luminance value from the first outside cross point to the inside cross point, and the decrease ratio of the luminance from the second inside cross point to the outside point. A first processing for mainly calculating the change of the luminance value from the first outside cross point to inside point, second processing for mainly calculating the change of the luminance value from the second inside cross point to outside cross point, and third processing for synthesizing the first and second processed results are executed in parallel so that each luminance value of the inside part of a polygon can be sequentially calculated in a scan direction for each scan line.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention is applied to an image display device or the like which draws and displays a figure on a memory, and draws a polygon such as a triangle so that an edge portion becomes smooth. About.

[Prior art]

When a figure is drawn on a memory, an ideal line is represented by points on a grid arranged at equal intervals in the vertical and horizontal directions. Therefore, as shown in FIG. It becomes a line. In order to reduce this jagging, an anti-aliasing technique has been proposed. FIG. 24 is a diagram for explaining this technique. In this method, when one pixel is considered as one square, the brightness value is determined depending on how much a straight line covers each pixel as shown in FIG. FIG. 2B shows an example in which the luminance of each pixel is determined based on such a criterion. As in this example, 1
The straight line can be drawn smoothly by expressing the straight line with the luminance difference.

[0003]

However, in the conventional anti-aliasing method, the calculation is complicated because it is necessary to calculate how much an ideal straight line covers each pixel. In addition, special processing must be performed only on the edge portion of the triangle edge, so that there is a problem that the drawing speed of the triangle is reduced.

The present invention has been made in view of such a problem, and uses an anti-aliasing technique for smoothly drawing edges, and sequentially performs pixel-sharing along a scan line in the same manner as a normal drawing process. An object of the present invention is to provide a polygon drawing method and apparatus which can generate data and can perform high-speed drawing.

[0005]

According to the polygon drawing apparatus of the present invention, an edge portion of a polygon is drawn smoothly by giving a luminance value corresponding to an area covering each grid on a drawing plane. In the polygon drawing apparatus, data on an intersection between each edge of the polygon to be drawn and a scan line, wherein the first outside intersection and the inside intersection corresponding to the scan direction upstream edge of the scan line, A second outer intersection and an inner intersection corresponding to the scanning direction downstream edge of the scan line, an increase rate of the luminance value from the first outer intersection to the inner intersection, and a second inner intersection to an outer intersection from the second inner intersection. Edge calculating means for obtaining line intersection data including the reduction rate of the luminance value for each scan line; and each of the scan line data obtained by the edge calculating means. A first process for mainly calculating a change in the luminance value from the first outer intersection to the inner intersection for each scan line based on the line intersection data for each scan line, and a process for calculating the change from the second inner intersection to the outer intersection for each scan line. By executing in parallel a second process for mainly calculating a change in the brightness value of the polygon and a third process for synthesizing the results obtained in the first and second processes, Scan line processing means for sequentially obtaining the respective luminance values along the scan line.

A polygon drawing program stored in a medium according to the present invention provides a brightness value according to an area covering each grid on a drawing plane, so that an edge portion of a polygon is drawn smoothly. A first outer intersection and an inner intersection corresponding to an intersection between each edge of the polygon to be drawn and the scan line, the first outer intersection and the inner intersection corresponding to an upstream edge in the scan direction of the scan line; A second outer intersection and an inner intersection corresponding to a downstream edge of the line in the scanning direction;
An edge calculation step of obtaining, for each scan line, line intersection data including an increase rate of the luminance value from the outer intersection to the inner intersection, and a decrease rate of the luminance value from the second inner intersection to the outer intersection. A first process of mainly calculating a change in luminance value from the first outer intersection to the inner intersection for each scan line based on the line intersection data for each scan line obtained in the edge calculation step; The second processing for mainly calculating the change in the luminance value from the second inner intersection to the outer intersection and the third processing for synthesizing the results obtained in the first and second processing are performed in parallel. And a scan line processing step of sequentially obtaining each luminance value inside the polygon along the scan line. And butterflies.

Further, a polygon drawing method according to the present invention is characterized in that:
In the polygon drawing method in which a polygon edge portion is smoothly drawn by giving a luminance value according to an area covering each grid on the drawing plane, each edge of the polygon to be drawn and a scan line A first outer intersection and an inner intersection corresponding to the scan direction upstream edge of the scan line, and a second outer intersection and an inner intersection corresponding to the scan direction downstream edge of the scan line. An intersection, an increasing rate of the luminance value from the first outer intersection to the inner intersection, and the second
The line intersection data including the reduction rate of the luminance value from the inner intersection to the outer intersection is obtained for each scan line, and based on the obtained line intersection data for each scan line, the line intersection data is obtained for each scan line. A first process for mainly calculating a change in luminance value from the first outer intersection to the inner intersection, and a second process for mainly calculating a change in luminance value from the second inner intersection to the outer intersection.
By executing the third processing for synthesizing the results obtained in the first and second processings in parallel, each luminance value inside the polygon is sequentially obtained along the scan line. It is characterized by the following.

According to the present invention, the first outer intersection and the inner intersection corresponding to the upstream edge in the scan direction of the scan line by the edge calculation, the second outer intersection and the inner intersection also corresponding to the downstream edge, the first The increase rate of the luminance value from the outer intersection to the inner intersection and the decrease rate of the luminance value from the second inner intersection to the outer intersection are determined for each scan line, and the luminance from the first outer intersection to the inner intersection is calculated. A first process for mainly calculating a change in the value, a second process for mainly calculating a change in the luminance value from the second inner intersection to the outer intersection, and the results of the first and second processes are combined. Since the third processing and the third processing are executed in parallel, the luminance value can be obtained in order from the upstream side to the downstream side of the scan line, and the sequence along the scan line can be obtained. Catcher Le processing becomes possible. In particular, in this case, even when the vertices at the upper and lower ends, the vertices in the middle thereof, and these vertices are not located on the line, the luminance value can be easily calculated by the common processing method. Therefore, high-speed drawing processing can be realized.

The edge calculating means finds a position on the grid adjacent to the actual intersection on the downstream side in the scanning direction as the first outer intersection and the inner intersection, respectively, as the second outer intersection and the inner intersection. The position on the grid adjacent to the actual intersection on the upstream side in the scanning direction is determined, and the luminance value at the first outer intersection and the luminance value at the point on the grid adjacent to the second inner intersection on the downstream side in the scanning direction are calculated. If each of them is calculated as an initial value, all the processing is calculation processing of the luminance value on the grid, so that higher-speed processing can be performed.

The first and second outer intersections and the inner intersections can be obtained based on, for example, a trajectory when the vertices of the polygon to be drawn are dragged by a diamond block having vertical and horizontal dimensions corresponding to a grid interval. it can.

The scan line processing means outputs, for example, as a first process, an increase rate from the first outer intersection to the inner intersection for each scan line, and outputs each luminance value. A constant luminance value is output after the inner intersection of, and as a second process, the reduction rate is accumulated from the second inner intersection to the outer intersection, and each luminance value is output.
A constant luminance value is output after the outer intersection of, and a luminance value on each scan line is processed only by addition and subtraction, such as subtracting the result of the second processing from the result of the first processing as the third processing. Can be calculated, so that high-speed drawing processing can be performed.

The scan line processing means may use a value corresponding to a distance from the scan line to the vertex as the constant luminance value when the vertex of the polygon is located between the scan lines. .

Further, when the vertices other than the vertices at the upper and lower ends of the polygon are located between the scan lines, the scan line processing means performs processing based on the distance from the vertices to the upper scan line; By separately executing and combining the processing based on the distance to the scan line, the processing can be shared, and the luminance value can be calculated by a simple calculation.

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Preferred embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a triangle drawing apparatus according to one embodiment of the present invention. This device includes an edge calculation circuit 1, a horizontal line processing circuit 2, a pixel processing circuit 3, and a memory 4. The edge calculation circuit 1 calculates the vertex coordinates (X _A , Y _A ), (X _B , Y _B ),
From (X _C , Y _C ), line intersection data relating to the intersection between the triangle and each scan line is calculated. In this example, the line intersection data is
It consists of coordinate values (Y _N , XLe, XLi, XRi, XRe) and luminance value information (I ₀ L, ddIL, I ₀ R, ddIR). From these line intersection data, the horizontal line processing circuit 2 calculates, for each scan line,
For example, coordinate values (X _P , Y _P ) for each pixel in order from the left
And a luminance value I _P corresponding to the pixel, and supplies this to the pixel processing circuit 3. The pixel processing circuit 3 generates pixel data corresponding to the luminance value I _P with respect to the pixel-based coordinate values (X _P , Y _P ) obtained by the horizontal line processing unit, and writes the pixel data to the memory 4. In the specification of the present application, the luminance value I _P of a pixel takes a value of 0 to 1. This may be a luminance value as it is, but a luminance correction coefficient for correcting a luminance value calculated separately is
It may be processed as the luminance value here.

FIG. 2 is a diagram showing each coordinate value obtained by the edge calculation circuit 1. Here, each vertex A, B,
C is a diamond-shaped box having a width of ± 0.5 of the grid width in the horizontal (X) and vertical (Y) directions, respectively.
The locus of the box indicated by the broken line in the figure when dragging between the vertices A, B, and C is defined as a triangular edge. Four intersections between the edge and each horizontal (scan) line are obtained for the left and right edges and for each line outside and inside each edge. Also, these intersections are not actual intersections, but points on the grid immediately inside the actual intersections are selected. Therefore, the coordinate values included in the line intersection data are summarized as follows.

Y _N : Y coordinate of line N XLe: X coordinate outside left edge of 〃 (on grid) XLi: X coordinate inside left edge of （(on grid) XRi: X coordinate inside right edge of Ｎ (on grid) XRe: X coordinate outside right edge of 〃 (on grid)

Based on the coordinate values thus obtained, as shown in FIG. 3, the luminance value I gradually increases from XLe to XLi, and gradually increases from XRi to XRe.
In order to determine the brightness value I inside the triangle so that the brightness decreases, the initial value I ₀ L of the brightness in XLe and the increase rate ddIL thereof, and the initial brightness value in the next X-direction pixel of XRi. The value I ₀ R and its reduction rate ddIR are determined.

FIGS. 4 and 5 are diagrams for explaining a method for obtaining these coordinate values and luminance values. FIG. 4 shows a method for obtaining the left edge, and FIG. 5 shows a method for obtaining the right edge. That's how it works. For both edges,
The distance in the X direction relative to the distance between the vertices in the Y direction (Y coordinate is 1
Assuming that XD is the amount of movement of the X coordinate when moving by the line, and YD is the distance in the Y direction relative to the distance in the X direction (the amount of movement of the Y coordinate when the X coordinate moves by one pixel), | YD | <
In the case of | XD | (a) and in the case of | YD | ≧ | XD | (b), the method of obtaining is slightly different.

When the left edge is | YD | <| XD | (close to horizontal) In FIG. 4 (a), the true intersection XL between the line N and the left edge has a slope XD from the upper vertex of this edge. Are added by the number of lines, and a point separated by | XD | / 2 in the X minus direction from the intersection XL is a true outside intersection XLer, and | XD | in the X plus direction from the intersection XL.
A point separated by / 2 is a true inner intersection point XLir. The values obtained by rounding up the decimal points of the true outer intersection XLer and the true inner intersection XLir are the outer intersection XLe on the grid and the inner intersection XLi on the grid, respectively.

The luminance value I at the true outer intersection XLer
Is 0, and the luminance value I of each pixel from XLe to XLi is determined such that the luminance value I at the true inner intersection XLir is 1, so that ddIL = | YD |

[0021]

[Number 1] _{I 0 L = (XLe-XLer} ) * ddIL I n L = I n-1 L + ddIL (n ≠ 0)

It is assumed that The luminance value I after XLi is 1.

When the left edge is | YD | ≧ | XD | (close to vertical) In FIG. 4 (b), the true intersection XL between the line N and the left edge has a slope XD from the vertex above this edge. Are added by the number of lines, and a point that is 0.5 away from the intersection XL in the X minus direction is a true outer intersection XLer, and a point that is 0.5 away from the intersection XL in the X plus direction is true. Becomes the inside intersection XLir. The values obtained by rounding up the decimal points of the true outer intersection XLer and the true inner intersection XLir are the outer intersection XLe on the grid and the inner intersection XLi on the grid, respectively. In this case, XL
e and XLi are necessarily pixel positions adjacent in the X direction.

The luminance value I at the true outer intersection XLer
Is 0 and the luminance value I ₀ L of the pixel of XLe is set so that the luminance value I at the true inner intersection XLir is 1.

[0025]

## EQU2 ## I ₀ L = XLe-XLer

Is determined as follows. Brightness value I of the next XLi
Becomes 1. In this case, ddIL does not need to be determined.

When the right edge is | YD | <| XD | (close to horizontal) In FIG. 5A, the true intersection XR between the line N and the right edge has a slope XD from the vertex above this edge. Are added by the number of lines, and a point separated by | XD | / 2 in the X minus direction from the intersection XR is a true inner intersection XRir, and | XD | in the X plus direction from the intersection XR.
A point separated by / 2 is a true outer intersection XRer. The values obtained by truncating the true inner intersection XRir and the true outer intersection XRer after the decimal point are the inner intersection XRi on the grid and the outer intersection XRe on the grid, respectively.

The luminance value I at the true inner intersection XRir
Is 1 and the luminance value I of each pixel from XRi + 1 to XRe is determined so that the luminance value I at the true outer intersection XRer becomes 0, so that ddIR = | YD |

[0029]

[Number 3] _{I 0 R = (XRer-XRi} -1) * ddIR I n R = I n-1 R-ddIR (n ≠ 0)

It is assumed that The luminance value I after XRe + 1 is 0.

When the right edge is | YD | ≧ | XD | (close to vertical) In FIG. 5B, the true intersection XR between the line N and the right edge has a slope XD from the upper vertex of this edge. Are added by the number of lines, and a point separated by 0.5 in the X minus direction from the intersection XR is a true inner intersection XRir, and a point separated by 0.5 in the X plus direction from the intersection XR is true. Is the outer intersection point XRer. The values obtained by truncating the true inner intersection XRir and the true outer intersection XRer after the decimal point are the inner intersection XRi on the grid and the outer intersection XRe on the grid, respectively. In this case, XR
i and XRe are necessarily pixel positions adjacent in the X direction.

The luminance value I at the true inner intersection XRir
Is 1 and the luminance value I ₀ R of the pixel of XRe is set so that the luminance value I at the true outer intersection XRer becomes ₀ .

[0033]

## EQU4 ## I ₀ R = XRer-XRe

Is determined as follows. Brightness value I of the next XRi
Becomes 1. In this case, ddIR does not need to be determined.

When the line intersection data is obtained in this way, as shown in FIG. 3, the luminance value I ₀ L is set as the initial value from the outer intersection XLe of the left edge, and the luminance increment value is ddIL.
, The luminance value is gradually increased to 1 over the inner intersection XLi, the luminance value I ₀ R is set as an initial value from the right side of the inner intersection XRi of the right edge, and the increment value (decrease value) of the luminance is dd.
By gradually decreasing the luminance value to 0 as the IR toward the outer intersection XRe, the luminance value I of each pixel can be obtained based on sequential processing along a normal scan line. In addition, as shown in FIG.
In the vicinity of the vertex, since the left and right edges are close to each other, the relationship between the outside intersection XLe of the left edge and the inside intersection XRi of the right edge and the relationship between the inside intersection XLi of the left edge and the outside intersection XRe of the right edge are respectively in the X direction. May be reversed. For this reason, the drawing of the luminance value I is performed from XLe to XRe, and if XLi and XRi do not appear during this time, a process for ignoring them is required.

Next, the details of the edge calculation circuit 1 will be described. FIG. 7 is a block diagram illustrating a configuration example of the edge calculation circuit 1. First, the vertex coordinates (X ₁ , Y ₁ ) of the triangle,
Given (X ₂ , Y ₂ ) and (X ₃ , Y ₃ ), the vertex with the smallest Y coordinate value is connected to A (X _A , Y _A ) and the vertex _{A of} the remaining two vertices. the vertex edge is located on the left side B when the (X _B, Y _B), the vertex edges when connected with the apex a is located on the right side and _{C (X C, Y C)} , which edge gradient calculation circuit 11 Given to. Edge gradient calculation circuit 11 is configured as shown for example in FIG. 8, the selecting each one of the X-coordinate X _A to X _C in the selector 21, 22, Y-coordinate by the selector 23, 24 Y _A to Y _C Are subtracted by the subtracters 25 and 26 from the outputs of the selectors 21 and 22 and the outputs of the selectors 23 and 24, respectively, and the result of the subtraction is divided by the divider 27. Straight lines AB and A shown by Equation 1
The inclinations of C and BC are calculated respectively.

[0037]

Equation 5] _{XD1 = (X B -X A)} / (Y B -Y A) XD2 = (X C -X A) / (Y C -Y A) XD3 = (X C -X B) / (Y _{C -Y B) YD1 = (Y} B -Y A) / (X B -X A) YD2 = (Y C -Y A) / (X C -X A) YD3 = (Y C -Y B) / ( X _C -X _B)

These inclination data are stored in the registers 28, respectively. The selector 29 selects a numerator denominator, and the selector 30 selects which register 28 stores the calculation result. Then, the selectors 21 to 21
24, 29 and 30 are controlled by the selector controller 31.

The inclination data XD1~XD3 and vertex data _{X A, X B, X C} , Y A is supplied to the edge coordinate calculating circuit 12, where Y coordinate value Y _N for each scan line
And the true edge positions X _L and X _R are obtained. The edge coordinate calculation circuit 12 is configured, for example, as shown in FIG. First, Y _A as an initial value of the Y coordinate value Y _N are selected by the selector 41 and stored in Y _N register 42. Thereafter, the Y coordinate value Y _N is updated by being added one by one by the adder 43. In each line, the first selected vertex X _A is the selector 44 and 46, the slope respectively the selector 45, 47 XD1, XD2 is selected. The initially stored respectively are selected vertex coordinates X _A edge coordinates X _L, as X _R to X _L register 50 and X _R register 51 by the selector 48 and 49, thereafter, the inclination of these by the adder 52 and 53 XD1, X
D2 is sequentially added to obtain edge coordinates X _L and X _R.

[0040] Here, the controller 13 of FIG. 7, Y _N
And Y _B, and outputs a control signal S1 when Y _B first appeared on the basis of the magnitude relationship between Y _C, and outputs a control signal S2 when Y _C first appears. When the control signal S1 is output, the selector 4
4 and 45 respectively select X _B and XD 3, and when the control signal S 2 is output, the selectors 46 and 47 select
Selects X _C and XD 3 respectively. Thereby, switching of the straight line is performed.

The obtained edge coordinates X _L and X _R correspond to the inclination X
It is supplied to the edge range calculation circuit 14 together with D1 to XD3. The edge range calculation circuit 14 is configured, for example, as shown in FIG. The upper circuit is a circuit for calculating the outer intersection XLe and the inner intersection XLi of the left edge, and the lower circuit is a circuit for calculating the inner intersection XRi and the outer intersection XRe of the right edge. is there. First, the selectors 61 and 62 determine the inclination data XD1,
XD2 is selected, the absolute value is converted into absolute values by absolute value converting circuits 63 and 64, and a value obtained by halving the values by 1/2 circuits 65 and 66 is calculated. The selectors 67 and 68 introduce the outputs of the half circuits 65 and 66 on one side and “0.5” on the other side,
Either one is selected by the control signal S3. For this reason, the controller 13 in FIG. 7 determines whether the edge has a gentle inclination (| YD | <| XD |) or a steep inclination based on the inclination data YD1 to YD3 (|
YD│ ≧ │XD│). Outputs of the selectors 67 and 68 are supplied to subtracters 69 and 70.
And the addition and subtraction of the edge coordinates X _L and X _R by the adders 71 and 72, respectively, the calculation result is rounded up by the round-up circuits 73 and 74 for the left edge, and the round-down circuits 75 and 76 for the right edge. The calculation result is rounded down, so that the intersection coordinates XL
e, XLi, XRi, and XRe are calculated and stored in registers 77, 78, 79, and 80, respectively. Further, true outer intersections XLer and XRer are obtained from the calculation results before rounding and rounding up.
When switching to a new edge, the selectors 61 and 62 switch one of the inclination data to XD3 by the control signals S1 and S2.

The calculated intersection coordinates XLe, XLi, XR
i, XRe, XLer. XRer is the inclination data YD1
Are supplied to the luminance initial value / increment value calculation circuit 15 together with .about.YD3. The luminance initial value / increment value calculating circuit 15 is configured, for example, as shown in FIG. Slope data YD1
YD3 is converted into absolute values by absolute value conversion circuits 85 to 88 and supplied to selectors 92 and 99, respectively. FIG.
In one circuit, the upper half is a circuit for calculating the luminance of the left edge, and the lower half is a circuit for calculating the luminance of the right edge. That is, the true outer intersection XLe of the left edge and the outer intersection X on the grid
The difference from Le is obtained by the subtractor 91, and this difference is multiplied by the multiplier 93 with | YD 1 | or | YD 3 | selected by the selector 92. The selector 94 selects the result of the multiplication as the initial luminance value I ₀ L when the inclination of the left edge is gentle. However, when the inclination of the left edge is steep, the selector 94 uses the difference value before the multiplication as the initial luminance value. Select as I ₀ L. The initial value I ₀ L is stored in the I ₀ L register 95 and | YD1 | or | YD3 selected by the selector 92.
Is stored in the ddIL register 96.

Also, the true outer intersection XRer of the right edge
And the outer intersection XR on the grid selected by the selector 97
e or the difference from the inside intersection XRi + 1 is obtained by the subtractor 98.
This difference is | YD2 |
Or | YD3 | in the multiplier 100. C
Lector 101 is used when the inclination of the left edge is gentle.
Multiplied by the initial luminance value I₀Select as R, but left
If the side edge is steep, the difference value before multiplication is
Initial value I of₀Select as R. This initial value I₀ R is I₀
Stored in the R register 102 and selected by the selector 99.
| YD2 | or | YD3 | is the ddIR register 103.
Is stored in

Next, the horizontal line processing circuit will be described. FIG. 12 is a block diagram illustrating a configuration example of the horizontal line processing circuit 2. In this example, the value of Y _N becomes the pixel Y coordinate Y _P as it is. At the start of the processing of one scan line, the X _P register 111, X-coordinate X _P of the first processing pixels on the scan line is stored. The X coordinate _XP is selected by the selector 112, and the initial value is X
Le. Also, XLe, XLi, XRi, XRe
Are the corresponding registers 113, 114, 11
Set to 5,116. The X coordinate _XP is calculated by the adder 11
“0” is sequentially added to “0”, and “1” is added along the scan line.
Move to the right one by one. This X coordinate _XP is used as the comparator 11
XLe, 7, 118, 119, 120 respectively.
XLi, XRi, and XRe are compared with each other, and the controller 121 controls each unit based on the comparison result.

[0045] That is, when X _P equals XLe is I ₀ L is selected by the selector 122, which is stored in the I _P1 register 123, when X _P is less than the larger XLi than XLe is the I _P1 register 123 with the cumulated value of the increment ddIL adder 124 to the value is stored is selected in the I _P1 register 123. In addition, X _P is XRi
Is exceeded, the selector 125 selects I ₀ R, which is stored in the _IP2 register 126. _XP is X
When the large XRe less than ri + 1 is increment (decrement value) the value to the subtractor 127 of the I _P2 register 126 dd
The value obtained by sequentially subtracting IR is selected and the I _P2 register 126 is selected.
Is stored in The value of the registers 123 and 126 and "1"
XLi but is supplied to the selector 128, X _P from XLe
Until -1 output of the register 123, the X _P from XLi to XRi "1", X _P is between from XRi + 1 until XRe will be the output of the register 126 is selected as the luminance value I _P. Further, the controller 121 starts the operation of one scan line by the START signal from the preceding circuit, X _P outputs an END signal indicating completion of processing in the preceding stage circuit with that exceeding the XRE.

As described above, according to this circuit, the luminance value of a pixel can be sequentially obtained along a scan line, so that high-speed processing can be performed.

In the above embodiment, the description has been made on the assumption that the Y coordinate of the vertex exists on the line. However, as shown in FIG. 13, for example, the coordinates (X
_{A, Y A), (X} B, Y B), (X C, when Y _C) is not present on the line, the fractional part of the Y-coordinate (hereinafter referred to as Y _LSB) by considering the, Further smooth expression is possible. In this case, as shown in FIG. 14, when a vertex is included between scan lines, ΔY serving as a reference of a luminance value is set as follows, and a luminance value I _P is obtained by multiplying the above-described luminance value by ΔY. I do.

(A) When the top vertex is included between the scan lines ΔY = 1−Y _LSB (b) When the vertex is not included between the scan lines ΔY = Y _LSB = 1 (c) The bottom apex between the scan lines When ΔY = Y _LSB

For this reason, in this embodiment, FIG.
The edge coordinate calculation circuit 12 is configured as shown in FIG.
In this circuit, the Y coordinate Y of the vertices A, B, and C is_A, Y_B, Y_C
To the selector 131 by the control signals S1 and S2.
Select the output of this selector 131 and round it down.
Subtractor 133 subtracts the value rounded down by circuit 132
By this, Y at the vertex_LSBIs calculated. Selector 13
4 switches between the output of the subtractor 133 and "1"
Yields Y_LSBRegister 135 contains less than 1 at the vertex
Y, which is “1” in other parts_LSBStore
You. The output of the truncation circuit 132 is supplied to the selector 136.
Through Y_NStored as an initial value in the register 137
You. Y_NThe register 137 stores “1” in the adder 138.
The sequentially added values are stored as updated values. Y
_LSBY stored in register 135_LSB Is the subtractor 139
Is subtracted from "1". Selector 140
ΔY corresponding to each of the cases (a), (b) and (c) described above
Output the value.

The circuit for obtaining the X coordinates X _L and X _R of the edge intersection is basically the same as the circuit shown in FIG. 9, but XD 1, XD 2 and XD 3 include multipliers 150 and 15.
Since ΔY are respectively multiplied by 1,152,153, increment in determining the X _L, X _R in the next line of vertices, a different value is the increment of the other line.

FIG. 16 is a block diagram of the horizontal line processing circuit 2 in this embodiment. The same parts as those in FIG. In this embodiment, the processing of the portion including the vertices is simplified by subtracting the results I _P1 and I _P2 of the left edge processing and the right edge processing separately by the subtractor 164. The selector 162 and 163, the value of ΔY are also given, the controller 161 selects the ΔY by the selector 162 when the X _P is equal to or greater than XLi, the selector 163 when the X _P exceeds XRe Select ΔY. I ₀ L, dd
IL, I ₀ R, and ddIR are set to values based on ΔY in advance. In this example, I ₀ R, ddIR
Are the initial value and the increase value of the luminance decrease value from the inside of the right edge, respectively.
Of course, the weighting by ΔY may be performed on the added values I _P1 and I _P2 and the luminance value I _{P of the} final result.

In this circuit, the scan line on which the upper vertex exists first is processed as follows. That is, the two edges connected to the upper vertex are divided into three patterns according to their inclinations, as shown in FIG. FIG. 11A shows the case where the signs of the inclinations of the left and right edges are different, and FIG. 10B shows the case where both the left and right edges are negative.
Indicates that both the left and right edges are positive. In each case, the outputs I _P1 and I _P2 of the adders 124 and 127 are as shown in FIG.
8 is represented by the area of each filled area. Accordingly, by subtracting I _P2 from I _P1 by the subtractor 164, the luminance I _{P of the} vertex portion between the lines can be easily obtained.

[0053] When there is no vertex on the scan in line, as shown in FIG. 19, but the [Delta] Y = 1, it is possible to calculate the luminance I _P at each pixel X _P by exactly the same operation as described above.

Further, as shown in FIG. 20, when an end point B exists between scan lines, the same processing is performed by dividing the scan line into upper and lower sides of the end point B. First,
As shown in FIG. 21A, the luminance I _P of the upper part is calculated, and then, as shown in FIG. 21B, the luminance I _P of the lower part is calculated.
Calculate _P. At this time, the Y coordinate values are the same. Then, these calculation results are added and mixed, is determined as the luminance value I _P for the same pixel.

[0055] As shown in FIG. 22, even if there is a lower apex of between scan lines, and by exactly the same procedure described above, it is possible to determine the brightness value I _P of each pixel.

In the above embodiment, the edge processing of a triangle has been described.
Needless to say, the present invention can be applied to edge processing of a polygon. In the above embodiment, the brightness value of a point on the grid is obtained. However, the correction may be made at the time of drawing a horizontal line from the brightness value of an actual point.

Further, in the above-described embodiment, the processing of each unit is realized by hardware, but the processing of each unit can be realized by software. In this case, the polygon drawing processing program can be provided by being recorded on an appropriate recording medium.

[0058]

As described above, according to the present invention, the first outer intersection and the inner intersection corresponding to the upstream edge in the scan direction of the scan line, and the second outer intersection corresponding to the downstream edge are also calculated by the edge calculation. Intersection and inner intersection,
The increasing rate of the luminance value from the first outer intersection to the inner intersection and the decreasing rate of the luminance value from the second inner intersection to the outer intersection are obtained for each scan line, and further from the first outer intersection to the inner intersection. A first process for mainly calculating a change in the brightness value of the second, a second process for mainly calculating a change in the brightness value from the second inner intersection to the outer intersection, and a first and a second processing result. Since the third processing to be combined is executed in parallel, the luminance value can be obtained in order from the upstream side to the downstream side of the scan line, and sequential processing along the scan line is possible. become. In particular, in this case, even when the vertices at the upper and lower ends, the vertices in the middle thereof, and these vertices are not located on the line, the luminance value can be easily calculated by the common processing method. Therefore, high-speed drawing processing can be realized.

[Brief description of the drawings]

FIG. 1 is a block diagram of a polygon drawing apparatus according to an embodiment of the present invention.

FIG. 2 is a diagram for explaining processing contents of an edge calculation circuit in the same device.

FIG. 3 is a diagram for explaining an operation of a horizontal line processing circuit in the same device.

FIG. 4 is a diagram for explaining a method of calculating various data of a right edge in the edge calculation circuit.

FIG. 5 is a diagram for explaining a method of calculating various data of a left edge in the edge calculation circuit.

FIG. 6 is a diagram for explaining processing of a vertex in a horizontal line processing circuit.

FIG. 7 is a detailed block diagram of an edge calculation circuit.

FIG. 8 is a block diagram of an edge inclination calculation circuit in the same circuit.

FIG. 9 is a block diagram of an edge coordinate calculation circuit in the circuit.

FIG. 10 is a block diagram of an edge range calculation circuit in the same circuit.

FIG. 11 is a block diagram of a luminance initial value / increment value calculation circuit in the same circuit.

FIG. 12 is a detailed block diagram of a horizontal line processing circuit.

FIG. 13 is a diagram showing a polygon applied to another embodiment of the present invention.

FIG. 14 is a diagram showing a pattern between lines of the same polygon.

FIG. 15 is a block diagram of an edge coordinate calculation circuit of the embodiment.

FIG. 16 is a block diagram of a horizontal line processing circuit of the embodiment.

FIG. 17 is a diagram showing an aspect of vertices of the same polygon.

FIG. 18 is a diagram for explaining the operation of the horizontal line processing circuit corresponding to each of the aspects.

FIG. 19 is a diagram for explaining the operation of the horizontal line processing circuit in the middle part of the polygon.

FIG. 20 is a diagram showing an embodiment including polygonal ends between lines.

FIG. 21 is a diagram for explaining an operation of the horizontal line processing circuit in the case of FIG. 20;

FIG. 22 is a diagram for explaining processing of a lower end portion of a polygon.

FIG. 23 is a diagram illustrating a conventional straight line drawing method.

FIG. 24 is a diagram for explaining a conventional anti-aliasing straight line drawing method.

[Explanation of symbols]

1 ... edge calculation circuit, 2 ... horizontal line processing circuit, 3 ... pixel processing circuit, 4 ... memory.

Claims (8)

[Claims] 1. A polygon drawing device which smoothly draws an edge portion of a polygon by giving a luminance value according to an area covering each grid on a drawing plane, wherein: Data on the intersection between each edge and the scan line, wherein the first outer intersection and the inner intersection corresponding to the scan direction upstream edge of the scan line, and the second outer intersection and the inner intersection corresponding to the scan line downstream edge of the scan line. Outer intersection and inner intersection, the rate of increase of the brightness value from the first outer intersection to the inner intersection,
Edge calculating means for obtaining, for each scan line, line intersection data including a reduction rate of the luminance value from the second inner intersection to the outer intersection; and a line for each scan line obtained by the edge calculator. A first process for mainly calculating a change in luminance value from the first outer intersection to the inner intersection for each scan line based on the intersection data; and a luminance processing from the second inner intersection to the outer intersection for each scan line. By executing in parallel a second process for mainly calculating the change and a third process for synthesizing the results obtained in the first and second processes, each brightness value inside the polygon is obtained. And a scan line processing means for sequentially obtaining the following along the scan line. 2. The edge calculating means finds a position on a grid adjacent to an actual intersection on the downstream side in the scanning direction as the first outer intersection and the inner intersection, respectively, and calculates the second outer intersection and the inner intersection. The position on the grid adjacent to the actual intersection on the upstream side in the scanning direction is determined, and the luminance value at the first outer intersection and the luminance at the point on the grid adjacent to the second inner intersection on the downstream side in the scanning direction are determined. 2. The polygon drawing apparatus according to claim 1, wherein values are calculated as initial values. 3. The first and second outer intersections based on a trajectory when the vertices of the polygon to be drawn are dragged by a diamond block having a vertical and horizontal dimension corresponding to a grid interval. The polygon drawing apparatus according to claim 1, wherein the polygon intersection calculating section calculates an inside intersection point. 4. The scan line processing means outputs the luminance values by accumulating the increasing rate from the first outer intersection to the inner intersection for each scan line as the first processing, After the first inner intersection, a constant luminance value is output. As the second processing, the reduction rates are accumulated from the second inner intersection to the outer intersection, and each luminance value is output. A constant luminance value is output after the outer intersection point of, and the result of the second processing is subtracted from the result of the first processing as the third processing. The polygon drawing apparatus according to any one of claims 1 to 6. 5. The scan line processing means uses a value corresponding to a distance from a scan line to the vertex as the constant luminance value when a vertex of the polygon is located between the scan lines. 5. The polygon drawing apparatus according to claim 4, wherein: 6. When the vertices other than the upper and lower vertices of the polygon are located between the scan lines, the scan line processing means performs processing based on a distance from the vertex to an upper scan line. The polygon drawing according to any one of claims 1 to 5, wherein a luminance value is calculated by separately performing processing based on a distance to a lower scan line and performing synthesis. apparatus. 7. A medium storing a polygon drawing program for rendering a polygon edge portion smoothly by giving a luminance value corresponding to an area covering each grid on a drawing plane. Data on the intersection of each edge of the power polygon with the scan line, including a first outer intersection and an inner intersection corresponding to the scan direction upstream edge of the scan line, and a scan direction downstream edge of the scan line. A corresponding second outer intersection and an inner intersection, the rate of increase of the luminance value from the first outer intersection to the inner intersection,
An edge calculating step of obtaining line intersection data including a decrease rate of the luminance value from the second inner intersection to the outer intersection for each scan line; and a line for each scan line obtained in the edge calculation step. A first process for mainly calculating a change in the luminance value from the first outer intersection to the inner intersection for each scan line based on the intersection data; and a luminance processing from the second inner intersection to the outer intersection for each scan line. By simultaneously executing a second process for mainly calculating the change and a third process for synthesizing the results obtained in the first and second processes, each brightness value inside the polygon is obtained. And a scan line processing step of sequentially obtaining the following along the scan line. 8. A polygon drawing method in which an edge portion of a polygon is smoothly drawn by giving a luminance value according to an area covering each grid on a drawing plane, wherein: Data on the intersection between each edge and the scan line, wherein the first outer intersection and the inner intersection corresponding to the scan direction upstream edge of the scan line, and the second outer intersection and the inner intersection corresponding to the scan line downstream edge of the scan line. Outer intersection and inner intersection, the rate of increase of the brightness value from the first outer intersection to the inner intersection,
In addition, line intersection data including the reduction rate of the luminance value from the second inner intersection to the outer intersection is obtained for each scan line, and each scan is determined based on the obtained line intersection data for each scan line. A first process for mainly calculating a change in luminance value from the first outer intersection to the inner intersection for each line, and a second process for mainly calculating a change in luminance value from the second inner intersection to the outer intersection. By executing the processing and the third processing for synthesizing the results obtained in the first and second processing in parallel, each luminance value inside the polygon is sequentially read along the scan line. A polygon drawing method, characterized in that a polygon drawing method is provided.