Frame buffer organization and reordering Number:6,833,834 from the United States Patent and Trademark Office (PTO) owispatent

Title: Frame buffer organization and reordering

Abstract: A graphics system includes a frame buffer, a write address generator, and a pixel buffer. A burst of pixels received from the frame buffer may not be in display order. In one embodiment, a write address generator calculates a write address for each pixel in the burst of pixels output from the frame buffer. The write address corresponds to a relative display order within the burst for each respective pixel. Each pixel in the burst is stored to its write address in the pixel buffer. This way, the pixels in the burst are stored in display order within the pixel buffer.

Patent Number: 6,833,834 Issued on 12/21/2004 to Wasserman,   et al.

---

Inventors:	Wasserman; Michael A. (Redwood City, CA); Lavelle; Michael G. (Saratoga, CA); Kehlet; David C. (Los Altos, CA); Tang; Yan Yan (Mountain View, CA); Kubalska; Ewa M. (San Jose, CA)
Assignee:	Sun Microsystems, Inc. (Santa Clara, CA)
Appl. No.:	021096
Filed:	December 12, 2001

---

Current U.S. Class:	345/537 ; 345/545; 345/570; 345/574
Field of Search:	345/564,570,572-574,503,520,531,533,537,545

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5544306		August 1996		Deering et al.
	5796412		August 1998		Kim
	5945997		August 1999		Zhao et al.
	6310657		October 2001		Chauvel et al.
	6323868		November 2001		Paluch et al.
	6496192		December 2002		Shreesha et al.
	2003/0016302		January 2003		Fudge et al.

Other References

3D-RAM Spec 8 Press Release dated May 20, 1997, 2 pages. . 3D-RAM Spec www.mitsubishichips.com/data/datasheets/memory/mempdf/ds/c99001.pdf, (date Aug. 1996 given in press release, see A3), 170 pages. . Pacifica RAMDAC spec BT497/8 from Brooktree, Feb. 1996, 53 pages. . "Sun.TM. Elite3D Frame Lock and Buffer Swap Synchronization Installation Guide", Aug. 1999, 42 pages..

Primary Examiner: Chauhan; Ulka J.
Attorney, Agent or Firm: Meyertons Hood Kivlin Kowert & Goetzel, P.C. Hood; Jeffrey C.

---

Claims

---

What is claimed is:

1. A graphics system comprising: a frame buffer configured to output pixels, wherein the pixels output by the frame buffer are output in a first order different from display order; a write address generator configured to calculate a write address for each pixel output by the frame buffer, wherein each write address corresponds to a relative display order of a respective pixel; and a pixel buffer coupled to receive the pixels output from the frame buffer in the first order and configured to store the received pixels at the write addresses calculated by the write address generator.

2. The graphics system of claim 1, wherein the frame buffer is configured to output the pixels in bursts.

3. The graphics system of claim 2, wherein each write address corresponds to the relative display order of a respective pixel within a burst of pixels.

4. The graphics system of claim 2, wherein the pixel buffer comprises a plurality of partitions, wherein each partition is configured to store at least one burst of pixels for a respective display channel.

5. The graphics system of claim 4, wherein the pixel buffer is configured to store the pixels as pixel pairs.

6. The graphics system of claim 4, wherein the write address generator comprises a base address generator, wherein the base address generator is configured to generate a same base address for all of the pixels output in a first burst from the frame buffer.

7. The graphics system of claim 6, wherein the write address generator comprises an offset generator configured to generate an offset for each pixel that corresponds to each pixel's relative display order with respect to each of the other pixels in the first burst.

8. The graphics system of claim 7, wherein the write address generator is configured to concatenate the base address and the offset to produce the write address.

9. The graphics system of claim 2, wherein the pixel buffer comprises a plurality of blocks, wherein a first portion of the blocks are each configured to store a portion of the pixels received in a first burst.

10. The graphics system of claim 9, wherein a first display channel's allocated blocks of pixels are intermingled with a second display channel's allocated blocks of pixels within the pixel buffer.

11. The graphics system of claim 9, wherein the write address generator is configured to track which blocks in the pixel buffer are allocated and to track which display channel each allocated block stores pixels for.

12. The graphics system of claim 9, wherein the write address generator is further configured to track a relative display order of each of the blocks that are storing pixels for a first display channel.

13. The graphics system of claim 9, wherein the write address generator comprises a base address generator configured to generate a first base address of a first block for a first portion of the pixels output in the first burst and to generate a second base address of a second block for a second portion of the pixels output in the first burst.

14. The graphics system of claim 13, further comprising an offset generator configured to generate an offset for each pixel in the first portion of the pixels that corresponds to each pixel's relative display order within the first portion of the pixels.

15. The graphics system of claim 1, wherein the frame buffer comprises one or more 3D-RAM memory devices.

16. The graphics system of claim 1, wherein the frame buffer comprises multiple memory banks.

17. The graphics system of claim 16, wherein the multiple memory banks are interleaved.

18. The graphics system of claim 1, wherein the pixels output by the frame buffer are output in the first order, different from the display order, because the frame buffer is configured for improved rendering efficiency.

19. A graphics system comprising: a frame buffer configured to output pixels, wherein the pixels output by the frame buffer are not output in display order; a pixel buffer coupled to store the pixels output by the frame buffer in an order that the pixels are output from the frame buffer; and a read address generator configured to calculate a read address for each pixel stored in the pixel buffer, wherein each read address corresponds to a relative display order of a respective pixel, and wherein successively generated read addresses access pixels in the pixel buffer in display order; wherein the frame buffer is configured to output the pixels in bursts; wherein the pixel buffer comprises a plurality of partitions; and wherein each partition is configured to store at least one burst of pixels for a respective display channel.

20. The graphics system of claim 19, wherein the pixel buffer is configured to store the pixels as pixel pairs.

