Graphical rendering system using simultaneous parallel query Z-buffer and method therefor

A graphics rendering system comprising:

• a magnitude comparison content addressable memory for (i) receiving coordinate values including numerical z-coordinate values of corresponding geometry data, and (ii) for performing simultaneous arithmetic magnitude comparisons between a plurality of said received coordinate values with previously stored coordinate values in said magnitude comparison content addressable memory, and (iii) for generating an occulting signal representing results from said plurality of arithmetic magnitude comparisons of said received coordinate values with said stored coordinate values, and (iv) for updating said stored coordinate values in response to a result of said arithmetic magnitude comparisons;
• a processor coupled to said magnitude comparison content addressable memory for processing said geometry data responsive to said generated occulting signal from said magnitude comparison content addressable memory;
• and
• a frame buffer coupled to said processor for storing said processed geometry data from said processor.

A method of converting imagery in the form of a set of geometry data stored in a data memory to rasterized pixel data stored in a frame buffer for presentation on a display screen, said method comprising the steps of:

• storing a number, for use as a z-coordinate value with each of a plurality of image pixels represented by said frame buffer, in a storage location within a magnitude comparison content addressable memory buffer;
• selecting a geometry data item having at least one z-coordinate value from said set of geometry data;
• generating an approximating boundary characterization of said selected geometry data based on coordinate parameters of said selected geometry data;
• determining a minimum z-coordinate value of said selected geometry data;
• simultaneously performing, for each of pixel in said image said plurality of pixels, an arithmetic magnitude comparison test between said geometry object data minimum z-coordinate value and said stored z-coordinate values of said image pixels;
• and
• discarding identifying on a pixel-by-pixel basis, any of said pixels forming a portion of said selected geometry data for which said minimum z-coordinate value is greater than said previously stored z-coordinate values within said boundary characterization prior to rasterization of said selected geometry data;
• and
• rasterizing only portions of said geometry data not identified as having said minimum z-coordinate value greater than said previously stored z-coordinate.

A method of converting geometry data having coordinates in a three-dimensional scene to pixels having color values in a two-dimensional frame, the method comprising:

• (a) storing pixel distance values, at least one of the pixel distance values being associated with a pixel location in the frame;
• (b) for each of a plurality of multiple-pixel cells, generating and storing at least one cell distance value, each cell distance value being a single value representing all of the pixel distance values of the corresponding pixel locations within the cell;
• (c) selecting a subset of the geometry data;
• (d) determining, for the selected subset, a geometry distance value that represents the closest distance to the geometry data in the selected subset;
• (e) simultaneously performing a plurality of magnitude comparisons between the geometry distance value and a plurality of stored cell distance values on a pixel-by-pixel basis;
• (f) indicating the selected subset as hidden, on a cell-by-cell basis, if the geometry distance value is greater than the stored cell distance values;
• (g) for any geometry data indicated as not hidden on a cell-by-cell basis, generating pixel-based depth values to determine if the geometry is hidden on a pixel-by-pixel basis;
• (h) for any geometry data indicated as hidden on a cell-by-cell basis, omitting generation of color values and pixel-based depth values;
• and
• (i) generating cell-based depth values from pixel-based depth values, storing the cell-based depth values for use in step (e).

A method of converting polygons having coordinates in a three-dimensional scene to pixels having color values in a two-dimensional frame, the method comprising:

• (a) storing pixel distance values, at least one of the pixel distance values being associated with each pixel location;
• (b) for each of a plurality of multiple-pixel cells, generating and storing at least one cell distance value, each cell distance value being a single value representing all of the pixel distance values of the corresponding pixel locations within the cell;
• (c) selecting at least one of the polygons;
• (d) determining, for the selected polygon, a polygon distance value, the polygon distance value representing the smallest distance to the selected polygon;
• (e) simultaneously performing a plurality of magnitude comparisons between the polygon distance value and a plurality of previously stored cell distance values on a pixel-by-pixel basis;
• (f) indicating the polygon as hidden, on a cell-by-cell basis, if the stored distance value represents a location closer than the polygon distance value represents;
• (g) for any polygon indicated as not hidden on a cell-by-cell basis, generating pixel-based depth values to determine if the geometry is hidden on a pixel-by-pixel basis;
• (h) generating color values and pixel-based depth values, on a pixel-by-pixel basis, omitting any polygons indicated as hidden at that pixel;
• and
• (i) generating cell-based depth values from pixel-based depth values, storing the cell-based depth values for use in step (e).

