JPH036785A - Clipping circuit - Google Patents

Abstract

PURPOSE:To suppress the increment of useless processing without overlappedly outputting the same vertex in polygons including the vertex existing on a clipping boundary by providing the clipping circuit with a clipping deciding circuit for deciding coordinates to be outputted as a clipped result. CONSTITUTION:An inside/outside deciding circuit 105 decides the positional relation of the coordinates of a vertex of an inputted polygon to the clipping boundary, whether the coordinates are included in the inside or outside or on the boundary. The clipping deciding circuit 109 decides the positional relation of a segment connecting adjacent vertexes with the clipping boundary by using the decided result and an inside/outside deciding result obtained for just preceding vertex precedently inputted and stored in a vertex register 107 and stored in an inside/outside deciding result register 107. If necessary, the coordinates of an intersecting point between a segment calculated by an intersecting point calculating circuit 112 and the clipping boundary and the coordinates of the inputted vertex are outputted through a vertex output circuit 114 in accordance with the positional relation of respective coordinates. Even when another polygon including the same vertex existing in the clipping boundary is inputted, the same vertex is not over-lappedly outputted.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to a clipping circuit for a graphic display device, and particularly to a clipping circuit that receives as input a coordinate series of vertices representing a polygon and removes portions existing outside the clipping area.
The clipping circuit that outputs the coordinate series of the vertices constituting a new polygon consisting only of internal parts is also conventional technology. A new vine. In this case, it is necessary to cut out the protruding part of the object so that the displayed figure fits within the view boat. This process is called clipping, and the boundary for cutting is called the clipping boundary. General 11: l-, the displayed object is 2 When the display object is a dimensional object, the clipping boundary is composed of a plurality of two-dimensional straight lines, and when the display object is a three-dimensional object, the clipping boundary is composed of a plurality of three-dimensional planes.

