JPH0157390B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to a graphic processing device, and more particularly to a graphic processing device having an arbitrary polygon area coloring function.

[Technology background]

Recently, as graphic processing including color information has become popular, many graphic processing devices are equipped with an area coloring function.

The conventional area coloring function, for example, when specifying a polygon ABCD to be area colored as shown in Figure 1,
By sequentially scanning in the row direction like l ₁ , l ₂ , l ₃ , ..., the sections sandwiched between two straight lines [a ₁ , b ₁ ], [a ₂ , b ₂ ], [a ₃ , c ₁ ]... are identified and colored one by one.

This method poses no problem when applied to convex polygons that do not include any concave portions, as shown in Figure 1, but when applied to concave polygons or composite polygons as shown in Figure 2 a, b, and c. In the case of rectangular shapes, the coloring logic is complicated, so the area coloring function cannot be applied directly.
The operator must first divide the polygon into multiple convex polygons and then use the area coloring function described above.
For this reason, in the case of area coloring processing of complex figures, a considerable amount of effort and time was required.

[Object and structure of the invention]

The object of the present invention is to automatically divide any complex polygon into convex polygons to which the area coloring function can be applied, that is, shapes such as triangles or trapezoids, and to which it is possible to perform area coloring. The purpose of this invention is to provide a processing device.

The functions of the present invention for this purpose include a means for setting the coordinates of the vertices and valley points on the figure to be colored, and a means for setting the coordinates of the vertices and valley points on the figure to be colored, and the means for setting the intersection point where a straight line parallel to the horizontal axis passing through these apex and valley points intersects the side of the figure. Find the coordinates, sort them in addition to the coordinates of the apex and valley points above, create a work point sequence aligned with one corner on the screen as the base point, and then move each point in the work point sequence upward or downward. means for counting the number of each extending line segment and creating a line segment table; means for sequentially cutting out triangles or trapezoids including sides parallel to the horizontal axis on the line segment table; It is characterized by having a means for sequentially coloring the surface.

[Embodiments of the invention]

First, the principle of the present invention will be explained.

First, set the coordinates of the vertices and valley points of the polygon to be painted. For example, in the star-shaped example shown in FIG. 3a, five diagonally shaded areas must be colored. Therefore, as shown in Figure 3b, a ₁ , a ₂ ,
Input a ₃ , a ₄ , and a ₅ , and then calculate the coordinates of valley points b ₁ , b ₂ , b ₃ , b ₄ , and b ₅ from the respective coordinates. Based on the y-coordinates of the apex and valley points, the polygon is sliced in the horizontal direction, that is, parallel to the x-axis, as shown in FIG. 3c. As a result of slicing, any polygon is always converted into a set of triangles and trapezoids (including squares). These triangles or trapezoids are sequentially cut out one by one and registered. In this way, by sequentially performing area coloring processing on the registered triangles or trapezoids using the area coloring function, the entire target area can be colored, as shown in Figure 3a.Next, the main area can be colored. The details of the invention will be explained based on examples.

FIG. 4 is a schematic diagram of one embodiment of the present invention.
In the figure, 1 is a graphic processing device, 2 is a display unit,
3 is an input operation section such as a keyboard, light pen, etc.; 4
5 is an input processing unit, 5 is a display data storage unit, 6 is an area coloring figure setting unit, 7 is an observation point coordinate table, 8 is a preprocessing unit, 9 is a line segment table, 10 is a figure division processing unit, and 11 is a divided figure Table 12 represents a surface coloring processing section. In this figure, in order to simplify the explanation, parts of the configuration of the graphic processing apparatus other than those specifically related to the area coloring process of the present invention are omitted.

The command or data input from the input operation section 3 is identified by the input processing section 4, a processing function corresponding to the content of the command is activated, and the data is stored in the display data storage section 5.
In the case of this embodiment, since the input command is an area coloring command, the input processing section 4 activates the area coloring figure setting section 6. Next, when the positions of the vertices of the polygon to be painted are set using, for example, a light pen, the coordinate data is stored in the display data storage section 5 and displayed on the display section 2. , is also notified to the area coloring figure setting section 6.