A method of processing polygons having coordinates in a three-dimensional scene and pixels in a two-dimensional frame, the method comprising:

• (a) for each of a plurality of multiple-pixel cells, generating and storing at least one cell distance value, the cell distance value being generated from corresponding pixel distance values and not less than any of those corresponding pixel distance values;
• (b) determining, for a selected polygon, a polygon distance value, the polygon distance value representing the smallest distance to the selected polygon;
• and
• (c) simultaneously performing a plurality of magnitude comparisons between the polygon distance value and a plurality of previously stored cell distance values on a pixel-by-pixel basis.

A graphics processor comprising:

• polygon input means, coupled to an external host processor, to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene;
• polygon processing means, coupled to the input means, to receive polygon coordinate values associated with a selected set of one or more polygons and generate a closest polygon distance value representing the closest distance to any point on the selected polygons;
• pixel distance means to store pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels, pixel distance values being received from pixel output means;
• cell processing means, coupled to the pixel distance means, to receive pixel distance values associated with a cell group of pixel locations and generate at least one cell distance value representing all of the pixel locations in the selected cell;
• parallel magnitude comparison content addressable memory means, coupled to the cell processing means and the polygon processing means, to receive and store a plurality of the generated cell distance values, and to simultaneously compare a plurality of the stored cell distance values with the closest polygon distance value and indicate on a pixel-by-pixel basis, for all of the pixel locations represented by each of the cells, if the selected set of polygons is hidden;
• and
• pixel output means, coupled to the input means and the parallel comparison means, to receive polygon date omitting polygons indicated as hidden at each pixel location and generate color values and pixel distance values for each pixel location in the frame.

A graphics processing system comprising:

• a graphics processor including:
• polygon input means, coupled to an external host processor, to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene;
• polygon processing means, coupled to the input means, to receive polygon coordinate values associated with a selected set of one or more polygons and generate a closest polygon distance value representing the closest distance to any point on the selected polygons;
• pixel distance means to store pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels, pixel distance values being received from pixel output means;
• cell processing means, coupled to the pixel distance means, to receive pixel distance values associated with a cell group of pixel locations and generate at least one cell distance value representing all of the pixel locations in the selected cell;
• parallel magnitude comparison content addressable memory means, coupled to the cell processing means and the polygon processing means, to receive and store a plurality of the generated cell distance values, and to simultaneously compare each of the stored cell distance values with the closest polygon distance value and indicate on a pixel-by-pixel basis, for all of the pixel locations represented by each of the cells, if the selected set of polygons is hidden;
• and
• pixel output means, coupled to the input means and the parallel comparison means, to receive polygon data omitting polygons indicated as hidden at each pixel location and generate color values and pixel distance values for each pixel location in the frame;
• and
• a frame buffer, coupled to the graphics processor, to receive and store the generated color values for each pixel location in the frame.

A graphics processing system comprising:

• a plurality of graphics processors, each of the graphics processors including:
• polygon input means, coupled to an external host processor, to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene;
• polygon processing means, coupled to the input means, to receive polygon coordinate values associated with a selected set of one or more polygons and generate a closest polygon distance value representing the closest distance to any point on the selected polygons;
• pixel distance means to store pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels, pixel distance values being received from pixel output means;
• cell processing means, coupled to the pixel distance means, to receive pixel distance values associated with a cell group of pixel locations and generate at least one cell distance value representing all of the pixel locations in the selected cell;
• parallel magnitude comparison content addressable memory means, coupled to the cell processing means and the polygon processing means, to receive and store a plurality of the generated cell distance values, and to simultaneously compare each of the stored cell distance values with the closest polygon distance value and indicate on a pixel-by-pixel basis, for all of the pixel locations represented by each of the cells, if the selected set of polygons is hidden;
• and
• pixel output means, coupled to the input means and the parallel comparison means, to receive polygon data omitting polygons indicated as hidden at each pixel location and generate color values and pixel distance values for each pixel location in the frame;
• and
• a frame buffer, wherein the frame buffer includes a plurality of frame buffer blocks, each frame buffer block coupled to a corresponding graphics processor to receive and store the generated color values for each pixel location in a predetermined block portion of the frame.

