DE69033283T2 - Method and device for accelerating picture windows in graphic systems - Google Patents

Description

Field of the invention

This invention relates to computer workstation windowing systems. More particularly, this invention relates to a method and apparatus for accelerating graphics primitive rendering on multitasking workstations that use graphics pipelines.

Background of the invention

Computer workstations provide system users with powerful tools to support a number of functions. An example of one of the more useful functions that workstations provide is the ability to perform highly detailed graphics simulations for a variety of applications. Graphics simulations are particularly useful for engineers and designers who perform computer-aided design (CAD) and computer-aided management (CAM) tasks.

Modern workstations include graphics capabilities that use "window" systems to achieve graphics manipulation. An emerging standard for graphics window systems is the "X" window system developed at the Massachusetts Institute of Technology. The X window system is described in K. Akeley and T. Jermoluk, "High-Performance Polygon Rendering," Computer Graphics, 239 to 246, (August 1988). Newer window systems in graphics workstations must provide a variety of high-performance windows, and still maintain a high level of user interactivity with the workstation. Previously, software solutions were implemented to provide increased user interactivity with the window system in graphics workstations. However, the trend is Other software solutions that increase user interactivity with the system tend to increase processor working time, thereby increasing the time in which graphics rendering for the screen in the workstation can be achieved.

A primary function of window systems in graphics workstations is to provide the user with simultaneous access to multiple processes on the workstation. However, each of these processes interfaces with the user through its own area on the workstation display. The overall result is an increase in user productivity because multiple windows allow the user to manage more than one task at a time. However, each process associated with a window sees the workstation's resources as if it were the sole owner. Consequently, the resources, such as the processing unit, memory, peripherals and graphics hardware, must be shared by these processes in a manner that prevents interprocess contention on the workstation.

Graphics workstations generally use graphics "pipelines" that connect the various components of the system. A graphics pipeline is a series of data processing elements that pass graphics commands through the graphics system. Today, graphics pipelines and windowing systems are evolving to support multitasking workstations.

The typical graphics pipeline interfaces a "host" processor to the graphics system, which provides the various graphics commands available to the system and also interfaces with the user. The host processor is interfaced through the graphics pipeline to a "transformation engine," which generally comprises a number of parallel floating-point processors. The transformation engine executes a variety of of system tasks, including context management, matrix transformation calculations, light modeling and effective radiance calculations, and control of the vector and polygon rendering hardware.

Graphics systems require a specific scheme to be implemented to "render" or draw graphics primitives for the system screen. A "graphics primitive" comprises an elementary component of a graphics image, such as a polygon or vector. All graphics images are formed from combinations of these graphics primitives. Many schemes can be used to perform graphics primitive rendering. One such scheme is the "spline mosaic" scheme used in the TURBO-SRX graphics systems of Hewlett-Packard Company Graphics Technology Division, Fort Collins, Colorado. Regardless of the type of graphics rendering scheme used by the graphics workstation, the transformation engine is necessary in managing the graphics rendering.

A graphics "frame buffer" interfaces downstream of the host processor and the transformation engine in the pipeline in the graphics window system. A "frame buffer" generally comprises a plurality of video random access memory (VRAM) computer chips that store information concerning pixel activation on the display corresponding to the particular graphics primitives being rendered on the screen. Generally, the frame buffer contains all data graphics information written to the windows and stores this information until the graphics system is prepared to render this information on the workstation screen. The frame buffer is generally dynamic and is periodically refreshed until the information stored in it is rendered on the screen. The host and the frame buffer have associated bandwidths. The Bandwidth is a measure of the rate of data flow over a data path.

To accelerate multiple processes on a graphics system, the graphics pipeline must be able to handle multiple "contexts." A graphics context consists of the current set of attributes, the matrix stack, the light sources, the shading control, the spline basis matrices, and other hardware state information. Earlier graphics systems were generally only able to support a single graphics context at a time and required the host software to perform the switching between all contexts. In these systems, software context switching requires the host to store the context for each active process in virtual memory, write the context to the device when the process is active, and read the context back to the system. This process is extremely time consuming and inefficient, and does not adequately support high-level graphics operations in the graphics system.

Several problems exist in known graphics window systems that use graphics pipelines. A major known difficulty arises when multiple contexts must be switched through the pipeline. Whenever a window context needs to be changed or "switched" through the graphics pipeline, the pipeline must be "flushed." Flushing requires that the pipeline be flushed of data to determine whether all data associated with the previous context has been piped through the pipeline to the frame buffer.

This method of context switching is fraught with problems. Since all data must be flushed from the pipeline to determine whether the previous context has been passed through to the frame buffer before the next context can be entered into the pipeline from the host, severe limitations are imposed on rendering graphics primitives to the screen in a timely manner. form, significantly slowing the system. Furthermore, host management of this form of context switching greatly increases the overhead of the host, thereby reducing host efficiency, and increasing the host processor time allocated to tasks not associated with actively preparing data to the frame buffer. Consequently, flushing the graphics pipeline is an inadequate and inefficient method of achieving context switching in newer windowing systems that use graphics pipelines.

From GB-A-2211706 it is known to distribute a FIFO memory among the pipeline stages. A latch before each pipeline stage acts as a FIFO of depth one to store the data sent by the previous stage when the current stage is not ready to receive it. A register is added to each stage to latch the current hold signal sent by a following stage before it is sent to the previous stage. The hold signal of one stage causes a hold signal to be generated by the next previous stage while the process of latching the data and transmitting the hold signals through the pipeline continues.

