JPH0664618B2 - Clipping circuit - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a clipping circuit for a graphic display device, and more particularly to a clipping circuit for clipping a portion of a line segment that intersects with the clipping boundary and is outside the clipping boundary.

2. Description of the Related Art When displaying an object 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 generally called clipping (or clipping), and the boundaries for cutting are called clipping boundaries. When the display object is a two-dimensional object, the clipping boundary is composed of a plurality of (generally four) two-dimensional straight lines,
When the display object is a three-dimensional object, the clipping boundary is composed of a plurality of (generally four to six) three-dimensional planes. On the other hand, the display object is often approximated by a polygon 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 an unnecessary portion of the polygon into a plurality of clipping boundary lines or boundary surfaces. Possible solutions to this process are I Sutherland and G. Sutherland and G.
"Reentrant Polygon Clipping" by W. Hodgman, Communications of the ACM, Volume 17, Issue 1 ("Reentrant Polygon
Clipping ", CACM, Vol.17, No. 1), pp32-42, 1974. This algorithm inputs polygons as a sequence of vertices and creates straight lines or When clipping of one straight line or plane is completed, clipping is performed for the next straight line or plane with the polygon formed of the row of vertices output as the processing result as an input. The characteristic of this algorithm is that, in addition to sequentially clipping each clipping boundary, a polygon is considered as a row of vertices and clipping is performed on a line segment connecting two adjacent vertices. The relationship between a certain clipping boundary (which may be one side or a straight line) and two adjacent vertices that form a polygon is shown in FIG. Figure 2a-c.
In 201, 201 indicates a clipping boundary, 202 indicates an inside of the clipping boundary 201, and 203 indicates an outside of the clipping boundary 201. However, it is assumed that the clipping boundary 201 is included inside. Figure 2a shows two vertices Pi and
The case where both Pj are in the inside 202 is shown. In this case, the line segment P
iPj204 is also inside 202. Figure 2b shows two vertices Pi
And Pj are both outside 203. in this case,
The line segment PiPj204 is also outside. Figure 2c shows two vertices P
One of i and Pj (Pi in this example) is inside 202 and the other (Pj in this example) is outside 203. In this case, only part of the line segment PiPj 204 is inside 202. Line segment PiPj
If the intersection of 204 and clipping boundary 201 is Pk, the line segment PiPj
205 is inside. Therefore, a clipped polygonal vertex row for the input polygonal vertex row is generated by cutting out unnecessary portions in each case of FIG.

FIG. 3 shows an example in which two-dimensional clipping is performed using this algorithm. In FIG. 3A, 301 is a polygon P ₀ , P ₁ , P ₂ to be clipped, 302 is a clipping boundary x = x ₁ , 303 is a clipping boundary x = x ₂ , 304 is a clipping boundary y. = Y ₁ and 305 indicates a clipping boundary y = y ₂ . Reference numeral 306 denotes a polygon resulting from clipping the polygon 301 with clipping boundaries 302 to 305. First the polygon 301 against the clipping boundary 302
Taking the case of clipping as an example, the clipping procedure for one clipping boundary will be described.

The polygon 301 is input as a sequence of vertices P ₀ , P ₁ and P ₂ .
First, since the two points P ₀ and P ₁ are both inside 308 with respect to the clipping boundary 302, the two points P ₀ and P ₁ are output as they are as the vertices of the clipping result polygon 309.

Next, since P ₂ of the two points P ₁ and P ₂ is outside 307, the line segment And the intersection P ₃ of the clipping boundary 302 is output. Finally, of P ₂ and P ₀ , P ₂ is on the outside 307 and P ₀ is on the inside 308. And a clipping boundary 302 intersecting point P ₄ is output. As a result of the above, the polygon 30 indicated by the row of vertices P ₀ , P ₁ , P ₃ and P ₄
9 is the clipping result for clipping boundary 302. Similarly, the clipping result for the sequential clipping boundary 303 is shown in FIG. 3c, the clipping result for the clipping boundary 304 is shown in FIG. 3d, and the clipping result for the clipping boundary 305 is shown in FIG. 3e. The polygon P ₉ , P finally obtained is 306 in FIG. 3e.
₅ , P ₇ , P ₈ , P ₃ , P ₄ , and P ₁₀ are shown.

Problems to be Solved by the Invention However, when considering the hardware implementation of the algorithm described above, to determine whether a certain point is inside or outside the clipping boundary, the coordinate value of the point is determined. Is a simple process such as comparing the size with a value indicating the clipping boundary, but when one of the two adjacent points of the polygon to be clipped is inside the clipping boundary and the other is outside, the clipping boundary In order to obtain the intersection of the line segment connecting the two points with and, multiplication and division are necessary, which is disadvantageous for hardware implementation. In addition, instead of calculating the intersections linearly, the “midpoint division method” that finds the midpoints of the two points and asymptotically searches for the intersections is the R.F. Sproll and A.I. Sutherland (RFSpro
"A Clipping Divider" by ull and IESutherland, FJC C, published by Thompson Books ("Clipping Divider", FJCC, Thompson)
Books) pp765-775,1968.
It can be said that the “midpoint division method” is an effective method because the calculation of the midpoint of two points normally represented by the coordinate system can be realized by simple hardware such as addition and shift calculations. However, in the coordinate conversion process prior to clipping,
Since the representation of the transformation is easy and the synthesis of the transformation can be described by the product of transformation matrices, the coordinate representation in the homogeneous coordinate system is generally used instead of the ordinary coordinate system. Further, it is desirable to perform clipping in the homogeneous coordinate system due to the problem of calculation accuracy (due to the “reentrant polygon clipping”). However, as will be described later in the embodiment of the invention, since the midpoint of two points given by the coordinate values in the homogeneous coordinate system cannot be found by simple addition, the above-mentioned "midpoint in hardware implementation" There was a problem that the advantage of "division method" was lost.

In view of such a point, the present invention provides a clipping circuit that obtains an intersection of a line segment connecting two points represented by a homogeneous coordinate system and a clipping boundary by using only simple addition and subtraction and shift operations. The purpose is to

Means for Solving the Problem In order to solve the above-mentioned problems, the present invention provides, in order to solve the above-mentioned problems, homogeneous coordinates of a first end point, which is inside the clipping boundary, of two end points of a line segment intersecting the clipping boundary. A first register group for storing coordinate values in the system, a second register group for storing coordinate values in a homogeneous coordinate system of a second endpoint outside the clipping boundary, and the first register group.
Coordinate data of the first end point stored in the register group of No. 2 and the absolute value of the W coordinate of the coordinate value of the second end point stored in the second register group, and both or one of the coordinate data is compared. To a digit matching circuit for multiplying both by an appropriate value so that the digits of both absolute values are equal, and corresponding elements of the coordinate values of each of the first and second end points aligned by the digit matching circuit. And a third point having the output value of the adding circuit as a coordinate value in the homogeneous coordinate system is on the boundary with respect to the clipping boundary, inside the boundary, or at the boundary. Based on the output of the determination circuit and the determination circuit that determines which is external,
When the third point is on the boundary with respect to the clipping boundary, the output value of the adder circuit is output as the coordinate value of the intersection of the clipping boundary and the line segment, and when it is inside the boundary, the adder circuit is output. Is stored in the first register group, and when it is outside the boundary, the control circuit stores the output value of the adder circuit in the second register group.

With the above-described structure, the present invention receives the coordinate values of the two end points of the line segment intersecting the clipping boundary in the homogeneous coordinate system as input data, stores them in the first and second register groups, and uses the digit matching circuit to respectively receive them. The coordinate value stored in the register group of is multiplied by an appropriate number (for example, addition or shift operation is performed), and each w coordinate (in the case of two dimensions, the third dimension element of the coordinate value, in the case of three dimensions). Is the fourth-dimensional element of the coordinate value) and the absolute value of the absolute value is aligned, and the value obtained by simply adding the aligned coordinate value by the adder circuit is regarded as the "pseudo midpoint" coordinate value. The same processing as the "midpoint division method" is performed. That is, the determination circuit determines the positional relationship between the point and the clipping boundary, and the control circuit outputs the output of the adder circuit to the first register group when the point is inside the clipping boundary. This value and the value already stored in the second register group are stored as the coordinate values of the two end points of the new line segment, and the above processing is repeated, and the point is outside the clipping boundary. , The output of the adder circuit is stored in the second register group, and this value and the value already stored in the first register group are coordinate values of the two end points of the new line segment. The above process is repeated, and when the above point is on the clipping boundary, the output of the adding circuit is output as the coordinate value of the desired intersection point, and the clipping process for one line segment is completed.

