Apparatus and method for performing setup operations in a 3-D graphics pipeline using unified primitive descriptors

• US 6,577,305 B1
• Filed: 08/20/1999
• Issued: 06/10/2003
• Est. Priority Date: 08/20/1998
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Duluk, Jerome F. Jr., Fang, Emerson S., Dodgen, Stephen L., Cuan, George, Hessel, Richard E., Hsu, Hengwei, Benkual, Jack, Trivedi, Sushma S., Arnold, Vaughn T.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/378,598
• Time in Patent Office: 1,390 Days
• Field of Search: 345/418, 345/419, 345/420, 345/421, 345/423, 345/424
• US Class Current: 345/419
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G06T 15/80 Shading
• CPC Class Codes: G06T 15/83 Phong shading
• CPC Class Codes: G06T 15/87 Gouraud shading

Abstract

The present invention provides post tile sorting setup in a tiled graphics pipeline architecture. In particular, the present invention determines a set of clipping points that identify intersections of a primitive with a tile. The mid-pipeline setup unit is adapted to compute a minimum depth value for that part of the primitive intersecting the tile. The mid-pipeline setup unit can be adapted to process primitives with x-coordinates that are screen based and y-coordinates that are tile based. Additionally, to the mid-pipeline setup unit is adapted to represent both line segments and triangles as quadrilaterals, wherein not all of a quadrilateral'"'"'s vertices are required to describe a triangle.

Claims

1. A three-dimensional (3-D) graphics processor for generating a rendered image from image data including vertices describing a plurality of graphics primitives, the processor comprising:

(1) asort unit comprising;

(1a) logic spatially sorting the plurality of graphics primitives according to their location within the rendered two-dimensional image; and

(1b) logic outputting the spatially sorted primitives according to their spatial sorting; and

(2) a setup unit comprising (2a) logic computing spatial derivatives of the spatially sorted primitives received from the sort unit; and

(2b) logic converting at least some of the spatially sorted primitives into a uniform quadrilateral representation having four vertices.

2. The 3-D graphics processor of claim 1 wherein:

the sort unit further comprising;

logic sorting the graphics primitives according to a plurality of tiles, each tile being a region encompassing an area of the rendered image, the plurality of tiles jointly covering the entire area of the rendered image;

memory storing the plurality of sorted graphics primitives;

logic selecting a current tile from the plurality of tiles; and

logic outputting spatially sorted primitives from the current tile; and

wherein said logic computing spatial derivatives computes spatial derivatives for each of the spatially sorted primitives one or more times, the number of times being equal to the number of tiles overlapped by each of the spatially sorted primitives.

3. The 3-D graphics processor of claim 2 wherein the setup unit further comprising:

logic computing a minimum depth value for that part of each of the received spatially sorted primitives intersecting the current tile.

4. The 3-D graphics processor of claim 2, wherein the setup unit further comprising:

logic breaking up a stippled line primitive into multiple individual line segments, with lengths of the individual line segments corresponding to sequences of 1 bits in a stipple pattern, each of the individual line segments being sent to subsequent units in the 3-D graphics pipeline as separate primitives; and

logic reducing unnecessary processing by discarding the individual line segments that lie outside of the current tile;

logic generating vertex values that comprise tile relative y-values and screen relative x-values; and

logic generating, for each of the received spatially sorted primitives, a bounding box that circumscribes those parts of the received spatially sorted primitives that intersect the current tile.

5. The 3-D graphics processor of claim 1 wherein the converting logic further comprises:

(a) means for generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment, if the received spatially sorted primitive is a line segment represented by two vertices; and

(b) means for generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid, if the received spatially sorted primitive is a triangle represented by three vertices.

6. The 3-D graphics processor of claim 5 wherein the setup unit further comprising:

logic clipping the unified quadrilateral representation to a tile, the tile being a rectangular region within the area of rendered image, the clipped representation comprising a left top vertex and a right top vertex both located at the top edge of the tile.

