Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-17
2001-04-24
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06222550
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to 3D graphics systems, and more particularly to multiple or parallel 3D pipelines.
BACKGROUND OF THE INVENTION
Portable notebook or laptop personal computers (PCs) have become enormously popular. Portable PC's have traditionally had lower-performance components than desktop PC's. In particular, these notebook PC's have suffered from lower-quality graphics while desktop PC's are more likely to have better graphics.
An extremely compute-intensive use of a PC is the rendering of three-dimensional (3D) objects for display on a two-dimensional display screen. Yet 3D-graphics applications are becoming more popular with computer users and should continue to gain popularity as higher-performance computers emerge.
Three-dimensional objects or surfaces are approximated as connected polygons, usually triangles. Greater detail can be obtained by using a greater number of smaller triangles to approximate the object as well as texture maps to render the surface material type. The 3D pipeline consists of two major segments or processes. The first segment is commonly referred to as Geometry. In turn, Geometry consists of Transformations and Lighting. First, the 3D polygonal database is transformed to image space through the mathematical transformations of translation, rotation, clipping, projection and scaling. Next, lighting and atmospheric effects are added. The second major pipeline segment is the Rasterization process. In turn, this process consists of triangle set-up and pixel rasterization. In a typical Application Interface (API), any or all pipeline segments may be accelerated in hardware. The focus of this invention relates to an improved method for hardware acceleration of the last stage, mainly Pixel Rasterization, henceforth referred to as the Pixel Engine (PE).
The image displayed on the computer's screen is generated from the position and attitude, surface attributes such as color and texture as well as environmental conditions such as lighting and atmosphere. The Geometry process produces image-space triangles described by three vertices and their color, depth, texture and other attributes. The Triangle Set-Up process produces the adjusted pixel positions as well as the attribute gradients. The Pixel Pipe then has the responsibility of generating all the pixel colors within the triangle. It uses the starting values and interpolates across the triangle by means of incremental methods; both linear and non-linear interpolations are required. The final color for each pixel is composited from all the attributes being combined in a manner selected by the application. Thus a large amount of computational work is needed to interpolate and composite the colors of the many pixels within the triangle.
The color of a pixel is designated by the intensity of the red, green, and blue (RGB) color components. Each color component may be encoded as a multi-bit binary value. Other components, such as depth, fog, texture, specular reflectivity, and the blending-factor alpha (&agr;), are often used. These components can be used for blending, shading, or distance effects and are herein designated by the letter A.
The 3D graphics engine first sets up individual triangles for rendering, performing any transformations necessary. Color, texture and other attribute values and their gradients for each triangle are output from a triangle setup engine (TSE) to the Pixel Pipes. A span engine (SE) “walks” each of the three edges of the triangle, determining endpoint pixel and attribute values where horizontal-line “spans” intersect the triangle edges. Then a raster engine (RE) receives an endpoint for a span and interpolates the attribute values for each pixel on the span. The visible pixels are then written to a frame buffer for display.
PARALLEL PROCESSING
Higher-performance 3D systems could benefit if superscalar or multiple pipelines were used. Rendering of pixels or triangles could be performed in parallel, multiplying the pixel throughput. Other systems, such as described by Kelly et al., U.S. Pat. No. 5,307,449, performed pre-processing during the previous frame rather than the current frame, increasing latency. Parallelism was provided on a scan-line basis by parallel pipelines. Watkins, U.S. Pat. No. 5,598,517, uses parallel rendering processors that render primitives using a multi-level hierarchy. Parallelism is provided for areas of triangles, rather than for the triangles themselves.
Parallelism may be provided in several different ways. Parallel raster engines (RE) could output pixels in parallel for the same scan lines in a triangle. Parallel span engines, each feeding a separate raster engine, could operate on two spans in the same triangle. Both of these schemes provide limited performance gains since parallelism is provided within a single triangle thus limiting the efficiency of load-balancing among parallel pipelines.
Better performance could be achieved by processing entire triangles in parallel. Since triangles contain many spans, a larger chunk of pixels can be processed in parallel, improving performance trough more efficient load-balancing among parallel pipelines. Unfortunately, synchronization of these parallel triangle pixel-pipelines is problematic under certain operational modes.
Triangles may vary widely in size, and thus some triangles may take much more time to render than others. When triangles being processed in the two pipelines overlap, special care is required to avoid display errors. A depth or Z buffer may be used to depth-resolve pixels in a triangle, allowing parallel triangle rendering. However, the two triangles being rendered may access the same pixel at the same time. One pipeline could update a pixel while the other pipeline is reading the pixel, resulting in a pixel error. Many clock cycles may be required during the memory access to read or write the pixel.
Semaphores or mailboxes may be used by the two pipelines to coherently share pixels.
FIG. 1
shows semaphores for pixels in a 3D parallel processor. Each pixel
12
contains the R,G,B and other component values. Stored along with each pixel
12
is semaphore
14
. Semaphore
14
is set by one pipeline to lock out the other pipeline from accessing the pixel after it has initiated a memory access to the pixel.
Although using semaphores
12
is a robust method to ensure coherency, table
10
can be quite large in size, since there may be more than one million pixels displayed. The additional bit may be difficult to ‘fit’ into commercially available memory chips usually configured along byte boundaries.
SCOREBOARD TABLES—FIG.
2
FIG. 2
illustrates a scoreboard method for pixel-access coherency for parallel triangle pixel-pipelines. Rather than provide a semaphore for each pixel on the screen, a scoreboard table is provided for each pipeline. The scoreboard contains a list of pixels currently being processed in that pipeline. The other pipeline must compare addresses of pixels entering its pipeline to the pixels in the other pipeline's scoreboard table. The pipeline is held or the new pixel is halted when a match occurs.
Pipeline
1
has scoreboard table
20
that includes pixel addresses
16
for each pixel being processed by pipeline
1
. Valid bits
18
are set as each pixel enters the pipeline, or alternately, as each pixel is accessed in memory. Once the pipeline has finished writing the pixel to memory, valid bit
18
is cleared for the pixel. Pipeline
2
likewise has scoreboard table
22
with pixel addresses
16
and valid bits
18
. Pipeline
2
must compare each pixel address
18
with a set valid bit
18
in pipeline
1
's scoreboard table
20
with the pixel address of any new pixels. Pipeline
1
must likewise compare each new pixel with each valid pixel address in pipeline
2
's table
22
.
While such scoreboard tables are useful, many pixels can be processed at a time in a pipeline. Thus many pixel addresses may need to be stored. Larger triangles may require many pixel addresses. Many comparisons are needed,
Li Ming-Ju
Rosman Andrew
Auvinen Stuart T.
NeoMagic Corp.
Nguyen Phu K.
LandOfFree
Multiple triangle pixel-pipelines with span-range pixel... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple triangle pixel-pipelines with span-range pixel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple triangle pixel-pipelines with span-range pixel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522431