Further timing problems exist in windowing systems that use graphics pipelines. All graphics pipelines experience pipeline "latency," which is defined as the time required for a single primitive to traverse the pipeline. A significant difficulty is encountered during context switching in graphics pipelines as a result of pipeline latency, since pipeline latency reduces the responsiveness and user interactivity of the windowing system. Furthermore, complex primitives require significant processing time to render and therefore force other primitives to assume a wait state in the pipeline until they are fully rendered to the screen.

Thus, window operations that should theoretically be interactive with the user often force the user to wait while graphics primitives are rendered. As graphics pipelines and graphics workstations evolve to support more complex primitives and longer pipelines, pipeline latency and pipeline flushing now present prohibitive problems in the ongoing effort to increase pipeline throughput and efficiency.

There is therefore a long-recognized need in the art for graphics pipeline architectures that eliminate the need for pipeline flushing and reduce pipeline latency. There is also a long-recognized need in the art for pipelined graphics systems that support switching between multiple contexts. There is also a long-recognized need in the art for graphics systems that support multiple contexts but reduce the need for complex host management and processor overhead. These needs have not been met in the graphics windowing art by any current software implementations currently in use.

US-A-4814884 discloses a window generator which receives an array of video data and applies an identification code to rectangular sub-regions to identify different target areas within a given background area. The window generator includes video pipeline processing circuitry for collecting separate statistics for each target area.

According to the present invention, a system and a method for rendering graphics primitives according to claims 1 and 19 are provided as follows:

These are systems for processing basic elements that initially prepared in window-relative addresses, in a graphics frame buffer. The systems include host processor means for providing graphics instructions to render primitives in window relative addresses, scan converter means interfacing with the host processor means for rendering the graphics primitives through a graphics pipeline in the graphics frame buffer according to window relative addresses, pipeline bypass means interfacing with the host processor means for bussing window offset addresses from the host, the window offset addresses specifying the position of the window in the frame buffer, and table means interfacing with the pipeline bypass means for receiving and storing the window offset addresses and applying the window offset addresses to the window relative addresses, thereby rendering the graphics primitives in the frame buffer according to the frame buffer relative addresses determined according to the window offset addresses.

Methods for rendering graphics primitives in a frame buffer without flushing the pipeline to change window offset addresses are provided.

The methods include rendering the graphics primitives through the graphics pipeline according to window relative addresses, determining the window offset addresses corresponding to the frame buffer relative addresses at any time during the rendering, transferring window offset addresses to an address manipulator at any time during the rendering, applying the window offset addresses to the window relative addresses to obtain frame buffer relative addresses for the window containing the graphics primitives after determining and transferring the window offset addresses, and transferring the graphics primitives to the frame buffer according to the frame buffer relative addresses.

Computer windowing systems comprising a host, a graphics subsystem, a frame buffer, a pipeline, a pipeline bypass, and an address manipulator are provided. The computer window systems include source register means for storing a source reference address of a block of primitives to be moved, destination register means for storing a destination reference address of the block of primitives, size register means for storing data indicative of the size of the block, source specifier means for storing data indicative of whether the source reference address of the block is a window relative address or a screen relative address, destination specifier means for storing data indicative of whether the destination reference address of the block is a window relative address or a screen relative address, and table means interfaced with the pipeline bypass means for receiving and storing the window offset addresses and applying the window offset addresses to the window relative addresses, thereby rendering the graphics primitives in the frame buffer in accordance with the frame buffer relative addresses determined in accordance with the window offset addresses can be determined.

Systems for moving blocks in a windowed graphics system having a frame buffer are also provided.

The systems comprise a plurality of first register means for storing source address data of a block in the form of window relative addresses, a plurality of second register means interfaced to the plurality of first register means for storing destination address data of the block in the form of frame buffer relative addresses, and block movement means interfaced to the first and second register means for moving the block from the source to the destination in accordance with the Address data in the first or second register devices.

Systems are also provided for moving blocks in a windowed graphics system having a frame buffer.

The systems include a plurality of first register means for storing source address data of a block in the form of window-relative addresses, a plurality of second register means interfacing with the plurality of first register means for storing destination address data of the block in the form of window-relative addresses, and block movement means interfacing with the first and second register means for moving the block from the source to the destination according to the address data in the first and second register means.

Systems are also provided for moving blocks in a windowed graphics system having a frame buffer.

The systems include a plurality of first register means for storing source address data of a block in the form of frame buffer relative addresses, a plurality of second register means interfacing with the plurality of first register means for storing destination address data of the block in the form of frame buffer addresses, and block moving means interfacing with the first and second register means for moving the block from the source to the destination according to the address data in the first and second register means.

Short description of the drawings

Fig. 1 is a block diagram of a windowed graphics system that uses a graphics pipeline and a graphics pipeline bypass.

Figure 2 is a block diagram of a windowed graphics system that uses a graphics pipeline, a graphics pipeline bypass, a mark register, and a stop mark register.

Figure 3 is a flow diagram of a method provided in accordance with this invention using mark registers and stop mark registers.

Fig. 4 is a block diagram of a window graphics system in which window-related addressing is performed.

Figure 5 is a flow diagram of a method provided in accordance with this invention for window-related addressing and for implementing virtual windows.

Figure 6 is a block diagram of a windowed graphics system that uses a graphics pipeline and a graphics pipeline bypass to move block data through the graphics pipeline bypass to a frame buffer.

Figure 7 is a flow diagram of a method provided in accordance with this invention for moving block data and for preparing the block data in a frame buffer according to the frame buffer-related addresses.

Fig. 8 is a block diagram of a graphics window system for transferring large blocks of data from a host processor through a burst block using FIFO registers to a frame buffer.