Embodiments Before describing the embodiments of the present invention with reference to the drawings, a description and proof of the principle on which the present invention is based will be given.
All coordinate values used in the following description indicate points in a three-dimensional space, but when clipping on a two-dimensional plane is considered, the dimension of the coordinate value can be reduced by one (that is, the z coordinate is omitted). Can be easily analogized by. It should be noted that coordinate values expressed in lower case alphabets [eg (x, y, z)] are used as coordinate values in the normal coordinate system, and upper case letters are used to add the fourth coordinate w. A thing [eg (x, y, z, w)] is used as the coordinate value of the homogeneous coordinate system.

The clipping boundary condition is generally It is expressed by Think in. The point (x, y, z) in the normal coordinate system is expressed as (X, Y, Z, w) in the homogeneous coordinate system. However, w is not 0, Satisfy the relationship. Therefore, equation (2), which indicates the clipping boundary condition, is expressed as follows in the homogeneous coordinate system.

Or Since the corresponding normal coordinates do not change even if the coordinate value in the homogeneous coordinate system is multiplied by a scalar other than 0, only the case of the formula (4) will be considered. As can be seen from equation (4), the clipping boundary consists of the six planes shown in equation (6).

Now, two points P ₁ (X ₁ , Y ₁ , Z ₁ , w ₁ ) and P ₂ (X ₂ , Y ₂ , Z ₂ , w ₂ ) for one clipping boundary w−X = 0.
Consider the case of clipping a line segment that connects to. However,
Let w ₁ and w ₂ > 0.