21. The graphics system of claim 19, wherein the read address generator comprises a base address generator, wherein the base address generator is configured to generate a same base address for all of the pixels output in a first burst from the frame buffer.

22. The graphics system of claim 21, wherein the read address generator comprises an offset generator configured to generate an offset that corresponds to each pixel's relative display order within the first burst.

23. The graphics system of claim 22, wherein the read address generator is configured to concatenate the base address and the offset to produce the read address.

24. A method of reordering pixels received from a frame buffer, comprising: receiving a plurality of pixels from the frame buffer, wherein the pixels are received in an order other than display order; storing the pixels in a pixel buffer in the order they are received; generating a read address for each pixel stored in the pixel buffer, wherein each read address corresponds to a relative display order of a respective pixel; and reading the pixels out of the pixel buffer using successively generated read addresses generated by said generating, wherein successively generated read addresses address pixels in display order; wherein said receiving comprises receiving a burst of pixels; wherein the relative display order comprises the relative display order within the burst; wherein the pixel buffer comprises a plurality of partitions, wherein each partition is configured to store pixels for a respective display channel, and wherein said storing comprises storing at least one burst of pixels for a first display channel in a first partition.

25. The method of claim 24, further comprising storing the pixels as pixel pairs.

26. The method of claim 24, wherein said generating comprises generating a base address, wherein a same base address is generated for all of the pixels output in a first burst from the frame buffer.

27. The method of claim 26, wherein said generating comprises generating an offset for each pixel in the first burst, wherein each pixel's offset corresponds to that pixel's relative display order within the first burst.

28. The method of claim 27, wherein said generating comprises concatenating the base address and the offset to produce the read address.

29. A method of reordering pixels received from a frame buffer, comprising: receiving a plurality of pixels from the frame buffer, wherein the pixels are received in an order other than display order; generating a write address for each pixel received from the frame buffer, wherein each write address corresponds to a relative display order of a respective pixel; and storing the pixels in the pixel buffer using successively generated write addresses generated by said generating.

30. The method of claim 29, wherein said receiving comprises receiving a burst of pixels from the frame buffer.

31. The method of claim 30, wherein each write address corresponds to the relative display order within the burst of pixels.

32. The method of claim 30, wherein said storing comprises storing at least one burst of pixels for a respective display channel within a partition in the pixel buffer.

33. The method of claim 32, further comprising storing the pixels as pixel pairs.

34. The method of claim 32, wherein said generating comprises generating a base address, wherein a same base address is generated for all of the pixels output in a first burst from the frame buffer.

35. The method of claim 34, wherein said generating comprises generating an offset that corresponds to each pixel's relative display order with respect to each of the other pixels in the first burst.

36. The method of claim 35, wherein said generating comprises concatenating the base address and the offset to produce the write address.

37. The method of claim 30, wherein said generating comprises generating write addresses for the pixels so that the pixels in a first burst are stored in at least one block in the pixel buffer.

38. The method of claim 37, wherein a first display channel's blocks of pixels are intermingled with a second display channel's blocks of pixels within the pixel buffer.

39. The method of claim 37, further comprising tracking which blocks in the pixel buffer are allocated and tracking which display channel each allocated block stores pixels for.

40. The method of claim 37, further comprising tracking a relative display order of each of the blocks that are storing pixels for a first display channel.

41. The method of claim 37, wherein said generating further comprises generating a first base address for a first block and generating an offset for each pixel within a first portion of the first burst, wherein the offset corresponds to each pixel's relative display order within the first burst.

42. The method of claim 41, wherein said generating further comprises concatenating the first base address and the offset to generate the write address for each pixel in the first portion.

43. The method of claim 29, wherein the frame buffer comprises one or more 3D-RAM memory devices.

44. The method of claim 29, wherein the frame buffer comprises multiple memory banks.

45. The method of claim 44, wherein the multiple memory banks are interleaved.

46. The method of claim 45, wherein the multiple memory banks are interleaved for improved write efficiency into the frame buffer.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to graphics systems and, more particularly, to the organization and reordering of display information in the frame buffer.

2. Description of the Related Art

A computer system typically relies upon its graphics system for producing visual output on the computer screen or display device. Early graphics systems were only responsible for taking what the processor produced as output and displaying it on the screen. In essence, they acted as simple translators or interfaces. Modem graphics systems, however, incorporate graphics processors with a great deal of processing power. They now act more like coprocessors rather than simple translators. This change is due to the recent increase in both the complexity and amount of data being sent to the display device. For example, modern computer displays have many more pixels, greater color depth, and are able to display more complex images with higher refresh rates than earlier models. Similarly, the images displayed are now more complex and may involve advanced techniques such as anti-aliasing and texture mapping.

As a result, without considerable processing power in the graphics system, the CPU would spend a great deal of time performing graphics calculations. This could rob the computer system of the processing power needed for performing other tasks associated with program execution and thereby dramatically reduce overall system performance. With a powerful graphics system, however, when the CPU is instructed to draw a box on the screen, the CPU is freed from having to compute the position and color of each pixel. Instead, the CPU may send a request to the video card stating, "draw a box at these coordinates." The graphics system then draws the box, freeing the processor to perform other tasks.

Generally, a graphics system in a computer is a type of video adapter that contains its own processor to boost performance levels. These processors are specialized for computing graphical transformations, so they tend to achieve better results than the general-purpose CPU used by the computer system. In addition, they free up the computer's CPU to execute other commands while the graphics system is handling graphics computations. The popularity of graphics applications, and especially multimedia applications, has made high performance graphics systems a common feature in many new computer systems. Most computer manufacturers now bundle a high performance graphics system with their computing systems.