A graphics processor comprising:

• polygon processing means, receiving polygon data associated with a selected set of one or more polygons representing a three-dimensional scene and generating a closest polygon distance value representing the closest distance to any point on the selected polygons;
• pixel distance means to store pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels, pixel distance values being received from pixel output means;
• cell processing means receiving pixel distance values associated with a cell group of pixel locations included in a two-dimensional scene and generating at least one cell distance value;
• parallel magnitude comparison content addressable memory means, coupled to the cell processing means and the polygon processing means, to receive and store a plurality of the generated cell distance values, and to simultaneously compare each of the stored cell distance values with the closest polygon distance value and indicate on a pixel-by-pixel basis, for all of the pixel locations represented by each of the cells, if the selected set of polygons is hidden;
• and
• pixel output means, coupled to the input means and the parallel comparison means, to receive polygon data omitting polygons indicated as hidden at each pixel location and generate color values and pixel distance values for each pixel location in the frame.

A graphics processor comprising:

• a polygon processor, coupled to an external host processor to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene, including a control circuit that selects a set of one or more polygons and a geometry processor that computes a closest polygon distance value representing the closest distance to any point on the selected polygons;
• a cell processor processing cells on a pixel-by-pixel basis, coupled to a pixel distance buffer to receive pixel distance values associated with a cell group of pixel locations, including first arithmetic magnitude comparison content addressable memory comparators that identify, for each of a plurality of cells, a farthest cell distance value to represent all of the pixel locations in the each cell, and second arithmetic comparators that simultaneously compare each of the farthest cell distance values with the closest polygon distance value;
• and
• a pixel processor, coupled to the polygon processor to receive polygon data and coupled to the cell processor to receive comparison results, including a circuit that selectively omits generation of color values for hidden portions of polygons, including for polygons and cell groups of pixels where the closest polygon distance value is greater than the farthest cell distance value.

A graphics processor comprising:

• a polygon processor, coupled to an external host processor to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene, including a control circuit that selects a set of one or more polygons and a geometry processor that computes a closest polygon distance value representing the closest distance to any point on the selected polygons;
• a pixel distance buffer holding pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels;
• a cell processor processing cells on a pixel-by-pixel basis, coupled to a pixel distance buffer to receive pixel distance values associated with a cell group of pixel locations, including first arithmetic magnitude comparison content addressable memory comparators that identify, for each of a plurality of cells, a farthest cell distance value to represent all of the pixel locations in the each cell, and second arithmetic comparator that simultaneously compare each of the farthest cell distance values with the closest polygon distance value;
• and
• a pixel processor, coupled to the polygon processor to receive polygon data and coupled to the cell processor to receive comparison results, including a circuit that selectively omits generation of color values for hidden portions of polygons, including for polygons and cell groups of pixels where the closest polygon distance value is greater than the farthest cell distance value.

A method of converting geometry data having coordinates in a three-dimensional scene to pixels having color values in a two-dimensional frame, the method comprising:

