Computer graphics processing and selective visual display system – Computer graphics display memory system – Memory partitioning
Reexamination Certificate
2002-02-19
2004-08-17
Tung, Kee M. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Memory partitioning
C345S443000, C345S506000
Reexamination Certificate
active
06778177
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for rasterizing a graphic primitive and, in particular, to an accelerated method for rasterizing a graphic primitive in a graphics system in order to generate pixel data for the graphic primitive from graphic primitive description data.
BACKGROUND OF THE INVENTION AN DESCRIPTION OF THE PRIOR ART
For accelerating the process of image-rendering of three-dimensional images, it is known to use multi-processors or hardware pipelines in parallel. Each of these units acts upon a sub-set of the information contained in an entire image, as has been described by James D. Foly et. al in “Computergraphic Principles and Practice”, second edition, 1990, pages 887 to 902. This task can be divided up by either processing, in parallel, objects (polygons) in the image, or by processing certain sections of the image in parallel. Mere implementation of the division of objects leads to a subdivision of the object level description of a scene (vertex list), so that each of the processors is equally loaded. This division is carried out independently of the arrangement of the respective objects in the three-dimensional world or in a frame buffer.
The implementation of the division of the task by forming sections in an image is effected by subdividing a frame buffer into sub-sections which normally have the same size. With regard to dividing the frame buffer, there is the possibility of either associating the same with large, continuous pixel blocks or of effecting the association in an interleaved manner.
FIG. 21
shows the above-described possibilities of partitioning a frame buffer with regard to the case of a graphics system operating with four graphics processing engines.
FIG. 21
a
shows the association of large continuous pixel blocks to the respective graphics processing engines. As can be seen, in this exemplary case, the frame buffer
10
is subdivided into four equallysized blocks which are associated to the engines.
FIG. 21
b
shows the interleaved frame partitioning of the frame buffer
10
, and it can be seen that the processing of the individual pixels
12
, which are represented by the boxes in
FIG. 21
, is effected in an interleaved manner by the four graphics processing engines of the graphics system.
Interleaved partitioning is used very frequently, since it offers the advantage that the workload of the individual processors is automatically balanced. Except for the smallest polygons, all polygons are located in all partitions of the frame, so that almost every image renderer is supplied with the same number of pixels. Interleaved frame buffer partitioning is also referred to as “distributed frame buffer”.
FIG. 22
shows a block diagram of a conventional graphics system having a pipeline for pixel processing. The graphics system, in its entirety, is denoted by reference numeral
14
and includes a scan converter
16
receiving, at its input, data which write onto the graphic primitive, e.g., a polygon, to be processed. The scan converter
16
processes the received data and produces, at its output, interpolator commands which are entered into a parameter interpolator
18
. The output of the parameter interpolator
18
is connected to a first input of a pixel pipeline
20
. The output of the pixel pipeline
20
is connected to a memory subsystem
24
via a packing unit
22
. Data from the memory subsystem
24
are supplied to the second input of the pixel pipeline
20
via a depacking unit
26
.
FIG. 23
shows a block diagram of a conventional graphics system with a plurality of pipelines working in parallel. The graphics system, in its entirety, is denoted by reference numeral
28
, and identical or similar elements, such as in the system in
FIG. 22
, are provided with the same reference numerals. Unlike the graphics system illustrated in
FIG. 22
, the scan converter
16
is designed as a parallel scan converter and, similarly, the parameter interpolator
18
is designed as a parallel parameter interpolator. This parallel parameter interpolator
18
has a plurality of outputs for supplying data to a plurality of pixel pipelines
20
0
-
20
n
, outputs of the pixel pipelines being connected with the packing unit
22
. The depacking unit
26
is connected with the second inputs of the respective pixel pipeline
20
0
-
20
n
.
Parallel image processing using interleaved frame partitioning constitutes a very suitable method for hardware implementation of image-rendering pipelines, as shown in FIG.
23
. The memory subsystem
24
typically manages so-called memory words containing a plurality of pixels. A 128-bit word, for example, contains four color pixels (true color pixels), with each pixel including
32
bits. The memory subsystem
24
can either read or write such a word during a clock cycle. In a graphics system having a single pixel pipeline, such as is shown in
FIG. 22
, the depacking unit
26
must, for fragment calculation (e.g., texture fade-overs, reflecting additions, target fade-overs, dithering, raster operations, and the like), extract one pixel per clock and convert it into the internal color format. Packing unit
22
converts the results of the pixel pipeline calculation into the color format stored in the memory and unites several pixels to form one memory word.
Systems having several image-rendering pipelines, as are shown in
FIG. 23
, can process, in parallel, several pixels contained in one memory word. If the number of pixel pipelines is equal to the number of pixels per memory word, packing and depacking the same becomes trivial.
Graphics processing systems mostly use image-rendering engines whose primitives are polygons. In addition, these polygons are limited to certain types, such as triangles or quadrilateral elements. More complex polygons can then be defined using these graphic primitives.
The basic challenge in processing graphic primitives is that determining whether a point in a screen area is within or outside the graphic primitive to be rendered must be as simple as possible. For triangles, this can be achieved, for example, in that the three edges forming the graphic primitive are written onto by means of linear edge functions.
FIG. 24
shows an example of a linear edge function. In the Cartesian co-ordinate system in
FIG. 24
, an edge
30
of a graphic primitive is illustrated by way of example, and the starting point and the end point, respectively, of the edge are determined by the co-ordinates x
0
and y
0
and x
1
and y
1
, respectively.
It can be determined by the edge function indicated in the right-hand section of
FIG. 24
whether a point within the Cartesian co-ordinate system is located to the left or the right of the edge or on the edge. Point P is located on the edge
30
and, in this case, the value for the edge function is 0. Point Q is located to the right of edge
30
and, in this case, the result of the edge function is larger than 0, whereas for point R, which is located to the left of edge
30
, the result of the edge function is smaller than 0. In other words, each of the linear edge functions yields a value of 0 for co-ordinates which are located exactly on the edge or on the line, a positive value for co-ordinates located to one side of the line or edge, and a negative value for co-ordinates located to the other side of the line or edge. The sign of the linear edge function subdivides the drawing surface into two half-planes.
Linear edge functions are further described in the following articles: J. Pineda “A Parallel Algorithm for Polygon Rasterisation” Seggraph Proceedings, Vol. 22, No. 4, 1988, pages 17 to 20; H. Fuchs et. al, “Fast Spheres Shadows, Textures, Transparences, and Image Enhancements in Pixel-Planes”; Seggraph Proceedings, Vol. 19, No. 3, 1985, pages 111 to 120; Dunnet, White, Lister, Grinsdale University of Sussex, “The Image Chip for High Performance”, IEEE Computer Graphics and Applications, November 1992, pages 41 to 51.
By multiplying the edge functions with the value of −1, the sign for the half-planes can be inverted, and the edg
Dougherty, Clements Hofer, & Bernard
SP3D Chip Design GmbH
Tung Kee M.
LandOfFree
Method for rasterizing a graphics basic component 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 for rasterizing a graphics basic component, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rasterizing a graphics basic component will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3360355