In many applications, it may be useful to have two monitors or displays connected to the same computer system. For example, in some graphical editing applications, it is desirable to use one monitor to show a close-up of an area being edited, while another monitor shows a wider field of view of the object or picture being edited. Alternatively, some users may configure one monitor to display the object being edited and the other monitor to display various palettes or editing options that can be used while editing. Another situation where multiple displays are useful occurs when several users are connected to a single computer. In such a situation, it may be desirable for each user to have their own display. In another situation, it may simply be desirable to have multiple displays that each display a different portion of an image in order to provide a larger display than would otherwise be possible. Another example is stereo goggles, which present different images to their wearer's left and right eyes in order to create a stereo viewing effect. These examples illustrate just a few of the many situations where it is useful to have multiple displays connected to the same computer system.

Given the complexity and expense of many graphics systems, it may be desirable to provide a graphics system that can support multiple displays without duplicating the entire graphics system. Thus, there is a need to be able to share portions of a graphics system between multiple display channels.

SUMMARY

Various embodiments of a graphics system and method for reordering pixels output from a frame buffer are disclosed. In one embodiment, the graphics system may include a frame buffer, a write address generator, and a pixel buffer. The frame buffer is configured to output pixels, but the pixels may not be output in display order. For example, the frame buffer may be configured so that pixels may be more efficiently written into the frame buffer (e.g., based on the arrangement of interleaves within the frame buffer and the input configuration of the frame buffer). The pixels may be stored in the frame buffer in a way that makes it inefficient to read them from the frame buffer in display order. Accordingly, pixels may be output from the frame buffer in an order other than display order. The write address generator may be configured to calculate a write address for each pixel output by the frame buffer. Each write address corresponds to a relative display order of a respective pixel. The pixel buffer is coupled to store the pixels output by the frame buffer at the write addresses calculated by the write address generator.

In some embodiments, the graphics system may be configured to output the pixels in bursts. The pixel buffer may include multiple partitions, and each partition may be configured to store at least one burst of pixels for a respective display channel. The write address generator may include a base address generator, which may generate the same base address for all of the pixels output in a first burst, and an offset address generator, which may generate an offset for each pixel that corresponds to each pixel's relative display order within the first burst. The write address generator may be configured to concatenate the base address and the offset to produce the write address. By storing the pixels at their respective write addresses, the pixels received in each burst may be stored in display order within the pixel buffer.

In some embodiments the write address generator may be configured to calculate write addresses for the pixels so that the pixels in a first burst are stored in at least one block in the pixel buffer. The write address generator may be configured to store each display channel's blocks of pixels in any unallocated blocks in the pixel buffer. The write address generator may also be configured to track those blocks in the pixel buffer that are already allocated, which display channel each allocated block is storing pixels for, and the relative display order of the blocks storing pixels for each display channel.

In some embodiments of the graphics system, the frame buffer may include one or more 3D-RAM memory devices, multiple memory banks, and/or multiple interleaves.

In alternative embodiments, the graphics system may include a frame buffer, a read address generator, and a pixel buffer. The frame buffer may not output pixels in display order. Pixels output from the frame buffer may be stored in the pixel buffer in the order they are read from the frame buffer. A read address generator may calculate a read address for each pixel stored in the pixel buffer. Each read address corresponds to a relative display order of a respective pixel. Successively generated read addresses access pixels in the pixel buffer in display order.

BRIEF DESCRIPTION OF THE DRAWINGS

A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:

FIG. 1 is an illustration of a typical computer system and display;

FIG. 2 is a drawing of one embodiment of a computer system;

FIG. 3 illustrates one embodiment of graphics system;

FIG. 4 illustrates one embodiment of a media processor that may be included in a graphics system;

FIG. 5 illustrates one embodiment of a hardware accelerator that may be included in a graphics system;

FIG. 6 illustrates one embodiment of a video output processor that may be included in a graphics system;

FIG. 7 shows one embodiment of a dual-channel, demand driven video output processor;

FIG. 8 illustrates another embodiment of a dual-channel, demand driven video output processor;

FIG. 9 shows one embodiment of a method of sharing an output pipeline between two display channels;

FIG. 10A shows another embodiment of a method of sharing an output pipeline between two display channels;

FIG. 10B shows another embodiment of a method of sharing an output pipeline between two display channels;

FIG. 11A shows one embodiment of a frame buffer;

FIG. 11B shows one embodiment of a 3D-RAM;

FIG. 12A shows one embodiment of a method of arbitrating between two request streams in a way that reduces inefficiencies;

FIG. 12B shows one embodiment of a method of arbitrating between two request streams in a way that reduces frame buffer inefficiency;

FIG. 12C shows another embodiment of a method of arbitrating between two request streams in a way that reduces frame buffer inefficiency;

FIG. 13 illustrates one embodiment of a pixel write controller;

FIG. 14 shows one embodiment of a write address generator;

FIG. 15 is a flowchart of one embodiment of a method of reordering pixels;

FIG. 16 is a flowchart of another embodiment of a method of reordering pixels;

FIG. 17 shows one embodiment of a graphics system configured to synchronize multiple display channels;

FIG. 18 shows one embodiment of a display timing generator;

FIG. 19 illustrates synchronization signals and blanking intervals according to one embodiment;

FIG. 20A shows one embodiment of a method of synchronizing multiple display channels;

FIG. 20B shows another embodiment of a method of synchronizing multiple display channels;

FIG. 20C shows yet another embodiment of a method of synchronizing multiple display channels;

FIG. 21 illustrates one embodiment of a graphics system configured to pan across a portion of a frame buffer image;

FIG. 22 shows one embodiment of a method of panning across a frame buffer image;

FIG. 23 shows one embodiment of a graphics system that includes multiple signature analysis registers;

FIG. 24 shows one embodiment of a signature analysis register; and

FIG. 25 shows one embodiment of a method of capturing a signature from a frame of display information.