Figure 9A is a flow diagram of a method provided in accordance with this invention for transferring large blocks of data along a pipeline bypass from a host processor to a burst block.

Figure 9B is a flow diagram of a method provided in accordance with this invention for transferring data from a burst block to a pixel cache.

Detailed description of the preferred embodiments

The inventors of the subject matter claimed and disclosed herein solved the above-mentioned needs long recognized in the art by implementing a graphics windowing system using a graphics pipeline with a separate path for instructions and data that do not require traversal of the graphics pipeline. This separate path is defined herein as a "pipeline bypass bus" and provides data instructions and blocks with direct access to the data buffer without traversing the pipeline bus. The pipeline bypass bus supports block moves, block reads and writes, as well as other hardware, rather than software, data transfer functions.

The pipeline bypass bus also provides fast access to the frame buffer for relatively simple instructions originating from the host processor. Furthermore, the pipeline bypass bus reduces the graphics pipeline overhead and provides services required by the windowing system that would otherwise have to be processed by the pipeline bus. While the pipeline bus provides high performance performance conditioning, the pipeline bypass bus provides fast block operations and direct frame buffer access to the data output by the host processor.

As shown in Figure 1, a graphics system consists of a host processor 20 that interfaces 30 with a transformation engine 40. Pipeline 50 interfaces host processor 20 and transformation engine 40 with a rendering circuit 60. Elements in pipeline 50 include a graphics processor that performs a variety of tasks in the graphics window system. These tasks include passing data through the graphics system and processing the graphics commands through various hardware blocks and software functions. The terms pipeline, pipeline bus, and pipeline processor are used interchangeably throughout to refer to the graphics pipeline processor. Window circuit 65, in preferred embodiments, comprises graphics hardware provided in accordance with this invention for rendering graphics primitives on windows to frame buffer 70. The window circuit is interfaced with the frame buffer 70 and the rendering circuit 60. These graphics primitives, as well as other graphics commands, are issued by the host processor 20 and manipulated by the transformation engine 40 through the graphics pipeline 50 for delivery to the frame buffer 70. After the rendering circuit 60 has rendered a window with a specific context through the window circuit 65 for the frame buffer 70, the window is rendered on a raster display 80.

A pipeline bypass bus 90 is interfaced 30 with the host processor 20 and the frame buffer 70. The pipeline bypass bus 90 provides a separate data path from the host processor 20 to the frame buffer 70. Thus, when data is passed through the pipeline bypass bus 90 to the frame buffer 70, no additional time overhead is introduced by the graphics pipeline. The pipeline bypass The transfer bus 90 provides fast block transfer operations and direct frame buffer access for data output from the host processor 20.

In preferred embodiments, hardware solutions are provided in accordance with this invention that eliminate the need for pipeline flushing and reduce pipeline latency, thereby increasing window acceleration through the system. In further preferred embodiments, hardware implementations enable the storage of multiple graphics contexts on the graphics system.

Furthermore, in the methods and apparatus provided in accordance with this invention, windows in the graphics system can be considered "virtual" devices. A virtual device operates according to window-related addresses through the graphics pipeline independently of addresses corresponding to the frame buffer or raster display. Since windows and window context switching can thus be rendered according to window-related addresses, the need for pipeline flushing is eliminated and pipeline latency is significantly reduced. Consequently, each window in the window system can view the graphics pipeline as an exclusive resource since time-consuming manipulations of the window that increase pipeline latency are eliminated. Thus, the methods and apparatus provided in accordance with the present invention fulfill a long-felt need in the art for graphics systems that support multiple window contexts and eliminate the need for pipeline flushing.

Referring to Figure 2, a host processor 20 is interfaced with a conditioning circuit 60 along the pipeline 50. A marker register 100 is arranged between the conditioning circuit 60 and a frame buffer 70. In the preferred embodiments, the pipeline marker register 100 is accessed from the host processor through the pipeline bus 50. The marking register 100 prevents unnecessary pipeline flushing when it is desired to change a window context.

A window context change often requires changing system resources, such as window clipping levels or window display mode levels. Furthermore, these system resources must often be changed during context switching because they are a limited resource and are shared by multiple processes. The tag register 100 provides a preferred resource for switching contexts compared to previous software solutions that may tend to reduce the need for pipeline flushing but do not -- and cannot -- eliminate it.

In the preferred embodiments, the tag register 100 tracks currently active contexts traversing the graphics pipeline 50 from the host processor 20. In other preferred embodiments, a "tag" is sent between each context switch from the host processor 20 along the pipeline 50. The tag register is incremented each time a context traverses the pipeline such that a table of contexts currently in the pipeline is maintained by the system in the tag register 100. The table shows the context number, window clipping levels, window identification, and tag numbers for each active context in the pipeline. As contexts are processed through the pipeline bus 50, the pipeline tag register 100 is automatically updated each time a tag reaches the end of the pipeline bus 50.

A stop mark register 110 is interfaced between the host processor 20 and the frame buffer 70 in the Pipeline bypass bus 90. In further preferred embodiments, stop marker register 110 is set to a particular value according to the particular application specified by host processor 20 and the user. When a context switch occurs, the windowing system may read the value of marker register 100 and compare it to the predetermined value in stop marker register 110 to determine which contexts are still in the pipeline. If the marker register value is equal to the stop marker register value, the windowing system will wait until the current context has been processed by the system and passed to frame buffer 70. If the stop marker register value is not equal to the marker register value, the context being switched is not in the pipeline, and the context switch and clip level changes may occur immediately. Therefore, under no circumstances will it be necessary to halt the flow of data in the pipeline or to prevent the host processor from continuing to place instructions and data on the pipeline. Thus, the need for pipeline flushing is eliminated.

