JP3312382B2 - Normal vector coordinate converter - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a normal vector coordinate conversion apparatus, and more particularly, to an apparatus particularly suitable for normal vector coordinate conversion in a graphic processing apparatus.

[0002]

2. Description of the Related Art Conventionally, in a graphic processing apparatus for processing a three-dimensional graphic, a normal vector is used for discriminating the front and back of a polygon constituting the graphic, calculating the color and brightness of the polygon, and the like. Further, in this graphic processing device, since the coordinate system in which the graphic is initially defined is different from the coordinate system for displaying the graphic, not only each polygon constituting the graphic but also each polygon is attached. For the normal vector, it is necessary to perform coordinate conversion between coordinate systems. Conventionally, to meet this demand,
Although coordinate transformation using the homogeneous coordinate transformation matrix of row 4 is performed, it is not sufficient to perform the coordinate transformation processing based on the homogeneous coordinate transformation matrix for the normals. Normalization processing is performed.

[0003]

When performing the above-described normal vector coordinate conversion processing, not only matrix operation based on a homogeneous coordinate conversion matrix but also normalization processing is required for each normal vector. In addition, since the number of polygons to be processed is generally extremely large, the ratio of normal vector normalization processing to the entire graphic processing becomes considerably large, and as a result, the graphic processing speed is reduced. There is.

[0004] Incidentally, even if the apparatus is other than the graphic processing apparatus,
A similar problem occurs if the apparatus requires coordinate transformation of the normal vector.

[0005]

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned problems, and an object of the present invention is to provide a normal vector coordinate conversion apparatus which can eliminate the normalization process which has been conventionally required in the normal vector coordinate conversion. It is intended to provide.

[0006]

[0007]

According to a first aspect of the present invention, there is provided a normal vector coordinate conversion apparatus for determining whether or not a normal vector to be converted is normalized, and a target coordinate conversion. A second discriminating means for discriminating whether or not is the one that preserves an angle; and for each element of the sub-matrix except the fourth row and fourth column of the homogeneous coordinate transformation matrix, A coordinate transformation matrix output unit that outputs a coordinate transformation matrix obtained by multiplying a reciprocal of a square root of a sum of squares of a row element, and a first determination unit that indicates that a normal vector to be transformed is normalized. In response to the determination result from the second determination unit indicating that the target coordinate conversion is to save the angle, and the coordinate conversion processing based on the coordinate conversion matrix output from the coordinate conversion matrix output unit. And a coordinate transformation means for performing.

[0008]

[0009]

According to the first aspect of the present invention, the normal vector coordinate conversion device determines whether or not the normal vector to be converted is normalized by the first determination means, and the target coordinate conversion stores the angle. It is determined by the second determination means whether or not the operation is performed. Also, a coordinate transformation obtained by multiplying each element of the partial matrix excluding the fourth row and the fourth column of the homogeneous coordinate transformation matrix by the reciprocal of the square root of the sum of squares of any row element of the partial matrix. The matrix is output by the coordinate transformation matrix output means. The determination result from the first determination unit indicating that the normal vector to be converted is normalized, and the determination result from the second determination unit indicating that the target coordinate conversion preserves the angle. In response to the result, the coordinate conversion unit performs a coordinate conversion process based on the coordinate conversion matrix output from the coordinate conversion matrix output unit. Therefore, special processing for normalization can be made unnecessary as compared with a conventional apparatus that has performed matrix operation and normalization processing. As a result, the amount of processing required to convert the normal vector into coordinates can be greatly reduced,
The coordinate conversion processing speed can be significantly improved.

More specifically, for example, when a vector orthogonal to a tangent of a circle and a circle is subjected to coordinate transformation for non-uniform enlargement by a conventional method, the circle is transformed into an ellipse.
The transformed vector is no longer perpendicular to the tangent of the ellipse. Here, the original vector corresponds to the normal vector. The present inventor has clarified the cause of such an inconvenience, and does not perform coordinate transformation of only the normal vector, but carries out coordinate transformation of a plane indicated by the normal vector, thereby converting the original normal vector after the coordinate transformation. It has been found that the coordinate transformation of the normal vector can be achieved so that it becomes a normal vector also for the figure.In addition, when the original normal vector is normalized under predetermined conditions, special normalization is performed. It has also been found that a normalized normal vector after conversion can be obtained without performing any processing for this purpose, and the present invention has been completed. Details will be described below.

[0011] a normal vector _{N (N x, N y,} N z) equation of the surface represented by the _{N x x + N y y +} N z z + R = 0, the matrix [M] by equation coordinate transformed face N _{x'x + N y'y + N} z'z + R'= 0, the normal vector to the surface of the converted N'(N _x
, N _y ′, N _z ′).