While the invention admits various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form (or forms) disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the present invention as defined by the appended claims. Note, the headings are for organizational purposes only and are not meant to be used to limit or interpret the description or claims. Furthermore, note that the word "may" is used throughout this application in a permissive sense (i.e., having the potential to, being able to), not a mandatory sense (i.e., must)." The term "include", and derivations thereof, mean "including, but not limited to". The term "connected" means "directly or indirectly connected", and the term "coupled" means "directly or indirectly coupled".

DETAILED DESCRIPTION OF EMBODIMENTS

Computer System--FIG. 1

Referring now to FIG. 1, one embodiment of a computer system 80 that includes a graphics system is shown. The graphics system may be comprised in any of various systems, including a computer system, network PC, Internet appliance, a television, including HDTV systems and interactive television systems, personal digital assistants (PDAs), virtual reality systems, and other devices which display 2D and or 3D graphics, among others.

As shown, the computer system 80 comprises a system unit 82 and a video monitor or display device 84 coupled to the system unit 82. The display device 84 may be any of various types of display monitors or devices (e.g., a CRT, LCD, or gas-plasma display). Various input devices may be connected to the computer system, including a keyboard 86 and/or a mouse 88, or other input device (e.g., a trackball, digitizer, tablet, six-degree of freedom input device, head tracker, eye tracker, data glove, or body sensors). Application software may be executed by the computer system 80 to display graphical objects on display device 84.

Computer System Block Diagram--FIG. 2

Referring now to FIG. 2, a simplified block diagram illustrating the computer system of FIG. 1 is shown. Elements of the computer system that are not necessary for an understanding of the present invention are not shown for convenience. As shown, the computer system 80 includes a central processing unit (CPU) 102 coupled to a high-speed memory bus or system bus 104 also referred to as the host bus 104. A system memory 106 may also be coupled to high-speed bus 104.

Host processor 102 may comprise one or more processors of varying types, e.g., microprocessors, multi-processors and CPUs. The system memory 106 may comprise any combination of different types of memory subsystems, including random access memories, (e.g., static random access memories or "SRAMs," synchronous dynamic random access memories or "SDRAMs," and Rambus dynamic access memories or "RDRAM," among others) and mass storage devices. The system bus or host bus 104 may comprise one or more communication or host computer buses (for communication between host processors, CPUs, and memory subsystems) as well as specialized subsystem buses.

In FIG. 2, a graphics system 112 is coupled to the high-speed memory bus 104. The graphics system 112 may also be coupled to a separate peripheral bus that is coupled to the memory bus 104. The 3-D graphics system 112 may be coupled to the bus 104 by, for example, a crossbar switch or other bus connectivity logic. It is assumed that various other peripheral devices, or other buses, may be connected to the high-speed memory bus 104. It is noted that the graphics system may be coupled to one or more of the buses in computer system 80 and/or may be coupled to various types of buses. In addition, the graphics system may be coupled to a communication port and thereby directly receive graphics data from an external source, e.g., the Internet or a network. As shown in the figure, one or more display devices 84 may be connected to the graphics system 112 comprised in the computer system 80.

Host CPU 102 may transfer information to and from the graphics system 112 according to a programmed input/output (I/O) protocol over host bus 104. Alternatively, graphics system 112 may access the memory subsystem 106 according to a direct memory access (DMA) protocol or through intelligent bus mastering.

A graphics application program conforming to an application programming interface (API) such as OpenGL or Java 3D may execute on host CPU 102 and generate commands and data that define a geometric primitive (graphics data) such as a polygon for output on display device 84. As defined by the particular graphics interface used, these primitives may have separate color properties for the front and back surfaces. Host processor 102 may transfer this graphics data to memory subsystem 106. Thereafter, the host processor 102 may operate to transfer the graphics data to the graphics system 112 over the host bus 104. In another embodiment, the graphics system 112 may read in geometry data arrays over the host bus 104 using DMA access cycles. In yet another embodiment, the graphics system 112 may be coupled to the system memory 106 through a direct port, such as the Advanced Graphics Port (AGP) promulgated by Intel Corporation.

The graphics system may receive graphics data from any of various sources, including the host CPU 102 and/or the system memory 106, other memory, or from an external source such as a network, e.g., the Internet, or from a broadcast medium, e.g., television, or from other sources.

Note while graphics system 112 is depicted as part of computer system 80, graphics system 112 may also be configured as a stand-alone device (e.g., with its own built-in display). Graphics system 112 may also be configured as a single chip device or as part of a system-on-a-chip or a multi-chip module. Additionally, in some embodiments, certain elements of the illustrated graphics system 112 may be implemented in software.

Graphics System--FIG. 3

Referring now to FIG. 3, a functional block diagram illustrating one embodiment of graphics system 112 is shown. Note that many other embodiments of graphics system 112 are possible and contemplated. Graphics system 112 may comprise one or more media processors 14, one or more hardware accelerators 18, one or more texture buffers 20, one or more frame buffers 22, and one or more video output processors 24. Graphics system 112 may also comprise one or more digital-to-analog converters (DACs) 26 and/or one or more video encoders 28. Media processor 14 and/or hardware accelerator 18 may be any suitable type of high performance processor (e.g., specialized graphics processors or calculation units, multimedia processors, DSPs, or general purpose processors).

In some embodiments, media processor 14 and hardware accelerator 18 may be comprised within the same integrated circuit. In other embodiments, portions of media processor 14 and/or hardware accelerator 18 may be comprised within separate integrated circuits.

As shown, graphics system 112 may include an interface to a host bus (e.g., host bus 104 in FIG. 2) or peripheral bus to enable graphics system 112 to communicate with a host system (e.g., computer system 80). More particularly, host bus 104 may allow a host processor to send commands to the graphics system 112. In one embodiment, host bus 104 may be a bi-directional bus.

Each functional block of graphics system 112 is described in more detail below.

Media Processor--FIG. 4