7. The graphics processor of claim 1, wherein the logic outputting the spatially sorted primitives according to their spatial sorting further outputfing spatially sorted primitives such that all primitives sorted to a first spatial region in the rendered image are output before any primitives sorted to a second spatial region independent of the object to which the primitive corresponds.

8. The graphics processor of claim 1, wherein the logic spatially sorting the plurality of graphics primitives comprises logic spatially sorting a plurality of uniform quadrilateral primitive representations having four vertices.

9. The 3-D graphics processor of claim 1, the converting logic comprising a uniform quadrilateral primitive representation generator for:

(i) generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment, if the received spatially sorted primitive is a line segment represented by two vertices; and

(b) generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid, if the received spatially sorted primitive is a triangle represented by three vertices.

10. The 3-D graphics processor of claim 5, wherein the converting logic converts all of the received spatially sorted primitives into a uniform quadrilateral representation.

11. The 3-D graphics processor of claim 5, wherein said other than a quadrilateral representation includes a two-vertex line representation and a three-vertex triangle representation.

12. A three-dimensional (3-D) graphics processor for generating a rendered image from image data including vertices describing a plurality of graphics primitives, the processor comprising:

(1) a sort unit comprising;

(1a) logic spatially sorting the plurality of graphics primitives according to their location within the rendered two-dimensional image; and

(1b) logic outputting the spatially sorted primitives according to their spatial sorting; and

(2) a setup unit comprising;

logic computing spatial derivatives of the spatially sorted primitives received from the sort unit;

logic sorting the vertices of each of the spatially sorted primitives and using the sorted vertices in subsequent operations;

logic converting a line segment represented by two vertices into a quadrilateral, the quadrilateral being represented by four vertices;

logic calculating depth gradients using the sorted vertices; and

logic generating pointers to identify the sorting order of the vertices.

13. A three-dimensional (3-D) graphics rendering method for generating a rendered image from a plurality of graphics primitives, the method comprising:

receiving a graphics primitive, the graphics primitive comprising one or more vertices;

converting the graphics primitive into a uniform quadrilateral representation having four vertices, the converting step further comprising;

(a) if the graphics primitive is a line segment represented by two vertices, computing four new vertices from the two vertices of the line segment for inclusion in the uniform quadrilateral representation; and

(b) if the graphics primitive is a triangle represented by three vertices, selecting the three vertices of the triangle and labeling a fourth vertex as invalid for inclusion in the uniform quadrilateral representation.

14. The method of claim 13, further comprising:

clipping the unified quadrilateral representation to a tile, the tile being a rectangular region within the area of rendered image, the clipped representation comprising a left top vertex and a right top vertex both located at the top edge of the tile.

15. The method of claim 13, further comprising:

packaging the clipped representation into a primitive packet, the primitive packet representing one primitive; and

processing the primitive packet to cull out parts of the primitive that definitely do not contribute to the rendered image.

16. The method of claim 13, wherein the converting step further comprising:

computing a partial spatial derivative of z with respect to x and a partial spatial derivative of z with respect to y for inclusion in the uniform quadrilateral representation.

17. The method of claim 13, wherein said converting comprises converting each of the received spatially sorted primitives into a uniform quadrilateral representation.

18. A computing system for generating a rendered image from image data including vertices describing a plurality of graphics primitives, the system comprising:

a general-purpose computer; and

a graphics processor coupled to host processor;

the graphics processor comprising;

(1) a sort unit comprising;

(1a) logic spatially sorting the plurality of graphics primitives according their location within the rendered two-dimensional image; and

(1b) logic outputting the spatially sorted primitives according to their spatial sorting; and

(2) a setup unit comprising (2a) logic computing spatial derivatives of the spatially sorted primitives received from the sort unit; and

(2b) logic converting at least some of the spatially sorted primitives into a uniform quadrilateral representation having four vertices.

