Computer graphics processing and selective visual display system – Computer graphics display memory system – Addressing
Reexamination Certificate
2000-02-29
2003-09-02
Tung, Kee M. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Addressing
C345S572000, C345S582000, C345S552000
Reexamination Certificate
active
06614443
ABSTRACT:
TECHNICAL FIELD
The present invention is related generally to the field of computer graphics, and more particularly, to addressing graphics data, such as texture data, in a computer graphics processing system.
BACKGROUND OF THE INVENTION
A graphics accelerator is a specialized graphics processing subsystem for a computer system that relieves a host processor from performing all the graphics processing involved in rendering a graphics image on a display device. The host processor of the computer system executes an application program that generates geometry information used to define graphics elements on the display device. The graphics elements that are displayed are typically modeled from polygon graphics primitives. For example, a triangle is a commonly used polygon for rendering three dimensional objects on the display device. Setup calculations are initially performed by the host processor to define the triangle primitives. The application program then transfers the geometry information from the processor to the graphics processing system so that the triangles may be modified by adding shading, hazing, or other features before being displayed. The graphics processing system, as opposed to the processor, has the task of rendering the corresponding graphics elements on the display device to allow the processor to handle other system requests.
Some polygon graphics primitives also include specifications to map texture data, representative of graphic images, within the polygons. Texture mapping refers to techniques for adding surface detail, or a texture map, to areas or surfaces of the polygons displayed on the display device. A typical texture map is represented in a computer memory as a bitmap or other raster-based encoded format, and includes point elements, or “texels,” which reside in a (s, t) texture coordinate space. The graphics data representing the texels of a texture map are stored in a memory of the computer system and used to generate the color values of point elements, or “pixels” of the display device which reside in an (x, y) display coordinate space. As illustrated in
FIG. 1
, the memory in which the texture data is stored is typically implemented using a one-dimensional memory space partitioned into several memory pages. The memory is allocated by addressing the texture data in a sequential fashion. That is, the resulting physical memory address for the texture data of a particular texel is an offset value that corresponds to the first byte of the texture data for the particular texel.
Generally, the process of texture mapping occurs by accessing the texels from the memory that stores the texture data, and transferring the texture data to predetermined points of the graphics primitive being texture mapped. The (s, t) coordinates for the individual texels are calculated and then converted to physical memory addresses. The texture map data are read out of memory and applied within the respective polygon in particular fashions depending on the placement and perspective of their associated polygon. The process of texture mapping operates by applying color or visual attributes of texels of the (s, t) texture map to corresponding pixels of the graphics primitive on the display. Thus, color values for pixels in (x, y) display coordinate space are determined based on sampled texture map values. Where the original graphics primitives are three dimensional, texture mapping often involves maintaining certain perspective attributes with respect to the surface detail added to the graphics primitive. After texture mapping, a version of the texture image is visible on surfaces of the graphics primitive with the proper perspective.
The color value for a pixel is usually determined by using a method of bilinear filtering. In bilinear filtering, the color values of the four texels closest to the respective location of the pixel are weighted and a resulting color value for the pixel is interpolated therefrom. For example, illustrated in
FIG. 1
is a portion of four rows of texels from a texture map
10
. The color value for pixel P
a,a
is determined from the color value of texels C
0,0
, C
0,1
, C
1,0
, and C
1,1
. Similarly, the color value for pixel P
b,b
is determined from the color value of texels C
0,1
, C
0,2
, C
1,1
, and C
1,2
.
As illustrated by
FIG. 1
, using bilinear filtering to determine the color value of pixels in an (x, y) display coordinate space requires texture data from two different rows of texels. Where a memory paging scheme is employed for the memory in which the texture data is stored, it is often the case that the memory pages are large enough to contain data for only one row of the texture map. Consequently, when retrieving the texture data to calculate the color of a pixel, an average of two page misses will occur because two different memory pages must be accessed to retrieve the required texture data. Page misses result in inefficient data access of the texture data.
A conventional approach to the problem of multiple page misses is dividing the memory space in which the texture data is stored into several two-dimensional (2D) segments. As illustrated in
FIG. 2
, although the width of the texture map is divided into several 2D segments, the texture data for texels of several adjacent rows may be stored on a common memory page. Thus, the number of page misses occurring during texture application is reduced. However, allocating memory in a 2D manner is difficult to accomplish, and results in inefficient use of available memory. For example, memory fragmentation issues are exacerbated when attempting to allocate memory in 2D segments. Furthermore, it is generally difficult to find memory allocation algorithms that can optimally allocate memory in 2D manner.
Therefore, there is a need for a system and method for allocating memory in a one-dimensional memory space that results in fewer page misses than conventional approaches.
SUMMARY OF THE INVENTION
A method and apparatus for mapping graphics data of a texture map into virtual two-dimensional (2D) memory arrays implemented in a one-dimensional memory space. The texture map is partitioned into 2
u+v
two-dimensional arrays where each of the arrays has a dimension of 2
m
bytes×2
n
rows, and the graphics data is then mapped from a respective two-dimensional array into the one-dimensional memory space. Mapping occurs by calculating an offset value based on the coordinates of a respective texel of the texture map. The offset value is represented by a first group of m bits, a second group of u bits, a third group of n bits, and a fourth group of v bits, arranged so that the first group represents the least significant bits and the fourth group represents the most significant bits. The arrangement of the groups of the offset value are then reordered to produce a respective memory address for the one-dimensional memory space. The order of the groups for the respective memory address is first, third, second, and fourth groups, from least to most significant bits.
REFERENCES:
patent: 5495563 (1996-02-01), Winser
patent: 5726689 (1998-03-01), Negishi et al.
patent: 6104415 (2000-08-01), Gossett
Dorsey & Whitney LLP
Micro)n Technology, Inc.
Tung Kee M.
LandOfFree
Method and system for addressing graphics data for efficient... 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 system for addressing graphics data for efficient..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for addressing graphics data for efficient... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3075133