System and method for utilizing fast polygon fill routines in a graphics display system
First Claim
1. A method in a graphics display system for filling a polygon having a boundary of a plurality of line definable by a plurality of selectable pels, said method comprising:
- testing the polygon for strict convexity;
traversing sequentially the boundary along each one of said plurality of lines one at a time;
storing, during said sequential traverse for a given line of said traverse, a minimum value of at least one of said plurality of selectable pels for each one of a plurality of scan lines if said minimum value is less than a different value for any different one of said selectable pels of said boundary of said polygon at said scan line;
storing, during said sequential traverse for a given line of said traverse, a maximum value of at least one of said plurality of selectable pels for each one of a plurality of scan lines if said maximum value is greater than a different value for any different one of said selectable pels of said boundary of said polygon at said scan line; and
drawing a fill line, after said sequential traverse, between said selectable pel having said minimum value and said selectable pel having said maximum value for each one of said plurality of scan lines.
1 Assignment
0 Petitions
Accused Products
Abstract
Two polygon fill algorithms are presented for filling polygons on a graphics display. The first polygon fill algorithm fills polygons that are strictly convex. The second polygon fill algorithm fills a larger class of polygons than the first polygon fill algorithm which includes polygons being concave in the x direction, and polygons having crossing lines. The first polygon fill algorithm tests the polygon for strict convexity by testing for a consistent turning direction, and by testing for once around in the y direction. The first polygon fill algorithm then stores the maximum and minimum value of the pel selected by the Bresenham algorithm for each scan line of the polygon. The fill line is drawn from the pel having the minimum value to the pel having the maximum value for each scan line of the polygon. The second polygon fill algorithm tests the polygon to ensure that it can be filled with one unique fill line for each scan line of the polygon. The second polygon fill algorithm stores both a minimum value and maximum value for each scan line line of the polygon for each line of the polygon. A fill line is then drawn from the least minimum value to the greatest maximum value for each scan line of the polygon.
33 Citations
28 Claims
-
1. A method in a graphics display system for filling a polygon having a boundary of a plurality of line definable by a plurality of selectable pels, said method comprising:
-
testing the polygon for strict convexity; traversing sequentially the boundary along each one of said plurality of lines one at a time; storing, during said sequential traverse for a given line of said traverse, a minimum value of at least one of said plurality of selectable pels for each one of a plurality of scan lines if said minimum value is less than a different value for any different one of said selectable pels of said boundary of said polygon at said scan line; storing, during said sequential traverse for a given line of said traverse, a maximum value of at least one of said plurality of selectable pels for each one of a plurality of scan lines if said maximum value is greater than a different value for any different one of said selectable pels of said boundary of said polygon at said scan line; and drawing a fill line, after said sequential traverse, between said selectable pel having said minimum value and said selectable pel having said maximum value for each one of said plurality of scan lines. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method in a graphics display system for filling a polygon having a boundary definable by selectable pels, said method comprising:
- traversing sequentially the boundary along said selectable pels;
storing in an array, during said sequential traverse, a maximum value of said selectable pel for each one of a plurality of scan lines of said polygon during said traverse from a y minimum value of said polygon to a y maximum value of said polygon; storing in said array, during said sequential traverse, a minimum value of said selectable pel for each one of said plurality of scan lines of said polygon during said traverse from said y maximum value of said polygon to said y minimum value of said polygon; and drawing a fill line, after said sequential traverse, from said selectable pel of minimum value to said selectable pel of maximum value for each one of said plurality of scan lines.
- traversing sequentially the boundary along said selectable pels;
-
10. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; and stepping repetitively from a previous scan line to a next scan line during said sequential traverse.
-
-
11. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of a last selectable pel on the previous scan line after said step from said previous scan line to said next scan line if said one of said plurality of lines is determined to be in a first octant.
-
-
12. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of a last selectable pel on the next scan line if the next scan line is a last scan line of said line of said polygon and if said one of said plurality of lines is determined to be in a first octant.
-
-
13. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of a last selectable pel on the previous scan line after said step from said previous scan line to said next scan line, if said one of said plurality of lines is determined to be in a fifth octant.
-
-
14. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon;
stepping repetitively from a previous scan line to a next scan line during said sequential traverse; andstoring a value of a last selectable pel on the next scan line if the next scan line is a last scan line of said line of said polygon, and if said one of said plurality of lines is determined to be in a fifth octant.
-
-
15. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of the selectable pel on said next scan line if said one of said plurality of lines is determined to be in a second octant.
-
-
16. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of the selectable pel on said next scan line if said one of said plurality of lines is in a third octant.
-
-
17. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and
storing a value of the selectable pel on said next scan line if said one of said plurality of lines is in a sixth octant.
-
-
18. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of the selectable pel on said next scan line if said one of said plurality of lines in in a seventh octant.
-
-
19. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan lines to a next scan line during said sequential traverse; and storing a value of a first selectable pel on the next scan line after said step from said previous scan line to said next scan line if said one of said plurality of lines is in a fourth octant.
-
-
20. A method for selecting a plurality of outer pels along a boundary of a polygon having a plurality of lines definable by a plurality of selectable pels, each one of said plurality of lines being in one of eight octants, said method comprising:
-
determining the octant of each one of said plurality of lines of said polygon; traversing sequentially the lines of the polygon; stepping repetitively from a previous scan line to a next scan line during said sequential traverse; and storing a value of a first selectable pel on the next scan line after said step from said previous scan line to said next scan line if said one of said plurality of lines is in an eighth octant.
-
-
21. A system having a graphics display for filling a polygon having a boundary definable by a plurality of selectable pels, said system comprising:
-
means for traversing sequentially the boundary along said plurality of selectable pels; means for storing in a memory array during said traverse a value of an outer pel of said boundary of said plurality of selectable pels for each one of a plurality of scan lines of said polygon; and means for drawing a fill line, after said traverse, between said outer pels having said stored values, for each scan line. - View Dependent Claims (22)
-
-
23. A method for filling a polygon having a plurality of lines definable by a plurality of selectable pels in a graphics display system comprising:
-
testing the polygon for one continuous scan line for each one of a plurality of scan lines within said polygon; traversing sequentially the lines of the polygon; storing a minimum and a maximum value of said selectable pels for each one of said plurality of scan lines for each one of said plurality of lines during said traverse; and
drawing a fill line, after said traverse, from a least value of said minimum value to a greatest value of said maximum value for each one of said plurality of scan lines. - View Dependent Claims (24, 25)
-
-
26. A method for filling a polygon having a plurality of lines definable by a plurality of selectable pels in a graphics display system comprising:
-
determining if a sum of all of a plurality of interior angles of said polygon is equal to 360 degrees; traversing sequentially the lines of the polygon; storing, during said traverse, a value of an outer pel of said selectable pels for each one of said plurality of scan lines for each one of said plurality of lines during said traverse; and drawing a fill line, after said traverse, from said outer pel having a least value to said outer pel having a greatest value for each one of said plurality of scan lines.
-
-
27. A method for filling a polygon having a plurality of lines definable by a plurality of selectable pels in a graphics display system comprising:
-
traversing firstly the polygon in a same direction along the selectable pels of the polygon from a lowest point of the polygon to a highest point of the polygon; storing in a second table a minimum and a maximum value of said selectable pels for each one of a plurality of scan lines during said first traverse; traversing secondly the polygon in the same direction along the selectable pels of the polygon from the highest point of the polygon to the lowest point of the polygon; storing in a first table the minimum and the maximum value of said selectable pels for each one of a plurality of scan lines of the polygon during said second traverse; and drawing a fill line from a least minimum value from the first and second table to a greatest maximum value from the first and second table for each one of a plurality of scan lines of the polygon.
-
-
28. A system having a graphics display for displaying polygons having a plurality of lines definable by a plurality of selectable pels, said system comprising:
-
means for a first polygon traverse along the selectable pels of the lines of the polygon from a lowest point of the polygon to a highest point of the polygon; a second array for storing from said first traverse a minimum and a maximum value of said selectable pels for each one of a plurality of scan lines of said polygon; means for a second polygon traverse along the selectable pels of the lines of the polygon from the highest point of the polygon to the lowest point of the polygon; a first array for storing from said second traverse the minimum and the maximum value of said selectable pels for each one of said plurality of scan lines of said polygon; and means for drawing a fill line from a least minimum value of said first and second array to a greatest maximum value of said first and second array for each one of said plurality of scan lines.
-
Specification