19. The computing system of claim 18 wherein:

the sort unit further comprises;

logic sorting the graphics primitives according to a plurality of tiles, each tile being a region encompassing an area of the rendered image, the plurality of tiles jointly covering the entire area of the rendered image;

memory storing the plurality of sorted graphics primitives;

logic selecting a current tile from the plurality of tiles; and

logic outputting spatially sorted primitives from the current tile; and

the setup unit further comprising;

logic computing spatial derivatives for each of the spatially sorted primitives one or more times, the number of times being equal to the number of tiles overlapped by each of the spatially sorted primitives.

20. The computing system of claim 18, wherein the converting logic further comprises:

(a) means for generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment, if the received spatially sorted primitive is a line segment represented by two vertices; and

(b) means for generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid, if the received spatially sorted primitive is a triangle represented by three vertices.

21. The computing system of claim 18, wherein the logic outputting the spatially sorted primitives according to their spatial sorting further outputting spatially sorted primitives such that all primitives sorted to a first spatial region in the rendered image are output before any primitives sorted to a second spatial region independent of the object to which the primitive corresponds.

22. The computing system of claim 18, wherein the the converting logic comprising comprises a uniform quadrilateral representation generator for:

(i) generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment, if the received spatially sorted primitive is a line segment represented by two vertices; and

(ii) generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid, if the received spatially sorted primitive is a triangle represented by three vertices.

23. A 3-D graphics processor generating a rendered image, the processor comprising:

means for spatially sorting a plurality of graphics primitives according to their location within the two-dimensional rendered image;

means for outputting said graphics primitives according to their location within the rendered image; and

means for computing spatial derivatives of the spatially sorted primitives; and

means for converting at least some of said spatially sorted primitives into a uniform quadrilateral representation having four vertices.

24. The 3-D graphics processor of claim 23, further comprising:

means for sorting the graphics primitives according to a plurality of tiles, each tile being a region encompassing an area of the rendered image, the plurality of tiles jointly covering the entire area of the rendered image;

means for storing the plurality of sorted graphics primitives;

means for selecting a current tile from the plurality of tiles; and

means for computing spatial derivatives for each of the spatially sorted primitives one or more times, the number of times being equal to the number of tiles overlapped by each of the spatially sorted primitives.

25. The 3-D graphics processor of claim 23, the means for converting further comprising:

(a) if the received spatially sorted primitive is a line segment represented by two vertices, means for generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment; and

(b) if the received spatially sorted primitive is a triangle represented by three vertices, means for generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid.

26. The processor of claim 25, wherein said means for converting converts all of the spatially sorted primitives into a uniform quadrilateral representation.

27. The graphics processor of claim 23, wherein the means for outputting said graphics primitives according to their location within the rendered image further including means for outputting graphics primitives such that all primitives sorted to a first spatial region in the rendered image are output before any graphics primitives sorted to a second spatial region independent of an object to which the primitive corresponds.

28. A method for generating a rendered image from a plurality of graphics primitives, the method comprising the steps:

receiving the plurality of graphics primitives;

spatially sorting the graphics primitives according to a plurality of tiles, each tile including a region encompassing an area of the rendered image;

selecting a current tile from the plurality of tiles; and

computing spatial derivatives of the spatially sorted primitives in the current tile; and

converting at least some of said spatially sorted primitives into a uniform quadrilateral representation having four vertices.

29. The method of claim 28, the converting step comprising the steps:

(a) if the graphics primitive is a line segment represented by two vertices, (i) computing four new vertices from the two vertices of the line segment for inclusion in the uniform quadrilateral representation; and

(b) if the graphics primitive is a triangle represented by three vertices, (ii) selecting the three vertices of the triangle and (iii) labeling a fourth vertex as invalid for inclusion in the uniform quadrilateral representation.

30. The method of claim 29, further comprising the step:

