JP3146031B2 - Segment data management method and clipping processing method using this management method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a segment data management method applied to image processing and a clipping processing method using the management method.

[0002]

2. Description of the Related Art A segment data management method and a clipping processing method disclosed in JP-A-1-304588 are as follows.

The vertices of a figure as shown in FIG. 8 are sequentially read in a counterclockwise direction, and when the entry vertices (P0, P4) and the exit vertices (P2, P5) are found, each pair of the entry vertices and the exit vertices is determined. The segment data management memory 1 shown in FIG. 9 is created. The segment data management memory 1 stores data for managing each area of the clip segment memory 2. The data stored in the segment data management memory 1 is an entry vertex pointer, an entry vertex Y coordinate, the number of words in a clip area, and a segment memory pointer, which are created for each area.

[0004] A root pointer is provided which points to the approaching vertex pointer of the first area. The entry vertex pointer is a pointer that connects the entry vertices in ascending order of the Y coordinate value. The entry vertex Y coordinate value is used to calculate the coordinate value of the segment. The number of words in the clip area is used to determine the size of the clip segment memory 2. Segment memory pointer is used to determine the first address of each area of the clip segment memory 2. The entry vertex indicates a vertex that has entered when the scan line is sequentially incremented, and the exit vertex indicates a vertex that deviates when the scan line is incremented.

The creation of the segment management memory 1 is performed according to the following procedure. First, it is determined that the vertex P0 is the approach vertex, and the Y coordinate is registered as the approach vertex Y coordinate.
Next, the exit vertex is determined sequentially from the vertex P1. Then, it is determined that the vertex P2 is the exit vertex. Exit vertex P2
Is registered as the number of words in the clip area. Clip segment memory 2
Is registered as a segment memory pointer,
The sum of the number of words in the clip area and the number of words in the clip area is used as the segment memory pointer of the area of the pair of the next entry vertex and the exit vertex.

In the same manner, a set of an ingress vertex and an exit vertex is similarly created and registered in the segment data management memory 1. Finally, the Y-coordinate values of the approaching vertices are sorted in ascending order, and connected by the approaching vertex pointer.

To create the clip segment memory 2, first, the scan line Ys is set to the minimum Y coordinate value of the clip area. A start point X coordinate value and an end point X coordinate value which are clip segments on the scan line are generated. Then, based on the fact that the scan line Ys is not smaller than the Y coordinate value of the entry vertex in a certain area of the segment data management memory 1 and the Y coordinate value of the exit vertex in that area (Y coordinate value of the entry vertex + the number of words in the clip area). Scan line Ys
Is not large. If any negative result is obtained, another area is searched for an area satisfying the above condition. That is, an area for storing the clip segment is found.

When a storage area is found, the storage address is obtained by calculating storage address = scan line Ys−entry vertex Y coordinate value + segment memory pointer, and the segment data start point X coordinate value and end point X coordinate value are stored. These operations are performed on the scan line that crosses the clip area by incrementing the scan line Ys.

The clip segment access and clipping processing from the segment memory will now be described. The root pointer is extracted from the segment management memory 1, and the Y coordinate value of the entry vertex and the number of words in the clip area are extracted from the area pointed to by the root pointer. The stored area is found while making the determination in the same manner as when the segment memory was created, the read address is obtained by the same expression as the expression for obtaining the storage address, and the start point X coordinate value and end point X coordinate value of the clip segment are read. . Then, a common part of the drawing segment and the clip segment is extracted and mapped.

[0010]

However, in such a conventional segment data management method and the conventional clipping processing method, the management mechanism of the clip segment memory 2 is complicated, and particularly when there are a plurality of closed clip paths, a plurality of clip segments are required. The segment data management memory 1 has to be created, and there is a problem that it is further complicated.

Also, since the segment data management memory 1 and the clip segment memory 2 are created separately, there is a problem that the reading of the vertices of the figure is duplicated and the speed is reduced. In addition, an address calculation is required when registering and reading data into and from the clip segment memory 2, and there is also a problem that the speed is reduced in this regard.

It is an object of the present invention to provide a segment data management method capable of performing high-speed processing with a simple management configuration and improving practicality, and a clipping processing method using this management method.