• (a) storing pixel distance values, at least one of the pixel distance values being associated with a pixel location in the frame;
• (b) for each of a plurality of multiple-pixel cells, generating and storing at least one cell distance value, each cell distance value being a single value representing all of the pixel distance values of the corresponding pixel locations within the cell;
• (c) selecting a subset of the geometry data;
• (d) determining, for the selected subset, a geometry distance value that represents the closest distance to the geometry data in the selected subset;
• (e) simultaneously performing on a pixel-by-pixel basis in a magnitude comparison content addressable memory a plurality of magnitude comparisons between the geometry distance value and a plurality of stored cell distance values using a tiled array of identical circuit blocks, each of a plurality of the circuit blocks being coupled to a common input databus for the geometry distance value, each of a plurality of the circuit blocks having an individually addressable register for storing a respective cell distance value, each of a plurality of the circuit blocks having a magnitude comparator coupled to the geometry distance value and the respective cell distance value;
• (f) indicating the selected subset as hidden, on a cell-by-cell basis, if the geometry distance value is greater than the stored cell distance values;
• (g) for any geometry data indicated as not hidden on a cell-by-cell basis, generating pixel-based depth values to determine if the geometry is hidden on a pixel-by-pixel basis;
• (h) for any geometry data indicated as hidden on a cell-by-cell basis, omitting generation of color values and pixel-based depth values;
• (i) generating cell-based depth values from pixel-based depth values, storing the cell-based depth values for use in step (e);
• (j) for any geometry data not indicated as hidden on a cell-by-cell basis, generating color values for pixels not hidden on a pixel-by-pixel basis;
• and
• (k) processing multiple frame instances, each frame instance being generated for a plurality of multiple-cell blocks, each block being generated by repetitively performing steps (a) through (f) for geometry subsets of the geometry database that potentially effect the block, steps (g) through (i) being postponed until after the entire geometry database has been traversed;
• and
• wherein the geometry data comprises one or more of polygons, surfaces, volumes and objects;
• and
• the cell distance value is not less than the maximum of the pixel distance values of the corresponding pixel locations within the cell.

A graphics processor comprising:

• polygon input means, coupled to an external host processor, to receive polygon data, including coordinate data, associated with each of a plurality of polygons representing a three-dimensional scene;
• polygon processing means, coupled to the input means, to receive polygon coordinate values associated with a selected set of one or more polygons and generate a closest polygon distance value representing the closest distance to any point on the selected polygons;
• pixel distance means, coupled to the polygon processing means, to receive and selectively store pixel distance values associated with individual pixel locations included in a two-dimensional frame of pixels, pixel distance values being received from pixel output means;
• cell processing means, coupled to the pixel distance means, to receive pixel distance values associated with a cell group of pixel locations and generate at least one cell distance value representing all of the pixel locations in the selected cell;
• parallel magnitude comparison content addressable memory means, coupled to the cell processing means and the polygon processing means, to receive and store a plurality of the generated cell distance values, and to simultaneously compare each of the stored cell distance values with the closest polygon distance value and indicate on a pixel-by-pixel basis, for all of the pixel locations represented by each of the cells, if the selected set of polygons is hidden, wherein completion of the parallel comparison requires a predetermined number of clock cycles, and in a single clock cycle, one parallel comparison is completed and its result stored and another parallel comparison operation is started, and the stored cell distance values represent all the pixel locations corresponding to a rectangular array of pixels configured to process sub-frame blocks of pixels, the array size based on the available number of parallel comparison circuits;
• pixel output means, coupled to the input means and the parallel comparison means, to receive polygon data omitting polygons indicated as hidden at each pixel location and generate color values and pixel distance values for each pixel location in the frame;
• and
• tag means, coupled to the polygon processing means and the pixel output means, to receive and store tags identifying which polygons are responsible for pixel color in order to postpone generating color values for each pixel until all updating of pixel distance values is done;
• wherein the pixel distance means includes update means, coupled to the parallel comparison means, to receive and selectively store updated pixel distance values depending on cell magnitude comparison results.

A graphics rendering system comprising:

• a magnitude comparison content addressable memory for:
• (i) receiving coordinate values including coordinate values of corresponding geometry data, and
• (ii) performing depth comparisons in parallel, said depth comparison being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results, and
• (iii) for generating an occulting signal representing said plurality of comparison results, and
• (iv) for updating said stored coordinate values in response to said occulting signal;
• a processor coupled to said magnitude comparison content addressable memory for processing said geometry data responsive to said occulting signal to generate pixel-based data;
• and
• a frame buffer coupled to said processor for storing at least some of said generated pixel-based data.

A graphics rendering system comprising:

