System, apparatus and method for spatially sorting image data in a three-dimensional graphics pipeline

• US 6,552,723 B1
• Filed: 08/20/1999
• Issued: 04/22/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., Redgrave, Jason R., Hessel, Richard E., Trivedi, Sushma S.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/378,633
• Time in Patent Office: 1,341 Days
• Field of Search: 345/418, 345/419, 345/420, 345/431, 345/421, 345/422, 345/423, 345/424, 345/502
• 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 is a mid-pipeline sorting unit that sorts image data mid-pipeline in a tiled 3-D graphics pipeline architecture. The image data includes vertices of geometric primitives. The mid-pipeline sorting determines whether a geometric primitive intersects a region of a 2-D window. The 2-D window having been divided into multiple such regions. Upon determining which region of the 2-D window that the geometric primitive intersects, the mid-pipeline sorting unit stores the vertices that define the geometric primitive into a memory in a manner that associates each of the geometric primitive'"'"'s vertices with the region that was intersected. After the image data is sorted into the memory, the mid pipeline sorting unit sends the sorted image data to the subsequent stage on a region by region basis.

Yet another embodiment of the present invention provides a guaranteed conservative memory estimate to the mid-pipeline sorting stage of whether there is enough free memory for the mid pipeline sorting unit to sort and store the image data.

Yet another embodiment of the present invention sends image data from a memory to a next stage in a graphics pipeline in a spatially staggered sequence.

Claims

1. In a tiled 3-D graphics pipeline, an apparatus for sorting image data, the apparatus being operatively coupled to a previous processing stage of the graphics pipeline and a subsequent processing stage of the graphics pipeline, the apparatus being adapted to read the image data from the previous stage, the image data comprising a set of vertices of a geometric primitive, the apparatus comprising:

a mid-pipeline sorting unit comprising a memory for storing sorted image data, the mid-pipeline sorting unit being adapted to determine if the geometric primitive intersects at least one region of a set of regions that define the area of a 2-D window, and if the geometric primitive intersects a particular region of the set of regions, the mid-pipeline sorting unit being further adapted to store the set of vertices into the memory in a manner that associates each of the geometric primitive'"'"'s vertices with the particular region, the mid pipeline sorting unit being further adapted to send the sorted image data to the subsequent stage on a region-by-region basis.

2. In a tile based 3-D graphics pipeline, an apparatus for providing a guaranteed conservative memory estimate to a mid-pipeline sorting stage having a memory for storing image data that is sorted with respect to a plurality of regions that define a 2-D window, the mid-pipeline storage unit maintaining a set of memory information used to manage the memory, the system being operatively coupled to the mid-pipelined sorting stage, the apparatus comprising:

a guaranteed conservative memory estimate circuit that is adapted to receive the image data and the memory information from the mid-pipeline sorting unit, the guaranteed conservative memory estimate circuit being further adapted to make a determination of whether there is enough free memory in the memory for the mid-pipeline sorting unit to sort the image data into the memory, the guaranteed conservative memory estimate circuit being further adapted to return the determination to the mid-pipeline sorting unit.

3. In a tile based 3-D graphics pipeline having a plurality of pipeline stages, a mid-pipeline sorting unit comprising:

first means for coupling said mid-pipeline sorting unit to a previous stage;

a memory for storing image data that has been sorted with respect to a set of regions coupled to said first means;

a tile generator circuit coupled to said memory configured to determine a spatially staggered sequence of regions to send to a subsequent pipeline stage; and

second means for coupling said mid-pipeline sorting unit to said subsequent stage, said second means coupled to said tile generator circuit.

4. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising spatial data, mode data, and control data, the spatial data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

(A) receiving one or more sort scissor windows;

(B) receiving the image data;

(C) receiving a signal indicating a programmatically selectable mode of operation for the device, the mode of operation being either a time order mode or a sorted transparency mode,

(D) sorting the geometry primitives into a plurality of tiles according to how the geometry primitives overlap the plurality of tiles, each tile comprising an area of the image, considering for the overlap only the tiles within the one or more sort scissor windows in effect at the time the geometry primitive is received, the step of sorting the geometry primitives being done one of two ways depending on the selected mode of operation;