[0013]

According to a first aspect of the present invention, a figure formed by a clip path is trapezoidally divided by scan lines passing through vertices and intersections, and scan lines of interest are sequentially incremented for each scan line. The clip segment of the same scan line in the valid clip area is extracted, the coordinates of the start point and the end point of the clip segment are sequentially registered in the clip segment memory, and the start address of the registered clip segment memory is focused on the clip of the scan line. To register in the bucket.

According to a second aspect of the present invention, a figure consisting of a clip path is divided into trapezoids in advance by scan lines passing through vertices and intersections, and the scan lines of interest are sequentially incremented so that the same scan in a valid clip area for each scan line is performed. The clip segment of the line is taken out, the coordinates of the start point and the end point of the clip segment are sequentially registered in the clip segment memory, and the start address of the registered clip segment memory is registered in the clip bucket of the scan line of interest. In this state, the figure composed of the drawing path is divided into trapezoids by scan lines passing through the vertices and intersections, and the scan lines of interest are sequentially incremented to extract the drawing segments of the scan lines in the effective drawing area for each scan line. Scanler Address from the clip bucket of the clip segment to the clip segment memory, the coordinates of the start point and end point of the clip segment are extracted from the clip segment memory based on the address, and the drawing segment section is clipped and mapped in the clip segment section. .

[0015]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram, and 11 is a clip processing unit. The clip processing unit 11 is provided with a drawing path and a clip path. The clip processing unit 11 clips the drawing path by the clip path, expands the drawing path into pixels, and supplies the clipped drawing path to the drawing memory 12. It is designed to be stored. The drawing memory 1
The drawing paths stored in the storage device 2 are sequentially read in a raster form and provided to the printer device 13 for printing or provided to the CRT display 14 for display.

The clip processing unit 11 includes a control unit 15,
Clip segment memory 16, clip bucket 1
7, a segment pixel conversion unit 18 and an input unit 19, which are connected via a bus line 20.

The control unit 15 of the clip processing unit 11 includes a microprocessor, and performs the processing shown in FIG. This processing will be described for the case where the graphic shown by the solid line in FIG. 6 is the clip path and the graphic shown by the dotted line is the drawing path.

First, in step S1, a graphic consisting of a clip path is drawn on a horizontal line (scan line) passing through vertices and intersections.
Divide by trapezoid. That is, the coordinates of the clip sides C0 to C4 are sequentially read to create the side data 21 as shown in FIG. The side data 21 includes the coordinates of the start point and end point of the side, and Y
The inclination of x with respect to the step 1 of the coordinate and the pointer to the next side data 21 are stored. Y, the smaller of the start point and end point of the side
The addresses of the side data 21 are stored in buckets 22 corresponding to the coordinates, and sequentially linked to create a side data list. Next, the clip sides are trapezoidally divided by straight lines parallel to the x-axis passing through the vertices CP01 and CP34. Then, the sides C0 and C1 located between these two parallel lines are registered in the active side table 23.

Next, in step S2, the start address of the clip segment memory 16 is set in the segment memory pointer smp. The processing in step S2 will be described in detail with reference to FIG.

That is, in step S21, the segment memory pointer s is set to Y2 of the clip bucket 17 shown in FIG.
Set the contents of mp. In step S22, a set of valid clip edges C0 from the edges in the active edge table 23
, C1 are taken out, and the section is set as a clip segment. In step S23, the x-coordinate X1s of the side C0 and the x-coordinate X1e of the side C1 on the scan line Y2 are stored in the segment memory pointer smp.
Register in order from.

Next, in step S24, the segment memory pointer smp is advanced by two. In step S25, it is determined whether or not all the edges of the active edge table 23 have been searched. However, since all of the edges have been searched, NULL is set in the segment memory pointer smp in step S26, and 1
Go forward.

Next, in step S27, it is determined whether or not all the scan lines included in the trapezoid have been completed. Since the trapezoid of interest further includes a scan line, the scan line Y is incremented in step S28. Let Y3 be the side C0, C1 in the active side table 23.
Are updated to X2s and X2e, respectively.

