Method and apparatus for span and subspan sorting rendering system

• US 5,977,987 A
• Filed: 07/26/1996
• Issued: 11/02/1999
• Est. Priority Date: 07/26/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Raycer, Inc.
• Inventors: Duluk, Jerome F. Jr.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/686,535
• Time in Patent Office: 1,194 Days
• Field of Search: 345/419, 345/441, 345/442, 345/443, 345/118
• US Class Current: 345/441
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A data shifting capability that permits sorting the data in addition to searching for obtaining real-time performance in color, with high quality imagery through a simple search of a spacial database based on a rectangularly shaped search region or range search. A sorting Magnitude Comparison Content Addressable Memory (SMCCAM) performs a range search, introducing a conservative approximation of the ideal Occluding Region, and provides a MCCAM wherein the data words stored in the fields are shifted to corresponding fields in an adjacent word, based on the magnitude comparisons. The 3D graphics method stores the parameters of a polygon span in a spatial database and a query operation is performed on the database to determine which of those spans, or portions of spans, are visible, and applies a rule for comparing a new span portion to an old span portion on a subspan-by-subspan basis, thereby providing additional polygon edge information within a raster line, providing anti-aliasing.

Claims

1. In a graphical processing system for processing 3-dimensional object geometry data and rendering at least some of said object geometry data on a 2-dimensional display screen, a method for rendering a display raster line comprising the steps:

(a) transforming at least one of said object geometry data into a polygonal representation, said polygonal representation comprising at least one polygon, each or said polygon defined by a set of polygon parameters including polygon vertices having display screen relative coordinates;

(b) sorting each said polygon using a bucket sorting routine wherein a separate memory bucket is allocated for each display raster line and each polygon is placed into the one particular bucket that corresponds to each polygon'"'"'s starting raster line; and

(c) for each display raster line

(i) maintaining a list of all current polygons that intersect a current display raster line currently being rendered;

(ii) generating a span for each polygon that intersects said current display raster line based on geometric properties of said polygon including said polygon parameters, each said span including subraster information describing the geometric shape of said span within a vertical extent of said display raster line;

(iii) storing said geometric properties of each said generated span into a span memory;

(iv) maintaining a current span portion that is part of a potentially visible one of said generated span, said current span portion comprised of a set of current subspans, each said current subspan representing a rectangular area within said current span portion, and said set of current subspans approximating an area of said current span portion,

(v) performing at least one span occluding test to find any new span that potentially occludes said current span portion, where said span occluding test comprises

(1) determining the leftmost, rightmost, and farthest spatial coordinates in said set of current subspans; and

(2) performing a query operation on the said stored geometric properties in said span memory to find all said spans whose stored geometric properties include a spatial coordinate located between said leftmost and said rightmost spatial coordinates of the said set of current subspans, and a spatial coordinate closer than said farthest spatial coordinate of the said set of current subspans;

(vi) generating a set of new subspans, each said new subspan representing a rectangular area within said new span, and said set of new subspans approximating an area of said new span;

(vii) for each said subspan in said set of current subspans, performing a subspan comparison comprising

(1) performing a spatial comparison between said subspan in said set of current subspans and a corresponding subspan in the said set of new subspans; and

(2) determining the visibility, partial visibility, or non-visibility of each subspan in said set of current subspans; and

(viii) updating said current span portion based on results of said subspan comparisons.

2. The method in claim 1, wherein said span memory comprises a data array in a random access memory (RAM).

3. The method of claim 1, further comprising the steps of:

rasterizing said spans or said portions of spans that are visible by rasterizing visible ones of said current subspans.

4. The method in claim 1, wherein said step of storing geometric properties of each said generated span into a span memory further comprises the steps of:

(a) comparing said span data being stored into said span memory to span data previously stored into said span memory to thereby compare first stored data directly with second stored data; and

(b) inserting said span data being stored into said span memory so as to maintain a sorted list of said span data within said span memory.

5. The method in claim 1, wherein said step of storing geometric properties of each said generated span is in order of precedence by left x-coordinate.

