Computer program product for utilizing fast polygon fill routines in a graphics display system

• US 5,710,578 A
• Filed: 05/09/1990
• Issued: 01/20/1998
• Est. Priority Date: 12/09/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Loucks, Larry Keith, Nguyen, Khoa Dang, Beauregard, Gary Michael, Urquhart, Robert John
• Primary Examiner(s): Fetting, Anton W.
• Application Number:
  US07/521,858
• Time in Patent Office: 2,813 Days
• Field of Search: 364/518, 364/521, 364/522, 340/723, 340/747, 340/728, 395/119-129, 395/140-143
• US Class Current: 345/441
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

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 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.

Claims

1. An article of manufacture comprising:

a computer usable medium having computer readable program code means embodied therein for causing a polygon having a boundary definable by a plurality of selectable pels on a graphics display to be filled, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means for causing the computer to store in an 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

computer readable program code means for causing the computer to draw a fill line, after said traverse, between said outer pels having said stored values, for each said one of said scan lines.

2. A computer program product for use with a graphics display device, said computer program product comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing a polygon having a boundary definable by a plurality of selectable pels in said graphics display device to be filled, said computer program product having;

computer readable program code means for causing a computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means for causing said computer to store in an array a maximum value of said selectable pels for each one of a plurality of scan lines of said polygon during said sequential traverse from a y minimum value of said polygon to a y maximum value of said polygon;

computer readable program code means for causing said computer to store in an array a minimum value of said selectable pels for each one of a plurality of scan lines of said polygon during said sequential traverse from a y maximum value of said polygon to a y minimum value of said polygon; and

computer readable program code means for causing said computer to draw 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.

3. A computer program product for use with a graphics display device, said computer program product comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing a polygon having a plurality of lines definable by a plurality of selectable pels in said graphics display device to be filled, said computer program product having;

computer readable first program code means for determining if a sign of a vector product is the same for each one of two adjacent lines of the polygon;

computer readable second program code means for determining if the algebraic sign of the difference in the y value for each of two adjacent vertices of the polygon changes less than 4 times;

computer readable program code means for causing a computer to store in memory a y minimum value and a y maximum value of the polygon during said determination made by said second program code means;

computer readable program code means for causing the computer to store in memory a maximum value of said selectable pels for each one of a plurality of scan lines of said polygon during a traverse from the y minimum value of said polygon to the y maximum value of said polygon if said first and second program code means for determining are true;

computer readable program code means for causing the computer to store in memory a minimum value of said selectable pels for each one of a plurality of scan lines of said polygon during the traverse from the y maximum value of said polygon to the y minimum value of said polygon if said first and second program code means for determining are true; and

computer readable program code means for causing the computer to draw a fill line, after said traverse, from said selectable pel of minimum value to said selectable pel of maximum value for each one of said plurality of scan lines if said first and second program code means for determining are true.

4. A computer program product comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing a display in a graphic display device of a filled polygon having a boundary of lines definable by a plurality of selectable pels, said computer program product having;

computer readable program code means for causing a computer to effect a test of the polygon for one continuous scan line for each one of a plurality of scan lines within said polygon;

computer readable program code means for causing the computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means for causing the computer to store during said traverse 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 if the test of the polygon for one continuous scan line for each one of said plurality of scan lines is positive; and

computer readable program code means for causing the computer to draw 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.

5. A computer program product comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing a display in a graphic display device of a filled polygon having a boundary of lines definable by a plurality of selectable pels, said computer program product including;

computer readable program code means for determining if the algebraic sign of the difference in the y value for each of two adjacent vertices of the polygon changes less than 4 times;

computer readable program code means for causing a computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each said respective boundary line;

computer readable program code means for causing the computer to store during said traverse 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 if the program code means for determining is true; and

computer readable program code means for causing the computer to draw 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.

6. A computer program product for use with a graphics display device, said computer program product comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing a polygon having a boundary of lines definable by a plurality of selectable pels in said graphics display device to be filled, said computer program product including;

computer readable first program code means for determining if a sign of a vector product is the same for each one of two adjacent lines of the polygon;

computer readable second program code means for determining if the algebraic sign of the difference in the y value for each of two adjacent vertices of the polygon changes less than 4 times;

computer readable program code means for causing a computer to store in memory a y minimum value and a y maximum value of the polygon during said determination made by said second program code means;

computer readable program code means for causing the computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means for causing the computer to store in memory a maximum value of said selectable pels for each one of a plurality of scan lines of said polygon during a sequential traverse from the y minimum value of said polygon to the y maximum value of said polygon if said first and second program code means for determining are true;

computer readable program code means for causing the computer to store in memory a minimum value of said selectable pels for each one of a plurality of scan lines of said polygon during the sequential traverse from the y maximum value of said polygon to the y minimum value of said polygon if said first and second program code means for determining are true;

computer readable program code means for causing the computer to draw a fill line, after said traverse, from said selectable pel of minimum value to said selectable pel of maximum value for each one of said plurality of scan lines if said first and second program code means for determining are true;

computer readable program code means for causing the computer to store 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 if the first program code means for determining is false and the second program code means for determining is true; and

computer readable program code means for causing the computer to draw 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 if said first program code means for determining is false and the second program code means for determining is true.

7. An article of manufacture for use in a computer system having an operating system and a graphics support library for filling a polygon having a boundary defined by a plurality of selectable pels displayed on a graphics display,

said article of manufacture comprising a computer usable medium having computer readable program code means embodied in said medium, said program code means including:

