This invention relates to texture mapping computer graphics systems and, more particularly, to methods and apparatus for storing graphics data, such as texture map data, in a linearly allocated memory.
Computer graphics systems are used for displaying graphical representations of objects on a two-dimensional display screen. In a typical computer graphics system, an object to be represented on the display screen is broken down into multiple graphics primitives. Primitives are basic components of a graphics image and may include points, lines, vectors and polygons, such as triangles. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent a view of one or more objects being represented on the screen.
Typically, the primitives that define the three-dimensional object to be rendered are provided from a host computer, which defines each primitive in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitive in terms of the X,Y,Z coordinates of its vertices, as well as the R,G,B color values of each vertex. Rendering hardware interpolates the primitive data to compute the display screen pixels that represent each primitive, and the R,G,B values for each pixel.
Texture mapping is commonly used in computer graphics systems to provide improved surface detail. Texture mapping involves mapping a source image, referred to as a texture, onto a surface of a three-dimensional object, and thereafter mapping the textured three-dimensional object to the two-dimensional display screen. Texture mapping involves applying one or more point elements (texels) of a texture to each point element (pixel) of the displayed portion of the object to which the texture is being mapped. Texture mapping hardware is conventionally provided with information indicating the manner in which the texels in a texture map correspond to the pixels on the display screen that represent the object. Each texel in a texture map is defined by S and T coordinates which identify its location in the two-dimensional texture map. In the case of a three-dimensional texture map, each texel is defined by S, T and R coordinates. For each pixel, the corresponding texel or texels that map to it are accessed from the texture map and are incorporated into the final R,G,B values generated for the pixel to represent the textured object on the display screen.
Each pixel in an object primitive may not map in a one-to-one correspondence with a single texel in the texture map. Depending on the size of the object on the display screen and the size of the texture map, a single pixel may map to multiple texels, or a single texel may map to multiple pixels. To facilitate texture mapping, a series of MIP maps may be created for each texture. A series of MIP maps includes a base map that corresponds directly to the texture map and a series of filtered maps, wherein each successive map is reduced in size by a factor of two in each of the two texture map dimensions. The series of texture MIP maps associated with the object being rendered is stored in a local memory accessible by the texture mapping hardware.
The texture mapping hardware can access texture data from any of the series of MIP maps. The determination of which map to access to provide the texel data for any particular pixel is based on the number of texels to which the pixel maps. If the pixel maps in one-to-one correspondence with a single texel in the texture map, then the base map is accessed. However, if the pixel maps to 4, 16 or 64 texels, then different level maps in the series of maps are accessed because those maps store texel data representing an average of 4, 16 and 64 texels in the texture map.
A pixel may not map directly to any one texel in the selected map and may fall between two or more texels in a single map or may fall between two maps. In this case, interpolation is utilized to accurately produce texel data. The texel data corresponding to a pixel can be a weighted average of four texel entries in a single map or a weighted average of eight texels in the two closest maps.
It is generally understood that there is two-dimensional locality in graphics rendering. That is, when a pixel is rendered, it is likely that the next pixel rendered will be near that pixel in X and/or Y. High performance requires that the hardware be designed to take advantage of this locality. In particular, the rendering of each pixel requires one or more memory locations to be accessed. The required image data or texture data may be stored in a frame buffer memory. In accessing the required data, there are different memory latencies for different address combinations within the memory. In general, it is faster to access another word which is located in the same xe2x80x9cpagexe2x80x9d of memory than to access a word in a different page. This is because changing from one page to another requires closing the first page and opening the second, while accessing two data words in the same page does not carry this overhead. A typical memory may have two or four banks. Each bank is subdivided into a number of pages. In general, the best performance is obtained by accessing either the same page within any given bank or accessing a different bank. Consecutively accessing the same bank but a different page within that bank causes a large performance penalty.
For the reasons described above, rendering performance is affected by the way in which image data and texture data are stored in memory. One technique for MIP map texture storage which utilizes fixed, rectangular memory buffers is disclosed in U.S. Pat. No. 5,801,708 issued Sep. 1, 1998 to Alcorn et al. The disclosed technique is compatible with host computers which utilize Unix and X-windows operating systems. However, personal computers (PCs) typically employ a linear memory allocation scheme. The linear memory allocation scheme subdivides memory into blocks and then allocates a number of consecutive blocks for a given use. In a graphics system, a linear memory allocation scheme is convenient to allow flexible utilization of the memory, rather than dedicating memory to specific uses. However, a purely linear memory allocation scheme does not provide optimum rendering performance.
A modification of the linear memory allocation scheme, known as pseudo-linear frame buffer mapping, strikes a compromise between PC requirements for a linear, completely configurable frame buffer and the advantages of rectangular pages. Rather than treating the frame buffer as a linear array of words, this method treats the frame buffer as a linear array of blocks. Each block is a small two-dimensional array of memory, which is designed to provide optimized access when rendering with two-dimensional locality. A range of blocks can be allocated as a group and given a block stride to provide a larger two-dimensional area. The block stride establishes the X dimension of the image area or texture map in units of blocks.
Notwithstanding the advantages of the pseudo-linear frame buffer mapping technique, application of this technique to storage of a series of MIP maps does not provide optimum rendering performance. Accordingly, there is a need for improved methods and apparatus for texture map storage in a linearly allocated memory.
According to a first aspect of the invention, a method is provided for allocating correlated data sets to memory in a computer graphics system. The method comprises the steps of dividing each of the correlated data sets into blocks of data, the correlated data sets including at least first and second data sets, defining at least first and second subsets of each of the data sets, wherein the first subsets are correlated and the second subsets are correlated, and defining at least first and second areas of the memory. Blocks of data from the first subset of the first data set and the second subset of the second data set are stored in the first memory area. Blocks of data from the second subset of the first data set and the first subset of the second data set are stored in the second memory area. The blocks of data representing each data set are stored in consecutive blocks of the memory.
In one embodiment, the correlated data sets comprise a series of texture maps. In another embodiment, the correlated data sets comprise an image data set and a Z-data set.
According to another aspect of the invention, a method is provided for allocating texture data among first and second separately accessible areas of memory in a texture mapping computer graphics system. The method comprises the steps of dividing each texture map in a series of texture maps into a set of blocks of data, the series of texture maps including odd level texture maps and even level texture maps, defining first and second map areas of each texture map that has a width greater than one block, storing blocks of data from the first map areas of the odd level texture maps in the first memory area, storing blocks of data from the second map areas of the even level texture maps in the first memory area, storing blocks of data from the second map areas of the odd level texture maps in the second memory area, and storing blocks of data from the first map areas of the even level texture maps in the second memory area. The blocks of data representing each texture map in the series of texture maps are stored in consecutive blocks of memory.
Each of the steps of storing blocks of data may comprise allocating each of the blocks of data to two different memory banks. The step of allocating of each of the blocks of data to two different memory banks may comprise reversing the allocation of blocks of data to different memory banks in successive pages of the memory when one half of a row of blocks in a texture map is allocated to more than one page of the memory.
In one embodiment, each page in the memory includes eight blocks of data, and each page is divided between the first memory area and the second memory area. The step of defining first and second map areas may comprise dividing each texture map into left and right areas of equal size. The allocation of the left and right areas to the first and second memory areas is reversed in successive texture maps in the series of texture maps.
According to another aspect of the invention, apparatus is provided for allocating texture data among first and second separately accessible areas of memory in a texture mapping computer graphics system. The apparatus comprises means for dividing each texture map in a series of texture maps into a set of blocks of data, the series of texture maps including odd level texture maps and even level texture maps, means for defining first and second map areas of each texture map that has a width greater than one block, first means for storing blocks of data from the first map areas of the odd level texture maps in the first memory area, second means for storing blocks of data from the second map areas of the even level texture maps in the first memory area, third means for storing blocks of data from the second map areas of the odd level texture maps in the second memory area, and fourth means for storing blocks of data from the first map areas of the even level texture maps in the second memory area. The blocks of data representing each texture map in the series of texture maps are stored in consecutive blocks of memory.