• a set of memory bits organized into words, where each word can perform one or more arithmetic magnitude comparisons between the stored data and the input data, for:
• (i) receiving coordinate values including coordinate values of corresponding geometry data, and
• (ii) performing depth comparisons in parallel, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results, and
• (iii) for generating an occulting signal representing said plurality of comparison results, and
• (iv) for updating said stored coordinate values in response to said occulting signal;
• a processor, coupled to said set of memory bits organized into words, for processing said geometry data responsive to said occulting signal to generate pixel-based data;
• and
• a frame buffer coupled to said processor for storing at least some of said generated pixel-based data.

A graphics rendering system comprising:

• a magnitude comparison content addressable memory for:
• (i) receiving coordinate values including coordinate values of corresponding geometry data, and
• (ii) performing depth comparisons in parallel, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results, and
• (iii) for generating an occulting signal representing said plurality of comparison results, and
• (iv) for updating said stored coordinate values in response to said occulting signal;
• a processor coupled to said magnitude comparison content addressable memory for processing said geometry data responsive to said occulting signal to generate pixel-based data and cell-based data, said cell-based data used in said updating said stored coordinate values in response to said occulting signal;
• and
• a frame buffer coupled to said processor for storing at least some of said generated pixel-based data.

A graphics rendering system comprising:

• a set of memory bits organized into words, where each word can perform one or more arithmetic magnitude comparisons between the stored data and the input data, for
• (i) receiving coordinate values including coordinate values of corresponding geometry data, and
• (ii) performing depth comparisons in parallel, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results, and
• (iii) for generating an occulting signal representing said plurality of comparison results, and
• (iv) for updating said stored coordinate values in response to said occulting signal;
• a processor, coupled to said set of memory bits organized into words, for processing said geometry data responsive to said occulting signal to generate pixel-based data and cell-based data, said cell-based data used in said updating said stored coordinate values in response to said occulting signal;
• and
• a frame buffer coupled to said processor for storing at least some of said generated pixel-based data.

A graphics rendering method comprising the steps:

• (a) receiving coordinate values including coordinate values of corresponding geometry data;
• (b) performing depth comparisons in parallel using a magnitude comparison content addressable memory, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results;
• (c) generating an occulting signal representing said plurality of comparison results;
• (d) updating said stored coordinate values in response to said occulting signal;
• and
• (e) processing said geometry data responsive to said occulting signal to generate pixel-based data.

A graphics rendering method comprising the steps:

• (a) receiving coordinate values including coordinate values of corresponding geometry data;
• (b) performing depth comparisons in parallel using a set of memory bits organized into words, where each word can perform one or more arithmetic magnitude comparisons between the stored data and the input data, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between said received coordinate values of corresponding geometry data and previously stored coordinate values, thereby generating a plurality of comparison results;
• (c) generating an occulting signal representing said plurality of comparison results;
• (d) updating said stored coordinate values in response to said occulting signal;
• and
• (e) processing said geometry data responsive to said occulting signal to generate pixel-based data.

A graphics rendering method comprising the steps:

• (a) receiving coordinate values including coordinate values of corresponding geometry data;
• (b) performing depth comparisons in parallel using a magnitude comparison content addressable memory, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between a plurality of said received coordinate values and previously stored coordinate values, thereby generating a plurality of comparison results;
• (c) generating an occulting signal representing said plurality of comparison results;
• (d) updating said stored coordinate values in response to said occulting signal;
• and
• (e) processing said geometry data responsive to said occulting signal to generate pixel-based data and cell-based data, said cell-based data generated from pixel-based data.

A graphics rendering method comprising the steps:

• (a) receiving coordinate values including coordinate values of corresponding geometry data;
• (b) performing depth comparisons in parallel using a set of memory bits organized into words, where each word can perform one or more arithmetic magnitude comparisons between the stored data and the input data, said depth comparisons being at least part of simultaneous arithmetic magnitude comparisons between a plurality of said received coordinate values and previously stored coordinate values, thereby generating a plurality of comparison results;
• (c) generating an occulting signal representing said plurality of comparison results;
• (d) updating said stored coordinate values in response to said occulting signal;
• and
• (e) processing said geometry data responsive to said occulting signal to generate pixel-based data and cell-based data, said cell-based data generated from pixel-based data.