6. The method in claim 1, wherein said rendering is performed by identifying visible polygon spans than can be rendered without performing pixel-by-pixel z-buffer comparisons.

7. The method in claim 1, wherein said step of maintaining a list of all current polygons includes the steps of:

discarding the sorted list of polygon spans from processing a previous raster line; and

building a new sorted list for each raster line as it is processed.

8. The method in claim 1, wherein said display screen relative coordinates include the location in object-precision screen coordinates of polygon vertices for said object geometry.

9. The method in claim 1, wherein said coordinates are not limited to coordinates within the bounding area of said display screen.

10. The method in claim 1, wherein said step of sorting said polygons using a bucket sorting routine includes the steps of generating one linked list per bucket, and using said linked list to perform said sorting.

11. The method in claim 1, wherein said polygon parameters include:

the location of said polygon vertices in object-precision screen coordinates, color information, edge derivatives for each polygon edge, starting raster line, ending raster line, and span derivative.

12. The method in claim 1, wherein said span memory comprises a double buffered span memory having first and second banks, wherein said span geometric properties are written to said first bank;

and wherein simultaneous to writing span geometric properties into said first bank, span geometric properties in said second bank are processed to identify visible span portions.

13. The method in claim 1, wherein said rendering is performed with sufficient speed to provide real time image generation.

14. In a graphical processing system for processing 3-dimensional object geometry data and rendering at least some of said object geometry data on a 2-dimensional display screen, a method for rendering a raster line comprising the steps of:

(a) transforming at least one of said object geometry data into a polygonal representation, said polygonal representation comprising at least one polygon, each or said polygon defined by a set of polygon parameters including polygon vertices having display screen relative coordinates;

(b) sorting each said polygon using a bucket sorting routine wherein a separate memory bucket is allocated for each display raster line and each polygon is placed into the one particular bucket that corresponds to its starting raster line; and

(c) for each raster line

(i) maintaining a list of all current polygons that intersect said raster line currently being rendered;

(ii) generating a span for each polygon that intersects said current raster line based on geometric properties of said polygon including said polygon parameters, each said span including subraster information describing the geometric shape of the span within the vertical extent of the raster scan line;

(iii) storing said geometric properties of each said generated span into a span memory comprising a sorting magnitude comparison content addressable memory (SMCCAM);

(iv) maintaining a current span portion that is part of a potentially visible one of said generated span, said current span portion comprised of a set of current subspans, each said current subspan representing a rectangular area within said current span portion, and said set of current subspans approximating an area of said current span portion,

(v) performing at least one span occluding test to find any new span that potentially occludes said current span portion;

where said span occluding test comprises (1) determining the leftmost, rightmost, and farthest spatial coordinates in the said set of current subspans, and (2) performing a query operation on the said stored geometric properties in said sorting magnitude comparison content addressable memory (SMCCAM) to find all said spans whose stored geometric properties include a spatial coordinate located between said leftmost and rightmost spatial coordinates of the said set of current subspans; and

a spatial coordinate closer than the said farthest spatial coordinate of the said set of current subspans;

(vi) generating a set of new subspans, each said new subspan representing a rectangular area within said new span, and said set of new subspans approximating the area of the said new span;

(vii) for each said subspan in said set of current subspans, performing a subspan comparison comprising (1) performing a spatial comparison between said subspan in the said set of current subspans and a corresponding subspan in the said set of new subspans, and (2) determining the visibility, partial visibility, or non-visibility of each subspan in the said set of current subspans; and

(viii) updating said current span portion based on results of said subspan comparisons; and

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;

providing an input comprising a plurality of input fields matching some of said data fields, each of said input fields divided into input bits so as to have a one-to-one bit correspondence to said data bits in said data fields in said words;

simultaneously comparing said plurality of input fields to all said words, with simultaneous field comparisons such that each said data field is compared to its corresponding input field, and generating a one-bit query result for each said word which query result is true when all said data fields within said word which are compared to one of said input fields compare favorably to each corresponding input field;

