Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-08
2004-08-10
Le, Uyen (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C712S014000, C716S030000
Reexamination Certificate
active
06775667
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems, and more particularly to a method and system for providing a hardware sort which is efficient and applicable to computer to, graphics system.
BACKGROUND OF THE INVENTION
Many computer systems must sort items based on the value of a key in order to achieve certain functions. Many such computer systems conventionally employ a software sort. For example, computer graphics systems may utilize a software sort in order to render an image. In current computer graphics systems, images of three-dimensional objects can be depicted on a two-dimensional display. The display typically includes a number of pixels arranged in a grid. To render an image, the image is typically broken into polygons. Each polygon may cover one or more pixels in the display. In order to give the illusion of depth, computer graphics systems use each polygon's “z value,” the distance of each polygon to the viewing plane. In particular, the polygons are ordered based on each polygon's z value. Thus, the key for such a sort is the z value. Once the polygons are sorted according to their z values, the computer graphics system can correctly blend the colors of translucent polygons and opaque polygons that can be seen through the translucent polygons to achieve the proper color to be displayed for each pixel.
In a conventional computer graphics system, the software sort occurs when a display list is generated through an application. The display list orders portions of three-dimensional objects, i.e. polygons, based on a key, typically the z value. The display list typically orders translucent polygons from back to front. Thus, the display list sorts translucent polygons. Although they may appear on the display list, opaque polygons are typically sorted using a conventional Z buffer.
Placing the polygons in the order prescribed by the display list allows the computer system to properly depict the images of the three-dimensional objects on the display. Hardware in the computer graphics system utilizes the display list, a frame buffer, and a z buffer to render the three-dimensional objects in the order dictated by the display list. The frame buffer and z buffer describe a portion of the three-dimensional object that is to be rendered. The frame buffer includes data such as color and alpha values for the polygon, while the z buffer includes the corresponding z values. The conventional computer graphics system provides the polygons described in the frame and z buffers to the display screen in the order prescribed by the display list. Thus, the display list generated by software is used to render the three-dimensional objects.
Although conventional computer graphics systems are capable of depicting three-dimensional objects, the software sort that generates the display list can be relatively slow. If the software sort is optimized, the sort time can be reduced to a limited extent. However, development time for the software sort is significantly increased. Moreover, changes to the display list and the software sort creating the display list may be difficult to implement. Finally, since the hardware requires a display list in order to properly render the objects, the computer system is limited to using those applications which provide a sorted display list. Without the display list and the attendant software sort, the computer system may not be able to properly depict three-dimensional objects.
A method and system for performing a hardware sort is described in co-pending U.S. patent application Ser. No. 09/062,872 entitled “Method and System for Providing a Hardware Sort in a Graphics System” filed on Apr. 20, 1998 and assigned to the assignee of the present application. Applicants hereby incorporate by reference the above-mentioned co-pending patent application. The hardware sort described in the above-mentioned co-pending application can be used to sort polygons for rendering on a display.
FIG. 1
is a block diagram of one embodiment of a hardware sorter
10
described in the above-mentioned co-pending application. The hardware sorter
10
is used by a computer graphics system which preferably renders a graphical image pixel-by-pixel. However, the system
10
can be used in another computer system for other purposes or in a computer graphics system which does not render an image pixel-by-pixel. The hardware sorter
10
sorts based on a particular key associated with a particular item. The key value is the z-value for a fragment. The fragment for a particular polygon includes data for the portion of the polygon that intersects a particular pixel. Such a polygon is termed an intersecting polygon for the particular pixel. More than one intersecting polygon can intersect a particular pixel. Although the hardware sorter
10
is described as sorting based on a z value, nothing prevents the hardware sorter
10
from sorting based on another key or accepting other types of data. Thus, the hardware sorter
10
is applicable to other systems requiring a sort, such as a router in a network.
The hardware sorter
10
includes a plurality of sort cells
11
. Note that although only four sort cells
11
are depicted, nothing prevents the hardware sorter
10
from having another number of sort cells
11
. In an embodiment disclosed in the above-mentioned co-pending application, the number of sort cells
11
is at least equal to the number of items to be sorted. Thus, in one embodiment, the number of sort cells
11
is the same as the number of processors which are used to process the fragments for intersecting polygons of a particular pixel in parallel. As disclosed in the above-mentioned co-pending application, the number of sort cells is typically sixteen. However, nothing prevents the use of another number of sort cells
11
.
The hardware sorter
10
further includes a new input line
12
for providing a new fragment in parallel to each of the sort cells
11
via new input
12
. Each sort cell
11
also includes an output
13
. The output
13
of a sort cell
11
is coupled to an input of a next sort cell
11
. The output
13
of the last sort cell
11
is not coupled to another sort cell
11
. Instead, the output
13
of the last sort cell
11
provides the output of the hardware sorter
10
.
The hardware sorter
10
generally functions as follows. Each sort cell
11
may have a fragment which corresponds to it (“corresponding fragment”). Each corresponding fragment includes a corresponding z value, which is used to sort the fragment, and corresponding data, such as color and alpha values for the corresponding fragment. A new fragment, including the new z value, is broadcast to each of the plurality of sort cells
11
. Generally, if the new fragment is the first fragment for a pixel, the first fragment is also placed in the first sort cell
11
. Where the new fragment is a first fragment for a pixel when the hardware sorter
10
is empty, the first fragment is placed in the first sort cell
11
. This may be accomplished by indicating that data in other sort cells
11
is invalid.
The new z value for the new fragment is compared to the corresponding z value in each sort cell
11
. Preferably, this function is accomplished using a comparator (not shown). Based on this comparison, each sort cell
11
retains the corresponding fragment, accepts the new fragment, or accepts the fragment corresponding to a previous sort cell
11
. If the corresponding fragment is to be retained, then the sort cell
11
keeps the corresponding fragment. If the corresponding fragment is not to be retained, then it is determined whether the sort cell
11
is to take the fragment corresponding to a previous sort cell
11
. If the sort cell
11
is to accept this fragment, the sort cell
11
takes the fragment corresponding to the previous cell and passes its corresponding fragment to be accepted by the next sort cell
11
. If the corresponding fragment from the previous sort cell
11
is not to be taken by the sort cell
11
, the sort cell
11
takes the new fragment and passes i
Lewis Michael C.
Movshovich Aleksandr
Broadcom Corporation
Le Uyen
Sawyer Law Group LLP
LandOfFree
Method and system for providing a hardware sort for a large... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for providing a hardware sort for a large..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for providing a hardware sort for a large... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301285