Computer graphics processing and selective visual display system – Computer graphic processing system
Reexamination Certificate
1998-11-12
2002-03-19
Tung, Kee M. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphic processing system
C345S561000, C345S421000
Reexamination Certificate
active
06359623
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a computer graphics display system and, more particularly, to a method and apparatus for performing scan conversion in a computer graphics display system.
BACKGROUND OF THE INVENTION
In three-dimensional (3-D) computer graphics display systems, primitives are rendered on a display device of the computer graphics display system to produce a visual image on the display device. Each primitive is defined by X, Y and Z values of the primitive, by the normals of the vertices of the primitive, and by the colors of the vertices. Computer graphics display systems have been proposed which would utilize a Z pyramid memory element, or Z buffer, to test for primitive occlusion. For example, one such system was proposed in an article entitled “Hierarchical Z-Buffer Visibility”, SIGGRAPH 93, Anaheim, Calif., Aug. 1-6 1993, by Greene, et al., that would utilize a Z pyramid memory element, or Z buffer, to test for primitive occlusion.
In the system proposed by Greene et al., the Z buffer stores the Z values for a current frame of pixels in a data structure arranged as a pyramid of Z values. These Z values in the pyramid are utilized in a hierarchical tiler to test new Z values to determine whether a each primitive associated with a new Z value is occluded. If a primitive is found to be occluded, there is no need to scan convert the primitive into pixels because the occluded primitive should not be displayed on the display device. This is because, if the occluded primitive is displayed, the occluded primitive will cover another primitive which is supposed to be in front of the occluded primitive in the image being rendered on the display device.
The article by Greene, et al. discusses building the Z pyramid from the original Z buffer and using the Z pyramid to test cubes comprised of a plurality of primitives for occlusion culling. This approach makes use of the observation that the cube is hidden with respect to the Z buffer if all of its faces correspond to hidden polygons.
Prior to performing this comparison, the Z pyramid is constructed by starting with pixel-level Z values as the base of the pyramid and by comparing subgroups of adjacent Z values to determine the maximum Z value for each subgroup. The maximum Z value for that subgroup is then stored in the Z buffer for the next level up in the pyramid. For example, if 64 Z values were contained in the Z buffer when the comparison began, the next level up in the pyramid will contain 16 Z values, with each of the 16 Z values corresponding to the maximum Z value of the four pixels compared in the corresponding subgroup in the level below it.
In this next level up, the Z values of each subgroup of four adjacent Z values are compared to determine the maximum Z value for each subgroup and then this maximum Z value is stored in the Z buffer for the next level up in the pyramid. Therefore, for the next level up in the pyramid, the Z buffer will contain four Z values. These four Z values are then compared to determine the maximum Z value, which is stored in the Z buffer for the next level up in the pyramid. This last maximum Z value corresponds to the top of the pyramid.
In the computer graphics display system proposed by Greene et al., once the Z pyramid has been constructed, the Z values for the primitives making up the faces of the cubes are compared beginning at a particular level of the pyramid and working down towards the base of the pyramid. For each primitive, the minimum Z value of the primitive is tested against the levels of the pyramid in a top-to-bottom sequence. If the minimum Z value for the primitive is greater than the pyramid Z value, then the primitive is fully occluded. If all of the primitives making up the faces of the cube are occluded, the cube is occluded and can be discarded. If not, the process continues at each level of the pyramid until the cube is either fully occluded or until the process reaches the level in the Z pyramid at which a primitive is found to be at least partially visible. Once a primitive corresponding to a face of the cube is found to be at least partially visible, the entire cube is scan converted into pixels using a typical scan conversion process.
Scan conversion is a process which determines the exact pixel locations on the screen of the display device that correspond to the primitives. Scan conversion is normally performed by an edge stepper engine which steps down along the edges of a primitive until a point on the edge of the primitive is reached at which the primitive intersects a scan line, and then steps across the span corresponding to the scan line to determine the point on the opposite side of the primitive at which the scan line intersects the primitive.
One disadvantage of the typical approach to performing scan conversion is that the typical approach begins at the pixel level at a starting pixel location, which must be determined for each span by either the host central processing unit (CPU) or by the geometry accelerator of the computer graphics display system. Determining the starting pixel location and the parameters associated with the starting pixel location for each span is a mathematically intensive process. Once the starting pixel location and the parameters associated with it have been determined for a particular span, the edge stepper then steps across the primitive in the above-discussed manner.
Another disadvantage of the typical approach to scan conversion is that it results in one-dimensional locality of pixels because of the manner in which an entire span of pixels are obtained for a scan line in the x direction (i.e., horizontal) before the next span of pixels are obtained for the next scan line. This results in one-dimensional grouping of pixels, i.e., grouping in terms of the x dimension in screen space, which does not facilitate organization and storage of pixels in the frame buffer memory. In order to maximize the speed with which pixels are read out of the frame buffer memory and sent to the display monitor, it is desirable to group pixels in the frame buffer memory in groups having two-dimensional locality, i.e., in terms of the x and y dimensions in screen space.
It would be advantageous to utilize a scan conversion process which would eliminate the necessity of determining the starting pixel location for each span and thereby simplify the scan conversion process. It would also be advantageous to link the scan conversion process with the occlusion testing process performed in the hierarchical tiler in order to take advantage of the hierarchy of the Z pyramid. This would enable the occlusion testing process and the scan conversion process to be performed simultaneously in the hierarchical tiler, which could significantly increase the overall throughput of the computer graphics display system. It would also be advantageous to utilize a scan conversion process which scan converts primitives into pixels which are grouped in terms of the x and y dimensions in screen space.
Accordingly, a need exists for an improved method and apparatus for performing scan conversion. A need also exists for a scan conversion process, which is performed in a hierarchical tiler simultaneously with occlusion testing.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for performing scan conversion in a computer graphics display system to determine pixel locations in screen space corresponding to a primitive being scan converted. Screen space corresponds to x and y coordinates of pixel locations on a display monitor of the computer graphics display system. The apparatus of the present invention comprises logic configured to convert a primitive into pixel locations in screen space, wherein each pixel location is defined by an x coordinate and by a y coordinate in screen space. Each primitive has a plurality of vertices, each of which is defined by an x coordinate and by a y coordinate in screen space.
The logic, which will be referred to hereinafter as the hierarchical tiler, subdivides the screen s
Hewlett--Packard Company
Tung Kee M.
LandOfFree
Method and apparatus for performing scan conversion in a... 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 apparatus for performing scan conversion in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing scan conversion in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844990