(D1) if the selected mode of operation is time order mode, the performed steps comprise;

(D1a) writing the image data into one or more first memories;

(D1b) generating first pointers, the first pointers each indicating the location of at least one of the geometry primitives in the first memory;

(D1c) generating second pointers, the second pointers each indicating the location of some of the mode data in the first memory;

(D1d) adding each of the first pointers to one or more first pointer lists, the first pointer lists being stored in a second memory; and

(D1e) adding each of the second pointers to at least one second pointer list, the second pointer lists being stored in a third memory;

(D2) if the selected mode of operation is sorted transparency mode, the performed steps comprise;

(D2a) storing a plurality of third pointer lists, each third pointer list comprising third pointers to the geometry primitives in the first memory, each third pointer list corresponding to one of the plurality of tiles; and

(D2b) adding the third pointer of one of the geometry primitives to one of more of the third pointer lists that correspond to tiles overlapped by the geometry primitive, each third pointer comprising the location of a particular primitive and a flag indicating whether the particular primitive is considered transparent;

(E) selecting tile groups from a plurality of tile groups, in a tile-group-by-tile-group manner, each of the tile groups being an adjacent one or more of the tiles;

(F) selecting the tiles within each of the tile groups, in a tile-by-tile manner; and

(G) outputting the geometry primitives that overlap the selected tile in one or more passes;

(G1) if the selected mode of operation is time order mode, the performed steps comprise;

(G1a) for the first pass, sequentially selecting the pointers from the pointer list corresponding to the selected tile and reading from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is not transparent; and

(G1b) for subsequent passes, sequentially selecting the pointers from the pointer list corresponding to the selected tile and reading from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is transparent; and

(G2) if the selected mode of operation is sorted transparency mode, the performed steps comprise;

(G2a) outputting the geometry primitives that overlap the selected tile within the selected tile group.

5. A device for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the device being operatively coupled to a previous stage of the graphics pipeline, and configured to receive the image data from the previous stage, the image data comprising spatial data, mode data, and control data, the spatial data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the device comprising:

one or more first memories storing the image data;

a second memory storing a plurality of first pointer lists, each first pointer list comprising first pointers, the first pointers each indicating the location of at least one of the geometry primitives in the first memory;

a third memory storing at least one second pointer list, each second pointer list comprising second pointers, the second pointers each indicating the location of some of the mode data in the first memory;

logic determining, for at least some of the geometry primitives, the tiles touched by the geometry primitives, the tiles each being associated with at least one of the first pointer lists; and

,

a write control coupled to the previous stage, the first memory, the second memory, and the third memory, the write control comprising;

logic receiving the image data from the previous stage;

logic writing the image data into the first memories;

logic generating the first pointers and the second pointers; and

logic writing the first pointers into the second memory and the second pointers into the third memory.

6. The device of claim 5, wherein an area of the generated 2D image comprises a plurality of tiles, the write control further comprising:

logic determining, for each of the first pointers, the first pointer lists to which the first pointer is added, the adding being based on which tiles are touched by the geometry primitive corresponding to the first pointer.

7. The device of claim 6, wherein the first memories store the image data in an order corresponding to a sequence in which the image data is received, thereby causing the first pointers and the second pointers to form a set of pointers that are sequentially related.

8. The device of claim 6, wherein a single memory comprises the first memories, the second memory, and the third memory.

9. The device of claim 6, wherein the write control further comprising:

logic estimating a bounding box that circumscribes a selected one of the geometry primitives before the tiles touched by the selected geometry primitive are determined; and

the logic determining the tiles touched by the geometry primitives further comprising logic testing only the tiles overlapped by the bounding box to be the tiles touched by the selected geometry primitive.

10. The device of claim 6, wherein the first pointer comprises:

a location of a particular one of the vertices of the corresponding geometry primitive; and

an offset from the particular vertex to the location of another one of the vertices associated with the corresponding geometry primitive.

