Hewlett-packard Company

Hewlett-packard Development Company, L.P.

Jon L Ashburn

Theodore G Rossin

Byron Alan Alcorn

Darel N Emmot

Alan S Krech, Jr

S Paul Tucker

Bryan G Prouty

Edmundo Rojas

Glenn W Strunk

Ted Scott Rakel

Michael S McGrath

Courtney D Goeltzenleuchter

James M Dewey

Methods and apparatus for compositing separately generated three-dimensional images in a two-dimensional graphics imaging pipeline of a computer graphics system to ultimately render a composited image on a display screen. The computer graphics system includes generally a graphics library and graphics hardware together defining the imaging pipeline, and a graphics application program invoking operations in the imaging pipeline through an application program interface provided by the graphics library. The imaging pipeline may be the only pipeline in the graphics system or it may be part of a larger rendering pipeline that also includes a geometric pipeline that generates two-dimensional images represented by pixel data. The graphics system also includes a frame buffer for storing pixel data to be displayed on the display device. The image compositing module performs depth testing and stencil testing on specific components of the next image that are separately and sequentially processed by the imaging pipeline. The stencil test is performed to determine initially which image is to be rendered at each pixel. An indication of the selected image is stored in a memory location associated with that pixel. The imaging pipeline writes to the frame buffer color data either the stored or next image based on the selected image indications.

Compositing separately-generated three-dimensional images

Frame buffer memory bandwidth is conserved by performing a depth comparison between colliding pixels at batch building time. If the incoming pixel fails the depth comparison, then it may be &ldquo;tossed&rdquo; and excluded from any batches currently under construction. The batch building process may then continue without the need for a batch flush responsive to the occurrence of the pixel collision. If the incoming pixel passes the depth comparison, then it may yet be possible to avoid flushing: The current rendering mode of the pipeline is determined. If the current rendering mode does not require read-modify-write operations, then the incoming pixel may be merged with the buffered pixel with which it collides. Merger of the two pixels may be accomplished by overwriting the buffered RGBA pixel components with those of the incoming pixel, but only those components corresponding to asserted bits in the incoming pixel's BEN. The buffered BEN may be replaced with the logical OR of the stored BEN and the incoming pixel's BEN.

Z test and conditional merger of colliding pixels during batch building

A buffer facilitates reordering of memory access commands in a memory access command stream so as to create column coherencies that may be exploited with burst-mode memory cycles. A multi-column data storage buffer is provided. Storage control circuitry stores data associated with a memory access command into the multi-column data storage buffer at a column that corresponds to at least one of the LSBs of the column address associated with the memory access command. Flush control circuitry flushes the data storage buffer, when required, in column order. Each entry in the data storage buffer is associated with a unique valid bit. At flush time, the flush control circuitry analyzes the valid bits to determine an appropriate burst type for executing the memory access commands represented by the flushed buffer contents. The flush control circuitry may indicate the determined burst type to memory controller hardware by means of a burst type flag. The data storage buffer may include multiple lines. Each line is associated with one line in a multi-line column address storage buffer. The storage control circuitry stores at least some of the MSBs of the data column addresses in the column address storage buffer. Column address comparison circuitry determines whether at least some of the MSBs of the column address of an incoming memory access command match those currently stored in a line of the column address storage buffer, and if so, select the matching line, but if not, select an unused line.

Creating column coherency for burst building in a memory access command stream

A buffer facilitates reordering of incoming memory access commands so that the memory access commands may be associated automatically according to their row/bank addresses. The storage capacity in the buffer may be dynamically allocated among groups as needed. When the buffer is flushed, groups of memory access commands are selected for flushing whose row/bank addresses are associated, thereby creating page coherency in the flushed memory access commands. Batches of commands may be flushed from the buffer according to a sequence designed to minimize same-bank page changes in frame buffer memory devices. Good candidate groups for flushing may be chosen according to criteria based on the binary bank address for the group, the size of the group, and the age of the group. Groups may be partially flushed. If so, a subsequent flush operation may resume flushing a partially-flushed group when to do so would be more beneficial than flushing a different group chosen solely based on its bank address. The first and last commands flushed in any batch are accompanied by flags indicating that they are the first and last commands in the batch, respectively.

Creating page coherency and improved bank sequencing in a memory access command stream

A 3D graphics controller configurable to simultaneously copy portions of a pixel region between a back buffer and a front buffer. The 3D graphics controller includes four memory controllers, each controlling a bank of frame buffer memory. A sequence of addresses defining a pixel region is generated. The addresses are distributed to the four memory controllers according to the memory banks (addresses) coupled thereto. Each memory controller is configured to read pixels according to the addresses and a first offset; and write the pixels according to the addresses and a second offset. The offsets are chosen so as not to shift pixels within the banks. Therefore, each memory controller simultaneously and independently copies a portion of the pixel region without accessing any other memory banks resulting in a copy of the entire pixel region.

Window copy-swap using multi-buffer hardware support