clipping the unified quadrilateral representation to the current tile, the clipped representation comprising;

an x left top coordinate, an x right top coordinate, a y top coordinate, an x left corner coordinate, a y left corner coordinate, an x right corner coordinate, a y right corner coordinate, and a y bottom coordinate.

31. The method of claim 28, further comprising the step:

breaking up a stippled line primitive into multiple individual line segments, with lengths of the individual line segments corresponding to sequences of 1 bits in a stipple pattern, each of the individual line segments being available for subsequent processing as separate primitives.

32. The method of claim 31, further comprising the step:

reducing unnecessary processing by discarding the individual line segments that lie outside of the current tile.

33. The method of claim 28, further comprising the steps:

generating a maximum z derivative, the maximum z derivative being, for the primitive, the greater of the partial derivative of z with respect to x and the partial derivative of z with respect to y;

generating a depth offset factor by multiplying the maximum x derivative by a user supplied factor; and

modifying the depth values in the vertices by using the computed depth offset.

34. A computer program for use in conjunction with a computer system, the computer program comprising a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the rendering of a digital representation of a final graphics image from a plurality of graphics primitives, to function in a specified manner, storing the final graphics image into a frame buffer memory, the program module including instructions for;

receiving the plurality of graphics primitives;

spatially sorting the graphics primitives according to a plurality of tiles, each tile being a region encompassing an area of the rendered image;

selecting a current tile from the plurality of tiles; and

computing spatial derivatives of the spatially sorted primitives in the current tile; and

converting at least some of said spatially sorted primitives into a uniform quadrilateral representation having four vertices.

35. The computer program of claim 34, the converting instructions comprising instructions such that:

(a) if the graphics primitive is a line segment represented by two vertices, computing four new vertices from the two vertices of the line segment for inclusion in the uniform quadrilateral representation; and

(b) if the graphics primitive is a triangle represented by three vertices, selecting the three vertices of the triangle and labeling a fourth vertex as invalid for inclusion in the uniform quadrilateral representation;

the program module further including instructions for;

clipping the unified quadrilateral representation to the current tile;

processing the unified quadrilateral representation to cull out parts of the primitive that definitely do not contribute to the rendered image;

computing a partial derivative of z with respect to x and a partial derivative with respect to y for inclusion in the uniform quadrilateral representation;

computing the derivative in the x-y plane for one or more edges of the uniform quadrilateral representation;

sorting the vertices of each of the spatially sorted primitives and using the sorted vertices for computing depth gradients;

determining a reference z-value for each of the primitives within the current tile;

generating a plurality of sample z-values from the reference z-value and the spatial derivatives; and

invalidating one of the spatially sorted primitives whenever a corresponding spatial derivative of the depth value overflows its computation.

36. A computer program for use in conjunction with a computer system, the computer program comprising a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the rendering of a digital representation of a final graphics image from a plurality of graphics primitives, to function in a specified manner, storing the final graphics image into a frame buffer memory, the program module including instructions for;

receiving a graphics primitive, the graphics primitive comprising one or more vertices;

converting the received graphics primitive into a uniform quadrilateral representation, the converting step comprising the steps;

(a) if the graphics primitive is a line segment represented by two vertices, computing four new vertices from the two vertices of the line segment for inclusion in the uniform quadrilateral representation; and

(b) if the graphics primitive is a triangle represented by three vertices, selecting the three vertices of the triangle and labeling a fourth vertex as invalid for inclusion in the uniform quadrilateral representation.

37. The computer program of claim 36, further comprising a computer program product stored on a tangible computer readable storage medium;

clipping the unified quadrilateral representation to a tile, the tile being a rectangular region within the area of rendered image;

clipping the unified quadrilateral representation to a tile, the tile being a rectangular region within the area of rendered image, the clipped representation comprising;

an x left top coordinate, an x right top coordinate, a y top coordinate, an x left corner coordinate, a y left corner coordinate, an x right corner coordinate, a y right corner coordinate, and a y bottom coordinate;