11. The device of claim 10, wherein the particular vertex is a completing vertex of the corresponding geometry primitive.

12. The device of claim 10, wherein the first pointer further comprises a plurality of line flags.

13. The device as in claim 7, wherein the device further comprises:

a read control coupled to the first memories, the second memory, and the third memory, the read control comprising;

logic selecting one of the first pointer lists;

logic reading the selected first pointer list from the second memory;

logic using the first pointers in the read first pointer list to read the geometry primitives from the first memories; and

logic outputting the read geometry primitives to a next stage of the 3D graphics processor.

14. The device of claim 6, wherein the device further comprises:

the logic writing the image data into the first memory further comprising logic writing the received image data in an order the image data is received, thereby writing the geometry primitives and mode data in the received order;

a read control coupled to the first memories, the second memory, and the third memory, the read control comprising;

logic selecting one of the tiles, the selected tile corresponding to a selected first pointer list, the selected first pointer list being one of the first pointer lists;

logic reading the selected first pointer list from the second memory;

logic reading the at least one second pointer list from the third memory;

logic using the first pointers in the read first pointer list to read the geometry primitives from the first memories;

logic using the second pointers in the read second pointer list to read the mode data from the first memories; and

output logic determining a sequence of outputting the read geometry primitives and the read mode data so as to preserve the received order of the read geometry primitives and the read mode data for the selected tile.

15. A sorting device configured to reconstruct the received order of data objects after the data objects have been sorted into a plurality of sort lists, the device comprising:

(1) a linear list memory storing the data objects in the order in which the data objects are received;

(2) a plurality of pointer memories, each pointer memory storing one of the sort lists, each of a plurality of entries in the sort list being at least part of an address into the linear list memory, the address being the location of one of the data objects in the linear list memory;

(3) a writing control comprising;

(3a) logic receiving one of the data objects;

(3b) logic writing the received data object into the linear list memory at a next available address, the next available address being numerically greater than addresses used for writing previously received data objects; and

(3c) sort logic sorting the received data object into one or more of the sort lists out of the plurality of sort lists, the sorting being done according to a sorting rule, the received data object being added to any one of the sort lists by appending at least part of the received object'"'"'s address in linear list memory to the end of the sort list; and

(4) a read control comprising;

(4a) logic selecting a subset of the plurality of sort lists;

(4b) logic maintaining a set of next addresses, each one of the next addresses being from a corresponding one of the sort lists in the subset of sort lists;

(4c) logic comparing the next addresses to each other to determine which of the next addresses is a numerically smallest address;

(4d) logic using the numerically smallest address to read one of the data objects from the linear list memory; and

(4e) logic replacing the numerically smallest address in the set of next addresses with a next sequential one of the addresses from the same sort list as the numerically smallest address.

16. The sorting device of claim 15 the device further comprising:

a sort memory comprising the plurality of pointer memories, the sort memory being dynamically allocated to sort lists on an as-needed basis; and

the sort logic further comprising;

logic allocating a data record in the sort memory, the data record comprising;

(a) one or more of the at least part of the addresses of the object addresses into the linear list memory; and

(b) a link pointer to another data record; and

logic constructing a linked list for each of the sort lists, the linked list being none, one, or more of the data records.

17. A method of reconstructing the received order of objects after the objects have been sorted into a plurality of sort lists, the method comprising the steps:

(1) a list writing procedure comprising the steps;

(1a) receiving one of the objects;

(1b) adding the received object to a linear list of a multiplicity of previously received objects, the received object being located at an address in the linear list such that the address is numerically greater than the addresses locating the multiplicity of previously received objects;

(1c) sorting the received object into one or more sort lists out of the plurality of sort lists, the sorting being done in accordance with a sorting rule, the received object being added to any one of the sort lists by appending the received object'"'"'s address to the end of the sort list; and

(2) a list reading procedure comprising the steps;

(2a) selecting a subset of the plurality of sort lists;

(2b) maintaining a set of next addresses, each one of the next addresses being from a corresponding one of the sort lists in the subset of sort lists;