storing a flag bit corresponding to said query result for each of said words; and

conditionally shifting data stored in said data fields of each said word to corresponding fields of a different adjacent word, said flag bits stored in said words.

15. The method of claim 14, further comprising the steps of:

rasterizing said spans or said portions of spans that are visible by rasterizing visible ones of said current subspans.

16. The method in claim 14, wherein said step of storing geometric properties of each said generated span into a span memory further comprises the steps of:

(a) comparing said span data being stored into said span memory to span data previously stored into said span memory to thereby compare first stored data directly with second stored data; and

(b) inserting said span data being stored into said span memory so as to maintain a sorted list of said span data within said span memory.

17. The method in claim 16, wherein said step of storing geometric properties of each said generated span is in order of precedence by left x-coordinate.

18. The method in claim 14, wherein said rendering is performed by identifying visible polygon spans than can be rendered without performing pixel-by-pixel z-buffer comparisons.

19. The method in claim 14, wherein said step of maintaining a list of all current polygons includes the steps of:

discarding the sorted list of polygon spans from processing a previous raster line; and

building a new sorted list for each raster line as it is processed.

20. The method in claim 14, wherein said display screen relative coordinates include the location in object-precision screen coordinates of polygon vertices for said object geometry.

21. The method in claim 14, wherein said coordinates are not limited to coordinates within the bounding area of said display screen.

22. The method in claim 14, wherein said step of sorting said polygons using a bucket sorting routine includes the steps of generating one linked list per bucket, and using said linked list to perform said sorting.

23. The method in claim 14, wherein said polygon parameters include:

the location of said polygon vertices in object-precision screen coordinates, color information, edge derivatives for each polygon edge, starting raster line, ending raster line, and span derivative.

24. The method in claim 14, wherein said span memory comprises a double buffered span memory having first and second banks, wherein said span geometric properties are written to said first bank;

and wherein simultaneous to writing span geometric properties into said first bank, span geometric properties in said second bank are processed to identify visible span portions.

25. The method in claim 14, wherein said rendering is performed with sufficient speed to provide real time image generation.

26. The method in claim 14, wherein said new sorted list is generated within about two clock cycles per stored data value, wherein during first said clock cycle, a query operation determines which said words perform said conditional shifting;

and wherein during second said clock cycle, said geometric properties of said span are written into said span memory.

27. The method in claim 14, wherein hidden surface removal is performed by processing spans rather than pixels, thereby reducing computation for scenes with any significant depth complexity.

28. The method in claim 14, wherein said polygon spans are stored in a SMCCAM, and wherein said step of performing a query further comprises directly querying the entire set of polygon spans stored in said SMCCAM to identify visible spans so that the number of comparison operations is proportional to the number of visible polygon spans which is a number smaller than the total number of spans.

29. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus comprising:

means for storing a plurality of words, each one 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 comprising a plurality of input fields matching some of said data fields, each of said input fields divided into input bits so as to have a one-to-one bit correspondence to said data bits in said data fields in said words;

query means for simultaneously comparing said plurality of input fields to all said words, with simultaneous field comparisons such that each said data field is compared to its corresponding input field, and for generating a one-bit query result for each said word which query result is true when all said data fields within said word which are compared to one of said input fields compare favorably to each corresponding input field;

flag memory storage means for storing a flag bit equal to said query result for each of said words; and

shifting means for conditionally shifting an entire one of said words, including said data stored in each said plurality of data fields associated with said one entire word, to corresponding fields of a different adjacent word, said conditional shifting creating an available word storage location in said means for storing capable of receiving and storing a newly inserted word.

30. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus as in claim 29 wherein said flag memory means include means for storing a plurality of said flag bits associated with each of said words.

31. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus as in claim 30 wherein said flag memory means includes means for outputting a multiplicity of output flag bits for each said word into query logic means which performs a selectable Boolean operation for each said word on both said output flag bits and said query result to form a flag result for each said word and stores said flag result into said flag memory.

32. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus memory as in claim 31 including control means for causing said fields comparisons to be one of a plurality of different query comparison operations including either equality, less-than, less-than-or-equal-to, greater-than, greater-than-or-equal-to, inequality, or don'"'"'t care.

33. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus as in claim 32 including at least one priority resolver means for selecting the highest priority said output flag bit from the multiplicity of said output flag bits for purposes of selecting one said word for either:

reading or writing, or for determining the set of set words perform said conditional shifting.

34. A sorting magnitude comparison content addressable memory (SMCCAM) as in claim 29 wherein for each said plurality of data bits, said storage means further includes a storage bit, and said shifting means further includes a shift register bit connected between said storage bit and a corresponding storage bit in said different adjacent word.

35. In a graphical processing system for processing 3-dimensional object geometry data and rendering at least some of said object geometry data on a 2-dimensional display screen, a method for rendering a display raster line comprising the steps:

(a) transforming at least one of said object geometry data into a polygonal representation, said polygonal representation comprising at least one polygon, each or said polygon defined by a set of polygon parameters including polygon vertices having display screen relative coordinates;

(b) sorting each said polygon using a bucket sorting routine wherein a separate memory bucket is allocated for each display raster line and each polygon is placed into the one particular bucket that corresponds to each polygon'"'"'s starting raster line; and

(c) for each display raster line

(i) maintaining a list of all current polygons that intersect a current display raster line currently being rendered;

(ii) generating a span for each polygon that intersects said current display raster line based on geometric properties of said polygon including said polygon parameters;

(iii) storing said geometric properties of each said generated span into a span memory; and

(iv) performing at least one span occluding test to determine which spans or portions of spans are visible in the rendered scene, where said span occluding test comprises

(1) selecting a current span portion which is part of a potentially visible one of said generated span;

(2)determining the leftmost, rightmost, and farthest spatial coordinates in said current span portion;

(3) performing a query operation on said stored geometric properties in said span memory to find all said spans whose stored geometric properties include a spatial coordinate located between said leftmost and said rightmost spatial coordinates of the said current span portion, and a spatial coordinate closer than the said farthest spatial coordinate of the said current span portion.

36. The method in claim 35, wherein said span memory comprises a data array in a random access memory (RAM).

37. The method of claim 35, further comprising the steps of:

rasterizing said spans or said portions of spans that are visible.

38. The method in claim 35, wherein said step of storing geometric properties of each said generated span into a span memory further comprises the steps of:

(a) comparing said span data being stored into said span memory to span data previously stored into said span memory to thereby compare first stored data directly with second stored data; and

(b) inserting said span data being stored into said span memory so as to maintain a sorted list of said span data within said span memory.

39. The method in claim 38, wherein said step of storing geometric properties of each said generated span further comprises sorting said spans in order of precedence by 1) left x-coordinate, 2) left z-coordinate, and 3) span derivative.

40. The method in claim 35, wherein said rendering is performed by identifying visible polygon spans than can be rendered without performing pixel-by-pixel z-buffer comparisons.

41. The method in claim 35, wherein said step of maintaining a list of all current polygons includes the steps of:

discarding the sorted list of polygon spans from processing a previous raster line and building a new sorted list for each raster line as it is processed.

42. The method in claim 35, wherein said display screen relative coordinates include the location in object-precision screen coordinates of polygon vertices for said object geometry.

43. The method in claim 35, wherein said coordinates are not limited to coordinates within the bounding area of said display screen.

44. The method in claim 35, wherein said step of sorting said polygons using a bucket sorting routine includes the steps of generating one linked list per bucket, and using said linked list to perform said sorting.

45. The method in claim 35, wherein said polygon parameters include:

the location of said polygon vertices in object-precision screen coordinates, color information, edge derivatives for each polygon edge, starting raster line, ending raster line, and span derivative.

46. The method in claim 35, wherein said span can be modeled as a member of the set consisting of a line segment a trapezoid, a quadrilateral, or combinations thereof.