FIG. 4 shows one embodiment of media processor 14. As shown, media processor 14 operates as the interface between graphics system 112 and computer system 80 by controlling the transfer of data between graphics system 112 and computer system 80. In some embodiments, media processor 14 may also be configured to perform transform, lighting, and/or other general-purpose processing on graphical data.

Transformation refers to manipulating an object and includes translating the object (i.e., moving the object to a different location), scaling the object (i.e., stretching or shrinking), and rotating the object (e.g., in three-dimensional space, or "3-space").

Lighting refers to calculating the illumination of the objects within the displayed image to determine what color and or brightness each individual object will have. Depending upon the shading algorithm being used (e.g., constant, Gourand, or Phong), lighting may be evaluated at a number of different locations. For example, if constant shading is used (i.e., each pixel of a polygon has the same lighting), then the lighting need only be calculated once per polygon. If Gourand shading is used, then the lighting is calculated once per vertex. Phong shading calculates the lighting on a per-pixel basis.

As illustrated, media processor 14 may be configured to receive graphical data via host interface 11. A graphics queue 148 may be included in media processor 14 to buffer a stream of data received via the accelerated port of host interface 11. The received graphics data may comprise one or more graphics primitives. As used herein, the term graphics primitive may include polygons, parametric surfaces, splines, NURBS (non-uniform rational B-splines), sub-divisions surfaces, fractals, volume primitives, voxels (i.e., three-dimensional pixels), and particle systems. In one embodiment, media processor 14 may also include a geometry data preprocessor 150 and one or more microprocessor units (MPUs) 152. MPUs 152 may be configured to perform vertex transform, lighting calculations, and programmable functions and to send results to hardware accelerator 18. MPUs 152 may also have read/write access to texels (i.e. the smallest addressable unit of a texture map, which is used to "wallpaper" a three-dimensional object) and pixels in the hardware accelerator 18. Geometry data preprocessor 150 may be configured to decompress geometry, to convert and format vertex data, to dispatch vertices and instructions to the MPUs 152, and to send vertex and attribute tags or register data to hardware accelerator 18.

As shown, media processor 14 may have other possible interfaces, including an interface to a memory. For example, as shown, media processor 14 may include direct Rambus interface 156 to a direct Rambus DRAM (DRDRAM) 16. A memory such as DRDRAM 16 may be used for program and data storage for MPUs 152. DRDRAM 16 may also be used to store display lists and/or vertex texture maps.

Media processor 14 may also include interfaces to other functional components of graphics system 112. For example, media processor 14 may have an interface to another specialized processor such as hardware accelerator 18. In the illustrated embodiment, controller 160 includes an accelerated port path that allows media processor 14 to control hardware accelerator 18. Media processor 14 may also include a direct interface, such as bus interface unit (BIU) 154, which provides a direct port path to memory 16 and to hardware accelerator 18 and video output processor 24 via controller 160.

Hardware Accelerator--FIG. 5

One or more hardware accelerators 18 may be configured to receive graphics instructions and data from media processor 14 and to perform a number of functions on the received data according to the received instructions. For example, hardware accelerator 18 may be configured to perform rasterization, 2D or 3D texturing, pixel transfers, imaging, fragment processing, clipping, depth cueing, transparency processing, set-up, and/or screen space rendering of various graphics primitives occurring within the graphics data. Each of these features is described separately below.

Clipping refers to the elimination of graphics primitives or portions of graphics primitives that lie outside of a 3D view volume in world space. The 3D view volume may represent that portion of world space that is visible to a virtual observer (or virtual camera) situated in world space. For example, the view volume may be a solid truncated pyramid generated by a 2D view window and a viewpoint located in world space. The solid truncated pyramid may be imagined as the union of all rays emanating from the viewpoint and passing through the view window. The viewpoint may represent the world space location of the virtual observer. In most cases, primitives or portions of primitives that lie outside the 3D view volume are not currently visible and may be eliminated from further processing. Primitives or portions of primitives that lie inside the 3D view volume are candidates for projection onto the 2D view window.

Set-up refers to mapping primitives to a three-dimensional viewport. This involves translating and transforming the objects from their original "world-coordinate" system to the established viewport's coordinates. This creates the correct perspective for three-dimensional objects displayed on the screen.

Screen-space rendering refers to the calculation performed to generate the data used to form each pixel that will be displayed. For example, hardware accelerator 18 may calculate "samples." Samples are points that have color information but no real area. Samples allow hardware accelerator 18 to "super-sample," or calculate more than one sample per pixel. Super-sampling may result in a higher quality image.

Hardware accelerator 18 may also include several interfaces. For example, in the illustrated embodiment, hardware accelerator 18 has four interfaces. Hardware accelerator 18 has an interface 161 (referred to as the "North Interface") to communicate with media processor 14. Hardware accelerator 18 may be configured to receive commands from media processor 14 through this interface. Additionally, hardware accelerator 18 may include an interface 176 to bus 32. Bus 32 may connect hardware accelerator 18 to boot PROM 30 and/or video output processor 24. Boot PROM 30 may be configured to store system initialization data and/or control code for frame buffer 22. Hardware accelerator 18 may also include an interface to a texture buffer 20. For example, hardware accelerator 18 may interface to texture buffer 20 using an eight-way interleaved texel bus that allows hardware accelerator 18 to read from and write to texture buffer 20. Hardware accelerator 18 may also interface to a frame buffer 22. For example, hardware accelerator 18 may be configured to read from and/or write to frame buffer 22 using a four-way interleaved pixel bus.

The vertex processor 162 may be configured to use the vertex tags received from the media processor 14 to perform ordered assembly of the vertex data from the MPUs 152. Vertices may be saved in and/or retrieved from a mesh buffer 164.

