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

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.

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.

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.

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.

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.

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.

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.

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.

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.