computing a partial derivative of z with respect to x and a partial derivative with respect to y for inclusion in the uniform quadrilateral representation; and

computing the derivative in the x-y plane for one or more edges of the uniform quadrilateral representation.

38. A three-dimensional (3-D) graphics processor for generating a rendered image from image data including vertices describing a plurality of graphics primitives, the processor comprising:

(1) a sort unit comprising;

(1a) logic spatially sorting the plurality of graphics primitives according to a plurality of files within the two-dimensional image, each of the files being a two dimensional area within the area of the image;

(1b) logic selecting a current file; and

(1b) logic outputting the spatially sorted primitives that overlap the current file; and

(2) a setup unit comprising;

(2a) logic computing spatial derivatives of the spatially sorted primitives received from the sort unit; and

(2b) logic calculating a single minimum depth value within the current tile for each of the received primitives, the calculated minimum depth values being used for a keep or discard decision for each of the received primitives with respect to the current file.

39. A three-dimensional (3-D) graphics processor for generating a rendered image, the processor comprising:

(1) a sort unit comprising;

(1a) logic spatially sorting a plurality of graphics primitives according to a plurality of tiles within the image, each of the tiles being a two dimensional area within the area of the image;

(1b) logic selecting a current tile; and

(1b) logic outputting the spatially sorted primitives that overlap the current tile; and

(2) a setup unit comprising;

(2a) logic computing spatial derivatives of the spatially sorted primitives received from the sort unit; and

(2b) logic clipping each of the received primitives along at east one of the edges of the current tile.

40. A three-dimensional (3-D) graphics processor for generating a rendered image, the processor comprising:

(1) a sort unit comprising;

(1a) logic spatially sorting a plurality of graphics primitives according to a plurality of tiles within the image, each of the tiles being a two dimensional area within the area of the image; and

(1b) logic outputting the spatially sorted primitives according to their spatial sorting; and

(2) a setup unit comprising;

(2a) logic computing spatial derivatives of the spatially sorted primitives received from the sort unit; and

(2b) converting logic converting at least some of the received spatially sorted primitives into a uniform quadrilateral representation, the converting logic further comprising;

(i) logic generating the uniform quadrilateral representation by computing four new vertices from the two vertices of the line segment, if the received spatially sorted primitive is a line segment represented by two vertices; and

(ii) logic generating the uniform quadrilateral representation by selecting the three vertices of the triangle and labeling a fourth vertex as invalid, if the received spatially sorted primitive is a triangle represented by three vertices.

41. A mid-pipeline setup unit configurable for use in a graphics pipeline processor for generating a two-dimensional rendered image in a window divided into tiles, from image data including vertices describing a plurality of graphics primitives, said mid-pipeline setup unit receiving said image data from a mid-pipeline sort unit having already sorted said image data into said files, said setup unit:

receiving said image data from said sort unit one file at a time and processing one primitive at a time, said setup unit comprising;

logic determining, for each primitive, dimensions of a tight bounding box circumscribing a part of a primitive intersecting a tile;

logic computing, for each primitive, a minimum depth value for a part of said primitive that intersects a file;

logic calculating a spatial derivative for each primitive that is a line or triangle; and

logic determining a reference stamp in said bounding box containing a vertex with said minimum depth value.

42. A method for generating a two-dimensional rendered image in a window divided into tiles, from image data including vertices describing a plurality of graphics primitives, said method comprising:

receiving said image data sorted into said files one tile at a time, and processing one primitive at a time;

determining, for each primitive, dimensions of a tight bounding box circumscribing a part of a primitive intersecting a tile;

computing, for each primitive, a minimum depth value for a part of said primitive that intersects a tile;

calculating a spatial derivative for each primitive that is a line or triangle; and

determining a reference stamp in said bounding box containing a vertex with said minimum depth value.