Computer graphics processing and selective visual display system – Computer graphics display memory system – Texture memory
Reexamination Certificate
2000-10-06
2003-09-09
Tung, Kee M. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Texture memory
C345S557000, C345S582000
Reexamination Certificate
active
06618053
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention pertains in general to computer graphics and in particular to a texture loading pipeline in a three-dimensional graphics system.
2. Background Art
Texture mapping has become a very common feature in computer systems such as game consoles, personal computers, and high-end workstations. Traditionally, texture mapping is used to add realism to computer graphics images without increasing the amount of geometry necessary to produce the images.
The concept of texture mapping is relatively simple: stretch an arbitrary image and paste it onto a three-dimensional (3-D) geometry. Mapping the texture to the 3-D geometry consists of computing, for each picture element (pixel) in the final image, the corresponding texture element (texel) in the texture image. There are many different techniques for performing this computation. In general, each of the techniques treats each pixel as a surface that has a corresponding surface in the texture image. The texture surface covered by a given pixel can contain an arbitrary, and not necessarily integer, number of texels of different colors. Each pixel, however, can have only one color. Usually, the color of the pixel is determined by taking multiple samples from the texture and filtering the samples at different stages of the rendering to derive the appropriate color.
When the textures are large, it is difficult to sample and filter the texture at the rate needed to rapidly draw 3-D scenes from changing perspectives. Specialized computer systems with large memories and fast graphics pipelines can use a brute force approach to process large textures at rates necessary to support the scene changes. However, dedicated hardware is often prohibitively costly and cannot be used in mass market platforms.
A common technique for overcoming this hurdle and dealing with large textures is a “mipmap.” A mipmap is a storage technique that stores a texture at multiple levels of resolution. A mipmap resembles an inverted pyramid. The top of the mipmap represents the largest texture having the highest amount of detail. Each level below the top has a resolution a power of two smaller than the previous level, and holds that much less detail. For example, if the top mipmap level of a two dimensional texture holds 64 texels, the immediately lower level has 16 texels. Subsequent levels hold four and one texel.
When a mipmapped texture is mapped on a polygon, the mipmap level that corresponds most closely to the size of the polygon is used. For example, if the polygon is a square having four pixels on a side, the mipmap level having 16 texels will be mapped onto the polygon. In effect, the mipmap reduces hardware demands by performing the image processing and filtering (i.e., scales down the texture to fit the polygon) ahead of time.
Storing a mipmap requires only ⅓ more memory than storing the original texture. However, storing even this much more data creates a problem. Textures must be stored in fast memory in order to meet the needs of renderer. The fastest systems use special memory for texture storage while slower systems use the fast video memory in the display buffer for texture memory. Textures can easily be too large to fit in these memories. For example, a texture representing North America at 25 meter resolution occupies more than 200 gigabytes of memory.
One solution to this problem is to subdivide the geometry. For example, a texture representing North America can be divided into four areas, which, in turn, can be subdivided into smaller areas. The texture can be divided and subdivided in the same manner as the geometry into smaller textures called “tiles.” Since the tiles are smaller than the original texture, the tiles can be stored, manipulated, and processed at the rate necessary to support 3-D rendering. Tiling, however, creates visible artifacts in the rendered scene, such as seams at the edges of the tiles. It may be possible to eliminate the artifacts from one viewpoint in the final image, but not from all possible viewpoints. Another disadvantage of tiling is that a complex database must be used to store the tiles and substantial processing time is required to regenerate the tiles whenever the texture is modified. Further, tiling requires that the underlying geometry be divided on the texture boundaries such that edges of the texture tiles match the edges of the geometry tiles, thereby making both automatic and real-time geometric reconstruction of underlying surfaces extremely difficult.
Another problem with mipmaps is that the large source texture might be composed of many smaller textures linked together. Some of textures might be from different sources and, therefore, have different resolutions (i.e., texels per unit of coordinate space). For example, a texture map of a large area, such as North America, might use low-resolution sources for textures of less populated areas and high-resolution sources for textures of more populated areas. Mipmaps do not provide a general way to represent the different resolutions of the textures. The fixed requirement that levels be separated by powers of two limit the use of mipmaps in this regard.
Accordingly, there is a need for a way to represent, store, and process texture data in a way that supports real-time 3-D rendering. The solution to this need should support the use of large textures and textures having differing resolutions and coordinate spaces.
DISCLOSURE OF THE INVENTION
The above needs are met by a texture loading pipeline that operates on a source texture having one or more levels of detail. Each level of detail (LOD) represents a rectangular subset of a particular region of the source texture at a particular resolution. There can be arbitrary relationships between the regions and resolutions represented by particular levels of detail. Thus, the source texture can be sparse and different levels of detail can represent different regions of the source texture at different resolutions.
Preferably, there are multiple instances of the texture loading pipeline, with each instance corresponding to one of the levels of detail in the source texture. The texture for a LOD is preferably subdivided into tiles and stored in a storage space. The storage space can be local to the computer system executing the texture loading pipeline and/or remote from the computer system. For example, the storage space can be located on a hard drive or CD-ROM attached to the computer system and/or in communication with the computer system through a network. The texture tiles can be compressed or uncompressed.
Texture tiles are retrieved from the storage space by an asynchronous request queue and stored in a tile cache. Compressed texture tiles are preferably stored in a compressed tile cache. An asynchronous decompression queue decompresses the texture tiles in the compressed tile cache and stores the decompressed tiles in a decompressed tile cache.
Textures in the region of interest are paged from the tile cache into a texture cache. The texture cache is preferably located in a high-speed memory, such as a dedicated texture memory in a graphics adapter. The textures in the region of interest, i.e., the region of the global coordinate space for which textures are requested, are preferably selected for paging via toroidal roaming. In toroidal roaming, an arbitrary rectangle, or other bounding shape, specifies the textures in the tile cache to page into the texture cache. The rectangle moves as the region of interest changes. Texels that leave the region of interest are deleted from the texture cache, texels that enter the region of interest are paged into the texture cache, and texels remaining in the region of interest are left in the texture cache.
By definition, the size of the region of interest is bounded by the resolution of the display
118
. The resolution of the display, refresh rate, and color depth of the textures, therefore, also define an upper bound on the rate of data, or bandwidth, required to update the texture cache. The real bandwidth, however, is o
Fenwick & West LLP
Tung Kee M.
Vicarious Visions Inc.
LandOfFree
Asynchronous multilevel texture pipeline does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Asynchronous multilevel texture pipeline, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asynchronous multilevel texture pipeline will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3039858