USRE38078EExpiredUtilityPatentIndex 93
Graphical rendering system using simultaneous parallel query Z-buffer and method therefor
Est. expiryApr 21, 2014(expired)· nominal 20-yr term from priority
Inventors:DULUK JR JEROME F
G06T 15/405G06T 2210/12
93
PatentIndex Score
32
Cited by
70
References
122
Claims
Abstract
Apparatus and method for a Parallel Query Z-coordinate Buffer are described. The apparatus and method perform a keep/discard decision on screen coordinate geometry before the geometry is converted or rendered into individual display screen pixels by implementing a parallel searching technique within a novel z-coordinate buffer based on a novel magnitude comparison content addressable memory (MCCAM) structure. The MCCAM provides means structure and method for performing simultaneous arithmetic magnitude comparisons on numerical quantities. These arithmetic magnitude comparisons include arithmetic less-than, greater-than, less-than-or-equal to, and greater-than-or-equal-to operations between coordinate values of a selected graphical object and the coordinate values of other objects in the image scene which may or may not occult the selected graphical object. Embodiments of the method and apparatus utilizing variations The structure and method support variations and combinations of bounding box occulting tests, vertex bounding box occulting tests, span occulting tests, and raster-write occulting tests, as well as combinations of these tests are described .
Claims
exact text as granted — not AI-modifiedI claim as follows:
1. A method of writing graphics images from 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 image pixel location represented by said frame buffer in 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 stored in said data memory;
generating a bounding box around said selected geometry data;
determining a minimum z-coordinate value of said selected geometry data;
simultaneously performing for each of a plurality of pixels defining said selected geometry item, prior to generation of pixel raster data from said selected geometry data item, an arithmetic magnitude comparison between said minimum z-coordinate value and said previously stored z-coordinate values associated with each of said plurality of pixels pixel location of previously selected geometry data currently stored on a pixel-by-pixel basis in said magnitude comparison content addressable memory buffer; and
discarding on a pixel-by-pixel basisidentifying, prior to generation of pixel raster data from said selected geometry data, a portionpixels of said selected geometry data for which said minimum z-coordinate value is greater than said previously stored z-coordinate values within said bounding box so that said discarded portion ; and ignoring said identified pixels of said selected geometry data is when writing said geometry data as raster data to said frame buffer so that said identified pixels are not written to said frame buffer.
2. The method of claim 1 , wherein said bounding box generated in said generating step is a minimum sized rectangle in a viewing plane defined by said display screen which covers the area covered by said selected geometry data.
3. The method of claim 1 , further comprising the step of:
replacing said previously stored z-coordinate values in said magnitude comparison content addressable memory buffer with the z-coordinate values of said selected geometry data when said minimum z-coordinate value is less than said previously stored z-coordinate values.
4. The method in claim 1 , wherein said step of simultaneously performing said plurality of arithmetic magnitude comparisons between said minimum z-coordinate value and said previously stored z-coordinate values of previously selected geometry data comprises simultaneously performing said arithmetic magnitude comparisons between said minimum z-coordinate value and all of said previously stored z-coordinate values.
5. The method of claim 1 , wherein said arithmetic magnitude comparison operations are selected from the group consisting of a greater-than arithmetic operation, a greater-than-or-equal-to arithmetic operation, a less-than arithmetic operation, and a less-than-or-equal-to arithmetic operation.
6. The method of claim 1 , further comprising the steps of:
storing a plurality of words, each of said words comprising a plurality of data fields, each of said data fields being divided into a plurality of data bits;
providingreceiving an input comprising a plurality of input fields matching some of said data fields of said words, and dividing each said input field of said received input into input bits so as to have a one-to-one bit correspondence to the said data bits in said data fields in of said stored words;
simultaneously comparing said plurality of input fields to all said words such that each said data field is compared to its corresponding said input, and for simultaneously generating a query result for each said word which is true when all said data fields within said word which are compared to one of said inputs compare favorably to each corresponding said input;
flag memory means for storing a flag bit equal to said query result for each of said words;
writing data to multiple words of said magnitude comparison content addressable memory simultaneously; and
performing multiple simultaneous queues of words of said magnitude comparison content addressable memory.
7. The method of claim 1 , wherein each said number stored in said magnitude comparison content addressable memory buffer for use as a z-coordinate value is a number indicating that said z-coordinate value is at an infinite distance from the viewing eyepoint.
8. The method of claim 1 , wherein said magnitude comparison test comprises applying a comparison test to all pixels previously stored in the MCCAM z-buffer and generating said a first boolean value for each pixel when the following formula is satisfied as false:
Pixel( x,y )=0 if [( x<x min )( x>x max )( y<y min )( y>y max )( z<z min )]. Pixel( x,y ) = 0 if [ ( x<x min ) ( x>x max ) ( y>y max ) ( z<z min ) ].
9. The method of claim 8 , wherein said first boolean value is generated from separate comparison result generating steps for each of the inequalities x<x min , x>x max , y<y min , y>y max , and z<z min .
10. The method of claim 9 , wherein said simultaneous arithmetic comparisons perform an occulting test uses a comparison apparatus of said MCCAM z-buffer including performing a comparison operation to determine if said bounding box is occulted by previously rasterized geometry; and wherein said comparison apparatus comprises:
means for performing the an arithmetic less-than operation between said x and said x min to generate an x min comparison result;
means for performing the an arithmetic greater-than operation between said x and said x max to generate an x max comparison result;
means for performing the an arithmetic less-than operation between said y and said y min to generate an y min comparison result;
means for performing the an arithmetic greater-than operation between said y and said y max to generate an y max comparison result;
means for performing the an arithmetic less-than operation between said z and said z min to generate an z min comparison result; and
logic means receiving said x min , x max , y min , y max , and z min comparison results and generating an occultation result based on said received comparison results and predetermined rules.
11. The method of claim 10 , wherein each said arithmetic less-than operation between said z and said z min comparison is performed simultaneously including comparisons for pixels outside said projected bounding box; whereby the value of occulted is determined in an amount of time independent of both the number of pixels or the size of the projected bounding box.
12. The method of claim 11 , wherein said bounding box occulting test further comprises the steps of:
terminating said occulting test at any time occulted is set to false; and
testing only pixels within a said projected bounding box for which x min ≦x≦x max and y min ≦y≦y max .
13. The method in claim 10 , wherein said MCCAM z-buffer comprises means for further comprising the step of writing values for said z-fields z- values while maintaining said x-fields and said y-fields x- values and y - values of said comparisons fixed.
14. The method in claim 10 , wherein said MCCAM further comprises means for further comprising the step of: performing a raster-write operation to simultaneously write a fixed z-value to multiple words adjacent along a display raster line of said MCCAM, and wherein said multiple words comprise words adjacent along a display raster line .
15. The method in claim 1 , further comprising the step of temporally correlating a sequence of image scenes through the use of tag pointers to source geometry stored in a tag field within said MCCAM z-buffer.
16. The system method of claim 1 , wherein said display screen pixels are divided into frame buffer is addressable as a plurality of sub-image blocks; and wherein said system comprises a plurality of magnitude comparison content addressable memory z-buffers arranged in parallel, each said magnitude comparison content addressable memory z-buffers processing data for one of said sub-image blocks; said parallel arrangement of magnitude comparison content addressable memory z-buffers operating to increase the overall input/output capability said system over that provided by a single magnitude comparison content addressable memory z-buffer step of simultaneously performing said arithmetic magnitude comparison is performed in parallel for each one of said plurality of sub- image blocks.
17. 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.
18. The graphics rendering system recited in claim 17 further comprising:
a z-buffer for storing actual z-coordinate values corresponding to said coordinate values of said geometry data from said processor; and wherein said z-coordinate values stored in said magnitude comparison content addressable memory are approximate z-coordinate values of said geometry data, said approximate z-coordinate values being greater-than-or-equal-to said actual z-coordinate value so that when a new geometry data is compared to said stored approximated z-coordinate value then said new geometry data is never declared occulted based on said approximated Z-coordinate value if it would not be declared occulted based on said actual z-coordinate value.
19. The graphics rendering system of claim 17 , wherein said magnitude comparison content addressable memory (MCCAM) further comprises:
means for storing a plurality of words, each of said words comprising a plurality of data fields, each of said data fields being divided into a plurality of data bits;
means for providing an input to said MCCAM, said input comprising a plurality of input fields matching some of said data fields, each said input being divided into input bits so as to have a one-to-one bit correspondence to said data bits in said data fields;
query means for simultaneously comparing said plurality of input fields to all of said words so that each said data field is compared to its corresponding input field, and for simultaneously generating a query result for each said word which result is true only when all said data fields within said word compare favorably to each corresponding said input; said query means including arithmetic magnitude comparator means associated with each said word storing a pixel z-value for comparing said stored pixel z-value with a reference value; and
flag memory means for storing a flag bit equal to said query result for each of said words.
20. The system of claim 19 , wherein:
said magnitude comparison content addressable memory further comprises means for writing data to multiple words of said magnitude comparison content addressable memory simultaneously; and
means for performing multiple simultaneous queries of words of said magnitude comparison content addressable memory;
whereby the number of clock cycles needed to process geometry data is reduced .
21. The graphics rendering system in claim 17 , wherein said magnitude comparison content addressable memory 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 comprises:
means for performing simultaneous arithmetic magnitude comparisons between all of said received coordinate values with said previously stored coordinate values in said magnitude comparison content addressable memory; and
wherein said arithmetic magnitude comparisons operations are selected from the group consisting of a greater-than arithmetic operation, a greater-than-or-equal-to arithmetic operation, a less-than arithmetic operation, and a less-than-or-equal-to arithmetic operation.
22. 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
discardingidentifying 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.
23. The method of claim 22 , wherein said comparison test is performed for every pixel in the display screen, and further comprising the steps of:
setting, for each of said pixels prior to performing said comparison test, an occulted parameter to true to indicate that the geometrical location associated with said pixel is occulted, independent of whether said pixel is actually occulted or not occulted;
determining the current z-coordinate value for each said pixel;
generating an approximating boundary characterization of said selected geometry data based on coordinate parameters of said selected geometry data;
determining whether said pixel is within a projection of said projected bounding box generated approximating boundary characterization for said selected geometry data, and if said pixel is within said projected bounding box projection, then comparing said current z-coordinate value for said pixel to said geometry data minimum z- coordinate value z min ;
if z min is not greater that than said z-coordinate value of said evaluating pixel, then setting said occulted parameter to false for said pixel indicating that said new geometry data may not be occulted and required requires additional processing to determine whether said geometry data is occulted or not; and
wherein every one of said pixels is evaluated for occultation simultaneously in a predetermined number of clock cycles independent of the number of pixels and independent of the size of the projected bounding box said approximating boundary characterization for said selected geometry data.
24. The method of claim 23 , wherein said predetermined number of clock cycles is one clock cycle.
25. The method of claim 24 , wherein said method further comprises the steps of:
terminating said bounding box occulting magnitude comparison test whenever a pixel is determined not to be occulted and said occulted value is set to false; and
testing only pixels within said projected bounding box approximating boundary characterization for said selected geometry data rather than all of said pixels within said display screen.
26. The method of claim 24 , wherein said comparison tests are is performed for all pixels in said display screen simultaneously and in parallel to search for and determine if identify any piece of geometry data that is occulted, so that an entire geometry data object is tested to determine if it is occulted before said geometry data object is rasterized into pixels so that if it is determined that said entire geometry data object is occulted then all of the computations for converting the geometry data object geometry to pixels are avoided.
27. The method of claim 23 , wherein said occulting test further comprises the steps of:
storing geometrical parameters for each pixel in a word in a data structure, said word including an x-field for storing and comparing the pixel x-value, a y-field for storing and comparing the pixel y-value, a z-field for storing and comparing the pixel z-value, and a logic field for storing and generating result signals including a pixel miss signal.
28. The method of claim 27 , wherein said word further includes an infinity flag field for indicating storing an indication that the z-value of the associated pixel is infinity, thus causing the pixel to be further away from the viewing point than any geometry could be located;
whereby said infinity flag field for all pixels may being set in parallel and thereby eliminate eliminating any need to separately write each z-value z- field with a large numerical z-value;
said infinity flag field being cleared whenever a new z-value is written to the associated pixel; and
wherein said arithmetic magnitude comparison test comprises applying a said comparison test to all of said pixels previously stored in said magnitude comparison content addressable memory (MCCAM) z-buffer, and generating said a first boolean value for each pixel when the following formula is satisfied as false:
Pixel(x,y)=0 if [(x<x min )(x>x max )(y<y min )(y>y max ){(z<z min )NOT(Infinity_Flag)}].
Pixel( x,y ) = 0 if [ ( x<x min ) ( x>x max ) ( y<y min ) ( y>y max ) { ( z<z min ) NOT ( Infinity — Flag )}].
29. The method of claim 28 , further comprising the steps of:
tagging pixels generating a said first boolean value indicating said pixel is not occuoted occulted for a subsequent processor to use in rendering temporally related scenes.
30. The method of claim 29 , further comprising the steps of:
grouping said tagged pixels together into segments along a display raster line.
31. 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 ).
32. The method of claim 31 , the step ( g ) further comprising:
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.
33. The method of claim 32 , wherein a resultant frame comprises a multiplicity of picture elements, wherein each picture element is a blending of one or more pixel color values generated in the step ( g ).
34. The method of claim 32 , wherein steps ( a ) through ( g ) are performed once for each of a plurality of subsets of the geometry data.
35. The method of claim 32 , wherein steps ( a ) through ( f ) are performed once for each of a plurality of subsets of the geometry data and then subsequently performing step ( g ).
36. The method of claim 32 , further comprising:
processing multiple frame instances, each frame instance being generated for a plurality of multiple - cell blocks, each block being generated by performing steps ( a ) through ( f ) once for each a particular plurality of subsets of the geometry data and then subsequently performing step ( g ) , the particular plurality of subsets being those that potentially effect the block being generated.
37. The method of claim 36 , wherein at least two of the plurality of multiple- cell blocks are generated in parallel.
38. The method of claim 36 , wherein during the performance of steps ( a ) through ( f ) for each block, at least one tag value is stored identifying an associated subset of geometry data, if the associated subset of geometry is not indicated as hidden at a pixel location.
39. The method of claim 38 , wherein each storing of the tag value is done on a pixel- by - pixel basis.
40. The method of claim 39 , further comprising:
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
the generating color values step further includes retrieving each previously stored tag value on a pixel - by - pixel basis, each retrieved tag value identifying the geometry subset responsible for the final color of the corresponding pixel, and using the identified geometry subset to generate the final color value.
41. The method of claim 31 , further comprising:
prior to the simultaneously performing step, choosing a contiguous plurality of cells, the shape, and location as to approximate a boundary characterization of the selected subset, and
during the simultaneously performing step, only considering cell distance values for cells in the contiguous plurality of cells.
42. The method of claim 41 , wherein the contiguous plurality of cells has a rectangular shape.
43. The method of claim 31 , further comprising:
prior to the selecting subset step, processing the frame in sub - frame blocks of pixels, the sub - frame blocks of pixels having rectangular shape and a substantially uniform size where the size is determined based on the number of magnitude comparisons that can be performed simultaneously.
44. The method of claim 31 , wherein the simultaneously performing step ( e ) is accomplished in a predetermined number of clock cycles.
45. The method of claim 31 , wherein the simultaneously performing step ( e ) is accomplished in a one clock cycle.
46. The method of claim 31 , wherein step ( e ) includes performing the magnitude comparisons using a magnitude comparison content addressable memory.
47. The method of claim 31 , wherein steps ( c ) and ( d ) are performed once for each of a plurality of subsets of the geometry data and then subsequently performing steps ( a ), ( b ), ( e ), ( f ) , and ( g ) for each of the plurality of subsets in increasing order of the corresponding geometry distance values.
48. The method of claim 31 , wherein the geometry data includes polygons, surfaces, and volumes.
49. The method of claim 31 , wherein the geometry data comprises items selected from the group consisting of polygons, surfaces, volumes, and combinations thereof.
50. The method of claim 31 , wherein the geometry data is stored in a geometry database organized in a hierarchical tree of objects, each object, in turn recursively includes one or more of polygons, surfaces, volumes and objects.
51. The method of claim 31 , further comprising:
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, step ( g ) being postponed until all the geometry data has been selected.
52. The method of claim 51 , wherein at least two of the plurality of multiple- cell blocks are generated in parallel.
53. The method of claim 31 , wherein said cell distance value is not less than the maximum of the pixel distance values of the corresponding pixel locations within the cell.
54. The method of claim 31 , wherein said cell distance value is the maximum of the pixel distance values of the corresponding pixel locations within the cell.
55. The method of claim 31 , wherein in step ( b ) , the storing of cell distance values is performed in parallel for a second plurality of cells.
56. The method of claim 31 , wherein the simultaneously performing step is performed as the result of a parallel query.
57. The method of claim 31 , further comprising:
processing multiple frame instances, each frame instance being generated for a plurality of multiple - cell blocks, each block being generated by performing steps ( a ) through ( g ) once for each of a particular plurality of subsets of the geometry data, the particular plurality of subsets being those subsets that potentially effect the block being generated.
58. The method of claim 57 , wherein at least two of the plurality of multiple- cell blocks are generated in parallel.
59. The method of claim 57 , wherein during the performance of steps ( a ) through ( g ) for each block, at least one tag value is stored identifying an associated subset of geometry data, if the associated subset of geometry is not indicated as hidden at a pixel location.
60. The method of claim 59 , wherein each storing of the tag value is done on a pixel- by - pixel basis.
61. The method of claim 60 , further comprising:
completing a particular frame instance, and during the generating of each block of a subsequent frame, selecting those geometry subsets having associated previously stored tag values before selecting other geometry subsets.
62. The method of claim 59 , wherein each storing of the tag value is done on a cell- by - cell basis.
63. The method of claim 62 , wherein each storing of the tag value for a particular cell is done only if the subset of geometry is not indicated as hidden at a predetermined pixel location within the cell.
64. The method of claim 63 , further comprising:
completing a particular frame instance, and during the generating of each block of a subsequent frame, selecting those geometry subsets having associated previously stored tag values before selecting other geometry subsets.
65. The method of claim 31 , wherein the simultaneous performing step is performed using a magnitude comparison content addressable memory.
66. The method of claim 31 , wherein the simultaneous performing step is performed 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 input data.
67. The method of claim 31 , wherein the simultaneous performing step is performed using a CAM wherein the stored data are treated as numbers and arithmetic magnitude comparisons are performed in parallel.
68. The method of claim 31 , wherein the simultaneous performing step is performed using a MCCAM Z- buffer.
69. The method of claim 31 , wherein the simultaneous performing step is performed using a set of memory bits organized into MCCAM words, each MCCAM word corresponding to one cell, each MCCAM word performing an arithmetic magnitude comparison between the stored cell distance value and the geometry distance value, the geometry distance value being input to each MCCAM word.
70. The method of claim 69 , wherein the stored cell distance values are write- only.
71. The method of claim 69 , wherein the MCCAM word includes an infinity flag, that causes each cell distance value to be treated as though it is equal to positive infinity.
72. The method of claim 31 , wherein the simultaneous performing step is performed 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.
73. 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 ).
74. 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.
75. The method of claim 74 , further comprising:
( d ) indicating the selected polygon as hidden, on a cell - by - cell basis, if the stored distance value is closer.
76. The method of claim 75 , wherein said step ( d ) of indicating the selected polygon as hidden, on a cell - by - cell basis, if the stored distance value is closer, comprises a step of indicating the selected polygon as hidden, on a cell - by - cell basis, if the stored distance value is closer to a selected viewing location.
77. The method of claim 74 , further comprising:
( e ) for any geometry data indicated as hidden on a cell - by - cell basis, omitting generation of color values.
78. The method of claim 77 , further comprising:
( f ) 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.
79. 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.
80. The graphics processor of claim 79 , wherein said plurality of generated cell distance values and the plurality of stored cell distance values being compared are the same.
81. The graphics processor of claim 79 , wherein the stored cell distance values represent all the pixel locations corresponding to a rectangular array of pixels configured to generate an approximate bounding box characterization of the selected set of polygons.
82. The graphics processor of claim 79 , wherein 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.
83. The graphics processor of claim 79 , 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.
84. The graphics processor of claim 83 , further comprising:
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.
85. The graphics processor of claim 79 , wherein completion of the parallel comparison requires a predetermined number of clock cycles.
86. The graphics processor of claim 85 , wherein the number of clock cycles is one clock cycle.
87. The graphics processor of claim 85 , wherein, in a single clock cycle, one parallel comparison is completed and its result stored and another parallel comparison operation is started.
88. The graphics processor of claim 79 , wherein the parallel comparison means includes a magnitude comparison content addressable memory.
89. The graphics processor of claim 79 , wherein the polygon processing means is configured to select sets of polygons in increasing order of closest polygon distance values.
90. 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.
91. A graphics processing system according to claim 90 , further comprising:
a host processor configured to run graphics application software and manipulate geometry data that represents one or more three - dimensional scenes, each scene including polygon data, including coordinate data, associated with each of a plurality of polygons.
92. 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.
93. A graphics processing system according to claim 92 , further comprising:
a host processor configured to run graphics application software and manipulate geometry data that represents one or more three - dimensional scenes, each scene including polygon data, including coordinate data, associated with each of a plurality of polygons.
94. 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.
95. The graphics processor of claim 94 , further comprising:
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 for each pixel location in the frame.
96. The graphics processor of claim 94 , wherein said generated at least one distance value represents all of the pixel locations in the selected cell.
97. 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.
98. 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.
99. 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.
100. 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.
101. 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.
102. The graphics rendering system of claim 101 having magnitude comparison content addressable memory also used for generating hit information, said hit information indicating to said processor which pixel- based data needs to be generated.
103. 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.
104. The graphics rendering system of claim 103 having magnitude comparison content addressable memory also used for generating hit information, said hit information indicating to said processor which pixel- based data needs to be generated.
105. 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.
106. The graphics rendering system of claim 105 having magnitude comparison content addressable memory also used for generating hit information, said hit information indicating to said processor which pixel- based data needs to be generated.
107. 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.
108. The graphics rendering system of claim 107 having magnitude comparison content addressable memory also used for generating hit information, said hit information indicating to said processor which pixel- based data needs to be generated.
109. 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.
110. The method of claim 109 , comprising the additional step:
( f ) storing at least some of said generated pixel - based data into a frame buffer.
111. The method of claim 109 , the step ( c ) further comprising generating hit information, said hit information indicating which pixel - based data needs to be generated in step ( e ).
112. 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.
113. The method of claim 112 , comprising the additional step:
( f ) storing at least some of said generated pixel - based data into a frame buffer.
114. The method of claim 112 , the step ( c ) further comprising generating hit information, said hit information indicating which pixel - based data needs to be generated in step ( e ).
115. 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.
116. The method of claim 115 , wherein said cell- based data is used in step ( d ) to update said stored coordinate values.
117. The method of claim 116 , comprising the additional step:
( f ) storing at least some of said generated pixel - based data into a frame buffer.
118. The method of claim 116 , the step ( c ) further comprising generating hit information, said hit information indicating which pixel - based data needs to be generated in step ( e ).
119. 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.
120. The method of claim 119 , wherein said cell- based data is used in step ( d ) to update said stored coordinate values.
121. The method of claim 120 , comprising the additional step:
( f ) storing at least some of said generated pixel - based data into a frame buffer.
122. The method of claim 120 , the step ( c ) further comprising generating hit information, said hit information indicating which pixel - based data needs to be generated in step ( e ).Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.