Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-03-17
2002-08-20
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S441000, C345S443000, C345S620000
Reexamination Certificate
active
06437780
ABSTRACT:
CROSS REFERENCE TO MICROFICHE APPENDIX
Appendix A, which is part of the present disclosure, is included in a microfiche appendix consisting of 1 sheet of microfiche having a total of 31 frames, and the microfiche appendix is incorporated herein by reference in its entirety. Microfiche Appendix A is a listing of pseudo code for computer programs and related data that can be prepared in the language VERILOG for implementing circuitry including a synchronizer that receives and stores graphics data for the generation of a screen display, for use with one illustrative implementation of this invention as described more completely below.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
A personal computer
10
(
FIG. 1A
) includes a graphics processor
14
that generates a display of a three-dimensional (abbreviated as “3D”) image on a screen
11
under the control of a central processing unit
15
. Graphics processor
14
forms the displayed image from descriptions of one or more graphics primitives, such as a line
16
(
FIG. 1B
) that connects points “A” and “B”, a triangle
17
(
FIG. 1C
) that connects points “C,” “D,” and “E,” a fan
18
(
FIG. 1D
) and a strip
19
(FIG.
1
E).
The image displayed on screen
11
is typically formed by a two-dimensional array of picture elements (called “pixels”) P
101
-P
109
(not all pixels are labeled in
FIG. 1F
) each of which has one or more attributes (such as color or texture). To reduce the hardware required to process all pixels at once, a screen
11
is subdivided into rectangular areas (called “tiles”) T
1
-TN, and each tile TI contains an equal number of pixels (e.g. 16 pixels) that form a portion of the displayed image. Each tile TI (in this example formed by the sixteen pixels being arranged in a square four pixels tall and four pixels wide) is held and processed one at a time in an on-chip memory included in graphics processor
14
.
In such a “tiled” architecture, it is necessary to determine the identities of tiles that are covered by one or more graphics primitives (such as triangles
110
and
120
in
FIG. 1F
) that are to be displayed on screen
11
. In the example illustrated in
FIG. 1F
, triangle
110
has vertices
111
-
113
and sides
114
-
116
, whereas triangle
120
has vertices
112
,
113
and
117
, and sides
116
,
118
and
119
. The touching of a tile TI (wherein 1≦I≦N) by triangles
110
and
120
is indicated by the presence (or absence) of the triangles' identifiers in a “bin” associated with tile TI, as shown in Table 1 below:
TABLE 1
Tile
Bin
Tile
Bin
Tile
Bin
T1
—
T11
—
T21
110, 120
T2
—
T12
—
T22
120
T3
110
T13
—
T23
120
T4
110
T14
110
T24
—
T5
—
T15
110
T25
—
T6
—
T16
110, 120
T26
110, 120
T7
—
T17
120
T27
120
T8
—
T18
—
T28
120
T9
110
T19
—
T29
120
T10
110
T20
110
T30
—
For convenience, not all bins are shown in Table 1. One prior art method (also called “brute force” method) for the “binning” of triangles (that is performed to obtain Table 1) examines each tile TI (wherein 1≦I≦N) in screen
11
, and checks whether any of triangles
110
and
120
covers tile TI.
Another prior art method (also called “bounding box” method) uses a rectangle (called “bounding box”) that touches the vertices of a triangle to be binned, and identifies all tiles within such a bounding box. For example, a bounding box
121
can be drawn around vertices
111
-
113
of triangle
110
, followed by identification of tiles T
2
-T
4
, T
8
-T
10
, T
14
-T
16
, T
20
-T
22
and T
26
-T
28
that are located within bounding box
121
.
The bounding box method results in certain tiles (e.g. tiles T
2
and T
8
) being identified although these tiles are not touched by the triangle being binned (e.g. triangle
110
). However, the bounding box method eliminates the need to examine (for triangle
110
) tiles that are outside of bounding box
121
(such as tiles T
1
, T
5
-T
7
, T
11
-T
13
, T
17
-T
19
, T
23
-T
25
and T
29
-TN). Therefore, the bounding box method is more efficient than the brute force method. Bounding boxes (also called “extent” boxes) are described in the book entitled “Computer Graphics, Principles and Practice” by Foley, van Dam, Feiner and Hughes, Addison-Wesley Publishing Company, Second Edition in C, 1996 (see pages 660-663; see also pages 336-337).
SUMMARY
A circuit (hereinafter “geometry tiler”) in accordance with this invention implements a method described herein to identify one or more tiles (in the form of, e.g. rectangular areas) on a computer's screen that are covered by (or touched by) a convex polygon (defined to be a polygon wherein each diagonal is fully contained within the polygon, and wherein each diagonal connects two vertices that do not belong to the same line segment of the polygon). Specifically, the geometry tiler identifies tiles (either precisely or approximately) by use of edges of the graphics primitive.
In one embodiment, the geometry tiler identifies the following types of tiles that are covered by or touched by a convex polygon: (a) vertex tiles, (b) edge tiles, and (c) interior tiles. Vertex tiles are tiles that are covered by the vertices of the convex polygon. Edge tiles are tiles that are not at the vertices, and are covered by or touched by line segments that form edges of the convex polygon. Interior tiles are tiles that are not covered by the edges or the vertices of a convex polygon, but are covered by an area enclosed by the convex polygon.
In one implementation, the geometry tiler includes a separate and distinct component for identifying (e.g. by driving on a predetermined bus a signal indicative of the item to be identified) two types of tiles: a vertex tiler that identifies vertex tiles, and a segment scanner that identifies edge tiles. The geometry tiler also includes an interior enumerator that identifies all tiles (including interior tiles, edge tiles and vertex tiles) that are covered by the convex polygon. Note that other implementations of a geometry tiler may have fewer components or more components than described herein. In this implementation, edge tiles along two opposing segments (e.g. a bottom segment and a top segment) of the convex polygon are identified simultaneously, so that all edge tiles are identified when scanning from a left most vertex to a right most vertex is completed.
Identification of edge tiles as described herein eliminates identification of one or more tiles (hereinafter “untouched” tiles) that are merely located adjacent to a convex polygon, but are not covered or touched by the convex polygon. Specifically, identification of tiles in a precise manner as described herein (e.g. identification of only those tiles that are covered by a to-be-displayed polygon) eliminates the prior art identification of tiles that are neither covered nor touched by the convex polygon.
Elimination of one or more untouched tiles from the identified tiles as described herein reduces both time and storage as follows. Elimination of untouched tiles reduces the time otherwise required in the prior art to identify the tiles to be processed for displaying a primitive, and the time to process the identified tiles for display. Moreover, elimination of one or more untouched tiles from the identified tiles also reduces the number of storage locations otherwise required in the prior art to hold the identities of the tiles to be processed, and the memory bandwidth otherwise required to transfer the tile identities to other circuits.
In one embodiment, a geometry tiler evaluates a function (also called “test function”) to determine the location of a current tile relative to the convex polygon (specifically, relative to a line segment of the convex polygon). One example of such a test function is the line function F(
Baltaretu Oana
Dignam David L.
Gupta Sanjay O.
NVIDIA US Investment Company
Padmanabhan Mano
Townsend and Townsend / and Crew LLP
Zimmerman Mark
LandOfFree
Method for determining tiles in a computer display that are... 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 determining tiles in a computer display that are..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining tiles in a computer display that are... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905192