The render pipeline 166 may be configured to receive vertices and convert them to fragments. The render pipeline 166 may be configured to rasterize 2D window system primitives (e.g., dots, fonts, Bresenham lines, polygons, rectangles, fast fills, and BLITs (Bit Block Transfers, which move a rectangular block of bits from main memory into display memory, which may speed the display of moving objects on screen)) and 3D primitives (e.g., smooth and large dots, smooth and wide DDA (Digital Differential Analyzer) lines, triangles, polygons, and fast clear) into pixel fragments. The render pipeline 166 may be configured to handle full-screen size primitives, to calculate plane and edge slopes, and to interpolate data down to pixel tile resolution using interpolants or components such as r, g, b (i.e., red, green, and blue vertex color); r2, g2, b2 (i.e., red, green, and blue specular color from lit textures); a (alpha); and z, s, t, r, and w (texture coordinates components).

In embodiments using supersampling, the sample generator 174 may be configured to generate samples from the fragments output by the render pipeline 166 and to determine which samples are inside the rasterization edge. Sample positions may be defined in loadable tables to enable stochastic sampling patterns.

Hardware accelerator 18 may be configured to write textured fragments from 3D primitives to frame buffer 22. The render pipeline 166 may send pixel tiles defining r, s, t and w to the texture address unit 168. The texture address unit 168 may determine the set of neighboring texels that are addressed by the fragment(s), as well as the interpolation coefficients for the texture filter, and write texels to the texture buffer 20. The texture buffer 20 may be interleaved to obtain as many neighboring texels as possible in each clock. The texture filter 170 may perform bilinear, trilinear or quadlinear interpolation. The pixel transfer unit 182 may also scale and bias and/or lookup texels. The texture environment 180 may apply texels to samples produced by the sample generator 174. The texture environment 180 may also be used to perform geometric transformations on images (e.g., bilinear scale, rotate, flip) as well as to perform other image filtering operations on texture buffer image data (e.g., bicubic scale and convolutions).

In the illustrated embodiment, the pixel transfer MUX 178 controls the input to the pixel transfer unit 182. The pixel transfer unit 182 may selectively unpack pixel data received via north interface 161, select channels from either the frame buffer 22 or the texture buffer 20, or select data received from the texture filter 170 or sample filter 172.

The pixel transfer unit 182 may be used to perform scale, bias, and/or color matrix operations, color lookup operations, histogram operations, accumulation operations, normalization operations, and/or min/max functions. Depending on the source of and operations performed on the processed data, the pixel transfer unit 182 may then output the data to the texture buffer 20 (via the texture buffer MUX 186), the frame buffer 22 (via the texture environment unit 180 and the fragment processor 184), or to the host (via north interface 161). For example, in one embodiment, when the pixel transfer unit 182 receives pixel data from the host via the pixel transfer MUX 178, the pixel transfer unit 182 may be used to perform a scale and bias or color matrix operation, followed by a color lookup or histogram operation, followed by a min/max function. The pixel transfer unit 182 may then output data to either the texture buffer 20 or the frame buffer 22.

Fragment processor 184 may be used to perform standard fragment processing operations such as the OpenGL fragment processing operations. For example, the fragment processor 184 may be configured to perform the following operations: fog, area pattern, scissor, alpha/color test, ownership test (WID), stencil test, depth test, alpha blends or logic ops (ROP), plane masking, buffer selection, pick hit/occlusion detection, and/or auxiliary clipping in order to accelerate overlapping windows.

Texture Buffer 20

Texture buffer 20 may include several SDRAMs. Texture buffer 20 may be configured to store texture maps, image processing buffers, and accumulation buffers for hardware accelerator 18. Texture buffer 20 may have many different capacities (e.g., depending on the type of SDRAM included in texture buffer 20). In some embodiments, each pair of SDRAMs may be independently row and column addressable.

Frame Buffer 22

Graphics system 112 may also include a frame buffer 22. In one embodiment, frame buffer 22 may include multiple memory devices (such as the M5M410092B 3D-RAM products developed by Mitsubishi). Frame buffer 22 may be configured as a display pixel buffer, an offscreen pixel buffer, and/or a supersample buffer. Furthermore, in one embodiment, certain portions of frame buffer 22 may be used as a display pixel buffer, while other portions may be used as an offscreen pixel buffer and supersample buffer. In some embodiments (e.g., if frame buffer 22 includes 3D-RAM devices), the frame buffer may be configured to perform certain operations on display information (e.g., transparency, WLUT, etc.).

Output Processor--FIG. 6

An output processor 24 may also be included within graphics system 112. The output processor 24 may buffer and process display information output from frame buffer 22. For example, the output processor 24 may be configured to read bursts of pixels from frame buffer 22. The output processor 24 may also be configured to perform double buffer selection (dbsel) if the frame buffer 22 is double-buffered, overlay transparency (using transparency/overlay unit 190), plane group extraction, gamma correction, psuedocolor or color lookup or bypass, and/or cursor generation. For example, in the illustrated embodiment, the output processor 24 includes WID (Window ID) lookup tables (WLUTs) 192 and gamma and color map lookup tables (GLUTs, CLUTs) 194. The output processor 24 may also be configured to support two output streams to two displays using the two independent raster timing generators 196. For example, one raster (e.g., 196A) may drive a 1280.times.1024 CRT while the other (e.g., 196B) may drive a NTSC or PAL device with encoded television video.

DAC 202 may operate as the final output stage of graphics system 112. The DAC 202 translates the digital pixel data received from GLUT/CLUTs/Cursor unit 194 into analog video signals that are then sent to a display device. In one embodiment, DAC 202 may be bypassed or omitted completely in order to output digital pixel data in lieu of analog video signals. This may be useful when a display device is based on a digital technology (e.g., an LCD-type display or a digital micro-mirror display).