Whether a displayed object is a two-dimensional object or a three-dimensional object, it is often expressed approximately as a set of polygons (
~ Therefore, clipping processing can be considered to be a process of cutting out unnecessary parts of each polygon that makes up an object with respect to multiple clipping boundary surfaces or boundary lines (hereinafter, clipping boundary surfaces and clipping boundary lines will be referred to as clipping boundary surfaces and clipping boundary lines). (collectively referred to as the "clipping boundary"). As a promising solution to this clipping process, I.E. Sutherland and G.W.
``Reentrant Borigon Clipping'' by W.
trant Polygon CC11p-pin,
'CACM, Vol, 17. No, 1), p
The method shown in p.32-42.1974=L can be cited. In this method, the polygon to be clipped is manually set as a row of vertices, and the clipping process is performed on one boundary of a straight line or plane that constitutes the clipping boundary. Row (X) When the processing for one boundary is completed, the polygon composed of the row of vertices output as the processing result is used as a new human power to perform clipping processing for the next boundary.The characteristics of this method are In addition to sequentially processing each clipping boundary as described above, it is also possible to consider a polygon as a series of vertices and perform clipping processing on line segments connecting two adjacent vertices.
FIG. 8 shows the positional relationship between one clipping boundary and two adjacent vertices forming a polygon. Figure 8 (a
) to (d), 801 indicates the clipping boundary, 80
2 indicates the inside of the clipping boundary 801, and 803 indicates the outside of the clipping boundary 801. If the clipping boundary 801 itself ('!S is included in either the inside 802 or the outside 803)
Vertex P804 and Vertex Q805C & Vertex P804 first
Assume that the input is input and the vertex Q805 is input next.(a) It has two vertices P804 and Q805 in Fig. 8.
In this case, the line segment PQ806 is also located inside 802.
b) (Yo) Even if the two vertices P804 and Q805 are both on the outside 803, in this case, the line segment PQ8
06 is also on the outside (C) in Figure 8 (table vertex P8
04 is on the inside 802 and Q805 is on the outside 803. In this case, if the intersection of line segment PQ806 and clipping boundary 801 is R807, line segment PR8
08 is inside Am Figure 8 (d) It Vertex Q80
5 is on the inside 802 and R804 is on the outside 803. In this case, if the intersection of line segment PQ806 and clipping boundary 801 is R807, line segment RQ809
is on the inside. Therefore, by cutting out unnecessary parts according to each case in Figure 8, a series of clipped polygon vertices can be generated for the series of input polygon vertices. The vertices to be output are shown in each case of (a) to (d) in FIG. For all vertices input in sequence, the positional relationship between two adjacent vertices and the clipping boundary is determined, and the coordinates of the input vertex and/or intersection point are output according to Fig. 9. Polygon clipping process is completed a Polygon A shown in Figure 10
A specific process flow when the above method is applied to the B CD 1001 will be described below. In Fig. 10, 1001 is the polygon AB to be clipped.
1002 indicates the clipping boundary, 1003 indicates the inside of the clipping boundary 1002, and 1004 indicates the outside of the clipping boundary 1002. It is assumed that the vertices of the polygon 1001 are input in the order of A, B, C, and D. First, the vertex A 1005 is input.

Vertex A 1005 is inside 1003 Next vertex B
1006 is input, vertex B 1006 is also inside 10
03 The case of (a) in Figure 8 or Figure 9 above is applied to the line segment A B 1007, and the vertex B
Even if 1006 is output and then vertex C1008 is manually input, vertex C1008 is on the outside 1004.
Line segment B C1009 has (
Case C) is applied, and the intersection point E 1010 between the line segment BC 1009 and the clipping boundary 1002 is output, and the vertex D 1011 is input next. The case of (b) in Fig. 8 or Fig. 9 is applied, and the vertex is not output (-Last Referring to the inside/outside determination result of vertex A 1005 with respect to clipping boundary 1002, vertex A 1005 is located inside 1003.
The case of (d) in Figure 8 or Figure 9 above is applied to 1013, and the intersection point F 1014 between the line segment D A 1013 and the clipping boundary 1002 is output first, and then the vertex A 1005 is output. Four vertices B, E, F, and A are output as a sequence of vertices of a polygon obtained by removing the portion outside 1004 of the clipping boundary 1002 from the input polygon 1001. Figure 11 shows a list of the flow of the above processing. 1st
In Figure 1, in the "Positional Relationship" column (Dai), the above-mentioned Even if it is shown which of the four cases shown in FIG. 8 or FIG. When inputting a polygon that includes vertices that exist, there is a problem that duplicate vertices on the clipping boundary are output.
In FIG. 12, 1202 indicates the clipping boundary, 1203 indicates the inside of the clipping boundary 1202, and 1204 indicates the outside of the clipping boundary 1202. However, the clipping boundary 1202 itself is inside 1203. It is assumed that the vertices B1206 and D 1210 are on the clipping boundary 1202. The vertices of polygon 1201 are input in the order of A, B, and C1D. Even if input
Vertex A 1205 is inside 1203 Next vertex B
Even if 1206 is input, vertex B 1206 is a vertex on the clipping boundary 1202. Therefore, from the previous assumption, it can be concluded that vertex B 1206 is also inside 1203.
The case of (a) in FIG. 8 or FIG. 9 is applied to the line segment A B 1207, and the vertex B 1206 is output. Next, if vertex C1208 is input, vertex C1208
The case of (C) in FIG. 8 or FIG. 9 above is applied to line segment B C1209.The intersection of line segment B C1209 and clipping boundary 1202 is the output force ( This intersection is equal to vertex B 1206, and vertex B 1206 will be output again. Even if vertex D 1210 is input next, vertex D 1210 is a vertex on clipping boundary 1202. Therefore, from the previous assumption, vertex D 1210 The provisional line segment CD 1211 is also located inside 1203.
Case (d) in the figure is applied, and the intersection of the line segment CD I211 and the clipping boundary 1202 is first output, and then the vertex D1210 is output.This intersection is equal to the vertex D1210~ Therefore, the vertex D1210 is 2
The force that causes vertex A 1205 to be input again is output one after another. Or, referring to the inside/outside determination result of vertex A 1205 with respect to the clipping boundary 1202 that was maintained when vertex A 1205 was first input,
The apex A 1205 is on the inside 1203. The tentative line segment D A 1212 has the shape (a
) is applied, and the vertex Al2O5 is output.The above result is a sequence of vertices of a polygon obtained by removing the part outside I204 of the clipping boundary 1202 from the input polygon 1201, and the five vertices B and B are ,D,D
, A are output. Therefore, the clipping boundary 1202
The above vertex B 1206 and vertex DI 210 are each output twice. Figure 13 shows a list of the above processing flow. Conversely, consider the case where the clipping boundary itself is included on the outside (the polygon 12 shown in Figure 12 above).
When inputting 01, the sumo wrestler omit the intermediate progress. Similarly, applying each of the cases in Figure 8 or Figure 9 above, it becomes as shown in Figure 14, and the result of clipping is 3. It seems as if the above-mentioned problem does not exist because the rows of vertices B, D, and A are output without duplication. However, if the clipping boundary itself is included on the outside, then when a polygon that includes vertices on the clipping boundary is manually generated (M), an example in which vertices on the clipping boundary are output duplicated is shown in Figure 15. In Fig. 15, 1501 indicates the polygon ABCD to be clipped, 1502 indicates the clipping boundary, and 1503
is inside the clipping boundary 1502, 1504
indicates the outside of the clipping boundary l502, and it is assumed that the vertex C1505 is on the clipping boundary 1502. By applying each case in Figure 9, the result will be as shown in Figure 16, and as a result of clipping, a string of five vertices B, C, C, D, and A will be output, with vertex C1505 being duplicated. The output is as shown above. When inputting a polygon that includes vertices on the clipping boundary, assuming that the clipping boundary itself is included either inside or outside, the clipping circuit based on this conventional clipping method calculates the clipping boundary. It is unavoidable that the vertices above are duplicated.
Clipping processing is performed on multiple clipping boundaries. The sequence of polygon vertices processed and output for one clipping boundary can be used as input for processing on the next clipping boundary. Therefore, intermediate clipping Processing for the vertices that were output redundantly in the processing of ζζ
In conventional clipping circuits, there is a problem in that the amount of processing increases when a polygon that includes vertices on the clipping boundary is input. L for polygon
An object of the present invention is to provide a ripping circuit that does not output the same vertex redundantly and does not increase unnecessary processing. A vertex register that holds the coordinates of the vertices of the human-entered polygon, a boundary register that holds the equation of the boundary surface or boundary line representing the clipping area, and the equation of the boundary surface or boundary line output by the boundary register. Input the coordinates of the input vertex and determine whether the vertex with the coordinates exists inside or outside the boundary surface or boundary line, or exists on the boundary surface or boundary line. an inside/outside determination circuit for determining the inside/outside determination circuit; an inside/outside determination result register for retaining the result determined by the inside/outside determination circuit for the previous vertex in the vertex series held by the vertex register; and the inside/outside determination circuit. a clipping judgment circuit which receives as input the first inside/outside judgment result outputted by the above-mentioned inside/outside judgment result and the second inside/outside judgment result held in the above-mentioned inside/outside judgment result register and judges the coordinates to be output as a result of clipping; A line segment whose two end points are the coordinates of the vertex and the coordinates held in the vertex register, and the equation of the boundary surface or boundary line output from the boundary register are input, and the line segment and the boundary surface or boundary line are input. an intersection calculation circuit that calculates the coordinates of the intersection according to the output of the clipping determination circuit; and 0 to 2 coordinates from the coordinates of the input vertex and the coordinates of the intersection output from the intersection calculation circuit. The present invention is a clipping circuit characterized by comprising a vertex output circuit that selects, orders, and outputs outputs according to the output of the clipping determination circuit.

According to the above-described configuration, the present invention determines whether the coordinates of the vertices of the input polygon and the positional relationship with the clipping boundary are inside, outside, or on the boundary using an inside/outside determination circuit. Using the judgment result and the inside/outside judgment result obtained for the previous vertex input earlier and held in the vertex register and held in the inside/outside judgment result register, the clipping judgment circuit calculates the difference between these two adjacent vertices. Determine the positional relationship between the line segment connecting the vertices and the clipping boundary, and if necessary, calculate the coordinates of the intersection between the line segment and the clipping boundary calculated by the intersection calculation circuit and the coordinates of the input vertex, Clipping processing is performed by outputting 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. 103 is the boundary register, 104 is the clipping boundary equation output from the boundary register 103, and 1
05 is the inside/outside judgment circuit, 106 is the inside/outside judgment result outputted from the inside/outside judgment circuit 105, and 107 is the inside/outside judgment result 105.
108 is the inside/outside determination result register for the previous vertex in the vertex series held in the inside/outside determination result register 107; 109 is the clipping determination circuit; 110 is the clipping determination circuit 10;
9 outputs a control signal, 111 outputs a control signal from the vertex register 102
112 is the coordinate of the previous vertex in the vertex series, 112 is the intersection calculation circuit, 113 is the coordinate of the intersection output by the intersection calculation circuit 112, 114 is the vertex output circuit, and 115 is the clipping process. The operation of the clipping circuit of the present invention configured as above will be described below. first,
Even if the coordinates of the vertices constituting the polygon are input one by one from an external circuit (not shown), the input coordinates of the vertices are stored in the vertex register 102 and the inside/outside determination circuit 105. Intersection calculation circuit 112 and vertex output circuit 114
The boundary register 103 holds equations of a plurality of clipping boundaries including at least the clipping boundary currently being processed, and outputs the equation 104 of the clipping boundary currently being processed. The inside/outside determination circuit 105 supplies the coordinates 10 of the input vertex to the determination circuit 105 and the intersection calculation circuit 112.
1 and the equation of the clipping boundary using a well-known technique in geometry to determine the positional relationship between the vertex and the clipping boundary.
) In Fig. 2, 201 indicates the clipping boundary, 202 indicates the inside of the clipping boundary 201, 203 indicates the outside of the clipping boundary 201, and 204 indicates the input vertex. However, it is assumed that the clipping boundary 201 is not included in either the inside 202 or the outside 203. In FIG. 204 is on the clipping boundary 201, (C) is the vertex 204
The inside/outside determination circuit 105 uses the determination result 106 as a signal indicating which of the three types is present.
The input vertex 1 is output as follows and stored in the inside/outside judgment result register 107. Also supplied to the clipping judgment circuit 109. Clipping judgment circuit 1091:L Input vertex 1
Using the inside/outside judgment result 106 for 01 and the inside/outside judgment result 108 for the previous vertex in the vertex series of the polygon held in the inside/outside judgment result register 107,
Determines the positional relationship between the line segment connecting the currently input vertex and the previous vertex and the clipping boundary, determines the coordinates of the vertex to be output as a result of clipping processing, and controls the vertex output circuit 114. A module that supplies signal 110
At this time, if it is determined that the intersection between the line segment and the clipping boundary should be output (above intersection calculation circuit 1
Control signal 1 instructs to calculate the intersection point 113 also for 12
FIG. 3(a) to (i) show all nine positional relationships between the line segment and the clipping boundary. In FIG. 3, 201 to 203 (the same as in FIG.
The intersection point R between Q and the clipping boundary 201 is shown in Fig. 4. Corresponding to each case in Fig. 3, the inside/outside judgment result 106 and the inside/outside judgment result register for the input vertex coordinates 101 are shown. The relationship between the inside/outside determination result 108 for the previous vertex in the polygon vertex series held in 107 and the vertex determined to be output by the clipping determination circuit 109 is shown. If the relationship shown in Figure 4 is completely included in the relationship shown in Figure 9 above, it is guaranteed that vertices that are not on the clipping boundary can be processed in the same way as the conventional clipping circuit. The coordinates 101 of the vertex input to the calculation circuit 112, the coordinates 111 of the previous vertex in the polygon vertex series held in the vertex register 102, and the coordinates 111 of the previous vertex held in the boundary register 103 & the target of current processing Equation 10 of the clipping boundary is
4, the coordinates of the intersection of the clipping boundary and the line segment connecting the currently input vertex and the previous vertex are determined using the control signal 11 indicating the determination result of the clipping determination circuit ■09.
A control signal 110 indicating the judgment result of the clipping judgment circuit 109
(i.e., according to the relationship shown in FIG. 4), the coordinates 113 of the intersection calculated as necessary by the intersection calculation circuit 112,
The currently input vertex coordinates 101 or = 0 or the coordinates 115 of two vertices are output in order.
0 @ Figure 12 @ and Figure 15 respectively show the processing flow when performing clipping processing using the clipping circuit of the present invention on the polygons shown in Figures 5 @ 6 @ and shown in FIG. The first
For the example polygon in figure 0,
, F, A For the example polygon in Figure 12, there are three vertices B, D, A (for the example polygon in Figure 15, there are four vertices B, C). , D, and A (respectively, the vertices are output without overlapping). -The sword is expressed individually as software.Using a normal CPU (Central Processing Unit),
The functions of each circuit may be realized by software,
It should be added that the clipping circuit of the present invention can be constructed by realizing each register using a normal memory device or a CPU register.

Effects of the Invention As explained above, according to the present invention, when a polygon including vertices on the clipping boundary is input, the ripping circuit does not output the same vertices twice. It is possible to realize this, prevent unnecessary increases in processing, and improve processing speed.

[Brief explanation of drawings]

Figure 1 is a block diagram showing the configuration of an embodiment of the clipping circuit of the present invention. Figure 2 is the positional relationship between one vertex and the clipping boundary. Figure 3 is the positional relationship between the line segment connecting two vertices and the clipping boundary. Figure 4 shows the correspondence between the positional relationship shown in Figure 3 and the relationship between the vertices to be output.
Figure 6 shows the processing flow when the polygon example shown in Figure 1 is processed using the clipping circuit of the present invention. A medical diagram showing the processing flow when processing using
Figure 7 shows the processing flow when the polygon example shown in Figure 15 is processed using the clipping circuit of the present invention. Figure 8 shows the line segments and clipping used in the conventional clipping circuit. Figure 9 shows the correspondence between the positional relationship shown in Figure 8 and the relationship between the vertices to be output. Figure 10 shows the plane showing an example of a polygon to be clipped. Figure 12 is a plane showing an example of a polygon to be clipped; Figure 13 is a plane showing an example of a polygon to be clipped; Figure 14 shows the flow of processing when a conventional clipping circuit is used to process the example polygon shown in the figure, assuming that the clipping boundary itself is included inside. Figure 15 shows the processing flow when using a conventional clipping circuit to process the polygon example shown, assuming that the clipping boundary itself is included on the outside. Plane showing an example of a polygon @ Fig. 16 is a diagram showing the flow of processing when the polygon example shown in Fig. 15 is processed using a conventional clipping circuit. The peak of JIHI 102.
... Apex Regis Hisa 103... Boundary Regis Hisa 1
05...Inside/outside judgment port a107...Inside/outside judgment result Regis Ku 109...Clipping judgment same area 112
... Intersection calculation same section 114 ... Vertex output regeneration

Claims (1)

[Claims] a vertex register that holds the coordinates of the vertices of the input polygon; a boundary register that holds the equation of the boundary surface or boundary line representing the clipping area; and the equation of the boundary surface or boundary line output from the boundary register and the The input coordinates of the vertex are input to determine whether the vertex with the coordinates exists inside or outside the boundary surface or boundary line, or exists on the boundary surface or boundary line. an inside/outside determination circuit for determining; an inside/outside determination result register for retaining a result determined by the inside/outside determination circuit for the previous vertex in the vertex series held by the vertex register; and an inside/outside determination result register for the inside/outside determination circuit. a clipping determination circuit that receives as input a first inside/outside determination result to be output and a second inside/outside determination result held in the inside/outside determination result register and determines coordinates to be output as a result of clipping;
A line segment whose two end points are the coordinates of the input vertex and the coordinates held in the vertex register, and the equation of the boundary surface or boundary line output from the boundary register are input, and the line segment and the coordinates held by the vertex register are input. an intersection calculation circuit that calculates the coordinates of the intersection with the boundary surface or the boundary line according to the output of the clipping determination circuit; and 0 from the coordinates of the input vertex and the coordinates of the intersection output from the intersection calculation circuit. or a vertex output circuit that selects, orders and outputs two coordinates according to the output of the clipping determination circuit.