Then, the process returns to step S21, and the content of the segment memory pointer smp is set in Y3 of the clip bucket 17, and in step S22, the x coordinate X2
s and X2e are clip segments, and in step S23, the x-coordinate X2s and the side C of the side C0 on the scan line Y3.
The x coordinate X2e of 1 is registered in the clip segment memory 16 in order from the segment memory pointer smp. Then, steps S24, S25, S26, and S27 are sequentially performed in the same manner as described above. The same processing is performed for the scan line Y4, and the process ends. Next, in step S3, a valid segment of the clip area is obtained and registered in the clip segment memory 16.

Next, in step S4, it is determined whether or not all the graphics on the clip path have been trapezoidally divided, and the processing of steps S1 to S3 is repeated until all of the clip paths have been trapezoidally divided. When all clip paths are divided into trapezoids, step S5
The trapezoidal division of the figure composed of the drawing path is performed by a horizontal line passing through the vertices and intersections. That is, in step S5, the drawing side l0
, L1, l2 are read, edge data, buckets, and edge data lists are created in the same manner as in step S1, and edges passing through the scan line of interest are entered into the active edge table.
The trapezoid is divided by a horizontal line passing through the vertices LP20 and LP01.

In step S6, a segment of a drawing path corresponding to the left side and the right side of the trapezoid sandwiched between the two horizontal lines is created, and the clipping segment is extracted from the clipping data and mapped. The processing in step S6 will be described in detail with reference to FIG.

That is, in step S61, a side is taken out from the active side table 23, and the left side is l2 and the right side is l0. X1s 'and X1e' are obtained by obtaining the x-coordinates of the scan line Y3, respectively, and are used as drawing segments on the scan line Y3. Then, in step S62, the drawing segment is clipped with the clip segment on the scan line Y3 and mapped.

In step S63, it is determined whether all the scan lines included in the trapezoid have been completed. If not, the scan line Y is incremented in step S64. Then, the process returns to step S61.

The processing in step S62 will be described in more detail with reference to FIG. That is, step S6201
Extract the start and end points of the clip segment with. Specifically, since the scan line of interest is Y3, the address to the clip segment memory 16 is fetched from the clip bucket 17 of Y3. Then, a set X2s, X2e of the x-coordinate of the clip segment stored in the clip segment memory 16 is extracted from the address.

Subsequently, in step S6202, it is determined whether or not the end point of the drawing segment is smaller than the start point of the clip segment. In this case, since the x coordinate X1e 'of the end point of the drawing segment is smaller than the x coordinate X2s of the starting point of the clip segment, the drawing segment is not mapped. Then, since there is still a scan line crossing the trapezoid, the scan line Y is incremented to Y4, and the processing of steps S61 to S64 in FIG. 4 is repeated. As a result, since the x-coordinates X1e 'and X2e' of the end point of the drawing segment are smaller than the x-coordinates X2s and X3s of the starting point of the clip segment from the scan lines Y3 to Y4, the drawing segment is not mapped.

In the scan line Y5, a set X3s', X3 of the x-coordinate of the start point and the end point of the drawing segment in step S61.
Obtain e '. In step S6201, the segment memory pointer smp is fetched from the clip bucket 17 on the scan line Y5, and the coordinate set X4s, X4e of the clip segment is obtained from the clip segment memory 16. Since the x coordinate X3s' of the start point of the drawing segment is larger than the x coordinate X4e of the end point of the clip segment taken out,
The process proceeds to steps S6202, S6203, and S6211, and the segment memory pointer smp is advanced by two. Since the contents of the clip segment memory 16 are not NULL, step S62
Return to 01. Then, the coordinate sets X5s and X5e of the clip segments are obtained from the clip segment memory 16. Since the x coordinate X3e 'of the end point of the drawing segment is smaller than the x coordinate of the starting point of the clip segment, the drawing segment is not mapped.

Since there is still a scan line crossing the trapezoid, the scan line Y is incremented to Y6, and in step S61, the coordinates X4s 'and X4e' of the left side l2 and right side l1 of the scan line Y6 are used as drawing segments. Then, in step S6201, the scan line Y6
The coordinates X6s and X6e of the clip segment in are extracted. Since the x-coordinate X4s 'of the start point of the drawing segment is smaller than the x-coordinate X6e of the end point of the clip segment, the process proceeds to steps S6202, S6203, S6204, S6208, S6210, and in step S6210, the start point X4s' of the drawing segment and the clip segment Map between the end point X6e. Then, in step S6211, the segment memory pointer smp
Advance two.

