JP2779265B2 - Grid processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Summary] Regarding a grid processing method in a graphic processing apparatus, an object of the present invention is to provide a grid processing method capable of improving the processing performance of grid expansion, and to store data from a host computer. A data memory, a graphics processing processor that analyzes data and issues a command for generating vector data, an image data generation processor that generates vector data corresponding to the command as pixel data, and an image data memory that stores pixel data In the graphic processing processor, a line is regarded as one line segment having a start point on the first corner side and a marker on the second corner side adjacent to the start point as an end point. First processing means for extending and clipping, starting point extension amount and end point extension A second processing means for obtaining the positional relationship between the line and the designated area by comparing the above, a third processing means for determining the direction of expansion based on the difference between the start-side extension amount and the end-point extension amount, and the number of the first marker And a fourth processing unit that determines whether or not a marker exists in the designated area by comparing the number of the last marker with the number of the last marker, and extends the grid over the entire designated area.

The present invention relates to a grid processing method in a graphic processing device.

In the graphic processing device, when extending the grid to a certain specified area, each row of the grid is regarded as a set of discrete points, and it is determined whether the grid is further expanded or stopped depending on whether there is a point falling within the specified area. Because it was determined, it was necessary to have an extended area, and the processing performance was degraded.

Therefore, it is necessary to speed up grid expansion processing.

[Prior Art] FIG. 9 (A) shows a non-expanded grid, and FIG. 9 (B) shows an expanded grid.

The grid consists of the first, second, and third corners, the number of markers on the side determined by the first and second corners (hereinafter referred to as a row), and the side determined by the first and third corners. The number of markers above (hereinafter referred to as a column) and a range mode that specifies whether to limit it to a parallelogram (including a rectangle) determined by three corners or to extend over the entire area specified separately, Has as a parameter.

In the following, it is assumed that no two of the three corners of the grid match, and that the number of markers on each side is two or more.

In FIGS. 9A and 9B, the first to third corners are
Are shown in FIG. 3 and the number of markers in the row and column directions is four and three.

 Next, the positional relationship between the rows is shown in FIG.

In FIG. 10, the n-th row (n = 0, ± 1, ± 2...
The positional relationship of ()) is such that the line of the marker arranged on the line connecting the first and second corners is the 0th row, and from there, toward the third corner, 1,2. In the opposite direction-
It is determined by numbering each line as 1, -2, ....

As shown in FIG. 11, with respect to the grid of FIG. 10, when a solid line area is designated, a dotted line area obtained by expanding the original area (designated area) by the minimum grid that gives the same pattern is defined as It is called an extended area.

Next, FIGS. 12A to 12C show an algorithm of a process in a case where the grid is extended to an entire specified area.

In FIG. 12 (A to C), when the 0th side is extended, there is a marker in the extended area, and when the 0th side is extended, there is a marker in the original area, When a marker is drawn and n is set to 1 and the n-th side is extended, a marker is present in the extended area, and when the n-th side is extended and a marker is present in the area, a marker is provided. To draw.

In the same case, the marker is drawn at the time of the −n-th time, the processing is continued as n + 1, and when the n-th side is last extended, and when there is no marker in the extended area, the processing is terminated. .

Here, as shown in FIG. 13, if only the check is performed in the original area, since the marker does not exist in the original area in the first row, the processing of the second and subsequent rows is not performed. The marker at the position of the third corner is not drawn. In order to avoid such a case, the processing is performed by checking whether or not a marker exists in both the extended area and the original area for one row.

[Problem to be Solved by the Invention] However, in such a conventional grid processing method, it is necessary to determine whether or not a marker exists in each of two regions of an original region and an extended region. Therefore, when the number of rows of the grid is increased, there is a problem that the processing performance of grid expansion is reduced.

The present invention has been made in view of such conventional problems, and has as its object to provide a grid processing method capable of improving the processing performance of grid expansion.

[Means for Solving the Problems] FIG. 1 is an explanatory view of the principle of the present invention.

In FIG. 1, 5 is a graphic data memory for storing data from a host computer, 6 is a graphic processor for analyzing data and issuing a command for generating vector data, and 7 is for storing vector data corresponding to the command. An image data generation processor that generates pixel data, 8 is an image data memory that stores pixel data, 6A is a line segment having a line as a start point on the first corner side and an end point on the second corner side, and First processing means for performing extension and clipping, 6B is second processing means for obtaining the positional relationship between the line and the designated area by comparing the start-side extension amount and the end-point extension amount, and 6C is the start-point extension amount and the end-point extension amount The third processing means for determining the direction of expansion based on the magnitude of the difference between the first marker and the last marker has a marker in the designated area by comparing the number of the first marker with the number of the last marker. A fourth processing means for determining whether or not to.