Referring to Figure 3, a flow chart of a preferred embodiment of a method implementing the mark/stop mark system of Figure 2 is shown. The system initializes a stop mark register through the pipeline bypass in a step 120. It is then desirable to "unplug" the pipeline in a step 125. The system initializes a mark register through the pipeline in a step 130 and sends data command segments through the pipeline in a step 135.

The host processor queries the system in a step 140 to determine if the pipeline is "plugged". The term "plugged" as used herein means that no data and graphics commands are flowing through the pipeline. If the pipeline is closed, the system performs the task for which the Stop or closing was desired. The system then initializes the next stop marker through the pipeline bypass in a step 155 and clears the pipeline in a step 160.

If the pipeline was not closed, the system asks in a step 145 if the pipeline is full. If the pipeline is full, the system returns to step 140. However, if the pipeline is not full, the system returns to step 125 where it opens the pipeline.

Concurrent with step 125, the host processor queries the system to determine if the mark register value is equal to the stop mark register value in a step 165. If the stop mark register value is equal to the mark register value, the system terminates the flow of pixel data to the frame buffer or "closes" the pipeline in a step 170. The host processor then queries the system to determine if the pipeline has been opened in a step 175. If the pipeline has not been opened, the system waits.

If the system is open, the host processor again queries the system in step 165 to determine if the mark value is equal to the stop mark value. If the stop mark value is not equal to the mark value, the host processor issues a command in step 180 that allows the pixel cache to write data to the frame buffer.

Otherwise, the host processor closes the pipeline in step 170 at the time the host processor polls the system to determine if the pipeline is closed in step 140. Consequently, the need to flush the pipeline has been eliminated because the closing of the pipeline only needs to occur for relatively short periods of time between the pixel cache and the frame buffer while a complex processing and a matrix transformation takes place beforehand in the pipeline. This advantageous result is achieved because the mark and stop mark registers tell the graphics system when the pixel data flow to the frame buffer must wait because a specific context has not yet been passed to the frame buffer.

Context switching using the mark and stop mark hardware provided in accordance with this invention thus eliminates the need for pipeline flushing, since the graphics pipeline never has to be flushed of data to determine whether a current context has been committed to the frame buffer. In this way, extremely fast and efficient context switching can be achieved, significantly improving the overall graphics system. The mark register and stop mark register hardware provided in accordance with this invention meets the long-recognized need in the art for context switching in graphics systems using a pipeline bus and a pipeline bypass bus.

The inventors of the subject matter claimed and disclosed herein discovered that all graphics applications run faster when they consider themselves the sole owner of the graphics system. This is a consequence of the fact that when a graphics application requests a window, the corresponding frame buffer is allocated to that application for graphics output. Thus, an ideal environment for graphics rendering would allow each graphics process to treat the window as a "standalone" or virtual graphics device.

Previous graphics systems typically required that the graphics process be modified to run within a window. These systems require the application to be "window intelligent" and post-process the application output to add window shards. zen or clipping on window boundaries to match the window environment. Software that performs these functions significantly reduces overall system performance because an excessive amount of host processor time is required to perform these tasks. The inventors of the subject matter claimed and disclosed herein implemented graphics functions in hardware that allow primitives in the pipeline bus to be specified relative to the window origin.

In the preferred embodiments, the window origin is a reference for the graphics primitives that are rendered for the window. The translation to screen-relative or "frame buffer-relative addresses" occurs after the scan conversion according to the window-relative addresses and before the frame buffer access. Thus, the application treats the window as a "virtual" full-screen device because the graphics system renders the primitives as if the window encompassed the entire frame buffer.

Operations of this nature can be performed by a transformation matrix. However, if the window offset is contained in the matrix stack, the pipeline must be flushed each time the window is moved or changed. After the pipeline is flushed, the new window offset can be added to the transformation matrix and the pipeline must be refilled. Consequently, a more preferred solution is to allow the application to access the window as if it owned the entire screen or frame buffer, and then to provide hardware that receives the window offset data according to the frame buffer-related addresses so that the window containing the graphics primitives can be prepared according to the frame buffer-related addresses for the frame buffer.

By preparing the primitives in window-related coordinates and performing the conversion of window screen-wise in the processing direction behind the rendering hardware in the pipeline, the need to clear the pipeline to render a window for the frame buffer is eliminated. The window translation thus accomplished in hardware is completely transparent to the application. The offset operations are performed in parallel with other pipeline operations through the pipeline bypass bus, so that no behavioral penalties for the various block operations or context switches are introduced into the window graphics system.

Referring to Figure 4, a host processor 20 is interfaced with a rendering circuit 60. In preferred embodiments, the rendering circuit 60 includes a transformation engine 210 and a scan converter 220. Preferably, the scan converter is a raster scan converter. A pixel cache 230 is interfaced with the scan converter along the pipeline bus 50. The pixel cache 230 is further interfaced with a frame buffer 70. In further preferred embodiments, a video random access memory (VRAM) 240 comprises the addressable frame buffer for the system. An address manipulator 250 is interfaced on a pipeline bypass bus 90. The address manipulator 250 is located along the pipeline bypass bus 90 between the host processor 20 and the frame buffer 70.

