Computer graphics processing and selective visual display system – Computer graphics display memory system – Memory allocation
Reexamination Certificate
1998-07-17
2002-04-02
Tung, Kee M. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Memory allocation
C345S555000, C345S544000
Reexamination Certificate
active
06366289
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to display memory management in a computer.
BACKGROUND OF THE INVENTION
There is a growing trend in the computer industry to make the graphical interface of a computer more compelling and realistic. Increasingly, applications for desktop computers involve more sophisticated 2D and 3D graphics and video. With the increase in computing power and improvements in multitasking operating systems, it is becoming more common for computers to concurrently execute multiple programs with user interfaces employing sophisticated graphics and video.
The images used to create sophisticated displays can require a great deal of memory and memory bandwidth. This requires the computer system to have more memory for storing, constructing and displaying images. In addition, the system must have enough memory bandwidth to allow read and write operations to update images and to construct the display image.
Computer systems such as a typical desktop personal computer (PC) or workstation generally use a frame buffer to store image data for each picture element on a display monitor such as a cathode ray tube (CRT) or Liquid Crystal Display (LCD). Each picture element on the monitor's screen has a corresponding instance of image data commonly referred to as a “pixel.” To convert the image data into an image visible on the screen, a display controller periodically reads the pixels in the frame buffer (usually around 60-75 times per second) and converts them into signals used to energize the picture elements on the screen.
To change the display image, the host processor of the computer modifies the pixels in the frame buffer. For instance, in conventional PC architectures, the computer issues read and write requests to a linear address space assigned to the frame buffer to read pixels and write new pixels into the frame buffer. In most computers, the operating system includes a software interface to the display hardware. Software executing in the computer can invoke functions in this interface to modify the display image. The software interface, in turn, communicates with the display hardware. For example, a program may invoke a bit block transfer function in the software interface to copy a new block of pixels to the frame buffer. The software interface translates this request into write requests to modify the contents of the frame buffer.
Some techniques have been developed to reduce the memory and memory bandwidth problems associated with frame buffer display architectures. One common way to support color displays with less memory is to use a color table or palette. A color table is an array of colors, where each color is typically represented by a Red, Green and Blue component. Each of these components is customarily represented by an 8 bit number. Rather than storing 24 bits for each pixel, each pixel represents an index into the color table. The display controller looks up the color value for each pixel as it generates the display's control signals. The color table, therefore, allows the computer to support a reasonable variety of colors while reducing the amount of memory to implement a frame buffer.
The color table approach reduces memory requirements, but is inherently limited because the table only provides a limited number of colors to choose from. An 8 bit index can only support 256 colors. While reducing the number of bits per pixel saves memory, it tends to decrease image quality.
Higher resolution workstations are capable of displaying from 1 to 2 million pixels for 24 bit per pixel (bpp) formats. These systems can achieve higher fidelity images because each pixel has 8 bits each for RGB components. These systems are expensive, however, because they typically use a frame buffer with enough memory to store a high resolution display image in 24 bpp format.
The use of a conventional frame buffer to store data for each picture element on the display screen is a major limitation of existing systems because it requires a great deal of memory. One solution is to use a different architecture that does not require a conventional frame buffer. However, it is difficult to change architectures because most of the operating systems and graphics support software is designed to interface with a conventional frame buffer that has a linear address space. New architectures can render current operating system and graphic support software obsolete.
An alternative display architecture supporting linear addressing to a compressed display image is described in co-pending U.S. patent application Ser. No. 08/695,163 filed Aug. 7, 1996, issued as U.S. Pat. No. 5,936,616, entitled “Method and System for Accessing and Displaying A Compressed Display Image In A Computer System,” which is hereby incorporated by reference. In addition to maintaining a display image in a compressed format, this architecture also allows applications to build display images by overlaying multiple image layers. A related application describing image layering in detail is co-pending U.S. patent application Ser. No. 08/671,412, filed Jun. 27, 1996, issued as U.S. Pat. No. 5,867,160, entitled “Method and System for Generating Images Using Gsprites,” which is hereby incorporated by reference.
For interactive graphics applications, it is usually disadvantageous to store a display image in a compressed format because the process of decompressing the image makes it more time consuming to access and modify the image before displaying it. For example, if a group of pixels needs to be updated to change the display image, the pixels need to be fetched from memory, decompressed and then modified. This process adds additional latency to the display process. Techniques for hiding this latency are described in co-pending U.S. patent application Ser. No. 08/670,553, filed Jun. 27, 1996, issued as U.S. Pat. No. 5,880,787, entitled “Method and System For Accessing Texture Data In Environments With High Latency In A Graphics Rendering System,” which is hereby incorporated by reference.
SUMMARY OF THE INVENTION
The invention provides a display controller and method for managing memory accesses to images stored in partially compressed form. The invention may be used to manage a display image, used to refresh the display screen, as well as other “off-screen” images that may or may not be visible on the screen. Examples of off-screen images include source bitmaps that are copied to the display image (e.g., copied in bit block transfer operations), texture maps, and sprites or overlay images that are composited to form the display image. In contrast to a conventional frame buffer, the display image is stored in randomly accessible blocks of pixels in memory. A virtual frame buffer controller maps requests for pixels in a frame buffer address format to addresses of pixels in blocks scattered randomly in physical memory. To improve performance, the controller leaves blocks in an uncompressed format until it is necessary to free up memory. The system compresses least recently used blocks when necessary to free up memory for other decompressed blocks.
One aspect of the invention is a method for managing pixel accesses to uncompressed and compressed blocks of the display image. The method maps the pixel address of a read or write request to a memory location within a block of pixels located at an arbitrary place in physical memory. The block of pixels is either in a compressed or uncompressed format. A data structure in the form of a list of pixel blocks keeps track of the physical memory location of each block in the display image, and whether the block is compressed or uncompressed. When a pixel access request maps to an uncompressed block, the method computes the address of the pixel in the block and allows the operation to proceed. When a pixel access request maps to a compressed block, the method initiates a decompression process for the block, allocates memory for the block and updates the data structure to reflect that the block is uncompressed.
The method summarized above is implemented in a display control
Klarquist & Sparkman, LLP
Microsoft Corporation
Tung Kee M.
LandOfFree
Method and system for managing a display image in compressed... 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 managing a display image in compressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for managing a display image in compressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2846088