[Operation] In the present invention, a line is regarded as one line segment starting at the first corner side and ending at a marker adjacent to the starting point on the second corner side, and the line segment is regarded as Cyrus. -Extend and clip the specified area using Beck's algorithm.

Next, from the comparison of the starting point extension amount and the ending point extension amount,
Find the positional relationship between a line and a specified area.

If the start point side extension amount ≦ the end point side extension amount, it is determined that the line and the designated area have a common part, and it is checked whether or not a marker exists in the designated area.

If the first marker number ≦ the last marker number, it is determined that the marker exists in the designated area, and the marker is drawn.

If the starting point extension amount> the ending point extension amount, it is determined that the line and the designated area do not have a common part. In this case, the start-side extension amount-the end-point extension amount is obtained and held, and the next line has no common part with the designated area, and the value of the start-point extension amount-the end-point extension amount is large. Determines that the direction is away from the designated area, and terminates expansion in that direction.

As described above, in the present invention, it is not necessary to make a determination in two regions for each row as in the related art, so that the processing performance of grid expansion can be improved even if the number of grid rows increases.

[Example] Hereinafter, an example of the present invention will be described with reference to the drawings.

 2 to 8 are views showing an embodiment of the present invention.

In FIG. 2, reference numeral 1 denotes an interface processor connected to a host computer 2. The interface processor 1 transfers a graphic order and data sent from the host computer 1 to a graphic data memory 5 via an address bus 3 and a data bus 4. To be stored.

Reference numeral 6 denotes a graphic processor. The graphic processor 6 analyzes data and the like stored in the graphic data memory 5 and issues a command for generating vector data to the image data generation processor 7.

The image data generation processor 7 generates vector data corresponding to the command issued from the graphic processor 6 as pixel data, and writes the pixel data to the image data memory 8. The pixel data written in the image data memory 8 is displayed on the CRT 9.

The graphic processing processor 6 performs a grid expansion process, and regards a line as a single line segment having a first corner side as a start point and a marker on the second corner side adjacent to the start point as an end point. First processing means 6A for performing extension and clipping, second processing means 6B for obtaining a positional relationship between a line and a specified area by comparing a start-side extension amount and an end-point extension amount, a start-point extension amount and an end-point extension amount A third processing means 6C for determining the direction of expansion according to the magnitude of the difference between the first and second markers, and a fourth processing means for determining whether or not a marker exists in the designated area by comparing the number of the first marker with the number of the last marker. Has the function of 6D.

 Next, the operation will be described.

First, a line is regarded as one line segment starting at the first corner and ending at a marker adjacent to the first corner on the second corner, and the Cyrus-Beck algorithm is applied to the line. This is used to extend or clip the designated area. The processing results of the Cyrus-Beck algorithm are shown in FIGS. 3 (A) and 3 (B).

Here, the results of the Cyrus-Beck algorithm for the start point side and the end point side are hereinafter referred to as a start point side extension amount and an end point side extension amount, respectively.

As shown in FIG. 3A, when the row and the area have a common portion, for example, the start-side extension amount is -1 and the end-point extension amount is 3.5. In addition, as shown in FIG. 3B, when the line and the area do not have a common portion, for example, the start-side extension amount is 3.5 and the end-point extension amount is 2.

Next, the grid extension processing will be described with reference to the flowcharts shown in FIGS.

 FIG. 4 shows processing on the side of the 0th row.

In FIG. 4, first, in step S1, extension or clipping of the 0th row is performed by the Cyrus-Beck algorithm. Next, in step S2, the starting-side extension amount ≦
It is determined whether or not the extension amount on the end point side. If the extension amount on the start point side ≦ the extension amount on the end point side, it is determined that the line and the designated area have a common part, and whether or not a marker exists in the designated area. The process proceeds to step S3 to check.

In step S3, the third corner side processing result is set to 0, and the anti-third corner side processing result is set to 0, and in step S4, the number of the first marker and the number of the last marker are calculated.

In other words, the starting point is numbered 0, and then the end point is 1, 2, ...
When the markers are numbered, the number of the first marker entering the specified area is given by the value obtained by rounding up the decimal part of the starting extension, and the number of the last marker entering the designated area is the ending extension. The fractional part of is rounded down.