In further preferred embodiments, the address manipulator 250 includes data registers for receiving offset addresses for each window from the host processor 20, a window-related conversion circuit, and data registers for storing a window identification. The window offsets are applied to each window by the address manipulator 250 before the windows containing graphics primitives are passed to the frame buffer 70. Since the window offsets are written to the address manipulator 250 by the pipeline bypass bus 90, these be updated asynchronously. The windows can thus be moved or merged through the pipeline bypass 90 to the frame buffer at the same time that the window-related rendering of the graphics primitives occurs at the scan converter 220 through the pipeline bus 50. Graphics applications and processes can therefore run on the graphics pipeline bus 50 without explicit knowledge of their final window location in the frame buffer. Thus, the windows in the graphics systems created in accordance with this invention truly act as virtual devices since they are able to view the graphics pipeline as an exclusive resource during window-related rendering operations.

Preferably, pixel cache 230 is interfaced 245 to an address manipulator by a control bus 240. Pixel cache 230 contains window-related addresses 245 of the graphics primitives prepared on the window relative to the window origin. As window offset data is written to address manipulator 250 by pipeline bypass bus 90, pixel cache 230 interfaces 245 to address manipulator 250 to provide the window-related data that is combined with the window offset addresses in the address manipulator. The address manipulator 250 is further interfaced with the frame buffer 70 so that the graphics windows can be transferred to the frame buffer in accordance with the frame buffer-related addresses 255.

Because the address manipulator 250 applies the window offsets to the graphics primitives that are addressed per window, the need to flush the graphics pipeline 50 when context changes occur is eliminated and the pipeline latency for the graphics systems is greatly reduced. These advantageous results are obtained because the complex manipulation associated with rendering the graphics primitives elements in the frame buffer-related addresses directly by the graphics pipeline is eliminated in systems and methods provided in accordance with this invention.

A flow chart for accomplishing window-related rendering in the window graphics systems provided in accordance with this invention is shown in Figure 5. Using a window manager, the pipeline processes an application through the pipeline. The application requests a window ID in a step 260. The window manager determines whether a new window ID has been requested in a step 265. If a new window ID has not been requested, the window manager determines whether a window move has been requested in a step 270. If no window move has been requested, the process returns to step 265. However, if a window move has been requested, the window manager closes the pipeline in a step 275.

The window manager then calculates a new window location in a step 280 and moves the window. The window manager also writes the window offset to the address manipulator in a step 285 and opens the pipeline in a step 290. The process then returns to step 265 to determine if a new window ID has been requested. Since a new window ID has not been requested at this point, the window manager assigns a window ID in a step 295 and closes the pipeline in a step 300.

The host processor then queries the system in a step 305 to determine if the new window ID has been received. If the new window ID has not been received, the system waits for the window manager to send a new window ID. However, if a new window ID has been received, the host processor sends the application having data or command segments for the assigned window ID through the pipeline in a step 310. The host processor be then determines whether the application has terminated in a step 315. If the application has not terminated, the host processor sends additional data or command segments through the pipeline in step 310. However, if the application has terminated, the window can be said to have been rendered and the window manager will have moved the window to its new location in step 280. The process then terminates at 320 until another window passes through the pipeline.

Window-relative rendering, achieved by the methods illustrated in Figure 5, eliminates the need for pipeline flushing. The window manager independently applies window offset addresses to window-relative data, while simultaneously allowing the pipeline to process windows according to the window-relative addresses. This has not been achieved before in the art and significantly increases the speed and timeliness of passing graphics primitives to the frame buffer.

Graphics window systems must support block movement operations to maximize system performance. In addition, block movement operations generally support basic window primitives, including raster text and icons. Other types of graphics block movement, such as shuffles and block "scaling," must also take advantage of the system's block movement capabilities.

A "block" can be considered an entire window or just a portion of a window that contains a set of graphics primitives on the graphics system. Block movements are particularly difficult to handle in a windowing environment because window offset addresses must be included in these operations, which are typically implemented as screen address-relative. In contrast, block movement operations within a window must be window-relative, so forcing all blocks movements in the graphics system are window-relative is neither an adequate nor a versatile solution. The reason that block movement operations within a window must be window-relative is that many objects, such as fonts, are stored in off-screen memory in the frame buffer, and therefore these objects are identified exclusively according to frame buffer-relative addresses.

The inventors of the subject matter claimed and disclosed herein discovered that the hardware implementation of a graphics block mover enables the graphics system to handle several different types of block move operations. In preferred embodiments, the hardware implementation of the block mover includes a register having the ability to store a bit for each operand output from the host processor that specifies whether the operand is window address related or screen address related. Block moves provided by methods and systems according to this invention can thus be window related, screen related, or any combination thereof.

Window systems according to this invention may include block movement hardware that provides window offsets through a pipeline bypass bus for windows having graphics primitives rendered according to the window-related addresses thereon. In further preferred embodiments, block moves initiated according to this invention write the block source and destination addresses, the block width and height, and a specific replacement rule through the pipeline bypass bus to the address manipulator prior to initiating the block move.

Consequently, a block movement provided according to this invention does not require that the window decision about its particular coordinate system as it passes through the graphics pipeline. This eliminates the need for the windowing system to incur additional processor overhead while manipulating graphics primitives according to frame-relative addresses, which would necessarily occur in parallel with the application or context processing. If a block in the work area of the frame buffer is off-screen, in preferred embodiments it can automatically be assumed to be screen-relative. If the block is displayed in the active screen area of the frame buffer, however, it can be assumed to be window-relatively addressed.

As shown in Figure 6, a host processor 20 issues graphics commands along a pipeline bus 50 to a window-relative rendering circuit 330. The window-relative rendering circuit 330 generally includes a raster scanner and a pixel cache buffer as illustrated in the previous figures. The window-relative rendering circuit 330 renders graphics primitives for the window according to the window-relative addresses.

