Method and apparatus for span and subspan sorting rendering system
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
152 Citations
68 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
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. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66)
-
-
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.
-
Specification