Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-10
2002-09-24
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000
Reexamination Certificate
active
06456284
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to graphics computer systems, and more particularly to a graphics processor, system and method for generating screen pixels in raster order utilizing a single interpolator.
BACKGROUND OF THE INVENTION
In conventional computer systems, images are displayed on a two-dimensional screen. The images are defined by arrays of pixels which are either stored in computer memory or received from sources connected to the computer system.
Many images of physical objects may be defined three-dimensionally and may be stored or received as three-dimensional raw data arrays. In recent years, efforts have been undertaken to utilize three-dimensional raw data to take into account the distance and various characteristics of objects within screen images. One of the problems associated with the generation and display of such screen images is the size and complexity of circuitry and logic currently required, to produce a stream of screen image data in the order required by a display. Various techniques have been developed to produce the screen data stream utilizing multi-stage graphics computer systems.
One of the graphics computer systems which have been developed to produce the screen data stream is shown in FIG.
1
A. Graphics computer system
101
may be implemented with a conventional X86 (such as the 400 series) IBM-compatible or MacIntosh personal Computer or a graphics engine that includes application unit
103
which generates geometries that are to be rendered. The output of application unit
103
is a stream of geometry data characterized in three-dimensional space. Transformation unit
105
transforms the geometry data from three-dimensional spatial coordinates to two-dimensional display coordinates corresponding to the screen plane. Transformation unit
105
also reformats the geometry data into a more unified format. For example, transformation unit
105
may accept as input independent polygons, quad strips, concave polygons and higher and only output triangle strips. The output of transformation unit
105
includes graphics primitives readable by rasterizer
107
in display coordinates. Rasterizer
107
receives the graphics primitives and converts them to pixels which in turn are transmitted to display
109
to generate a screen image.
Another graphics computer systems which has been developed to produce the screen data stream is shown in. FIG.
1
B. Graphics computer system
151
is shown which includes frame buffer
111
. Frame buffer
111
is utilized by system
151
to decouple the rendering process from a video refresh rate. This permits the image undergoing rendering to be updated at a slower rate than the screen image shown on display
109
is refreshed. Some implementations of rasterizers
107
require associated frame buffers
111
to reorder pixels into screen refresh order. The output of frame buffer
111
, or rasterizer
107
if no frame buffer
111
exists, is a stream of pixels, where each pixel contains one color associated with one screen pixel.
With reference to
FIG. 2A
, conventional rasterizer
107
is shown which outputs pixels in polygon order. The conventional rasterizer includes slope, vertical, horizontal slope, and horizontal processing units designated as delta calculation, vertical interpolate, horizontal delta calc, and horizontal interpolation units
203
,
205
,
207
,
209
respectively.
An example of triangle primitives rasterized by rasterizer
107
are shown in FIG.
2
B. The triangles are type classified as: top, bottom, left, and right facing triangles
253
,
255
,
257
,
259
.
Conventionally, rasterizing occurs in three steps. The first rasterizing step converts the three point format of the triangle into three edges. The edges are usually described in the form of By+C. The second rasterizing step evaluates points along the edges of the triangle. There are two interpolators utilized in the second step, one for the left edge on for the right edge. The output of the interpolator are referred to as spans, which are horizontal lines defined by a y-value, left and right x-values and any other parameters of the polygon defined at the ends of the span. The third rasterizing step also utilizes an interpolator which accepts a span and outputs the pixels that the span defines. For each pixel, the interpolator outputs the y-value and x-value of the current pixel and the value of the parameters of each pixel.
Graphics computer systems
151
utilizing such conventional rasterizers
107
require frame buffer
111
to reorder the pixels into the order needed by display
109
and also require a color unit to determine which pixel is visible and carries the color to be utilized by the associated screen pixel. Software applying the painters' algorithm provide a simple process to perform this task, which follows the rule that the last pixel sent to a pixel in frame buffer
111
replaces the pixel stored within frame buffer
111
. However, in order to perform this operation, the polygon data sent to rasterizer
107
must be sorted from back-to-front.
Conventional hardware, such as SGI-GTX manufactured by Silicon Graphics, Inc., that does not require back-to-front sorting applies a z-buffer algorithm. Z-buffer algorithms utilize an additional buffer, referred to as the z-buffer, that stores range values (z-values) as described by K. Akeley and T. Jermoluk in “High-Performance Polygon Rendering”, SIGGRAPH 88, 239-246. The pixel currently stored in frame buffer
111
and z-buffer is read by rasterizer
107
and the z-values of the new pixel and the pixel in frame buffer
111
are compared by rasterizer
107
. If the new pixel is in front of the pixel in frame buffer
111
then the new pixel replaces the pixel in frame buffer
111
, otherwise the new pixel is discarded. Some algorithms that determine the color of a screen pixel require information about more than just the frontmost polygon that intersects a screen pixel. Examples of cases where information about multiple polygons is needed include: anti-aliasing, CSG (constructional solid geometry), and transparency. One solution is to modify frame buffer
111
to hold a list of pixels at each point and after all polygons have been rendered process the list of rendered pixels at each screen pixel into a single color.
Other work has been done to modify graphics computer systems which use z-buffers to provide some of the features of the multiple pixel/screen pixel system without the cost of the memory needed by the multiple pixel/screen pixel system, for example by drawing the polygons in front-to-back or back-to-front order.
Rasterizers
107
that operate on data in polygon order are efficient, since a single interpolator rasterizes multiple polygons and, as long as there are polygons to be rasterized, the interpolator can be rendering. One of the disadvantages is that the pixels are not output in raster order and need to be reordered by frame buffer
111
. Additionally, since the pixels are output in polygon order, it is impossible to merge pixels from different polygons into a single screen pixel before the pixels are written into frame buffer
111
as a result the bandwidth needed into frame buffer
111
is very high. Another disadvantage is that if the color algorithm requires information about more than one rasterized pixel in each screen pixel either a very large frame buffer must be used or the polygons must be presorted, and presorted does not work in all cases.
A technique used to produce and transmit pixels in raster order is implemented with processor per primitive architecture
301
as partially shown in FIG.
3
. Processor architecture
301
includes array
303
of n processor-interpolator pairs. Each processor-interpolator pair of array
303
renders one polygon over the entire screen. The interpolators used in a processor per primitive are similar to those interpolators used in the polygon order system except that since the pixels are output in raster order there is no need to output the coordinate of each pixel. Instead, there is a need
Lewis Michael C.
Morein Stephen L.
Broadcom Corporation
Sawyer Law Group LLP
Vo Cliff N.
LandOfFree
Graphics processor, system and method for generating screen... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graphics processor, system and method for generating screen..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphics processor, system and method for generating screen... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860746