JPH0821085B2 - Clipping circuit - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a clipping circuit of a graphic display device, and more particularly, to a coordinate sequence of vertices representing a polygon as an input, removing a portion existing outside the clipping region, and The present invention relates to a clipping circuit that outputs a coordinate series of vertices that form a new polygon consisting only of existing portions.

2. Description of the Related Art When an object is displayed on a graphic display device, a graphic may appear beyond the viewport. In this case, it is necessary to cut out the protruding portion of the object so that the displayed figure fits in the viewport. This process is called clipping, and a boundary for clipping is called a clipping boundary. Generally, when the display object is a two-dimensional object, the clipping boundary is composed of a plurality of two-dimensional straight lines, and the display object is a three-dimensional object. Sometimes the clipping boundary is composed of multiple 3D planes. On the other hand, the display object is often approximately expressed as a set of polygons regardless of whether it is a two-dimensional object or a three-dimensional object. Therefore,
The clipping process is considered to be a process of cutting out an unnecessary portion of each polygon forming the object with respect to a plurality of clipping boundary surfaces or boundary lines. (Hereinafter,
The clipping boundary surface and the clipping boundary line are collectively referred to as "clipping boundary"). A powerful solution to this clipping process is
Sutherland and GW Hodgman (IESu
"Reentrant Polygon Clipping" by Ther-land and GWHod geman, Communications of the ACM, Volume 17, Issue 1 ("Reentran
t Polygon Clipping, ″ CACM.Vol.17, No.1), pp32−4
2, 1974, the method shown. In this method, a polygon to be clipped is input as a sequence of vertices, clipping processing is performed on one boundary of straight lines or planes that form the clipping boundary, and when the processing for one boundary ends, the processing result As a new input, a clipping process for the next boundary is performed by using a polygon composed of a sequence of vertices output as. The feature of this method is that, in addition to performing the above-mentioned sequential processing for each clipping boundary, the polygon is considered as a series of vertices, and clipping processing is performed for a line segment connecting two adjacent vertices. That is. The positional relationship between a certain clipping boundary and two adjacent vertices forming a polygon is shown in FIG. 80 in (a) to (d) of FIG.
1 indicates a clipping boundary, 802 indicates the inside of the clipping boundary 801, and 803 indicates the outside of the clipping boundary 801. Note that the clipping boundary 801 itself is the inner 8
It shall be included in either 02 or outside 803. For the vertex P804 and the vertex Q805, it is assumed that the vertex P804 is input first and then the vertex Q805 is input. FIG. 8A shows a case where the two vertices P804 and Q805 are both inside 802. In this case, the line segment PQ806 is also inside 8
It is in 02. FIG. 8B shows a case where the two vertices P804 and Q805 are both on the outer side 803. In this case, the line segment PQ806 is also outside. FIG. 8C shows the vertex P80.
4 is on the inside 802 and Q805 is on the outside 803. In this case, assuming that the intersection of the line segment PQ806 and the clipping boundary 801 is R807, the line segment PR808 is inside. FIG. 8D shows a case where the vertex Q805 is on the inner side 802 and P804 is on the outer side 803. In this case, assuming that the intersection of the line segment PQ806 and the clipping boundary 801 is R807, the line segment RQ809 is inside. Therefore, a clipped polygonal vertex sequence for the input polygonal vertex sequence is generated by cutting out unnecessary portions in each case of FIG. FIG. 9 shows the vertices to be output according to each of the cases (a) to (d) of FIG. For all the vertices sequentially input, the positional relationship between two adjacent vertices and the clipping boundary is determined, and the coordinates of the input vertices and / or intersections are output according to FIG. The clipping process for one polygon is completed. A specific processing flow when the above method is applied to the polygon ABCD1001 shown in FIG. 10 will be described below. In FIG. 10, 1001 is the polygon ABCD to be clipped, 1002 is the clipping boundary, 1003 is the inside of the clipping boundary 1002, 1004
Indicates the outside of the clipping boundary 1002. The vertices of polygon 1001 are input in the order of A, B, C, D. First, the vertex A1005 is input. The vertex A1005 is located inside 1003. Next, the vertex B1006 is input. Vertex B1006
Since it is also inside 1003, the case of (a) in FIG. 8 or FIG. 9 described above is applied to the line segment AB1007, and the vertex B1
006 is output. Next, the vertex C1008 is input. Vertex C1
Since 008 is on the outer side 1004, the case of (C) in FIG. 8 or FIG. 9 described above is applied to the line segment BC1009.
The intersection E1010 between 1009 and the clipping boundary 1002 is output. Next, the vertex D1011 is input. Vertex D1011 is outside 1004
Therefore, the case of (b) in FIG. 8 or FIG. 9 described above is applied to the line segment CD1012, and the vertex is not output.
Finally, referring to the inside / outside judgment result of the vertex A1005 with respect to the clipping boundary 1002 held when the vertex A1005 is input again or the first time the vertex A1005 is input, it is found that the vertex A1005 is inside 1003. , Line segment DA101
The case of (d) in FIG. 8 or FIG. 9 is applied to 3 and the intersection F101 of the line segment DA1013 and the clipping boundary 1002 is applied.
4 is output first, and then vertex A1005 is output. As a result of the above, four vertices B, E, F, A are output as a row of vertexes of the polygon obtained by removing the portion outside the clipping boundary 1002 from the input polygon 1001. Note that FIG. 11 shows a list of the above processing flow. 11th
In the figure, the column of “Position relation” indicates the above-mentioned first relation with respect to the positional relation between the line segment formed by “the vertex input one before” and “the vertex input (now)” and the clipping boundary 1002. 8
It shows which of the four cases of FIG. 9 or FIG. 9 has been applied.

However, in the clipping circuit based on the clipping processing method described above, when a polygon including vertices existing on the clipping boundary is input, the vertices on the clipping boundary are There was a problem of duplicate output. A specific description will be given using the polygon ABCD1201 shown in FIG. In FIG. 12, 1202 indicates a clipping boundary, 1203 indicates the inside of the clipping boundary 1202, and 1204 indicates the outside of the clipping boundary 1202. The clipping boundary 1202 itself is included in the inside 1203. It is also assumed that vertices B1206 and D1210 are on the clipping boundary 1202. In addition, polygon 12
The vertices of 01 are input in the order of A, B, C, D. First, the vertex A1205 is input. The apex A1205 is inside 1203. Next, the vertex B1206 is input. The vertex B1206 is a vertex on the clipping boundary 1202. Therefore, from the above assumption, since the vertex B1206 is also inside 1203, the line segment AB1207
The case of (a) in FIG. 8 or FIG. 9 is applied to, and the vertex B1206 is output. Next, the vertex C1208 is input. Since vertex C1208 is on the outer side 1204, line segment BC1209
The case of (C) in FIG. 8 or FIG. 9 is applied to the output, and the intersection of the line segment BC1209 and the clipping boundary 1202 is output. This intersection is equal to the vertex B1206, and again the vertex B12.
06 will be output. Next, the vertex D1210 is input. The vertex D1210 is a vertex on the clipping boundary 1202. Therefore, since the apex D1210 is also inside 1203 from the above assumption, the line segment CD1211 is shown in FIG.
The case of (d) in the figure is applied, the intersection of the line segment CD1211 and the clipping boundary 1202 is first output, and then the vertex D121.
0 is output, but this intersection is equal to vertex D1210. Therefore, two vertices D1210 are output in succession. Finally, referring to the inside / outside determination result of the vertex A1205 with respect to the clipping boundary 1202 held when the vertex A1205 is input again or the vertex A1205 is input first, the vertex A1205
Is inside 1203, the line segment DA1212 has
The case of Figure or (a) of Figure 9 is applied, and vertex A1205
Is output. As a result, five vertices B, B, D, D, A are formed as a row of vertices of the polygon obtained by removing the portion 1204 outside the clipping boundary 1202 with respect to the input polygon 1201.
Is output. Therefore, the vertices on the clipping boundary 1202
B1206 and vertex D1210 are output twice each. FIG. 13 shows a list of the above processing flow. In the above example, the clipping boundary itself is included inside. Conversely, consider the case where the clipping boundary itself is included outside. In this case,
When the polygon 1201 shown in FIG. 12 is input, the process in the middle is omitted, but if each case of FIG. 8 or FIG. 9 is applied in the same manner, it is shown in FIG. Becomes,
As a result of clipping, the sequence of three vertices B, D, A is output without duplication, and it seems that the above problem does not exist. However, even if the clipping boundary itself is included outside, when a polygon that also includes vertices on the clipping boundary is input, the vertices on the clipping boundary are output in duplicate. Shown in.
In FIG. 15, 1501 is the polygon ABCD to be clipped, 1502 is the clipping boundary, 1503 is the inside of the clipping boundary 1502, and 1504 is the clipping boundary.
The outside is shown for 1502 and the vertex C1505 is on the clipping boundary 1502. In this case, polygon 1501
When inputting, the process in the middle is omitted, but if each case of FIG. 8 or FIG. 9 is similarly applied,
As shown in FIG. 16, as a result of clipping, the sequence of five vertices B, C, C, D, and A is output, and the vertex C1505 is output in duplicate. As described above, regardless of whether the clipping boundary itself is included inside or outside, when a polygon that includes vertices on the clipping boundary is input, the clipping circuit based on this conventional clipping method uses the clipping boundary. It was unavoidable that the top vertices above were output in duplicate. In general, since clipping processing is performed on a plurality of clipping boundaries, a row of polygon vertices processed and output for one clipping boundary is used as an input for the processing for the next clipping boundary. Therefore, the processing for the vertices that are duplicately output in the clipping processing on the way is completely useless. As described above, the conventional clipping circuit has a problem that the processing amount increases when a polygon including vertices on the clipping boundary is input. In view of the above point, the present invention provides a clipping circuit that does not output the same vertices redundantly even for a polygon including vertices on a clipping boundary and does not cause unnecessary increase in processing. With the goal.

Means for Solving the Problems In order to solve the above problems, the present invention holds a vertex register that holds the coordinates of the vertices of an input polygon, and a boundary surface or boundary line equation that represents a clipping region. The boundary register and the equation of the boundary surface or boundary line output by the boundary register and the coordinates of the input vertex are input, and the vertex having that coordinate is inside the boundary face or boundary line. An inside / outside determination circuit for determining whether it exists, outside, or on a boundary surface or a boundary line, and the inside / outside determination for the previous vertex in the vertex series held by the vertex register An inside / outside determination result register that holds the result determined by the circuit, a first inside / outside determination result output from the inside / outside determination circuit, and a first / outside determination result register stored in the inside / outside determination result register. A clipping determination circuit that receives the inside / outside determination result of 2 and determines the coordinates to be output as a result of clipping, and a line segment that has the coordinates of the input vertex and the coordinates held by the vertex register as two end points. An intersection calculation circuit that receives the equation of the boundary surface or the boundary line output from the boundary register and calculates the coordinates of the intersection of the line segment and the boundary surface or the boundary line according to the output of the clipping determination circuit. And a vertex output circuit that selects and outputs 0 to 2 coordinates from the coordinates of the input vertex and the coordinates of the intersection point output from the intersection point calculation circuit according to the output of the clipping determination circuit and outputs them in sequence. A clipping circuit characterized by being provided.

The present invention has the above-mentioned configuration, and determines whether the coordinates of the vertices of the input polygon and the clipping boundary are inside, outside, or on the boundary by the inside / outside judging circuit. This judgment result and the previous vertex that was previously input and held in the vertex register are obtained,
Using the inside / outside judgment result held in the inside / outside judgment result register, the clipping judgment circuit judges the positional relationship between the line segment connecting these two adjacent vertices and the clipping boundary, and calculates the intersection point if necessary. Coordinates of the intersection of the line segment and the clipping boundary calculated by the circuit,
Clipping processing is performed by outputting the coordinates of the input vertices via the vertex output circuit according to the respective positional relationships.

Embodiment FIG. 1 is a block diagram showing the configuration of an embodiment of the clipping circuit of the present invention. In FIG. 1, 101 is the coordinates of the vertices of polygons that are sequentially input, 102 is the vertex register, 103 is the boundary register, 104 is the clipping boundary equation output from the boundary register 103, and 105 is the inside / outside determination circuit. 106 is the inside / outside determination result output from the inside / outside determination circuit 105, 107 is the inside / outside determination result register that holds the inside / outside determination result 105, and 108 is the previous / one in the vertex sequence held in the inside / outside determination result register 107. The result of the inside / outside determination for the vertices is held by 109 for the clipping determination circuit, 110 for the control signal output from the clipping determination circuit 109, and 111 for the vertex register 102. The coordinates of the previous vertex in the vertex series, 112 is the intersection calculation circuit, and 113 is the intersection calculation circuit.
The coordinates of the intersection point output by 112, 114 the vertex output circuit, 11
Reference numeral 5 indicates the coordinates of the vertices output as a result of clipping processing. The operation of the clipping circuit of the present invention configured as above will be described below. First, the coordinates of the vertices forming the polygon are sequentially input one by one from an external circuit (not shown). The input coordinates of the vertex are stored in the vertex register 102, and are also supplied to the inside / outside determination circuit 105, the intersection calculation circuit 112, and the vertex output circuit 114. The boundary register 103 holds at least a plurality of clipping boundary equations including the clipping boundary currently being processed, outputs the clipping boundary equation 104 currently being processed, and outputs the inside / outside determination circuit 105 and It is supplied to the intersection calculation circuit 112. The inside / outside determination circuit 105 determines the positional relationship between the vertex and the clipping boundary from the input coordinate 101 of the vertex and the clipping boundary equation using a known technique in geometry. There are three positional relationships shown in FIGS. 2 (a) to (C). In FIG. 2, 201 is a clipping boundary and 202 is a clipping boundary.
The inside of 201, the outside 203 to the clipping boundary 201, and the input vertex 204 are shown. However, clipping boundary 201 is inside 202 and outside 203
It is not included in any of the above. 2A shows the case where the vertex 204 is inside 202 with respect to the clipping boundary 201, FIG. 2B shows the case where the vertex 204 is on the clipping boundary 201, and FIG. 2C shows the case where the vertex 204 has the clipping boundary 201. To the outer side 203, respectively. The inside / outside determination circuit 105 outputs a signal indicating which of the above three types as the determination result 106, and the inside / outside determination result register 1
The data is stored in 07 and supplied to the clipping determination circuit 109. The clipping determination circuit 109 receives the input vertex 1
Inside / outside judgment result 106 for 01 and inside / outside judgment result register 1
Holds on 07. Using the inside / outside determination result 108 for the previous vertex in the polygonal vertex sequence, the positional relationship between the clipping point and the line segment connecting the currently input vertex and the previous vertex is determined, and clipping is performed. Determine the coordinates of the vertices that should be output as a result of the processing, and then use the vertex output circuit.
The control signal 110 is supplied to 114. At this time, when it is determined that the intersection of the line segment and the clipping boundary should be output, the intersection 113 is also input to the intersection calculation circuit 112.
A control signal 110 that directs the calculation of 9 (a) to (i) of FIG.
Show all positional relationships in the street. In FIG. 3, 201
Reference numerals 203 to 203 are the same as those in FIG. 301 is the previous input vertex P, 302 is the currently input vertex Q
303 is the intersection R of the line segment PQ and the clipping boundary 201,
Shown respectively. FIG. 4 shows the inside / outside determination result 106 for the input vertex coordinates 101 and the previous one in the polygonal vertex sequence held in the inside / outside determination result register 107, corresponding to each case of FIG. The relationship between the inside / outside determination result 108 for the vertices and the vertices determined to be output by the clipping determination circuit 109 is shown. Since the relationship shown in FIG. 4 completely includes the relationship shown in FIG. 9 above, for vertices not on the clipping boundary,
It is guaranteed that it can be processed like a conventional clipping circuit. The intersection calculation circuit 112 calculates the coordinates 101 of the input vertex.
And the coordinates 111 of the previous vertex in the polygonal vertex series held in the vertex register 102 and the boundary register 103.
Held in. Using the clipping boundary equation 104 that is currently the target of processing, the clipping determination circuit 109 determines the coordinates of the intersection of the clipping boundary and the line segment connecting the currently input vertex and the immediately preceding vertex. It is calculated according to the control signal 110 indicating the result. Vertex output circuit 114
Is the coordinate 113 of the intersection calculated as required by the intersection calculation circuit 112 in response to the control signal 110 indicating the determination result of the clipping determination circuit 109 (that is, according to the relationship of FIG. 4),
From the currently input vertex coordinates 101, 0 or two vertex coordinates 115 are output in order. The tenth of the above
The polygons shown in each of FIGS. 12, 12, and 15 are listed in FIG. 5 and FIG. 5, respectively, showing the flow of processing when clipping processing is performed using the clipping circuit of the present invention. It is shown in FIG. 6 and FIG. 7. For the polygon in the example of FIG. 10 above, the sequence of four vertices B, E, F, A is
For the polygon in the example in the figure, the row of three vertices B, D, A
For the polygon in the example in Fig. 5, four vertices B, C, D, and A are output without overlapping vertices. In FIG. 1 used to show the configuration of the embodiment of the present invention, each component (circuit and register) is individually represented as independent hardware, but a normal CPU (central processing unit) is used.
It should be added that the function of each circuit may be realized by software by using, and the clipping circuit of the present invention can be configured even if each register is realized by an ordinary memory device or a register of a CPU.

EFFECTS OF THE INVENTION As described above, according to the present invention, even when a polygon including vertices on a clipping boundary is input, the same vertices are not output in duplicate. A clipping circuit can be realized, useless processing can be prevented from increasing, and processing speed can be improved.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a clipping circuit of the present invention, FIG. 2 is a positional relationship diagram of one vertex and a clipping boundary, and FIG. 3 is a line segment connecting two vertices and a clipping boundary. The positional relationship diagram, FIG. 4 is a correspondence diagram showing the positional relationship shown in FIG. 3 and the relationship of the vertices to be output, and FIG.
FIG. 6 is a diagram showing the flow of processing when the clipping circuit of the present invention is applied to the polygonal example shown in FIG. 10, and FIG. 6 is the clipping of the present invention with respect to the polygonal example shown in FIG. FIG. 7 is a diagram showing the flow of processing when processing is performed using a circuit, and FIG. 7 is a diagram showing the flow of processing when processing is performed using the clipping circuit of the present invention for the polygonal example shown in FIG. FIG. 8 is a positional relationship diagram of a line segment and a clipping boundary used in a conventional clipping circuit, and FIG.
Correspondence diagram showing the relationship between the positional relationship shown in the figure and the vertices to be output, FIG. 10 is a plan view showing an example of a polygon to be clipped, and FIG. 11 is an example of the polygon shown in FIG. Fig. 12 is a plan view showing an example of a polygon to be clipped, and Fig. 13 is an example of the polygon shown in Fig. 12. On the other hand, assuming that the clipping boundary itself is included inside, a diagram showing the flow of processing when processing is performed using a conventional clipping circuit, FIG. 14 shows the polygon example shown in FIG. On the other hand, assuming that the clipping boundary itself is included outside, it is a diagram showing the flow of processing when processing is performed using a conventional clipping circuit, and FIG. 15 shows an example of a polygon to be clipped. Fig. 16 is a plan view and Fig. 16 is an example of the polygon shown in Fig. 15. On the other hand, it is a figure which shows the flow of a process when it processes using the conventional clipping circuit. 101 ... coordinates of the input vertex, 102 ... vertex register,
103 …… Boundary register, 105 …… Inside / outside judgment result, 107 ……
Inside / outside determination result register, 109 ... clipping determination circuit, 112 ... intersection calculation circuit, 114 ... vertex output circuit.

Claims (1)

[Claims] 1. A vertex register that holds the coordinates of the vertices of an input polygon, a boundary register that holds the boundary surface or boundary line equation that represents a clipping region, and a boundary surface or boundary that the boundary register outputs. The line equation and the coordinates of the input vertex are input, and the vertex having the coordinates is inside or outside the boundary surface or the boundary line, or on the boundary surface or the boundary line. And an internal / external determination result register for holding the result determined by the internal / external determination circuit for the previous vertex in the vertex sequence held by the vertex register, and The first inside / outside judgment result output from the inside / outside judgment circuit and the second inside / outside judgment result held in the inside / outside judgment result register are input and output as a clipping result. A clipping determination circuit that determines the coordinates to be processed, a line segment having the coordinates of the input vertex and the coordinates held by the vertex register as two end points, and a boundary surface or a boundary line output by the boundary register. An intersection calculation circuit that calculates the coordinates of the intersection of the line segment and the boundary surface or the boundary line according to the output of the clipping determination circuit using an equation as an input, and the coordinates of the input vertex and the intersection A clipping circuit, comprising: a vertex output circuit that selects 0 or 2 coordinates from the coordinates of the intersections output by the calculation circuit according to the output of the clipping determination circuit, and outputs them in sequence.