(2c) comparing the next addresses to each other to determine which of the next addresses is a numerically smallest address;

(2d) using the numerically smallest address to read one of the objects from the linear list; and

(2e) replacing the numerically smallest address in the set of next addresses with a next sequential one of the addresses from the same sort list as the numerically smallest address.

18. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising spatial data, mode data, and control data, the spatial data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

receiving the image data;

writing the image data into one or more first memories;

generating first pointers, the first pointers each indicating the location of at least one of the geometry primitives in the first memory;

generating second pointers, the second pointers each indicating the location of some of the mode data in the first memory;

adding each of the first pointers to one or more first pointer lists, the first pointer lists being stored in a second memory;

adding each of the second pointers to at least one second pointer list, the second pointer lists being stored in a third memory;

dividing the image area into a plurality of tiles; and

determining, for at least some of the geometry primitives, the tiles touched by the geometry primitives, the tiles each being associated with at least one of the first pointer lists.

19. The method of claim 18, further comprising the steps:

determining, for each of the first pointers, the first pointer lists to which the first pointer is added, the adding being based on which tiles are touched by the geometry primitive corresponding to the first pointer.

20. The method of claim 19, wherein the step of writing the image data stores the image data into the first memory in an order corresponding to a sequence in which the image data is received, thereby causing the first pointers and the second pointers to form a set of pointers that are sequentially related.

21. The method of claim 19, further comprising the steps:

estimating a bounding box that circumscribes a selected one of the geometry primitives before the tiles touched by the selected geometry primitive are determined; and

determining the tiles touched by the geometry primitives by testing only the tiles overlapped by the bounding box to be the tiles touched by the selected geometry primitive.

22. A device for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the device comprising:

a first memory storing the image data;

a second memory storing a plurality of pointer lists, each pointer list comprising locations of the geometry primitives in the first memory, each pointer list corresponding to one of a plurality of tiles, each tile comprising an area of the image;

logic adding the location of one of the geometry primitives to one of more of the pointer lists that correspond to tiles overlapped by the geometry primitive;

tile group logic selecting tile groups from a plurality of tile groups, in a tile-group-by-tile-group manner, each of the tile groups being an adjacent one or more of the tiles;

logic selecting tiles within each of the tile groups, in a tile-by-tile manner; and

logic outputting the geometry primitives that overlap the selected tile within the selected tile group.

23. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

sorting the geometry primitives according to how the geometry primitives overlap a plurality of tiles, each tile comprising an area of the image;

selecting tile groups from a plurality of tile groups, in a tile-group-by-tile-group manner, each of the tile groups being an adjacent one or more of the tiles;

selecting tiles within each of the tile groups, in a tile-by-tile manner; and

outputting the geometry primitives that overlap the selected tile within the selected tile group.

24. The method of claim 23, further comprising the step:

selecting a next selected tile group using the selected tile group and the rule;

25. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

receiving one or more sort scissor windows;

sorting the geometry primitives into a plurality of tiles according to how the geometry primitives overlap the plurality of tiles, each tile comprising an area of the image, considering for the overlap only the tiles within the one or more sort scissor windows in effect at the time the geometry primitive is received;

selecting tiles from the plurality of tiles, in a tile-by-tile manner; and

outputting the geometry primitives that are sorted into the selected tile.

26. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

receiving one or more first sort scissor windows;

associating each of the first sort scissor windows with one of a first subset of the geometry primitives;

sorting the geometry primitives into a plurality of tiles according to how the geometry primitives overlap the plurality of tiles, each tile comprising an area of the image;

selecting tiles from the plurality of tiles, in a tile-by-tile manner; and

outputting the geometry primitives that are sorted into the selected tile, but omitting from the output any considered one of the primitives not inside at least one of the first sort scissor windows having the association with the considered primitive.

27. A device for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each-vertex being associated with at least one of the plurality of the geometry primitives, the device comprising:

a first memory storing one or more sort scissor windows;

