Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-22
2002-10-01
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06460063
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a division circuit and a graphic display processing apparatus capable of performing processing at a high speed.
2. Description of the Related Art
Computer graphics are often used in a variety of computer aided design (CAD) systems and amusement machines. Especially, along with the recent advances in image processing techniques, systems using three-dimensional computer graphics are becoming rapidly widespread.
In three-dimensional computer graphics, the color value of each pixel is calculated at the time of deciding the color of each corresponding pixel. Then, rendering is performed for writing the calculated value to an address of a display buffer (frame buffer) corresponding to the pixel.
One of the rendering methods is polygon rendering. In this method, a three-dimensional model is expressed as an composite of triangular unit graphics (polygons). By drawing the polygons as units, the colors of the pixels of the display screen are decided.
In polygon rendering, coordinates (x, y, z), color data (R, G, B, &agr;), homogeneous coordinates (s, t) of texture data indicating a composite image pattern, and a value of the homogeneous term q for the respective vertexes of the triangle in a physical coordinate system are input and processing is performed for interpolation of these values inside the triangle.
Here, the homogeneous term q is, simply stated, like an expansion or reduction rate. Coordinates in a UV coordinate system of an actual texture buffer, namely, texture coordinate data (u, v), are comprised of the homogeneous coordinates (s, t) divided by the homogeneous term q to give “s/q” and “t/q” which in turn are multiplied by texture sizes USIZE and VSIZE, respectively.
In a three-dimensional computer graphic system using such polygon rendering, the texture data is read from the texture buffer when drawing, and texture mapping is performed for applying the read texture data on the surface of the three-dimensional model.
Note that when texture mapping is performed on a three-dimensional model, the expansion/reduction rate of the image indicated by the texture data to be applied to each pixel changes.
The texture buffer is accessed by using the above texture coordinate data (u, v). At the time of reading the texture data from the texture buffer, “s/q” and “t/q” are calculated for all pixels to calculate the texture coordinate data (u, v). Accordingly, the number of division operations becomes enormous.
Note that in the three-dimensional computer graphic system of the related art, the above “s/q” and “t/q” are calculated by a division circuit explained below.
Below, the division circuit of the related art will be explained.
FIG. 4
is a view of the configuration of an example of a division circuit
300
of the related art.
As shown in
FIG. 4
, the division circuit
300
comprises absolute value processors
301
and
302
, priority encoders
303
and
304
, shift processors
305
and
306
, a subtractor
307
, a reciprocal calculator
308
, a multiplier
309
, a shift processor
310
, and an encoder
311
.
In the division circuit
300
, the absolute value of a dividend s is normalized as shown in the equation (1) below for floating point representation of the input dividend s. When the sign of the dividend s is minus (negative), its index se and mantissa sm are generated based on the following equations (2) and (3).
s=sm×2
se
(1)
sm=(~s+1)/{2**int(log
2
(~s+1))} (2)
Note that equation (2) is an operation for shifting “~s+1” by exactly a complement of 1 of “int(log
2
(~s+1))” that is, “~int(log
2
(~s+1))”, toward the most significant bit (MSB).
se=int{log
2
(~s+1)} (3)
Specifically, when the sign of the dividend s is minus, as shown in
FIG. 5
, the absolute value processor
301
shown in
FIG. 4
calculates an inversion of the dividend s (Exclusive-OR), adds “+1” to the inversion result, finds a complement of 2 of the dividend s, that is, “~s+1”, and outputs the “~s+1” to the priority encoder
303
and the shift processor
305
.
Note that, in the absolute number processor
301
, the sign of the dividend s refers to a sign bit of the MSB of the dividend s. The sign is judged to be minus when the MSB is “1” and plus when the MSB is “0”.
A logarithm of 2 of “~s+1”, that is, “log
2
(~s+1)”, is found in the priority encoder
303
. A integer value of the logarithm of 2, that is, “log
2
(~s+1) ”, is output as an index se to the shift processor
305
and subtractor
307
.
Then, the shift processor
305
shifts “~s+1” by exactly the complement of 1 of “int(log
2
(~s+1))”, that is, “~int(log
2
(~s+1))”, that is, the complement of 1 of the index se, toward the MSB to calculate the mantissa sm. The mantissa sm is output to the multiplier
309
.
Also, in the above division circuit
300
, when the sign of the dividend s is plus (positive), the absolute value processor
301
, the priority encoder
303
, and the shift processor
305
normalize the absolute value of the input dividend s and generate its index se and mantissa sm based on the following equations (4) and (5):
sm=s/{2**int(log
2
s)} (4)
Note that equation (4) is an operation for shifting “s” by exactly the complement of 1 of “int(log
2
s)”, that is, “~int(log
2
s)”, toward the MSB.
se=int(log
2
s) (5)
Specifically, when the sign of the dividend s is plus, the dividend s passes through the absolute value processor
301
and is output to the priority encoder
303
and the shift processor
305
.
Then, the priority encoder
303
finds the logarithm of 2 of the dividend s, that is, “log
2
s”. The integer value of the logarithm of 2, that is, “log
2
s”, that is, “int(log
2
s)”, is output as the index se to the shift processor
305
and the subtractor
307
.
Then, the shift processor
305
shifts the dividend s by exactly the complement of 1 of “int(log
2
s)”, that is, “~int(log
2
s)”, toward the MSB and calculates the mantissa sm. The mantissa sm is output to the multiplier
309
.
The absolute value processor
302
, the priority encoder
304
, and the shift processor
306
shown in
FIG. 1
are used for calculating the index qe and mantissa qm of the divisor q. The processing is the same as that of the above absolute value processor
301
, priority encoder
303
, and shift processor
305
.
The reciprocal calculator
308
calculates the reciprocal of the mantissa qm of the divisor q and outputs the reciprocal “1/qm” to the multiplier
309
.
The multiplier
309
multiplies the mantissa sm and the reciprocal of the mantissa qm, that is, “1/qm”, and outputs the multiplication result “sm/qm” to the shift processor
310
.
The subtractor
307
subtracts the index qe from the index se and outputs the subtraction result “se−qe” to the shift processor
310
.
The shift processor
310
shifts the multiplication result “sm/qm” from the multiplier
309
by exactly the number of bits indicated by the subtraction result “se−qe” from the subtractor
307
toward the MSB and outputs the shift operation result S
310
to the encoder
311
.
The encoder
311
, based on the sign of the dividend s and the sign of the divisor q, adds “1” indicating minus to the one upper bit of the MSB of the shift operation result S
310
when the two signs are different and outputs the result as the division result “s/q”. When the sign of the dividend s and the sign of the divisor q are the same, the encoder
311
adds “0” indicating plus to the one upper bit of the MSB of the shift operation result S
310
and outputs the result as the division result “s/q”.
Summarizing the problem to be solved by the invention, in the above division circuit
300
of the related art shown in
FIG. 4
, the processing time of the path for finding “1/qm” from the divisor q is longer than the path for finding the mantissa sm from the dividend s by the amount of the processing in the reciprocal calc
Kananen, Esq. Ronald P.
Malzahn David H.
Rader & Fishman & Grauer, PLLC
Sony Corporation
LandOfFree
Division circuit and graphic display processing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Division circuit and graphic display processing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Division circuit and graphic display processing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2929270