From the formula (4), when X ₁ w ₁ and X ₂ w ₂ , two points P ₁
And P ₂ are both inside the clipping boundary, so the line segment Is also inside the clipping boundary. Also x ₁ > w ₁
When X ₂ > w ₂ , the two points P ₁ and P ₂ are both outside the clipping boundary, and thus the line segment Is also outside the clipping boundary. Also X ₁ > w ₁
And X ₂ w ₂ or X ₁ w ₁ and X ₂ > w ₂
When, one of the two points is inside the clipping boundary,
Line segment because the other is outside The part of the clip outside the clipping boundary must be clipped. It is now assumed that the point P ₁ is inside the clipping boundary and the point P ₂ is outside. line segment And the clipping boundary w−X = 0 intersects with P ₃ (X ₃ , Y
₃ , Z ₃ , w ₃ ), the point P ₃ is given by the following equation (7).

From the property of the coordinate values of the above-mentioned homogeneous coordinate system, equation (7) is Can be expressed as However, even if equation (8) is used, the intersection point P ₃
At least 6 multiplications are required to calculate on the other hand,
Consider a case where the above-mentioned "midpoint division method" in the normal coordinate system is applied. The coordinate values in the normal coordinate system corresponding to the two points P ₁ and P ₂ are respectively (X ₁ / w ₁ , Y ₁ / w ₁ , Z ₁ / Z ₁
w ₁ ) and (X ₂ / w ₂ , Y ₂ / w ₂ , Z ₂ / w ₂ ), the normal coordinate system corresponding to the midpoint P ₄ (X ₄ , Y ₄ , Z ₄ , w ₄ ). The coordinate value at is given by the following equation (9).

From the property of the coordinate values in the above-mentioned homogeneous coordinate system, equation (9) is Can be expressed as However, even if equation (10) is used, the midpoint P ₄
At least 7 multiplications are required to calculate
Therefore, the processing is more complicated than directly obtaining the intersection point P _3, and it is meaningless to apply the “midpoint division method”.

Therefore, consider a point P _M (X _M , Y _M , Z _M , w _M ) represented by the following equation (11) as a point that replaces the middle point P ₄ .

Now the vector connecting the two points P ₁ and P _M in the normal coordinate system Is expressed by the following equation (12).

On the other hand, the vector connecting the two points P ₁ and P ₂ Is expressed by the following equation (13).

Therefore, the following equation is derived from the equations (12) and (13).

Since w ₁ and w ₂ are both positive now, The relationship is established. From the above, the point P _M is a line segment It is a point between the upper end points P ₁ and P ₂ . Therefore, the formula (1
The coordinate value of the point P _M is obtained according to 1), the positional relationship with the clipping boundary is determined using the equation (4) for the obtained coordinate value, and the point P _M is inside the clipping boundary (X _M < w
_M ) then replace the coordinate value of point P _{1 with} the coordinate value of point P _M For point P _M outside the clipping boundary (X _M > w _M ), the coordinate value of point P ₂ is replaced with the coordinate value of point P _{M to} obtain a line segment. The same process as described above is repeated for the point P _M on the clipping boundary.

FIG. 1 is a diagram showing an embodiment of a clipping circuit for performing the clipping processing of the present invention described above.

