Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-02-02
2003-01-14
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
Reexamination Certificate
active
06507348
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to computers and more particularly to video graphics processing involving the generation of geometric primitives.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates a schematic block diagram of a computing system
10
that includes a central processing unit
12
, a chipset
14
, system memory
16
, a video graphics circuit
18
, and a display
20
. The video graphics circuit
18
includes a raster engine
22
and a frame buffer
24
. The system memory
16
, for processing video graphics data, includes geometry software
26
and texture maps
28
. The display
20
may be a CRT display, LCD display, or other type of computer display.
To process video graphic data, the central processing unit
12
executes the geometry software
26
to produce geometric primitives. The geometric primitives include attributes for each vertex of a triangle, where a plurality of triangles constitutes an object to be displayed. The attributes of the geometric primitives include spatial coordinates, texture coordinates, color data, and specular color data. Upon receiving the geometric primitives, the raster engine generates pixel data from the geometric primitives for each vertex and stores the pixel data in frame buffer
24
. In essence, the raster engine
22
generates pixel data for each pixel within a given triangle based on the geometric primitives of the vertices of the triangle. Once the raster engine has generated pixel data for an entire frame, or field, the raster engine retrieves the pixel data from the frame buffer
24
and provides it to display
20
for display. During the generation of pixel data, if the geometric primitives include a texture coordinate, the raster engine
22
retrieves texture information from texture maps
28
.
The geometry software
26
uses a Sutherland-Hodgeman Polygon Clipping Algorithm to produce the geometric primitives. In general, the Sutherland-Hodgeman Polygon Clipping Algorithm compares the vertices of each triangle of an object with a plane of a clip volume or one of a plurality of user defined planes.
FIG. 2
illustrates a clip volume, which includes six planes. As shown, the planes include a near plane
32
(which corresponds to an eye plane), a far plane
34
(which corresponds to the screen), a top plane
36
, a bottom plane
38
, a left-side plane
40
, and a right side plane
42
.
If the plane does not clip (i.e., intersect the triangle), another plane is compared. The Sutherland-Hodgeman Polygon Clipping Algorithm compares each plane with the triangle to determine whether a plane clips the triangle. If none of the planes clip the triangle, the geometric primitives of the triangle corresponding to the three original vertices are provided to the raster engine. If, however, at least one plane intersects the triangle, the Sutherland-Hodgeman Polygon Clipping Algorithm determines a clipping distance from each vertices with respect to the clipping plane (e.g., the clipping distances may correspond to d
1
, d
2
, and d
3
). If a vertex is within the clip volume, the clipping distance will be positive, if a vertex is outside the clip volume, the clipping distance would be negative. A positive clipping distance has a “zero” clip code and a negative clipping distance has a “1” clip code.
Having obtained the clip codes and clipping distances, the Sutherland-Hodgeman Polygon Clipping Algorithm determines the new vertices for the clipped triangle. To begin the Sutherland-Hodgeman Polygon Clipping Algorithm utilizes a clip code table to determine an operation to be performed. The clip code table includes binary codes for previous and current vertices and the corresponding operation. The following is an example of the clip code table.
previous vertex
current vertex
clip code
clip code
corresponding operation
0
0
add current vertex to clipped triangle
vertices list
0
1
calculate new vertex and add it to the
list, remove current vertex from the list
1
0
calculate new vertex and add it to the
list, and maintain the current vertex in
the list
1
1
remove the current vertex from the list
For a given triangle, V
1
, V
2
, and V
3
represent the three original vertices. For a first clip code table look-up, V
3
is the previous vertex and V
1
is the current vertex. For a second look up, V
1
is the previous vertex and V
2
is the current vertex. For a third look up, V
2
is the previous vertex and V
3
is the current vertex. For example, if V
1
and V
2
have a “zero” clip code, and V
3
has a “one” clip code the three table look ups have a binary code of (1,0), (0,0), and (0,1). Thus, the operation for V
3
to V
1
will be to add the current vertex (e.g., V
1
) and calculate and add a new vertex (e.g., C
0
). The operation for V
1
to V
2
will be to add the current vertex (e.g., V
2
). The operation for V
2
to V
3
will be to calculate and add a new vertex (e.g., C
1
).
To calculate the spatial coordinates of the new vertices (e.g., C
0
and C
1
), the Sutherland-Hodgeman Polygon Clipping Algorithm utilizes the homogenous vertex spatial coordinates (e.g., X, Y, Z, W) and the clipping distances. Such a calculation is process intensive. In addition to calculating the coordinates, the Sutherland-Hodgeman Polygon Clipping Algorithm determines the attributes (e.g., RGB color components, texture coordinates, etc.) for each of the new vertices.
As these values are calculated, they are stored in memory. Having stored these values, the Sutherland-Hodgeman Polygon Clipping Algorithm performs the same process for the next plane that clips the triangle and continues until all clipping planes have been processed. As one can imagine, the Sutherland-Hodgeman Polygon Clipping Algorithm requires a substantial amount of memory to store the attributes for all the vertices of a clipped triangle. For example, if each attribute is a 32 bit word, each vertex has 32 attributes, and there are 12 clipping planes, the memory requirement would be (12 plus 3)×32×32, which equals 2 K bytes of memory. Note that the 12 plus 3 corresponds to 12 clipping planes plus the three for the original vertices. Since a triangle is rarely clipped by more than a few planes, most of this memory is not used.
Once the attributes for the final vertices have been obtained, the geometry software
26
then performs lighting and/or texture processing for the clipped triangle. As is known, the lighting function determines the particular lighting effect that is to be rendered. The lighting effect may be from a single light source or a plurality of light sources wherein the light sources is either close to the object or at a diffused distance. The texture coordinate processing includes texture transformation or texture generation. Since the lighting and/or texture mapping functions are dependent on the finalized vertices of the clipped triangle, these processes must be performed after the clipping process. As such, they are done in a serial manner.
Therefore, a need exists for a method and apparatus that provides for parallel processing of geometric primitives and reduces memory requirements such that a hardware geometry engine may be practically implemented.
REFERENCES:
patent: 3816726 (1974-06-01), Sutherland et al.
patent: 5361386 (1994-11-01), Watkins et al.
Baldwin, Aug. 13, 1998, US Patent Application Publication 2002/0030693A1.*
Open GL—Programming Guide Ver 1.2 p. 38-41.
Barycentric Coordinates May 22, 1999.
Barycentric Coordinate—Geometric Problem May 22, 1999.
Van Obel Theorem & Barycentric Coordinates May 22, 1999.
Mang Michael A.
Manter Michael J.
Pringle Thomas B.
Taylor Ralph C.
ATI International SRL
Brier Jeffery
Cunningham G. F.
Vedder Price Kaufman and Kammholz
LandOfFree
Method and apparatus for clipping an object element in... 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 clipping an object element in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for clipping an object element in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3046993