Next, in step S5, it is determined whether or not the first marker number ≦ the last marker number, and the first marker number ≦
If the last marker number, the marker is drawn in the designated area assuming that the marker exists in the designated area. If the first marker number> the last marker number, no marker exists in the designated area. The process proceeds to step S11 in FIG.

In step S2, if the start point extension amount> the end point extension amount,
Since the line and the specified area do not have a common part, in this case, the starting point side extension amount−the ending point side extension amount is obtained in step S7 and held as the third corner side processing result and the anti-third corner side processing result. Keep it.

Next, the process of expanding to the third corner of the expansion in both directions shown in FIG. 5 is started. In step S11, n is set to 1 and the same process as described above is performed. In step S17, a marker is drawn, and the process of expanding to the third third corner side in the bidirectional expansion shown in FIG. 6 is started. Then, step S27
Then, n is set to n + 1, and the process returns to step S12 to continue the expansion process in both directions.

In FIG. 5, when the starting point side extension amount> the ending point side extension amount in step S13, the starting point side extension amount−the ending point side extension amount is obtained in step S18, and the third corner side processing result and the aforementioned The processing results are compared, and if the processing result on the third corner side <the processing result, it is determined that this direction is a direction away from the designated area, and the process proceeds to the extension to only the anti-third corner side in FIG. In this case as well, the drawing of the marker is continued in the same manner as described above, and if the extension on the start side> the extension on the end point in step S53, the extension on the start side−the extension on the end point is obtained in step S59, and When the third corner side processing result <the processing result, the processing is terminated.

Similarly, in the expansion to the anti-third corner side of the expansion in both directions in FIG. 6, if the anti-third corner side processing result <processing result in step S29, this direction is a direction away from the designated area. Therefore, the process proceeds to the expansion to only the third corner side shown in FIG. In FIG. 7, when the third corner side processing result <processing result in step S40, the process ends.

In this embodiment, as in the conventional case, 2
Since there is no need to make a determination in one area, the processing performance can be improved even if the number of rows in the grid increases.

[Effects of the Invention] As described above, according to the present invention, each line is regarded as a continuous line segment, and the continuous line segment is extended and clipped to perform grid expansion processing. Can be improved.

[Brief description of the drawings]

FIG. 1 is a diagram for explaining the principle of the present invention, FIG. 2 is a diagram showing an embodiment of the present invention, FIGS. 3 (A) and 3 (B) are diagrams showing processing results by the Cyrus-Beck algorithm, FIG. Fig. 5 is a flowchart showing the processing of the side of the 0th row. Fig. 5 is a flowchart showing the extension to the third corner side of the extension in both directions. Fig. 6 is an anti-third of the extension in both directions. 7 is a flowchart showing extension to the second corner side only, FIG. 7 is a flowchart showing extension to the third corner side only, FIG. 9 (A), FIG. B) is an explanatory diagram of a grid, FIG. 10 is an explanatory diagram of a positional relationship between rows, FIG. 11 is an explanatory diagram of an extended area, FIG. 12 (A to C) is a flowchart showing a conventional grid extending process, FIG. The figure is an explanatory view showing that it is not possible to remove the check in the extended area. In the drawing, 1 ... Interface processor, 2 ... Host computer, 3 ... Address bus, 4 ... Data bus, 5 ... Graphic data memory, 6 ... Graphic processor, 6A to 6D ... First to fourth processing means, 7 ... Image Data generation processor, 8 image data memory, 9 CRT.

Claims (1)

(57) [Claims] 1. A graphic data memory (5) for storing data from a host computer, a graphic processor (6) for analyzing data and issuing a command for generating vector data, and a vector data corresponding to the command. An image processing apparatus comprising: an image data generation processor (7) for generating pixel data as pixel data; and an image data memory (8) for storing pixel data. A first processing means (6A) for extending and clipping a specified area as one line segment having a marker adjacent to the start point on the second corner side as an end point, and a start point side extension amount and an end point side Second processing means (6B) for determining the positional relationship between the line and the designated area by comparing the extension amounts, and extending by the difference between the start-side extension amount and the end-point extension amount A third processing means (6C) for determining a direction; and a fourth processing means (6D) for determining whether or not a marker exists in the designated area by comparing the number of the first marker and the number of the last marker, A grid processing method characterized by extending the grid over the entire specified area.