In FIG. 1, 101 is the coordinate value data of the first end point inside the clipping boundary of the two end points of the line segment that intersects a certain clipping boundary, and 102 is the first value that stores the element of the coordinate value data 101. The register group 103 is the coordinate value data of the second end point outside the clipping boundary, and 104
Is a second register group that stores the elements of the coordinate value data 103, 105 is a digit alignment circuit that aligns the w coordinates of the coordinate value data stored in the register groups 102 and 104, and 106 is a digit. Reference numeral 107 denotes an adder circuit for adding corresponding elements of the coordinate value data corrected by the matching circuit 105, and 107 is a determination circuit for determining the positional relationship between a point having the coordinate value of the output of the adder circuit 106 and a given clipping boundary. A, 108
Outputs the output of the adder circuit 106 according to the result of the determination circuit 107.
2 shows a control circuit for storing in the register group 102, storing in the second register group 104, and outputting as the final result 109.

The functions of the adder circuit 106, the judgment circuit 107, and the control circuit 108 are the same as those described above, and therefore, the description thereof will be omitted, and only the function of the digit alignment circuit 105 will be supplementarily described.

When the absolute values of the w-coordinate values of the coordinate value data stored in the register groups 102 and 104 are very different (for example, when w ₁ << w ₂ ), the equation (14) is Therefore, the coordinate value of the point P _M output from the adding circuit 106 is a value very close to the coordinate value of the original end point P ₂ . Therefore, a phenomenon occurs in which the point P _M does not easily converge at the intersection with the clipping boundary. In extreme cases, adder circuit 10
"Lost-'occurs during the addition in 6, the process remains in either of the first two end points the point P _M is permanently may also happen that no ends. Therefore, by utilizing the property of the coordinate values in the above-mentioned homogeneous coordinate system, the digit matching circuit 105 compares the absolute values of the w coordinates of the coordinate data stored in the register groups 102 and 104, and finds that the digit of the absolute value is Digit alignment is performed by multiplying one or both coordinate value data by an appropriate value so that they are almost equal. This gives w _{2 in} equation (15)
/ (W ₁ + w ₂ ) also approaches 1/2, and the point P _M also approaches the true midpoint. This digit alignment processing is performed by a shift operation of the coordinate value data when the coordinate value data is expressed by a fixed point number, and by an addition or subtraction with respect to the exponent part of the coordinate value data when the coordinate value data is expressed by a floating point number. Since it can be realized, a multiplication circuit is not actually required.

Although w−X = 0 is used as the clipping boundary in the description of the embodiment, it goes without saying that it can be easily applied to other clipping boundaries by changing the judgment conditions in the judgment circuit 107.

EFFECTS OF THE INVENTION As described above, according to the present invention, clipping processing in a homogeneous coordinate system can be realized without using a multiplication / division circuit, which is suitable for hardware implementation, particularly for LSI implementation, and image generation in a graphic display device is possible. It greatly contributes to the speeding up and reduction of hardware cost.

[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 an explanatory diagram of a clipping algorithm, and FIG. 3 is a positional relationship diagram between a line segment connecting two end points and a clipping boundary. is there. 102, 104 ... Register group, 105 ... Digit alignment circuit, 106 ... Addition circuit, 107 ... Judgment circuit, 108 ... Control circuit.

Claims (1)

[Claims] 1. A first register group for storing coordinate values in a homogeneous coordinate system of a first end point inside the clipping boundary among two end points of a line segment intersecting the clipping boundary, and A second register group that stores coordinate values in a homogeneous coordinate system of a second endpoint that is external to the clipping boundary, a coordinate value of the first endpoint that is stored in the first register group, and the The absolute value of the W coordinate of the coordinate value of the second end point stored in the second register group is compared, and both or one coordinate data is multiplied by an appropriate value so that the digits of both absolute values become equal. Digit adjusting circuit and the first digit adjusted by the digit adjusting circuit
And an adder circuit for adding corresponding elements of the coordinate values of the respective second end points, and a third point having the output value of the adder circuit as coordinate values in the homogeneous coordinate system is a boundary with respect to the clipping boundary. A determination circuit for determining whether it is above, inside the boundary, or outside the boundary; and when the third point is on the boundary with respect to the clipping boundary based on the determination of the determination circuit, The output value of the adder circuit is output as the coordinate value of the intersection of the clipping boundary and the line segment, and the output value of the adder circuit is stored in the first register group when the third point is inside the boundary. And a control circuit for storing the output value of the adder circuit in the second register group when the third point is outside the boundary.