The window-referred rendering circuit 330 is further interfaced with a frame buffer 70. In preferred embodiments, the frame buffer 70 is a VRAM. The frame buffer 70 may be conceptually divided into two parts. The first part 340 corresponds to screen addresses, i.e., positions on the video screen where graphics primitives are actually displayed. The second part of the frame buffer 350 corresponds to an "off-screen" work area. The off-screen work area 350 is an area in which windows or blocks that have not been rendered on the video screen of the graphics system exist solely according to the frame buffer-referred addresses. Blocks that are on the first portion of the frame buffer 340 may be addressed relative to the screen in the frame buffer-relative addresses or the window-relative addresses as they are processed by the pipeline.

In the preferred embodiments, a source block 360 can be moved from the work area 350 to the destination window or block 370 in the first section 340 of the frame buffer 70. It will be apparent to those skilled in the art that the source and destination addresses could be interchanged such that blocks can be moved window-wise, screen-wise, or any combination thereof.

To move blocks between a destination and a source, the host processor 20 outputs window offset information over the pipeline bypass bus 90 to a plurality of data registers included in the address manipulator 250. A destination register 380 is adapted to store the destination address of the block output by the host processor 20. A source address register 390 is adapted to receive the source address of the block output by the host processor 20 over the pipeline bypass 90. In further preferred embodiments, it is desirable to write the block size into the block size register 400. In still further preferred embodiments, the block size comprises the block width and height so that the block can be written exactly to the appropriate destination in the frame buffer.

The specifier register 410 is adapted to receive data from the host processor 20 through the pipeline bypass bus 90 specifying whether the block to be moved is currently window address related or frame buffer address related. In further preferred embodiments, a single bit of the operand received from the host processor 20 and stored in the specifier register 410 specifies whether the block is window or screen-related. Thus, with the methods and apparatus of this invention, blocks that are window address-related or screen address-related can be moved between sources and destinations that are window-addressed or frame buffer-addressed.

Likewise, the source addresses and destination addresses may be addressed according to either the window-related addresses or the frame buffer-related addresses, and blocks may be simultaneously moved between source and destination addresses either within windows or in and around the frame buffer. Systems and methods provided in accordance with this invention therefore satisfy a long-felt need in the art for a highly efficient and versatile block movement circuit in graphics window systems using graphics pipelines.

In Figure 7, a flow chart of a block movement method provided in accordance with this invention is shown. In preferred embodiments, a block is rendered according to window-related addresses by a graphics pipeline in a step 420. The source addresses of the block are written to the source address register by the pipeline bypass in a step 430. Similarly, the destination addresses of the block are written to the destination address register by the pipeline bypass bus in a step 440. It is desirable to write the block size to the block size register by the pipeline bypass bus in a step 450.

The host processor queries a specifier register in a step 460 to determine whether a destination block was addressed according to window-related addresses or frame buffer-related addresses. Similarly, the host processor queries a specifier register in a step 465 to determine whether a source block was addressed according to window-related or frame buffer-related addresses. If the blocks have been addressed according to the frame buffer-relative addresses, a "zero" window offset is applied in a step 470 which effectively does not change the block addresses since the block is considered to be addressed frame buffer-relatively.

However, if the specifier register indicates that the blocks are window address-referred, window offset addresses are applied to the block in a step 480 so that the blocks are correctly addressed according to the frame buffer-referred addresses before the blocks are passed to the destination in the system frame buffer or the screen. After the window offsets are applied to the window address-referred blocks, the blocks can be passed to their destinations in the frame buffer in a step 490.

In further preferred embodiments, the block window offset addresses are written to the address manipulator by the pipeline bypass bus, and not by the graphics pipeline bus. Therefore, the graphics pipeline bus is not used to address the block relative to the frame buffer and is thus free to perform graphics primitive renderings for blocks and windows entirely according to the window-related addresses.

Methods and systems provided in accordance with this invention reduce pipeline latency because each window is effectively treated as a virtual device in the system. In addition, methods and devices provided in accordance with the present invention solve a long-known need in the art for graphics pipelines that eliminate the need for pipeline flushing because the time-consuming task of adding window offsets to window-addressed blocks and obtaining frame buffer-addressed blocks is eliminated. This goal is achieved by implementing a graphics pipeline bus that utilizes hardware on adapted to perform these tasks.

Newer graphics windowing systems with graphics pipelines demonstrate a need for the ability to move large amounts of pixel data to and from system memory. Software solutions that gave earlier graphics systems the ability to move large amounts of data in this way require an excessive amount of processor time to achieve this function. Consequently, earlier windowing systems that use a graphics pipeline with special-purpose software to provide the ability to move large blocks of data do not meet the long-recognized need in the art for graphics windowing systems that can efficiently move large blocks of data without placing undue burden on the host processor and graphics pipeline.

As shown in Figure 8, in accordance with this invention, a "burst" data hardware block 500 is provided that is interfaced to a pipeline bypass bus 90 and located between the host processor 20 and the pixel cache 230. The data block 500 is referred to as a "burst" data block because the host processor 20 can load the data block 500 with extremely large blocks of data through the pipeline bypass bus 90. Generally, these large blocks of data may include graphics animation data that is written to the frame buffer. These large blocks of data are organized as multiple rows of pixels called "scan lines." The data is organized in the host processor memory as an array of data, with the first data being the leftmost pixel of the first scan line, then progressing along the scan line to the rightmost pixel of the first scan line, then back to the leftmost pixel of the second scan line, etc. This forms a two-dimensional array of pixel data to be sent to the frame buffer.