47. The method in claim 35, wherein said span is defined by span parameters including:

(a) coordinates of a first span endpoint;

(b) coordinates of a second span endpoint;

(c) a span derivative dz/dx; and

(d) an information pointer comprising an address into a polygon information memory store where color information for said polygon is stored.

48. The method in claim 35, wherein said span memory comprises a double buffered span memory having first and second banks, wherein said span geometric properties are written to said first bank;

and wherein simultaneous to writing span geometric properties into said first bank, span geometric properties in said second bank are processed to identify visible span portions.

49. The method in claim 35, wherein said rendering is performed with sufficient speed to provide real time image generation.

50. The method in claim 35, wherein said span memory comprises a sorting magnitude comparison content addressable memory (SMCCAM), and said sorting magnitude comparison content addressable memory (SMCCAM) performs said query operations.

51. The method in claim 50, further comprising the steps of:

rasterizing said spans or said portions of spans that are visible.

52. The method in claim 51, wherein said step of storing geometric properties of each said generated span into a span memory further comprises the steps of:

(a) comparing said span data being stored into said span memory to span data previously stored into said span memory to thereby compare first stored data directly with second data; and

(b) inserting said span data being stored into said span memory so as to maintain a sorted list of said span data within said span memory.

53. The method in claim 50, wherein said step of storing geometric properties of each said generated span further comprises sorting said spans in order of precedence by 1) left x-coordinate, 2) left z-coordinate, and 3) span derivative.

54. The method in claim 50, wherein said rendering is performed by identifying visible polygon spans than can be rendered without performing pixel-by-pixel z-buffer comparisons.

55. The method in claim 50, wherein said step of maintaining a list of all current polygons includes the steps of:

discarding the sorted list of polygon spans from processing a previous raster line and building a new sorted list for each raster line as it is processed.

56. The method in claim 50, wherein said display screen relative coordinates include the location in object-precision screen coordinates of polygon vertices for said object geometry.

57. The method in claim 50, wherein said coordinates are not limited to coordinates within the bounding area of said display screen.

58. The method in claim 50, wherein said step of sorting said polygons using a bucket sorting routing includes the steps of generating one linked list per bucket, and using said linked list to perform said sorting.

59. The method in claim 50, wherein said polygon parameters include:

the location of said polygon vertices in object-precision screen coordinates, color information, edge derivatives for each polygon edge, starting raster line, ending raster line, and span derivative.

60. The method in claim 50, wherein each said span can be modeled as a member of the set consisting of a line segment, a trapezoid, a quadrilateral, or combinations thereof.

61. The method in claim 50, wherein said span is defined by span parameters including:

(a) coordinates of a first span endpoint;

(b) coordinates of a second span endpoint;

(c) a span derivative dz/dx; and

(d) an information pointer comprising an address into a polygon information memory store where color information for said polygon is stored.

62. The method in claim 50, wherein said span memory comprises a double buffered span memory having first and second banks, wherein said span geometric properties are written to said first bank;

and wherein simultaneous to writing span geometric properties into said first bank, span geometric properties in said second bank are processed to identify visible span portions.

63. The method in claim 50, wherein said rendering is performed with sufficient speed to provide real time image generation.

64. The method in claim 50, wherein said new sorted list is generated within about two clock cycles per stored data value, wherein during first said clock cycle, a query operation determines which said words perform said conditional shifting;

and wherein during second said clock cycle, said geometric properties of said span are written into said span memory.

65. The method in claim 50, wherein hidden surface removal is performed by processing spans rather than pixels, thereby reducing computation for scenes with any significant depth complexity.

66. The method in claim 50, wherein said polygon spans are stored in a SMCCAM, and wherein said step of performing a query further comprises directly querying the entire set of polygon spans stored in said SMCCAM to identify visible spans so that the number of comparison operations is proportional to the number of visible polygon spans which is a number smaller than the total number of spans.

67. In a graphical processing system for processing 3-dimensional object geometry data and rendering at least some of said object geometry data on a 2-dimensional display screen, a method for rendering a scan line comprising the steps of:

