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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.