The bundle consists of a number of first-in-to first-out (FIFO) registers shown at 510. The FIFOs are organized in banks. There are from 1 to "n" banks of FIFOs. Each FIFO bank buffers pixels along the scan line. The number of pixels buffered along a scan line depends on the depth of the FIFOs. Multiple scan lines, equal to the number of FIFO banks, can be buffered. The input port and output port of the FIFOs operate independently. Data is transferred from the host processor 20 to the FIFO input ports independently and in parallel with data transferred from the FIFO output ports to the pixel cache 230.

The banks are connected in parallel as seen from the pipeline bypass bus 90. The host processor 20 writes data from a scan line of data into the input port of one of the FIFO banks until that FIFO bank is full. The host processor then writes data from the next scan line of data into the input port of the next FIFO bank.

When data is available in all FIFO banks, data transfer from the output port of FIFOs 510 to the pixel cache can begin. This occurs in parallel with the host processor 20 sending data to the input port of FIFOs 510. Pixel cache 230 interfaces with VRAM 70 to allow data in burst 500 to be written to the frame buffer.

The graphics pipeline 50 is then closed and pixel data transfer from the graphics pipeline 50 to the frame buffer 70 is suspended while data transfer from the bundle 500 is active. Since the bundle 500 is interfaced to the pixel cache 230 by the pipeline bypass bus 90, the need to flush the graphics pipeline is eliminated.

If only a sub-region "sub-block" of the two-dimensional area of pixel data is to be sent to the frame buffer, one way is to send data from the left and the right edge. Two additional offset operands from the host processor are written to the address manipulator 230. The offsets specify the number of pixels along a scan line from the start of the scan line to the right edge and the left edge of the desired sub-block of data. These offsets instruct the address manipulator to truncate the data transferred from the FIFOs 510 to the pixel cache 230; ie, to the right or left of the desired sub-block of data.

In preferred embodiments, the bundle 500 consists of a number of first-in-first-out (FIFO) registers, shown generally at 510. The FIFOs 510 are connected in parallel in the bundle block 500. The FIFOs 510 are interfaced with the pipeline bypass bus 90 so that the host processor 20 can move large blocks of data in parallel to each of the FIFOs 510. The amount of data passed from the host processor 20 to the bundle 500 is limited only by the number of FIFOs connected in parallel in the bundle block.

The bundle 500 is interfaced with the pixel cache 230 so that it can transfer the data in the FIFOs 510 to the pixel cache 230 after the host processor 20 has written the desired data into the FIFOs 510. The pixel cache 230 is interfaced with the VRAM 70 to allow data in the bundle 500 to be passed to the frame buffer. Since the bundle 500 is interfaced with the pixel cache by the pipeline bypass bus 90, the graphics pipeline 50 is free to perform window-related rendering of other graphics primitives output by the host processor. Therefore, the use of the bundle 500 interfaced with the graphics pipeline bypass bus 90 reduces the graphics pipeline latency and eliminates the need to flush the pipeline 50 when a context switch is required for the data in the bundle 500. is desired.

In further preferred embodiments, the address manipulator 250 is provided, interfaced on the pipeline bypass bus 90 and located between the host processor 20 and the VRAM 70. The address manipulator operates as described above and conditions the data in the burst 500 according to the frame buffer-related addresses in the VRAM 70. It is necessary to use the address manipulator 250 because the data written by the host processor 20 into the FIFOs 510 in the burst 500 may appear in window-related addresses. Accordingly, the host processor 20 writes window offset addresses for the data in the FIFOs 510 into a data register in the address manipulator so that the address manipulator 250 can prepare the data in the FIFOs 510 according to the frame buffer-related addresses in the VRAM 70.

The address manipulator 250 also aligns data written to the FIFOs 510 to the frame buffer. The alignment is accomplished by an additional offset operand from the host processor 20 written to the address manipulator 250, which instructs the address manipulator to truncate data in the FIFOs 510 that is input to the pixel cache 230 and that falls out of the specified blocks in the frame buffer 240 when the data is rendered. In preferred embodiments, the truncation is necessary because the block data output from the burst 500 may be large enough to fall out of the specific destination addresses in the frame buffer.

In Fig. 9A, a flow chart of a preferred embodiment of the transfer of large data blocks from a host processor to a burst block is shown. The block destination addresses are written to the address manipulator by the pipeline bypass in a step 520. Similarly, the block size is determined in a step 530. through the pipeline bypass bus from the host processor to the address manipulator. It is then desirable to write the left edge and right edge offsets through the pipeline bypass to the address manipulator in a step 540.

The left edge and right edge offsets are then written to the address manipulator through the pipeline bypass bus in a step 540. In a step 550, the host processor polls the FIFOs to determine if there is room in the FIFOs. If there is no room in the FIFOs, the process must wait. However, if there is room in the FIFOs, the host processor polls if there is data to be transferred in a step 560. If there is no data to be transferred, the process ends. However, if there is data to be transferred, a single data is transferred in a step 570. In this way, data can be transferred from the host processor into the burst block.

In Figure 9B, a preferred embodiment of a flow chart for transferring data from a burst block to a pixel cache is shown. The host processor polls the burst block in a step 580 to determine if data is available in all FIFOs. If data is not available from all FIFOs, the process must wait. However, if data is available from all FIFOs, transfers of a single data from the burst block to the pixel cache are performed in a step 590. The host processor then polls the system in a step 600 to determine if all data has been transferred. When all data transfers have occurred, the process ends.

If the block is not aligned, the data that falls outside the window must be clipped from the block so that it is not illegally rendered outside the window on the screen. In this way, the bundle data can be piped to the frame buffer, thereby freeing the graphics pipeline from high overhead operations. Therefore, the burst transfer operations provided in accordance with this invention fulfill a long-recognized need in the art for windowing systems having the ability to move a large amount of pixel data through the system in an efficient manner.