DAC 202 may be a red-green-blue digital-to-analog converter configured to provide an analog video output to a display device such as a cathode ray tube (CRT) monitor. In one embodiment, RGB DAC 202 may be configured to provide a high resolution RGB analog video output at dot rates of 240 MHz. Similarly, encoder 200 may be configured to supply an encoded video signal to a display. For example, encoder 200 may provide encoded NTSC or PAL video to an S-Video or composite video television monitor or recording device.

In other embodiments, the output processor 24 may output pixel data to other combinations of displays. For example, by outputting pixel data to two DACs 202 (instead of one of each of DAC 202 and encoder 200), video output processor 24 may drive two CRTs. Alternatively, by using two encoders 200, video output processor 24 may supply appropriate video input to two television monitors. Generally, many different combinations of display devices may be supported by supplying the proper output device and/or converter for that display device.

Dual-channel, Demand Driven Output Processor

In many applications, it may be desirable to share a single graphics system such as graphics system 112 between multiple display channels. Furthermore, it may be desirable to share a single graphics system between two or more independent display channels that do not have synchronized blanking intervals.

In order to serve multiple independent display channels, it may be beneficial to present data to each channel based on that channel's actual demand as opposed to its theoretical demand. A particular channel's theoretical demand is typically a precalculated ratio of how many pixels that channel needs, on average, per cycle. Theoretical demand ignores the fact that a particular display channel may require more pixels at certain times and less pixels at others. For example, a channel may not require pixels during the cycle(s) that occur during vertical and/or horizontal blanking periods or intervals (i.e., the period between each frame and/or line of display data). That channel's actual demand during the non-blanking periods (i.e., the periods during which display data is being displayed) may thus be higher than the average demand in the precalculated ratio reflects. Similarly, that channel's actual demand during the blanking interval may be less than its theoretical demand.

The difference between actual and theoretical demand becomes important when multiple display channels are being served from the same frame buffer. When display channels with synchronized blanking intervals are served based on theoretical demand, when one channel stalls for a blanking interval, the other channel stalls, too, and thus both build up a surplus of output data during the blanking interval that they may then use during their higher-demand, non-blanking interval. However, if channels that do not have synchronized blanking intervals are served based on their theoretical demand, this beneficial build-up of data may not occur for one or more of the channels. For example, one channel may end up without any display data being available when it is needed, while at the same time another channel may have a surplus of display data available during a blanking interval.

Thus, in order to adequately serve independent displays, it may be beneficial to serve the displays based on their actual, not theoretical, demand. FIG. 7 shows an example of one embodiment of a graphics system configured to serve two independent display channels based on their actual demand. Note that even though the system shown in FIG. 7 is described as allowing displays with independent blanking intervals to share the same frame buffer, the system may also be compatible with displays that do have synchronized blanking intervals.

As shown in FIG. 7, a display information buffer 701 stores data for both channels, A and B. The display information buffer 701 may be configured to output data to one of the channels in response to receiving a request from one of the channels. For example, in one embodiment, the display information buffer 701 may be a frame buffer configured to output bursts of display information. In another embodiment, the display information buffer 701 may be a pixel buffer configured to output pairs of pixels.

Two requesters 709 may be configured to assert requests based on a corresponding channel's actual demand for display information. An arbiter 705 intercepts the channels' requests and selects one of the channels' requests to forward to the display information buffer 701. In one embodiment, the arbiter 705 determines which request to forward by determining which channel is neediest, i.e., which channel needs display data the soonest. For example, if the channels each have a display data output queue, the neediest channel may be the channel with the lowest level of data in its queue.

The requesters 709 for each channel may be configured to assert a request when certain conditions occur. For example, a channel's requester 709 may begin asserting a request after a vertical blanking period has finished and continue asserting requests until the beginning of the next vertical blanking interval. However, in many embodiments (e.g., embodiments in which the display information buffer 701 is configured to output bursts of graphics data), it may be preferable to have each channel structure its requests so that it can prefetch data. By prefetching data, each channel may be able to ensure that its data needs are met by taking into account the latency of the request process and the delay that may result from having to wait for another channel's request(s) to be served. Thus, in these embodiments, the requesters 709 may be configured to begin asserting requests at some time before the end of a vertical blanking interval and to cease asserting requests at some time before the beginning of the next vertical blanking interval.

In another embodiment, the requesters 709 may be configured to assert a request when their corresponding channel's level of display information in its display output queue 821 falls below a certain threshold. For example, requester 709A may be configured to assert a request when the level of display output queue 821A falls below half full.

FIG. 8 shows another embodiment of a shared output pipeline. FIG. 8 shows an output processor similar to that shown in FIG. 6, with the addition of several requesters 809 and arbiters 805 and 817, and the inclusion of a pixel buffer 815. In this embodiment, two display streams share graphics system resources. There are two stages of shared resources, referred to as the "wholesale" loop and the "retail" loop. These loops are illustrated in FIG. 8, as are final "consumer" loops for each display channel. The wholesale loop may be configured to output relatively large amounts of display information (e.g., bursts) in response to a request, while the retail loop may operate using smaller transfers (e.g., pairs of pixels). Thus, by requesting data from the wholesale loop, a channel may prefetch display information in anticipation of its actual demand. The wholesale loop's fairly large granularity (e.g., bursts of data) may encourage prefetching, because a channel that fails to request data soon enough from the wholesale loop may not have enough display information available for display at a later time. The finer granularity of the retail loop's request system allows more fine-tuning based on each channel's current demand.