Area coloring figure setting section 6, observation point coordinate table 7,
Preprocessing section 8, line segment table 9, figure division processing section 1
0. The divided figure table 11 is a figure dividing functional part based on the present invention, and detailed functions are shown in FIGS. 5 and 6, which will be described later.

The result of subdividing the polygon of the area coloring target figure into figures to which the area coloring function can be applied, that is, convex figures such as triangles and trapezoids, is stored in the divided figure table 11.

The area coloring processing unit 12 uses conventional scanning lines to
It is sufficient to perform area coloring by determining the area coloring section for each book, and the divided figures are taken out one by one from the divided figure table 11, area coloring processing is performed, and area coloring data is stored in the display data storage section 5. . The display data including the area coloring data in the display data storage section 5 is always read out to the display section 2, so that the area colored polygonal figure is displayed on the screen.

Next, the figure dividing function will be explained with reference to FIGS. 5 and 6.

The surface curve setting unit 6 receives each vertex data of an arbitrary number of polygons 1 to m inputted from the input operation unit 3 [a ₁₁ to a ₁ , n ₁ ]..., [a _n1 , a _n,on ] Calculate all the valley point positions from , and in addition to the vertex data, sort the x and y coordinates of these vertices and valley points in descending order of the y coordinate, or in descending order of the x coordinate if the y coordinates are the same, and observe. Create a point coordinate table 7.

The observation point coordinate table 7 stores the vertices and valley points that serve as clues for dividing the polygonal figure to be painted.
They are arranged in a line starting from the upper left and moving toward the lower right, and the figure is analyzed, divided, and extracted at this sequential point. However, this arrangement is only for convenience, and arrangements based on other base points are also possible.

The coordinate array of observation points obtained in this way is
In the observation point coordinate table 7, (y ₁ , x ₁ , ₁ ), (y ₁ , x ₁ ,
₂ ), ..., (y _× , x ₂ , ₁ ), ..., (y _k , x _k , ₁ ), ...
..., (y _k , x _k , l).

The preprocessing unit 8 draws a straight line parallel to the x-axis from the y-coordinate of each observation point in the observation point coordinate table 7, obtains all the coordinates of intersections with the sides of the figure, adds them to the table 7, sorts them again, and calculates line segments. Create the work point items in Table 9. The work point items in Table 9 created in this way are the coordinates of each subdivided figure created when the figure is sliced parallel to the x-axis at the observation point, that is, the coordinates of the vertices of the divided figure, from the upper left to the right. They are aligned toward the bottom.

The preprocessing unit 8 further counts the number of line segments extending upward and downward from these work points, that is, the vertices of the divided figure, and registers them in the table 9. This is then used in the process of cutting out divided figures.

The figure division processing unit 10 traces the working points of the line segment table 9 from top to bottom and performs a process of cutting out each divided figure. In this process, as illustrated in FIGS. 7 to 7, the upper left corner of each divided figure is taken as a base point, and line segments (sides) connected thereto are searched counterclockwise.

Therefore, first find the first work point that has a line segment from top to bottom in table 9, and use this as the base point in the order of downward line segment → rightward line segment → upward line segment, and the innermost one. A counterclockwise route is searched, and the adopted line segments are sequentially deleted from the table 9, and the process of cutting out the next divided figure is repeatedly executed for the remaining line segments. The coordinates of each vertex of the cut out divided figure are sequentially stored in the divided figure table 11. FIG. 6 shows a generalized version of this procedure.

In this way, when all the line segments registered in the line segment table 9 are deleted, the division process ends.