a second memory storing sorted geometry primitives, the geometry primitives sorted into a plurality of tiles according to how the geometry primitives overlap the plurality of tiles, each tile comprising an area of the image, considering for the overlap only the tiles within the one or more sort scissor windows in effect at the time the geometry primitive is received;

logic selecting tiles from the plurality of tiles, in a tile-by-tile manner; and

logic outputting the geometry primitives that are sorted into the selected tile.

28. A device for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the device comprising:

a first memory storing one or more first sort scissor windows, a first association associating each of the first sort scissor windows with one of a first subset of the geometry primitives;

a second memory storing sorted geometry primitives, the geometry primitives sorted into a plurality of tiles according to how the geometry primitives overlap the plurality of tiles, each tile comprising an area of the image;

logic selecting tiles from the plurality of tiles, in a tile-by-tile manner; and

output logic outputting the geometry primitives that are sorted into the selected tile, but omitting from the output any considered one of the primitives not inside at least one of the first sort scissor windows having the first association with the considered primitive.

29. A device for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the device comprising:

a first memory storing the image data;

a second memory storing a plurality of pointer lists, each pointer list comprising pointers to the geometry primitives in the first memory, each pointer list corresponding to one of a plurality of tiles, each tile comprising an area of the image;

logic adding the pointer of one of the geometry primitives to one of more of the pointer lists that correspond to tiles overlapped by the geometry primitive, each pointer comprising the location of a particular primitive and a flag indicating whether the particular primitive is considered transparent;

tile group logic selecting tile groups from a plurality of tile groups, in a tile-group-by-tile-group manner, each of the tile groups being an adjacent one or more of the tiles;

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

read logic outputting the geometry primitives that overlap the selected tile in one or more passes;

for the first pass, the read logic sequentially selects the pointers from the pointer list corresponding to the selected tile and reads from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is not transparent; and

for subsequent passes, the read logic sequentially selects the pointers from the pointer list corresponding to the selected tile and reads from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is transparent.

30. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising the steps:

storing the image data in a first memory;

storing a plurality of pointer lists, each pointer list comprising pointers to the geometry primitives in the first memory, each pointer list corresponding to one of a plurality of tiles, each tile comprising an area of the image;

adding the pointer of one of the geometry primitives to one of more of the pointer lists that correspond to tiles overlapped by the geometry primitive, each pointer comprising the location of a particular primitive and a flag indicating whether the particular primitive is considered transparent;

selecting a current tile from the plurality of tiles; and

outputting the geometry primitives that overlap the selected tile in one or more passes;

for the first pass, sequentially selecting the pointers from the pointer list corresponding to the selected tile and reading from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is not transparent; and

for subsequent passes, sequentially selecting the pointers from the pointer list corresponding to the selected tile and reading from the first memory only the geometry primitives whose corresponding pointer has the flag set to indicate the geometry primitive is transparent.

31. In a tiled 3-D graphics pipeline, an apparatus for sorting image data, the apparatus being operatively coupled to a previous processing stage of the graphics pipeline and a subsequent processing stage of the graphics pipeline, the apparatus being adapted to read the image data from the previous stage, the image data comprising a set of vertices of a geometric primitive, the apparatus comprising:

a mid-pipeline sorting unit configured to spatially sort the image data from the previous stage after the primitive data has been transformed to screen coordinates, but before the end of the graphics pipeline, such that only image data representing potentially visible portions of a window are sent to subsequent processing stages.

32. A method for sorting image data in a three-dimensional (3D) graphics pipeline, the 3D graphics pipeline generating a two-dimensional (2D) image from a plurality of geometry primitives, the image data comprising spatial data, mode data, and control data, the spatial data comprising a plurality of vertices, each vertex being associated with at least one of the plurality of the geometry primitives, the method comprising:

receiving the image data after the spatial data has been transformed to screen coordinates, but before the end of the graphics pipeline;

sorting said image data according to regions of the 2D image; and

outputting said image data on a region-by-region basis such that only image data representing potentially visible portions of the 2D image are sent to subsequent processing stages.