A clear color and count are stored in a frame buffer controller and in a video controller. The image buffer is cleared by writing the clear color into a color bit field and the count into a count bit field of each pixel. For each frame drawn, the count bit field of each pixel modified is updated with the count stored in the frame buffer controller. The counts stored in the frame buffer controller and the video controller are incremented with each new frame. When the counts reach maximum, the process repeats. Each time a pixel is read, the pixel's color bit field is replaced with the stored clear color if the pixel's count bit field is not equal to the stored count. The color bit field and the count bit field may be part of the same word of frame buffer memory. Or, the count value may be stored in an alpha bit field in lieu of an alpha value. If so, each time a pixel is read by the frame buffer controller, the pixel's count bit field may be replaced with a default alpha value stored in the frame buffer controller. Numerous pairs of clear count and clear color registers may be provided in the video controller, each pair corresponding to one window on the display. And numerous pairs of clear count and clear color registers may be provided in the frame buffer controller to better support double buffering and stereo operations.

Technique for reducing the frequency of frame buffer clearing

The invention provides for a system and method for minimizing space requirements and increasing speed in a geometry accelerator for a computer graphics system. In architecture, the system is implemented as follows. The geometry accelerator includes a plurality of processing elements (e.g., an arithmetic logic unit, a multiplier, a divider, a compare mechanism, a clamp mechanism, etc.) and a plurality of control units (e.g., a transform mechanism, a decomposition mechanism, a clip mechanism, a bow-tie mechanism, a light mechanism, a classify mechanism, a plane equation mechanism, a fog mechanism, etc.) that utilize the processing elements for performing data manipulations upon image data. In accordance with the invention, the control units are implemented in a read-only memory (ROM) via microcode. A next address field is associated with each of the microcode instructions and defines a location in the ROM of a next instruction to be executed. A plurality of control unit logic elements correspond respectively with the control units and control instruction branching within their respective control unit by defining the next address field. A branch central intelligence mechanism controls branching between the control units by defining the next address field.

ROM-based control unit in a geometry accelerator for a computer graphics system

The invention provides for a system and method for minimizing space requirements and increasing speed in a geometry accelerator for a computer graphics system by providing a branch central intelligence mechanism. Architecturally, the geometry accelerator includes a plurality of processing elements (e.g., an arithmetic logic unit, a multiplier, a divider, a compare mechanism, a clamp mechanism, etc.) and a plurality of control units (e.g., a transform mechanism, a decomposition mechanism, a clip mechanism, a bow-tie mechanism, a light mechanism, a classify mechanism, a plane equation mechanism, a fog mechanism, etc.) that utilize the processing elements for performing data manipulations upon image data. In accordance with the invention, the control units are implemented in a read-only memory (ROM) via microcode. A next address field is associated with each of the microcode instructions and defines a location in the ROM of a next instruction to be executed. A plurality of control unit logic elements correspond respectively with the control units and control instruction branching within their respective control unit by defining the next address field. Finally, a branch central intelligence mechanism controls branching between the control units by defining the next address field.

Centralized branch intelligence system and method for a geometry accelerator

ROM-based control units in a geometry accelerator for a computer

Apparatus for performing floating point divide operations includes a divider and a comparator. The divider performs a floating point divide operation on a floating point numerator and a floating point denominator. The comparator performs a comparison of the floating point denominator, except for a sign bit of the floating point denominator, with a floating point value of 0.0. A logic element, responsive to a control signal indicative of the floating point divide operation, provides to the comparator equal sign bits associated with the floating point denominator and the floating point value of 0.0. A result of the comparison indicates a divide by zero operation and is independent of the sign of the floating point denominator. The result of the comparison is used to determine a course of action before the divide operation is completed.

Methods and apparatus for fast check of floating point zero or negative

A quadrilateral is divided into two triangles so that each of the two triangles may then be filled by a triangle fill scan converter. Additionally, the vertices of a triangle are sorted to generate inputs to a fill scan converter. A circuit combines the functions of dividing the quadrilateral into triangles and generating the plane equations for the triangle fill scan converter. Accordingly, similar operations which are performed for both triangles of the quadrilateral may be shared between the plane equations for the two triangles. A circuit also combines the functions of generating the plane equations for any one triangle with automatic sorting of the triangle vertices.

Method and apparatus for fast quadrilateral generation in a computer

A control logic unit outputs a group of encoded control signals that have less redundancy than the FPU signals needed to control a floating point processor, thus requiring fewer signal lines using less area. Decoders electrically connected between the control logic unit and the floating point processor decode the control signals to provide the FPU signals. If the number of control signals is one less than the number of FPU signals, a priority encoder is used as the decoder, unless the FPU signals include a power savings signal. Otherwise a custom decoder is used. The most active signal of the group of FPU signals is selected as the signal to be eliminated when a priority encoder is used.

Reduced area floating point processor control logic utilizing a decoder

Inputs to a line scan stepper of a line scan converter are generated for a line segment so that the inputs are rendered in a predetermined rendering direction. The predetermined rendering direction includes an implied orientation for line segments that have an implied orientation, such as single line segments and line segments that are part of a polyline. The predetermined rendering direction also includes a consistent direction for polygon edge line segments. For adjacent line segments of a polyline, vertices are swapped in a virtual manner so that a vertex that is shared between the adjacent line segments need be provided only once to the line scan converter.

Growing community of inventors

Fort Collins, CO, United States of America

Jon L Ashburn