FIG. 8 shows an example of a divided figure, and FIG. 9 shows the initial contents of the line segment table 9. For example, for vertex P ₁ , the upper line fraction is "0" and the underline fraction is "2", and the next intersections P ₂ and P ₃ both have an upper line fraction of "1" and an underline fraction of "1".
FIG. 10 shows changes in the contents of tables 9 and 11 in the divided figure cutting out process based on the contents of the line segment table shown in FIG. Below, Figures 6 and 8
The specific operation will be explained with reference to FIGS.

In the first loop of the process shown in FIG. 6, first, process 1 detects the point _P1 with the first underlined segment,
In addition to storing it in table 11, it is also stored in table 9.
Subtract 1 from the underlined fraction of P ₁ (becomes 0). Next, in process 2, find the first point _P2 that has an upper line segment at the point with the y coordinate directly below _P1 , and store this in table 11,
Subtract the overline fraction of _P2 in Table 9 by 1 (becomes 0). Next, in process 3, the point P ₃ having the same y coordinate as P ₂ and the first upward line segment is found, and this is stored in table 11, and it is also stored in table 9.
The overline fraction of P ₃ is reduced by 1 (becomes 0). Furthermore, in process 4, find the first point P ₁ that has an underline segment at the same y coordinate as P ₃ , store this in table 11, and subtract 1 from the number of underline segments of P ₁ in table 9 (0 become).

In the above first loop processing, P ₁ , P ₂ , P ₃ ,
This means that one divided figure consisting of P ₁ has been cut out. The divided figure cut out in the next second loop starts from the first point _P2 with the underline segment,
A similar procedure is repeated to cut out divided figures consisting of P _x , P ₅ , P ₆ , and P ₃ . Thereafter, as shown in FIG. 10, the loop process is repeated a third and fourth time until all the contents of the table 9 become 0, thereby cutting out all the divided figures.

〔Effect of the invention〕

As described above, according to the present invention, any polygon can be converted into a set of simple convex angles, and the area coloring processing efficiency can be greatly improved.

[Brief explanation of drawings]

Fig. 1 is an explanatory diagram of the conventional area coloring function, Fig. 2 a, b, and c are diagrams showing examples of concave polygons and compound polygons, and Fig. 3 a, b, and c are explanatory diagrams of the principle of the present invention. ,
FIG. 4 is a configuration diagram of an apparatus according to an embodiment of the present invention, FIGS. 5 and 6 are detailed functional diagrams, FIG. 7 is an explanatory diagram of cutting out divided figures, and FIG. 8 is an explanation of a specific example of area coloring figures. 9 is an explanatory diagram of a line segment table used therein, and FIG. 10 is an explanatory diagram of changes in the table contents in the divided figure cutting process. In the figure, 1 is a graphic processing device, 2 is a display section,
3 is an input operation section, 4 is an input processing section, 5 is a display data storage section, 6 is an area coloring figure setting section, 7 is an observation point coordinate table, 8 is a preprocessing section, 9 is a line segment table,
Reference numeral 10 indicates a figure division processing section, 11 indicates a divided figure table, and 12 indicates a surface coloring processing section.

Claims (1)

[Claims] 1. A means for setting the coordinates of the vertices and valley points on the figure to be colored, and determining the coordinates of the intersection point where a straight line parallel to the horizontal axis passing through these apex and valley points intersects the side of the figure. In addition to the coordinates of the points, sort them and create a work point sequence that is aligned with one corner on the screen as the base point, and then calculate the number of line segments extending upward and downward for each point in the work point sequence. A means for counting and creating a line segment table in which each counted number of line segments is associated with a work point, and a means for tracing a work point sequence from one direction on the line segment table in a predetermined procedure to include sides parallel to the horizontal axis. Means for sequentially cutting out triangles or trapezoids, and subtracting each line segment included in the cut out triangle or trapezoid from the number of upward or downward line segments belonging to the corresponding work point in the line segment table; A graphic processing device characterized by comprising means for sequentially coloring triangles or trapezoids.