Since it is not NULL, the process returns to step S6201 and the x-coordinates X7s, X7 of the start point and end point of the clip segment
Take out 7e. Since the end point X4e 'of the drawing segment is smaller than the end point X7e of the clip segment, step S6202,
The process proceeds to steps S6203, S6205, and S6206. In step S6206, the start point X7s of the clip segment and the end point X of the drawing segment
4e 'is mapped. And scan line Y
The processing in 6 ends.

Thereafter, the processing of steps S61 to S64 is repeated up to the scan line Y9, and the processing is terminated. Since there is no other trapezoid consisting of the drawing paths sandwiched by the horizontal lines LP20 and LP01, it is determined in step S7 in FIG. 2 whether all the trapezoids sandwiched by the two horizontal lines have been mapped. In this case, all the trapezoids have been mapped. Therefore, the process proceeds to step S8. Then, in step S8, it is determined whether or not all of the graphics on the drawing path have been trapezoid-divided. In this case, there remains graphics that have not been trapezoid-divided, so that in step S5, the horizontal line passing through vertex LP01 and the vertex LP12 are passed through. The trapezoid is divided by the horizontal line, and the processing of steps S6 and S7 is performed in the same manner as described above, and all the mapping processing ends.

Using such a data management method makes it unnecessary to manage a complicated clip segment memory as in the related art. In addition, since the basic algorithm for creating segments of a clip graphic and a drawing graphic is the same, management is simplified.

Further, the judgment and calculation for each scan line for storing and reading the clip segment in the clip segment memory are unnecessary, and the clip segment can be accessed only by accessing the clip segment memory. It becomes possible.

[0037]

As described above, according to the present invention, it is possible to provide a segment data management method capable of performing high-speed processing with a simple management configuration and improving practicality, and a clipping processing method using this management method. It is.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention.

FIG. 2 is a flowchart showing main part processing of the embodiment.

FIG. 3 is a flowchart showing in detail a process of step S2 in FIG. 2;

FIG. 4 is a flowchart showing details of the process in step S6 in FIG. 2;

FIG. 5 is a flowchart showing the processing of step 62 in FIG. 4 in further detail;

FIG. 6 is an exemplary view for explaining segment data management and clipping processing in the embodiment.

FIG. 7 is a view for explaining a bucket, side data, a side data list, and an active side table used in the embodiment.

FIG. 8 is a diagram for explaining a conventional example.

FIG. 9 is a view for explaining segment data management in the conventional example.

[Explanation of symbols]

11: clip processing unit, 15: control unit, 16: clip segment memory, 17: clip bucket.

Claims (2)

(57) [Claims] 1. A graphic consisting of a clip path is trapezoidally divided by scan lines passing through vertices and intersections, and a scan line of interest is sequentially incremented to extract a clip segment of the same scan line in a valid clip area for each scan line. A segment data management method characterized by sequentially registering coordinates of a start point and an end point of the clip segment in a clip segment memory, and registering a start address of the registered clip segment memory in a clip bucket of a scan line of interest. 2. A graphic consisting of a clip path is divided into trapezoids by scan lines passing through vertices and intersections in advance, and a scan line of interest is sequentially incremented to extract a clip segment of the same scan line in a valid clip area for each scan line. The coordinates of the start point and the end point of the clip segment are sequentially registered in the clip segment memory, and the start address of the registered clip segment memory is registered in the clip bucket of the scan line of interest. Is divided into trapezoids by scan lines passing through vertices and intersections, the scan lines of interest are sequentially incremented to extract the drawing segments of the scan lines in the effective drawing area for each scan line, and the clip of the scan line of interest is extracted. Bake An address to the clip segment memory is obtained from the clip segment, coordinates of a start point and an end point of the clip segment are obtained from the clip segment memory based on the address, and a drawing segment section is clipped and mapped in the clip segment section. Clipping processing method.