Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-10-29
2001-07-10
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C706S032000
Reexamination Certificate
active
06260054
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer-graphics systems, and more particularly to reciprocal generators for texture-map perspective correction.
BACKGROUND OF THE INVENTION
Higher-integration IC's (integrated circuits) and lower costs have allowed for increasingly complex graphics systems in personal computers (PCs). The two-dimensional dimensional ‘blackboard’ of yesterday's PC's monitor is coming to life as three-dimensional objects are rendered in real-time using 3D graphics engines. Realistic-looking objects are rendered by extending the basic pixel (picture element) to include texture attributes comprised of texels (texture elements).
Complex calculations are required to transform and render 3D objects on the PC's two-dimensional screen. These objects are often rendered with surface textures. These textures are defined by texture maps. Texture maps are 2 dimensional arrays of pixels, or texels, that are transformed onto the surface in order to render finer detail.
The texture map describes the texture pattern of the surface as it appears to a viewer directly over the surface at a 90-degree normal to the surface. However, when a surface is viewed at an oblique angle, the surface texture is compressed. If viewed through a parallel projection, meaning the eye is at infinity, the compression is linear across the screen. However, if viewed through a perspective projection, meaning the eye is at a finite distance from the screen, the compression is non-linear. Thus some perspective correction is needed. This correction is accomplished by altering the address of the texel selected from the texture map.
FIG. 1
shows a texture map. The pixels in the texture map that form the surface pattern are arranged in a 2-dimensional coordinate space (u,v). One of the pixels in the texture map is selected by calculating the (u,v) coordinate of the texture map from the non-perspective-corrected pixel coordinates.
The 3D graphics engine generates a non-corrected coordinate that corresponds to (u/w, v/w). The (u,v) coordinate is obtained by multiplying u/w and v/w by w. However, w is not directly known. Instead, the reciprocal of w, called rw, is generated by the 3D engine or the applications-programming interface (API) along with (u/w, v/w). From rw, (u,v) is calculated as u=(u/w)*(1/rw) and v=(v/w)*(1/rw). The reciprocal of rw, 1/rw, must be calculated. The perspective for each pixel is corrected by the rw value.
Perspective correction thus requires the generation of the reciprocal of the rw value.
FIG. 2
highlights that w is obtained by performing a reciprocal function on the rw input. Then the reciprocal (w) is multiplied by the coordinates u/w and v/w to obtain the (u,v) coordinate for the texture map. Often a large table in memory such as table lookup
10
is used to perform directly the reciprocal function. Table lookups are desirable since the complex calculations can be performed ahead of time and stored in the table for all possible input values. Thus arithmetic logic circuits are not needed for the reciprocal function.
Unfortunately, reciprocal functions produce a large range of outputs. The rw value can itself be any number from near zero to 2
16
for a 16-bit rw. Values of rw that are near zero produce very large reciprocals. For example, the reciprocal of 0.001 is 1000, while the reciprocal of 0.000001 is 1,000,000. On the other hand, the reciprocal of 2
15
is 2
−15
, a very small number. The wide dynamic range of the reciprocal function presents a challenge when using lookup tables, since the tables can require many entries, requiring a large and expensive memory.
Although the rw, u/w, and v/w values are provided as 32-bit fixed-point variables, these could be converted to a floating-point format to more efficiently perform the reciprocal function. However, standard floating point formats may require very expensive mechanization.
What is desired is a reciprocal generator for perspective correction of texture maps in a 3D graphics system. It is desired to minimize the transistor count associated with the implementation while maintaining sufficient fidelity in the output in order to avoid aliasing effects. It is desired to maintain a high pipeline throughput rate for each pixel while minimizing the transistor count. It is desired to minimize the size of a lookup table for a reciprocal function. It is desired to efficiently organize entries in the lookup table to provide sufficient precision over a large dynamic range of inputs and outputs. A better approximation of a reciprocal function is desired when using a limited-size lookup table and attend antiogic circuits. A high-speed reciprocal generator that uses a lookup table and a minimal set of logic circuits and operates over a wide dynamic range is desired.
SUMMARY OF THE INVENTION
A reciprocal generator has an input bus. A leading-zero detector is coupled to the input bus. It generates a scale factor indicating a number of leading zeros of an input value on the input bus. A shifter is responsive to the leading-zero detector. It shifts the input bus by a number of bit-positions indicated by the leading-zero detector to produce a shifted input.
A lookup table is coupled to the shifter. It has entries, with each entry having an initial reciprocal field and a slope field. The lookup table outputs an initial reciprocal and a slope for an entry selected by a portion of the shifted input. An interpolator is coupled to the lookup table. It generates a reciprocal base from the initial reciprocal and the slope output by the lookup table. The reciprocal of the input bus is the reciprocal base from the interpolator scaled by the scale factor from the leading-zero detector. Thus the reciprocal is generated from the lookup table and the scale factor from the leading-zero detector.
In further aspects the input bus has an input range. The input range is divided into a plurality of sections. The lookup table does not have separate entries for each of the plurality of sections. Instead, the lookup table has entries for a last section, the last section having largest input values. Thus entries for the last section but not all sections are stored in the lookup table. Each successive section has twice an input range of a previous section. Thus successive sections are doubled in input-width.
In further aspects the interpolator further has a multiplier coupled to the lookup table and coupled to the shifter. It forms a product of lower bits of the shifted input and the slope from the lookup table. An adder is coupled to the multiplier and to the lookup table. It forms a sum of the product from the multiplier and the initial reciprocal from the lookup table. The sum from the adder is output as the reciprocal base.
In still further aspects the leading-zero detector is coupled to only upper bits of the input bus and not connected to lower bits of the input bus. Thus the leading-zero detector detects a limited number of leading zeros.
In other aspects the lookup table further stores entries for a first section. The first section has smallest input values. The smallest input values are less than input values from all other sections in the plurality of sections. Thus the lookup table contains entries for only the first section and the last section, but not for intermediate sections. The lookup table has a reduced number of entries than a table having separate entries for all sections.
In other aspects a scale mux is coupled to the leading-zero detector. It outputs the scale factor from the leading-zero detector for all sections except the first section, but it outputs a scale factor from the lookup table when the input value on the input bus is in the first section. The lookup table stores entries for the first section and the last section. The entries for the first section contain the initial reciprocal and a stored scale factor. The stored scale factor is output by the scale mux as the scale factor for the initial reciprocal. Thus scale factors for the first section are stored in the lookup table
Lin Tao
Rosman Andrew
Auvinen Stuart T.
NeoMagic Corp.
Ngo Chuong Dinh
LandOfFree
Reciprocal generator using piece-wise-linear segments of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reciprocal generator using piece-wise-linear segments of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reciprocal generator using piece-wise-linear segments of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441485