Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-04-01
2001-12-11
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S605000, C345S520000, C345S520000, C712S221000, C712S223000, C712S224000
Reexamination Certificate
active
06329999
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an encoder for encoding digital data composed of a plurality of bits, a method thereof, and a graphic processing apparatus.
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, a), homogeneous coordinates (s, t) of texture data indicating a composite image pattern, and a value of the homogeneous term a 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 a 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 a 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.
The texture mapped image data is written in a display memory (frame memory) after being subjected to predetermined processing.
The above three-dimensional computer graphic system, however, has a built-in first and second priority encoder (FSPE) for generating, for example, positional data of a first “1” bit and a second “1” bit seen from a most significant bit (MSB) in digital data comprised of a plurality of bits in a variety of circuits including for example a division circuit.
FIG. 10
is a view of the configuration of an FSPE encoder
50
of the related art.
As shown in
FIG. 10
, the FSPE encoder
50
comprises 16-bit priority encoders
51
and
53
and a 16-bit first valid bit mask unit
52
.
In the FSPE encoder
50
, input digital data
60
is input to the priority encoder
51
and the first valid bit mask unit
52
.
In the priority encoder
51
, a first “1” bit seen from the MSB in the digital data
60
is detected and 4-bit first bit encode data
61
indicating the position of the bit is generated.
In the first valid bit mask unit
52
, first valid bit mask data
63
, wherein a first “1” bit seen from the MSB in the digital data
60
is masked, that is, the bit is changed to “0”, is generated and output to the priority encoder
53
.
Next, in the priority encoder
53
, a first “1” bit seen from the MSB in the first valid bit mask data
63
is detected and 4-bit second bit encode data
62
indicating the position of the bit is generated.
Below, the processing of each of the components of the FSPE encoder will be explained in detail with reference to a flow chart.
[Priority Encoder
51
]
FIG. 11
is a flow chart of the processing in the priority encoder
51
in FIG.
10
.
Step S
1
: “0×0f”, that is, a hexadecimal “0f”, is substituted for a variable “sft”.
Step S
2
: The digital data
60
“in” is shifted toward a least significant bit (LSB) by exactly the amount of the variable “sft”.
Step S
3
: It is judged whether or not the result of the shift at Step S
2
is “1”. When it is “1”, the processing of Step S
4
is carried out, while when it is not “1”, the processing at Step S
5
is carried out.
Step S
4
: The value “0×0f−sft” obtained by subtracting the variable “sft” from the “0×0f”, that is, the hexadecimal “0f”, is output as the first bit encode data
61
.
Step S
5
: The variable “sft” is reduced by “1”.
Step S
6
: It is judged whether or not the variable “sft” is 0 or more. When it is 0 or more, the processing of Step S
2
is carried out, while when not, the processing of Step S
7
is carried out.
Step S
7
: “0×00” is output as the first bit encode data
61
.
Note that the processing shown in
FIG. 11
is as shown in
FIG. 12
when written in a C language.
The processing in the priority encoder
53
is the same as that in the above priority encoder
51
except that the processing is performed on the first valid bit mask data
63
.
[First Valid Bit Mask Unit
52
]
FIG. 13
is a flow chart of processing in the first valid bit mask unit
52
in FIG.
10
.
Step S
11
: The value “0×0f”, that is, the hexadecimal “0f”, is substituted for the variable “sft”.
Step S
12
: The digital data
60
“in” is shifted toward the LSB by exactly the amount of the variable “sft”.
Step S
13
: It is judged whether or not the result of the shift at Step S
12
is “1”. When it is “1”, the processing of Step S
14
is carried out, while when it is not “1”, the processing at Step S
16
is carried out.
Step S
14
: The value “0×ff”, that is, the hexadecimal “ff”, is shifted toward the LSB by exactly “0×10−sft” obtained by subtracting the variable “sft” from “0×10”. The result of the shift becomes a “mask”.
Step S
15
: The digital data
60
“in” is shifted toward the LSB by exactly the amount of the “mask” obtained at Step S
14
. The result of the shift is output to the priority encoder
53
shown in
FIG. 10
as the first valid bit mask data
63
.
Step S
16
: The variable “sft” is reduced by “1”.
Step S
17
: It is judged whether or not the variable “sft” is 0 or more. When it is 0 or more, the processing of Step S
12
is carried out, while when not, the processing of Step S
18
is carried out.
Step S
18
: The value “0×00” is output to the priority encoder
53
as the first valid bit mask data
63
.
Note that the processing shown in
FIG. 13
is as shown as
FIG. 14
when written in a C language.
Summarizing the problem to be solved by the present invention, in the FSPE encoder
50
built in the above three-dimensional computer graphic system of the related art, as shown in
FIG. 10
, two 16-bit priority encoders
51
and
53
are necessary, so it suffers from a disadvantage that the apparatus becomes large in size.
Also, the path on which the first valid bit mask unit
52
and the priority encoder
53
for performing the 16-bit operation are placed becomes a critical path of the calculation processing time, therefore it suffers from a disadvantage that the processing time becomes long. There is also a disadvantage that the scale of the circuit becomes large.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an encoder, a method thereof, and a graphic processing apparatus capable of generating positional data of a first “1” bit and a second “1” bit seen from the MSB at a high speed with a compact apparatus configuration.
Another object of the present invention is to provide an encoder and a method thereof capable of generating positional data of a first “1” bit and a second “1” bit seen from an LSB at a high speed with a compact apparatus configuration.
To attain the above objects, according to a first aspect of the present invention, there is provided an encoder for detecting a first bit located closest to the MSB and a second bit located second-closest to the MSB among bits of a first level included in digital data of n bits (n is an integer not less than 2) and producing location information of the first bit and the second bit, comprising a bit number detecting means for detecti
Kita Katsuya
Mitsushita Tatsumi
Kananen Ronald P.
Luu Matthew
Rader Fishman & Grauer
Sajous Wesner
Sony Corporation
LandOfFree
Encoder, method thereof and graphic 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 Encoder, method thereof and graphic processing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoder, method thereof and graphic processing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588622