In this case, coordinate points (X,
Assuming that a homogeneous coordinate expression of a point on the surface after conversion with respect to Y, Z, 1) is (X ′, Y ′, Z ′, w ′), w
Since '= 0 indicates a point at infinity, the homogenous coordinate expression is w' (X '
/ W ', Y' / w ', Z' / w ', 1), and when returned to normal coordinates, becomes w' (x ', y', z ', 1). Therefore, the relation of Equation 1 holds for points on the surface before and after the coordinate transformation.

[0013]

(Equation 1)

When the equations of the above surface are represented by matrices, they are as shown in Equations 2 and 3, respectively.

[0015]

(Equation 2)

[0016]

(Equation 3)

Further, since the relationship of (xyz 1) = w ′ (x′y′z ′ 1) [M] ⁻¹ is obtained from Expression 1, it is substituted into Expression 2 and both sides are divided by w ′. By doing so, the relationship of Equation 4 is obtained.

[0018]

(Equation 4)

The relationship of Expression 5 is obtained from Expressions 3 and 4;
By transposing both sides, the relationship of Expression 6 is obtained.

[0020]

(Equation 5)

[0021]

(Equation 6)

That is, it is understood that the coordinate transformation can be correctly performed on the normal vector by performing the coordinate transformation using the transposed matrix of the inverse matrix of the matrix [M]. However, in this case, it is necessary to calculate R. However, the fourth of the matrix [M]
If the element of the column is 0 00 p, it is found that R does not affect the coordinate transformation result (N _x N _y ＮN _z ) at all, and furthermore, the sub-matrix excluding the fourth row and the fourth column has It is also found that it is only necessary to perform coordinate transformation based on the coordinates. That is, if the fourth column of the matrix [M] is 0 0 0p, the fourth column of the inverse matrix [M] ^-1 is also 0 0 0 p ′, and the inverse matrix transpose ^t ([M] ^-1 ) Is the fourth row of 0 0
0 p '. Therefore, R is the coordinate transformation result (N _x
'N _y' N _z ') to no effect.

Further, it is assumed that the partial matrix [Mb] is given by Expression 7. In the following description, the original normal vector is (N), and the coordinate-transformed normal vector is (N).
').

[0024]

(Equation 7)

Then, it is assumed that the relations of Expressions 8 and 9 hold.

[0026]

(Equation 8)

And

[0028]

(Equation 9)

Also, r = (m11 ² + m12 ² + m1)
3 ² ) ^Set to ^-1/2 . In this case, the relationship between Expressions 8 and 9 is expressed by Expression 10.

[0030]

(Equation 10)

Here, [E] is a unit vector. Since this relationship can be modified as shown in Equation 11, it can be seen that r · [Mb] is an orthogonal matrix.

[0032]

[Equation 11]

By the way, r ² ·
By multiplying by [Mb] ⁻¹ , r ² · ^t [Mb] = [Mb] ^−1.
3 is obtained.

[0034]

(Equation 12)

[0035]

(Equation 13)

That is, (N) · (r · [Mb]) = (Ns
Performing coordinate transformation based on the equation (1) is equivalent to performing coordinate transformation based on Equation 12. Further, when (N) from the left of Expression 11 is transformed by multiplying ^t (N) from the right, ((N) · (r · [Mb])) · ^t ((N) · (r · [Mb) ])) = (N) · ^t (N). By substituting equation (13) into this equation and transforming it, the relationship of | (Ns ′) | = | (N) | is obtained. Therefore, when the normal vector is coordinate-transformed based on equation (13), the normal becomes You can see that the length of the vector is preserved.

Therefore, when the normal vector (N) is normalized, only the coordinate transformation based on r · [Mb] is performed, and the coordinate-transformed and normalized normal vector (Ns ') Can be obtained.

[0038]

BRIEF DESCRIPTION OF THE DRAWINGS FIG. FIG. 1 is a flowchart showing one embodiment of the normal vector coordinate conversion method of the present invention. Step SP
In step 1, a homogeneous matrix [M] for coordinate point conversion is set based on the setting conditions, and in step SP2,
Whether the original normal vector has been normalized and whether the set homogeneous matrix [M] preserves angles, ie, the original normal vector has been normalized, and Equations 8 and 9 Is determined. Then, in step SP2, when it is determined that the original normal vector is normalized, and it is determined that Expressions 8 and 9 are satisfied, r · [Mb] is calculated in step SP3 to obtain a normal conversion matrix. Conversely, if it is determined in step SP2 that the original normal vector is not normalized or does not satisfy at least one of Equations 8 and 9, ^t ([Mb] ^-1 ) is determined in Step SP4. Is calculated as a normal-line conversion matrix. After the processing of step SP3 or step SP4 is performed, step SP3
In step 5, coordinate transformation of the normal vector is performed based on the calculated normal transformation matrix. In step SP6, the original normal vector is normalized, and the set homogeneous matrix [M] determines the angle. Whether it is to be preserved, that is, the original normal vector is normalized and
It is determined whether or not Equation 9 is satisfied. And
If it is determined in step SP6 that the original normal vector has not been normalized or does not satisfy at least one of Equations 8 and 9, in Step SP7, normalization of the coordinate-transformed normal vector is performed. Perform processing. If the processing in step SP7 has been performed, or if it is determined in step SP6 that the original normal vectors have been normalized and that equations (8) and (9) are satisfied, all the target normals are determined in step SP8. It is determined whether or not the vector coordinate conversion has been completed. If there is a normal vector for which the coordinate conversion has not been completed, the process of step SP5 is performed again. Conversely, if it is determined that the coordinate conversion of all the target normal vectors has been completed, the series of processing ends.

As is apparent from the above description, when the original normal vector is normalized and the homogeneous matrix satisfies the equations (8) and (9), simply r · [Mb] is used for normal transformation. It is only necessary to perform the coordinate transformation of the normal vector as a matrix, and there is no need to perform the normalization processing after the coordinate transformation. Therefore, the processing for the coordinate transformation of the normal vector can be simplified. Also, once the matrix for normal transformation is calculated, it is only necessary to perform coordinate transformation processing on a large number of normal vectors, so even if it takes a little longer to calculate the matrix for normal transformation than the conventional method, As a whole, the processing can be greatly simplified and speeded up. Further, if the normal vector to be coordinate-transformed is not normalized, or if the homogeneous matrix does not satisfy at least one of Equations 8 and 9, conventional calculation of the matrix for normal transformation is performed. Although it takes a little longer than the method, the processing becomes complicated and slows down.However, in a general application program, the normal vector to be subjected to coordinate transformation is normalized, In most cases, the homogeneous matrix satisfies the formulas 8 and 9, so that the processing can be simplified and speeded up as a whole. As a result of the benchmark test performed by the present inventor, the processing amount in the graphic processing apparatus was reduced by about 14 to 15%, and the overall performance was reduced by about 17%.
It has been confirmed that the percentage has improved.

[0040]

Embodiment 2 FIG. 2 is a block diagram showing an embodiment of a normal vector coordinate converter according to the present invention. The normal vector coordinate conversion device of FIG. 2 includes a normalization determination unit 9 that determines whether a normal vector to be subjected to coordinate conversion has already been normalized, and a normalization determination unit 9 that performs coordinate point conversion based on setting conditions. A homogeneous matrix setting unit 1 for setting a homogeneous matrix [M];
A homogenous matrix discriminating unit 2 for discriminating whether or not the set homogenous matrix [M] preserves the angle, a discrimination result by the normalization discriminating unit 9 and a discrimination result by the homogenous matrix discriminating unit 2 A pair of normal-line conversion matrix calculation units 3 and 4 that selectively operate in response, and a normal line that holds the normal-line conversion matrix calculated by any of the normal-line conversion matrix calculation units 3 and 4 Conversion matrix holding unit 5
And a normal vector coordinate conversion unit 6 for performing coordinate conversion of the normal vector based on the normal conversion matrix, and a normalization determination unit 9 for indicating that the normal vector to be subjected to the coordinate conversion is not normalized. , And normalization for normalizing the coordinate-transformed normal vector in response to the determination result from the homogeneous matrix determination unit 2 indicating that the set homogeneous matrix does not preserve the angle. The processing unit 7 includes a normal vector coordinate conversion unit 6 corresponding to the number of normal vectors to be converted, and an iterative control unit 8 for repeatedly operating the normalization processing unit 7 as necessary.

The homogeneous matrix determination section 2 determines whether or not the set homogeneous matrix [M] satisfies Expressions 8 and 9. The normal-line conversion matrix calculation unit 3 calculates r · [Mb] as a normal-line conversion matrix, and the normal-line conversion matrix calculation unit 4 converts ^t ([Mb] ⁻¹ ) into a normal-line conversion. It is calculated as a use matrix.

The operation of the normal vector coordinate conversion device having the above configuration is as follows. First, the normalization determination unit 9 determines whether or not the normal vector to be subjected to coordinate conversion has already been normalized. Based on the setting conditions for coordinate conversion, the homogeneous matrix Is set, and whether the set homogeneous matrix satisfies both Equation 8 and Equation 9 is determined by the homogeneous matrix determination unit 2. Then, the normalization determining unit 9 determines that the normal vector to be subjected to the coordinate conversion has already been normalized,
When it is determined by the homogenous matrix determination unit 2 that Equations 8 and 9 are satisfied, r · [Mb] is calculated by the normal-line conversion matrix calculation unit 3 and stored in the normal-line conversion matrix holding unit 5. Supply. Conversely, it is determined by the normalization determining unit 9 that the normal vector to be subjected to the coordinate conversion has not been normalized, and / or the homogeneous matrix determining unit 2 does not satisfy at least one of Expressions 8 and 9. Is determined, ^t ([Mb] ^-1 ) is calculated by the normal-line conversion matrix calculation unit 4 and supplied to the normal-line conversion matrix holding unit 5.

After the matrix for normal vector coordinate conversion is held in the matrix holding unit 5 for normal line conversion as described above, the normal vector coordinate conversion unit 6 that is repeatedly operated by the repetition control unit 8 performs each method. Performs coordinate transformation of a line vector. Here, the matrix for normal vector coordinate transformation is r
In the case of [Mb], since the transformed normal vector is already in a normalized state, it is not necessary to perform further normalization processing, and the processing can be simplified and the speed can be increased. . However, if the matrix for normal vector coordinate conversion is ^t ([Mb] ^-1 ), the normal vector after conversion is not in a normalized state, so it is necessary to perform further normalization processing. By performing the normalization processing by the normalization processing unit 7, a coordinate-transformed and normalized normal vector can be obtained.

As is clear from the above description, when the matrix for normal vector coordinate conversion is ^t ([Mb] ^-1 ), the processing is performed by the amount required to be determined by the homogeneous matrix determination unit 2. Although it is complicated, in a general application program, the normal vector to be subjected to coordinate transformation has already been normalized, and the homogeneous matrix satisfies Expressions 8 and 9, ie, the normal line In most cases, the matrix for vector coordinate conversion is r · [Mb], so that the processing can be simplified and speeded up as a whole.

It should be noted that the present invention is not limited to the above embodiment. For example, it is determined whether or not the normal vector before coordinate transformation has already been normalized and whether or not Equations 8 and 9 are satisfied. It is possible to set / reset the flag in accordance with the result of the determination, and control whether to omit or execute the normalization processing in response to whether the flag is set or reset after the coordinate conversion. In addition, various design changes can be made without departing from the scope of the present invention.

[0046]

[0047]

According to the first aspect of the present invention, the square root of the sum of squares of any of the row elements of the sub-matrix is calculated for each element of the sub-matrix excluding the fourth row and the fourth column of the homogeneous coordinate transformation matrix. The coordinate transformation is performed only by performing the coordinate transformation based on the coordinate transformation matrix obtained by multiplying the reciprocal of, and a normalized normal vector can be obtained, eliminating the need for special processing for normalization. Since it is possible, the amount of processing required for performing coordinate transformation of the legal vector can be greatly reduced, and a unique effect that the coordinate transformation processing speed can be remarkably improved can be achieved.

[Brief description of the drawings]

FIG. 1 is a flowchart showing an embodiment of a normal vector coordinate conversion method according to the present invention.

FIG. 2 is a block diagram showing an embodiment of a normal vector coordinate conversion device according to the present invention.

[Explanation of symbols]

2 Homogeneous matrix discriminating section 3 Matrix calculating section for normal transformation 6 Normal vector coordinate transforming section 9 Normalization discriminating section

──────────────────────────────────────────────────続 き Continued on the front page (58) Fields surveyed (Int. Cl. ⁷ , DB name) G06F 17/10-17/18 G06T 1/00-1/40 G06T 3/00-5/50 G06T 9 / 00-9/40 G06T 11/00-11/40 G06T 15/00-15/60 G06T 17/00-17/30

Claims (1)

(57) [Claims] A first determining means for determining whether a normal vector to be converted is normalized; and determining whether or not a coordinate conversion to be performed preserves an angle. And a reciprocal of the square root of the sum of squares of any row element of the sub-matrix for each element of the sub-matrix excluding the fourth row and the fourth column of the homogeneous coordinate transformation matrix A coordinate transformation matrix output means (3) for outputting a coordinate transformation matrix obtained by multiplying by (1), and a first discrimination means (9) for indicating that a normal vector to be transformed is normalized.
A coordinate transformation matrix output means (3) in response to the judgment result from the second judgment means and the judgment result from the second judgment means (2) indicating that the target coordinate conversion is to save the angle.
And a coordinate conversion means (6) for performing a coordinate conversion process based on a coordinate conversion matrix output from the device.