In the wholesale loop, the two streams each assert requests for the frame buffer 22 to output a certain amount of display information such as pixels or samples. Each stream's requester 809 may be configured to assert a request in response to certain conditions that indicate each particular stream's data requirements. For example, each channel's requester 809 may be configured to request display information far enough in advance that, assuming the maximum possible latency of the wholesale loop, the channel will receive enough pixels when they are needed. For example, in one embodiment, each channel's requester 809 may be configured to begin asserting requests slightly before the end of a vertical blanking interval for that channel in order to accurately prefetch data. Similarly, since the data is being prefetched, each channel's requester may be configured to cease issuing requests slightly before the beginning of the vertical blanking interval. During these request times, each channel's requester may also concentrate requests between the time just before the end of a horizontal blanking period and just before the next horizontal blanking period begins, depending on the granularity of the wholesale loop. Multiple requests may be issued for each channel in order to retrieve a full frame from the frame buffer 22. By ceasing requests during the blanking interval, additional resources in the output processing pipeline may become available to perform operations normally performed during the blanking interval such as multi-buffer synchronization and WLUT update posting.

Thus, each channel's requester 809 outputs a request to the frame buffer 22. The arbiter 805 controls which, if any, of these requests is actually forwarded to the frame buffer 22. The arbiter 805 may estimate which channel will run out of pixels the soonest, and pass that channel's request to the frame buffer 22. For example, in one embodiment, the arbiter may receive a count of the number of valid blocks in that channel's block queue (BQ1 and BQ2) in the pixel buffer 815. If the number of blocks is above a certain threshold, the arbiter 805 may decide that channel is not "needy" and thus not forward its request. If, however, the number of valid blocks is below the threshold, the channel is needy and its request may be forwarded. If both channels have asserted requests at the same time, the arbiter 805 may first determine if either channel's block count is below the threshold. If neither channel is needy, the arbiter 805 may determine that neither request should be forwarded. If instead only one channel qualifies as needy, that channel's request may be forwarded. However, if both channel's block counts are below the threshold, the arbiter 805 may compare the valid block counts for each channel. The channel with the greater deficit (below the threshold) of blocks is the neediest channel, and its request may be forwarded. The threshold level may be selected based on the latency of the later stages in the output pipeline. For example, the threshold level may be a level that keeps enough display information in a block queue that the corresponding channel receives enough display information when it needs it, despite the latencies in the retail and consumer loops.

In some embodiments, the arbiter 805 may forward a channel's request by asserting several signals to the frame buffer 22. For example, in one embodiment, the arbiter 805 may assert both a burst request and a signal indicating which of the channels the burst request corresponds to. Furthermore, the arbiter 805 may also assert a signal indicating what type of burst request is being asserted. Examples of types of burst requests include: start of new frame, start of additional fields in frame, next burst in stream, last burst in scan, end of scanline, and end of field.

The frame buffer 22 is configured to output display information in response to receiving a request forwarded by the arbiter 805. In some embodiments, the frame buffer 22 may store the display information as pixels or portions of pixels. In other embodiments, the frame buffer 22 may store display information as samples. Depending on the embodiment, the frame buffer 22 outputs a certain amount and type of display information in response to a received request. For example, in one embodiment, the frame buffer may output display information in bursts.

In one embodiment, a display address generator and the frame buffer interface (not shown) may process the display information requests. The display address generator may track the current address of each channel's graphics data, so that when a request from that channel is received, the appropriate data can be output from the frame buffer 22. Thus, after a request is serviced, the display address generator may update the address for that channel's data. The frame buffer interface may control the actual graphics data transfer operation. The frame buffer interface may also, in one embodiment, send an acknowledgement in response to receiving a request. The display address generator and/or frame buffer interface may be included in a device such as hardware accelerator 18.

In the illustrated embodiment, the data stored in the frame buffer 22 may be additionally processed before actually being output to a display. For example, in one embodiment, pixel data may not be stored in the frame buffer 22 in raster order. As a result, once the out-of-order pixel data has been output from the frame buffer 22, it may pass through a descrambler 811, as will be discussed in more detail below. The descrambler 811 may be configured to correctly order the pixels within a certain grouping of data (e.g., correctly order pixels within each block).

The descrambled graphics data may then be sent to a pixel buffer 815. The pixel buffer 815 may be implemented as a shared buffer (as opposed to a partitioned buffer), and thus the channels' data streams may be physically intermingled within the buffer 815. For example, each channel's data stream may be implemented as a linked list. While this configuration may provide optimal use of the storage within the buffer 815, it may be hard to implement. Thus, in another embodiment, the pixel buffer 815 may be partitioned so that each data stream has its own dedicated storage space. While this embodiment may not optimize the use of the space available in the pixel buffer 815, it may be easier to implement than a shared buffer. Generally, the pixel data stored in the pixel buffer 815 may be described as being stored in a block queue for each channel (BQ1 and BQ2), regardless of how the pixel buffer 815 is actually shared between the channels.

As part of the retail loop, each channel may be able to request data from the pixel buffer 815. In order to serve both channels, a pixel request arbiter 817 may monitor the channels' pixel requests and choose one of the requests to forward to the pixel buffer 815. Like the wholesale loop's arbiter 805, in one embodiment, the pixel request arbiter 817 may arbitrate between the two channels by selecting the neediest channel's request. The neediest channel is the channel that needs the most pixels in the shortest amount of time. In one embodiment, the pixel request arbiter 817 may determine which channel is neediest based on the level of data in that channel's display output queue 821. The pixel request arbiter 817 may also control which pixel request is forwarded to the pixel buffer 815 based on which of the channels have pixel data available from the pixel buffer 815. For example, if both channels have data available and request pixels at the same time, the arbiter 817 may be configured to alternate between the channels' requests.

Table 1 shows an example of how the pixel request arbiter may operate according to another embodiment.

TABLE 1 Pixel request arbiter output according to one embodiment. BQ1 BQ2 Last Service Data Data Requests Stall Request Ready Ready Next Output None X X X X No Reads X 1 X X X No Reads PR1 0 X 1 X Read from BQ1 PR1 0 X 0 X No Reads PR2 0 X X 1 Read from BQ2 PR2 0 X X 0 No Reads PR1 & PR2 0 X 0 0 No Reads PR1 & PR2 0 X 1 0 Read from BQ1 PR1 & PR2 0 X 0