computer readable program code means embodied in said computer usable medium for causing a computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means embodied in said computer usable medium for causing a computer to generate an array, during said traverse, having a plurality of maximum values and a plurality of minimum values, each one of said maximum values representative of each one of an outer point of said boundary for each one of a plurality of scan lines during said traverse from a y minimum value of said polygon to a y maximum value of said polygon and each one of said minimum values representative of each one of said outer point of said boundary for each one of a plurality of scan lines during said traverse from the y maximum value of the polygon to the y minimum value of said polygon; and

computer readable program code means embodied in said computer usable medium for passing a pointer to the array, after said sequential traverse of said polygon, to a routine in the graphics support library of the computer for drawing a fill line from said outer point of said minimum value to said outer point of said maximum value for each one of said plurality of scan lines.

8. An article of manufacture for use in a computer system having an operating system and a graphics support library for filling a polygon having a boundary definable by a plurality of lines of a plurality of selectable pels displayed on a graphics display,

said article of manufacture comprising a computer usable medium having computer readable program code means embodied in said medium including:

computer readable program code means embodied in said computer usable medium for causing the computer to effect a test of the polygon to determine if there is one continuous scan line for each one of a plurality of scan lines of said polygon;

computer readable program code means embodied in said computer usable medium for causing the computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means embodied in said computer usable medium for causing the computer to generate an array having a minimum value and a maximum value each representing a point along the boundary of the polygon, during said traverse, for each one of said plurality of scan lines for each one of a plurality of lines of the polygon if the test to determine if there is one continuous scan line for each one of said plurality of scan lines is positive; and

computer readable program code means embodied in said computer usable medium for passing a pointer to the array, after said sequential traverse of said polygon, to a routine in the graphics support library of the computer for drawing a fill line between a least value of said minimum value and a greatest value of said maximum value for each one of said plurality of scan lines.

9. An article of manufacture for use in a computer system having an operating system and a graphics support library for filling a polygon having a boundary definable by a plurality of lines of a plurality of selectable pels displayed on a graphics display,

said article of manufacture comprising a computer usable medium having computer readable program code means embodied in said medium, including:

computer readable program code first means embodied in said computer usable medium for causing the computer to effect a determination if a sign of a vector product is the same for each one of two adjacent lines of the polygon;

computer readable program code second means embodied in said computer usable medium for causing the computer to effect a determination if the algebraic sign of the difference in a y value for each of two adjacent vertices of the polygon changes less than 4 times;

computer readable program code means embodied in said computer usable medium for causing the computer to store in memory, during said determination caused by said second means, a y minimum value and a y maximum value of the polygon;

computer readable program code means embodied in said computer usable medium for causing the computer to effect, with respect to one boundary line at a time, a sequential traverse of said plurality of selectable pels of each respective said boundary line;

computer readable program code means embodied in said computer usable medium for causing a computer to generate an array, during said traverse, having a maximum value representing an outer point of said boundary of said polygon for each one of a plurality of scan lines of said polygon during said sequential traverse from the y minimum value of said polygon to said y maximum value of said polygon, and having a minimum value representing an outer point of said boundary of said polygon for each one of a plurality of scan lines of said polygon during said sequential traverse from the y maximum value to the y minimum value of said polygon if said first and second means for determining are true;

computer readable program code means embodied in said computer usable medium for passing a pointer to the array, after said sequential traverse of said polygon, to a routine in the graphics support library of the computer for drawing a fill line between said outer points represented as said maximum value and said minimum value in said array for each one of said plurality of scan lines if said first and second means for determining are true;

computer readable program code means embodied in said computer usable medium for causing a computer to generate an array having a minimum value and a maximum value each representing a point along the boundary of the polygon, during said traverse, for each one of said plurality of scan lines for each one of a plurality of lines of the polygon if the first means for determining is false and the second means for determining is true; and

computer readable program code means embodied in said computer usable medium for passing a pointer to the array, after said sequential traverse of said polygon, to a routine in the graphics support library of the computer for drawing a fill line between a least value of said minimum value and a greatest value of said maximum value for each one of said plurality of scan lines if the first means for determining is false and the second means for determining is true.

10. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for filling a polygon having a boundary definable by a plurality of lines displayed on a graphics display of said machine, said method steps comprising:

testing the polygon to determine if there is one continuous scan line for each one of a plurality of scan lines of said polygon;

sequentially traversing first the boundary of the polygon from a lowest point of the polygon to a highest point of the polygon and sequentially traversing second the boundary of the polygon from the highest point of the polygon to the lowest point of the polygon;

generating a first array, during said first sequential traverse, having a minimum value and a maximum value representing a minimum point and a maximum point along the boundary of the polygon for each one of said plurality of scan lines for each one of a plurality of lines of the polygon if the test to determine if there is one continuous scan line for each one of said plurality of scan lines is positive;

generating a second array, during said second sequential traverse, having a minimum value and a maximum value representing a minimum point and a maximum point along the boundary of the polygon for each one of said plurality of scan lines for each one of a plurality of lines of the polygon if the test to determine if there is one continuous scan line for each one of said plurality of scan lines is positive;

combining said first array and said second array into one array having a greatest maximum value and a least minimum value for each one of said plurality of scan lines; and

passing a pointer to said one array, after said sequential traverse of said polygon, to a routine in a graphics support library in the machine for drawing a fill line between said least minimum value and said greatest maximum value for each one of said plurality of scan lines.