Methods and apparatus provided in accordance with this invention that implement hardware solutions for pipeline bypass buses in windowing systems using a graphics pipeline meet a long-known need in the art for methods and systems that eliminate the need for pipeline flushing and reduce pipeline latency. These long-known needs have not been met in the art by prior graphics windowing systems using software solutions. Graphics windowing systems in accordance with this invention that use graphics pipelines demonstrate a significant improvement over prior novel systems that render graphics primitives to a frame buffer or a screen. The graphics windowing systems provided in accordance with this invention treat windows as virtual graphics devices, thereby eliminating the need for pipeline flushing during context switching and greatly reducing pipeline latency.

Thus, certain preferred embodiments of methods and apparatus for accelerating graphics rendering in graphics windowing systems have been described.

Claims (25)

1. A system for preparing graphic primitives, which has the following characteristics: a host processor (20), a graphics subsystem, a frame buffer (70), a graphics pipeline (50), a window offset device adapted to store window offset addresses indicating a position of a window relative to the frame buffer (70), a pipeline bypass (90) interfaced with the window offset device and enabling the writing of the window offsets by the host processor (20), and an address manipulator (250) interfaced with the pipeline bypass (90), the address manipulator (250) comprising means (380, 390) for receiving and storing addresses and means (480) for converting addresses relative to a window origin to addresses relative to the frame buffer origin by adding a respective window offset address to each address relative to the window origin. 2. The system of claim 1, further comprising: a scan converter device (220) communicating with the window offset device and receiving the graphics data for performing a conversion of Addresses relative to the window origin and for communicating the results to the frame buffer (70), and an identification device (410) written to by the host processor (20) through the graphics pipeline for determining which window offsets in the window offset device relate to the translation of the addresses relative to the window origin. 3. The system of claim 2, wherein the scan converter (220) is positioned in the graphics pipeline (50) between the host processor (20) and the frame buffer (70). 4. The system of claim 2 or 3, wherein the scan converter (220) is a raster scan converter. 5. The system of any of claims 2 to 4, further comprising a storage device (230) positioned in the graphics pipeline (50) between the scan converter (220) and the frame buffer (70) for storing graphics data rendered in the window. 6. The system of claim 5, wherein the graphics data corresponds to pixel activation data. 7. The system of claim 5 or claim 6, wherein the window shifter is further interfaced with the storage device (230). 8. The system according to one of claims 5 to 7, wherein the address manipulation device (250) is further interfaced with the storage device (230). 9. The system according to any one of claims 5 to 8, wherein the storage device is a cache buffer (230). 10. The system of any preceding claim, wherein the address manipulation device (250) is positioned in the pipeline bypass (90) between the host processor (20) and the frame buffer (70). 11. The system of any preceding claim, wherein the frame buffer (70) comprises a video random access memory. 12. The system of any preceding claim, wherein the window offset means is positioned in the pipeline bypass (90) between the host processor (20) and the frame buffer (70). 13. The system of any preceding claim, wherein the address manipulation device (250) is further interfaced with the graphics pipeline (50). 14. The system according to one of the preceding claims, which has the following features: source register means (390) for storing a source reference address of a block of primitives to be moved; destination register means (380) for storing a destination reference address of the block of primitives; a dimension register means (400) for storing data indicative of the size of the block; source specifier means (410) for storing data indicating whether the source reference address of the block is an address relative to a window origin or an address relative to the Frame buffer origin; and destination specifier means (410) for storing data indicating whether the destination reference address of the block is an address relative to the window origin or an address relative to the frame buffer origin. 15. The system of claim 14, wherein the host processor (20) issues instructions to the address manipulator (250) to instruct the address manipulator (250) to move the block from the block's source address to the block's destination address. 16. The system of claim 14 or 15, wherein the reference address of the block corresponds to the source address of the block. 17. The system of any of claims 14 to 16, wherein the source means (390), the destination means (380), the dimension register means (400) and the specifier means (410) are positioned in the pipeline bypass (90) between the host processor (20) and the frame buffer (70). 18. The system of any of claims 14 to 16, wherein the source means (390), the destination means (380), the dimension register means (400) and the specifier means (410) are positioned in the graphics pipeline (50) between the host processor (20) and the frame buffer (70). 19. The system of any preceding claim, wherein the window offset means is a window offset table. 20. A method for rendering graphics primitives in a frame buffer (70) without a graphics pipeline (50) to change window offset addresses, the method comprising the following steps: rendering (420) the graphics primitives through the graphics pipeline (50) according to addresses relative to a window origin; determining (460) window offset addresses corresponding to addresses relative to the frame buffer origin at any time during the rendering; writing window offsets to a window offset device adapted to store the window offsets, the window offsets being written by a host processor through a pipeline bypass; transmitting window offset addresses to an address manipulator (250) at any time during rendering; adding (480) the window offset addresses to corresponding addresses relative to the window origin to obtain addresses relative to the frame buffer origin after determining (460) and transmitting the window offset addresses; and Transferring the graphics primitives to the frame buffer (70) according to addresses relative to the frame buffer origin. 21. The method of claim 20, wherein the step of rendering (420) the graphics primitives into a graphics window comprises scanning the graphics primitives to determine pixels to be activated on a graphics display. 22. The method of claim 21, wherein the scanning step is a raster scanning step. 23. The method of claim 21 or claim 22, further comprising storing the pixel activation data in a pixel cache buffer (230). 24. The method of any of claims 20 to 23, wherein the frame buffer (70) is a video random access memory. 25. The method of any of claims 20 to 24, wherein the window offset means is a window offset table.