(a) transforming at least one of said object geometry data into a polygonal representation, said polygonal representation comprising at least one polygon, each or said polygon defined by a set of polygon parameters including polygon vertices having display screen relative coordinates;

(b) sorting each said polygon using a bucket sorting routine wherein a separate memory bucket is allocated for each raster line and each polygon is placed into the one particular bucket that corresponds to a starting raster line for said polygon; and

(c) for each raster line;

(i) maintaining a list of all current polygons that intersect a current raster line currently being rendered;

(ii) generating a span for each polygon that intersects said current raster line based on geometric properties of said polygon including said polygon parameters, each said span including subraster information describing the geometric shape of said span within a vertical extent of said raster line;

(iii) storing said geometric properties of each said generated span into a sorting magnitude comparison content addressable memory (SMCCAM);

(iv) maintaining a current span portion that is part of a potentially visible one of said generated span, said current span portion comprised of a set of current subspans, each said current subspan representing a rectangular area within said current span portion, and said set of current subspans approximating an area of said current span portion,

(v) performing at least one span occluding test to find any new span that potentially occludes said current span portion, where said span occluding test comprises

(1) determining the leftmost, rightmost, and farthest spatial coordinates in the said set of current subspans; and

(2) performing a query operation on the said stored geometric properties in said SMCCAM to find all said spans whose stored geometric properties include a spatial coordinate located between said leftmost and said rightmost spatial coordinates of the said set of current subspans, and a spatial coordinate closer than said farthest spatial coordinate of said set of current subspans;

(vi) generating a set of new subspans, each said new subspan representing a rectangular area within said new span, and said set of new subspans approximating an area of the said new span;

(vii) for each said subspan in said set of current subspans, performing a subspan comparison comprising

(1) performing a spatial comparison between said subspan in the said set of current subspans and a corresponding subspan in said set of new subspans; and

(2) determining the visibility, partial visibility, or non-visibility of each subspan in said set of current subspans; and

(vii) updating said current span portion based on results of said subspan comparisons; and

wherein said step (iii) of storing geometric properties of each said generated span into a sorting magnitude comparison content addressable memory (SMCCAM) includes

storing a plurality of words into said SMCCAM, each of said words comprising a plurality of data fields, each of said data fields being divided into a plurality of data bits;

providing an input comprising a plurality of input fields matching some of said data fields, each of said input fields divided into input bits so as to have a one-to-one bit correspondence to said data bits in said data fields in said words;

simultaneously comparing said plurality of input fields to all said words, with simultaneous field comparisons such that each said data field is compared to its corresponding input field;

generating a one-bit query result for each said word which query result is true when all said data fields within said word which are compared to one of said input fields compare favorably to each corresponding input field;

storing a flag bit equal to said query result for each of said words; and

conditionally shifting data stored in said data fields of each said word to corresponding fields of a different adjacent word said flag bits stored in said words.

68. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus comprising:

a plurality of addressable memory storage bits, each said storage bit for storing a data bit, said memory storage bits arranged into a plurality of words;

an input circuit providing an input comprising a plurality of input bits matching some of said data bits so as to have a one-to-one bit correspondence to said data bits;

a comparator circuit simultaneously comparing said plurality of input bits to data bits in all said words, said comparator circuit making simultaneous comparisons such that each said data bit is compared to its corresponding input bit, and said comparator circuit generating a query result for each said word which query result has a first state when all said data bits within said word which are compared to one of said input bits compare favorably to each corresponding input bit, and a second state when said bits do not compare favorably;

a flag memory storage storing a flag bit equal to said query result for each of said words; and

a shift register coupled to said data bits and operable to conditionally shift an entire one of said words, including said stored data bits associated with said one entire word, to corresponding data bits of a different adjacent word;

said plurality of addressable memory storage bits, said comparator circuit, said flag memory, and said shift register in combination enabling said plurality of words to be physically stored as they are received from said input circuit in an ordered array according to magnitude.