Method and apparatus for cache index hashing

Computer graphics processing and selective visual display system – Computer graphics display memory system – Logical operations

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C345S634000, C345S667000, C345S557000, C711S002000, C711S118000, C711S127000, C711S132000

Reexamination Certificate

active

06549210

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of information storage and retrieval, and, more specifically, to a technique for improving cache memory performance.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. ArtX, and all ArtX-based trademarks and logos are trademarks or registered trademarks of ArtX, Inc. in the United States and other countries.
2. Background Art
Computers are often used to display graphical information. In some instances, graphical data or images are “rendered” by executing instructions from an application that is drawing the data or image to a display. An image is a regular two dimensional array in which every element of the array is a digital quantity of energy such as light/heat/density, etc. An image may also be viewed as a discretely sampled digital representation of an energy continuum with the same number of elements in each row. The image can also be procedurally generated dynamically at the time of display by the computer program or sampling device, for example. A displayed image may be made up of a plurality of graphical objects. Examples of graphical objects include points, lines, polygons, and three dimensional solid objects.
If you looked closely at a television screen, computer display, magazine page, etc., you would see that an image is made up of hundreds or thousands of tiny dots, where each dot is a different color. These dots are known as picture elements, or “pixels” for short when they are on a computer display and as dots when printed on a page. The color of each pixel is represented by a number value. To store an image in a computer memory, the number value of each pixel of the picture is stored. The number value represents the color and intensity of the pixel.
The accuracy with which a document can be reproduced is dependent on the “resolution” of the pixels that make up the document. The resolution of a pixel is the size of the number value used to describe that pixel. The size of the number value is limited by the number of “bits” in the memory available to describe each pixel (a bit is a binary number having a value of 1 or 0). The greater the number of bits available per pixel, the greater the resolution of the document. For example, when only one bit per pixel is available for storage, only two values are available for the pixel. If two bits are available, four levels of color or intensity are available. While greater resolution is desirable, it can lead to greater use of data storage. For example, if each pixel is represented by a 32-bit binary number, 320,000 bits of information would be required to represent a 100×100 pixel image. Such information is stored in what is referred to as a “Frame Buffer” (or “G array”).
The process of converting graphics data and instructions into a display image is known as “pixel rendering.” During pixel rendering, color and other details can be applied to areas and surfaces of these objects using “texture mapping” techniques. In texture mapping, a texture image (also referred to as a texture map, or simply as a texture) is mapped to an area or surface of a graphical object to produce a visually modified object with the added detail of the texture image. A texture image may contain, for example, an array of RGB (red, green, blue) color values, intensity values, or opacity values.
As an example of texture mapping, given a featureless graphical object in the form of a cube and a texture image defining a wood grain pattern, the wood grain pattern of the texture image may be mapped onto one or more surfaces of the cube such that the cube appears to be made out of wood. Other examples of texture mapping include mapping of product logo texture images to computer-modeled products, or mapping of texture images containing vegetation and trees to a barren computer-modeled landscape. Textures mapped onto geometric surfaces may also be used to provide additional motion and spatial cues that surface shading alone might not be capable of providing. For example, a featureless sphere rotating about an axis appears static until an irregular texture image or pattern is mapped to its surface.
Texture mapping involves using a texture image having a function defined in texture space. Typically, the texture space is represented as a two dimensional space, with “S” and “T” indices defining orthogonal axes (e.g., horizontal and vertical). A texture image is represented in texture space as an array in S and T of discrete texture elements or values called “texels.” The texture image is warped or mapped from the texture space into an image space having an array of picture elements called “pixels.” The pixels are associated with orthogonal axis coordinates “X” and “Y” in the image space which define a viewing plane for display. Based on the particular mapping function, a correspondence is generated between pixels representing an object or primitive in the image space and texels representing a texture image in the texture space.
Typically, a two-dimensional texture or pattern image is mapped onto a two or three-dimensional surface. For a two-dimensional surface, X and Y coordinates may be sufficient for defining a mapping function between pixels forming the surface and texels forming the texture image. For a three-dimensional surface, a perspective coordinate or other depth cueing mechanism may be provided to indicate distance from the viewing plane defined by the X and Y axes. The perspective coordinate may then be applied to the mapping function. For example, as the perspective coordinate value for a surface region increases (i.e., the surface region is further from the viewing plane), the mapping of the texture image may be darkened and/or compressed (i.e., neighboring pixels in the surface region will span an increased number of texels in the texture image), or otherwise warped, relative to surface regions having a lower perspective coordinate value. Through the application of depth cueing, the viewer is provided with a sense of distance or depth when viewing the rendered pixels.
FIGS. 1A-1C
illustrate a mapping of a brick-pattern texture image in texture space to a triangle primitive (
100
) in image space.
FIG. 1A
illustrates triangle primitive
100
in image space prior to texture mapping.
FIG. 1B
illustrates the brick-pattern texture image in texture space.
FIG. 1C
illustrates triangle primitive
100
in image space after texture mapping has completed.
In
FIG. 1A
, triangle primitive
100
is defined by vertices at X,Y coordinate pixel locations P
A
(X
A
,Y
A
), P
B
(X
B
,Y
B
) and P
C
(X
C
,Y
C
), where X is the horizontal axis and Y is the vertical axis. Pixels defining the perimeter of triangle primitive
100
may be explicitly stored in memory, or, to reduce storage requirements for individual primitives, the perimeter pixels may be linearly interpolated from the vertices defined by pixel locations P
A
(X
A
,Y
A
), P
B
(X
B
,Y
B
) and P
C
(X
C
,Y
C
). The interior of triangle primitive
100
is formed by those pixel locations that lie within the defined perimeter. The surface of triangle primitive
100
in this example comprises the union of the perimeter pixels (including the vertices) and the interior pixels.
In
FIG. 1B
, a brick pattern is stored as a texture image referenced by S and T coordinates. The brick pattern may be mapped to pixels in image space by accessing texels at integer S and T coordinates. In accordance with a particular mapping function, pixel vertices P
A
, P
B
and P
C
of the triangle primitive correspond to S and T coordinates (S
A
,T
A
), (S
B
,T
B
) and (S
C
,T
C
), respectively. The orientation of the mapped vertices indicates rotation and scaling of triangle primitive
100
with respect to the S and T texture space.
FIG

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for cache index hashing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for cache index hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for cache index hashing will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3072812

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.