Data structure for efficient retrieval of compressed texture...

Details Data structure for efficient retrieval of compressed texture... Data structure for efficient retrieval of compressed texture...

1998-07-31

2001-06-05

Brier, Jeffery (Department: 2672)

Computer graphics processing and selective visual display system

Display driving control circuitry

Physically integral with display elements

C345S205000, C345S205000, C345S440000, C345S519000

Reexamination Certificate

active

06243081

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to texture mapping in computer graphics systems. More particularly, the invention relates to data structures that enable efficient retrieval of compressed texture data from a memory system.
BACKGROUND
In the field of computer graphics, texture mapping is a known technique used to create the appearance of complexity on the surface of rendered objects without actually having to model every detail of the object's surface. Typically, the technique involves mapping a two-dimensional function or array (the texture) onto an object in three-dimensional object space and then projecting the resultant image back to two-dimensional screen space for display. The phrase “texture map” refers to the function or array that is used in the texture mapping process. A common two-dimensional texture map might consist of a repeatable pattern for representing a material, such as wood or marble for example. Three-dimensional texture maps are also used, but not as frequently. Three-dimensional texture maps are usually larger than two-dimensional texture maps. Texture maps are made up of a plurality of numerical values called texels. A texel's numerical value usually corresponds to an RGB color value and perhaps also to an alpha transparency value. (Other parameters may be included in texture maps in addition to, or in lieu of, RGB and alpha values.) A texel's location within a texture map may be designated using s,t coordinates.
A technique known as MIP mapping is also used in texture mapping. MIP mapping involves down-sampling a base texture map numerous times to develop a series of smaller texture maps, each of which represents the base map at a predetermined lower level of resolution. Typically, a map number is assigned to each map. For example, for a system in which two textures were stored, each at four different levels of resolution, eight unique map numbers would be required to refer to the texture maps individually. In systems that use MIP mapping, not only must the base map for each texture be stored in memory, but so must each of the downsampled maps for each texture. Thus, while texture maps yield important efficiencies for rendering complex images, they can become burdensome in terms of the amount of memory that is required to store them. Indeed, the size of the texture maps used to render an image can in some cases be larger than the rendered image itself.
One technique now being used to address the storage problem associated with texture maps is to store the texture maps in the system memory of the host computer rather than in a dedicated texture memory located within the graphics subsystem. This new technique is beneficial to the extent that it eliminates or reduces the need for a large, dedicated texture memory in the graphics subsystem. On the other hand, this new technique also creates a new problem for systems that utilize hardware rendering instead of software rendering: The rendering hardware of the graphics subsystem must make frequent use of the system bus to access large amounts of texture data stored in system memory. This places significant bandwidth demands on both the system bus and system memory.
Because of these memory space and bandwidth problems associated with texture mapping, it has become popular to logically partition stored texture maps into a number of equally-sized blocks. This is done because it is usually more efficient from a bus and memory utilization point of view to retrieve an entire block of texture data from system memory than to retrieve one texel at a time.
For the same reasons, it has also become popular to store texture maps in a compressed format. Various compression algorithms have been used for this purpose including JPEG, run-length encoding, Huffman encoding, vector quantization and Lempel-Ziv compression. Each of these algorithms may be classified in a number of different ways: First, is the algorithm lossy or lossless? Lossy algorithms frequently yield better compression rates than lossless ones, but they do so at the expense of image quality. Second, does the algorithm produce a compression ratio that is fixed or variable? In other words, will the algorithm compress every portion of an image to the same degree, or will it compress highly detailed portions of the image to a lesser degree than other portions of the image? It has been observed that lossless, variable-compression-rate algorithms are the most advantageous to use for texture mapping. This is because only lossless algorithms can preserve image quality perfectly throughout the compression/decompression process. And allowing variability in the compression ratio enables the greatest possible overall compression efficiency while preserving losslessness. Another factor of importance in choosing compression algorithms is whether and how easily the compressed texture data produced by the algorithm may be accessed randomly. It is often difficult to determine in advance how a given renderer will access a texture. Therefore, the ability to randomly access compressed texture data is extremely beneficial.
Yet another technique that has become popular is a combination of the abovedescribed methods: A texture map may be logically partitioned into blocks, and then compressed one block at a time. If the compressed texture map is stored in system memory as a set of individual compressed blocks, then a desired piece of texture data may be retrieved from system memory by retrieving only the individual compressed block that contains the desired data. Using this technique, the entire compressed texture map does not have to be retrieved from memory simply to access an individual piece of texture data within it. Moreover, because the block is retrieved in compressed format, additional bus and memory bandwidth savings are realized.
A primary problem arises, however, when attempting to implement the latter technique with data produced by variable-compression-ratio algorithms: By definition, use of a variable-compression-ratio algorithm means that the individual compressed blocks that represent the texture map will not all have the same length. Indeed, it is possible that each of the individual compressed blocks will have a different length even though the uncompressed texture map they represent was broken down into equally-sized blocks prior to compression. This complicates determining the starting address and length of a compressed block prior to accessing it. If a constant-compression-ratio algorithm is used to compress the blocks, then this problem can be avoided; the compressed blocks in such a case might simply be stored contiguously in system memory, and the offset required to address a particular block could be determined simply as a function of the block number and the known common block length. But constant-compression-ratio algorithms are usually lossy, and are undesirable for that reason.
It is therefore an object of the invention to provide a data structure that will enable efficient retrieval of compressed texture data from a memory.
It is a further object of the invention to provide a data structure that will yield particular efficiencies when the compressed texture data to be retrieved has been produced using a variable-compression-ratio algorithm.
SUMMARY OF THE INVENTION
In one aspect, the invention includes a compressed texture data structure stored in a computer-readable storage medium. The inventive compressed texture data structure enables efficient retrieval of compressed texture data from the computer-readable storage medium by a computer graphics display system. The compressed texture data structure includes at least first and second compressed texture data segments. The first compressed texture data segment starts at a first segment starting memory location, ends at a first segment ending memory location, has a first segment length, and contains a first compressed texture data block having a first compressed texture data block length. The second compressed texture data segment starts at a second segment s

Affiliated with

Also associated with

Rating

Data structure for efficient retrieval of compressed texture... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data structure for efficient retrieval of compressed texture..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for efficient retrieval of compressed texture... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2509153