Method and apparatus for performing polygon fills in graphical applications

Claim 1

A method of filling computer-generated polygon shapes, said shapes being formed on a matrix of pixels which is organized into individual horizontal raster lines, comprising the steps of: (a) storing data representative of the vertices defining each polygon edge; (b) computing points of intersection along one of said raster lines of a scan-line with said polygon edges, and assigning a crossed-edge count and a parity value based on said crossed edge count to each of said of intersections; (c) combining at said point of intersection all horizontal edges which are colinear with said scan-line and all intersecting vertices into a colinear horizontal edge; (d) calculating the number of polygon edges positioned above said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into an above edge count; (e) calculating the number of polygon edges positioned below said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into a below edge count; (f) comparing said above edge count and said below edge count, whereby if both said above edge count and said below edge count have even parity, the parity of the crossed-edge count of the colinear horizontal edge is inverted; and (g) modifying the string of said pixels along said raster line from the current point of intersection to the next point of intersection accordinq to the parity of said crossed-edge count, said modification being executed if the parity of said crossed-edge count is odd and said modification not executed if the parity of said crossed-edge count is even.

Claim 2

A method of filling computer-generated polygon shapes, said shapes being formed on a matrix of pixels which is organized into individual horizontal raster lines, comprising the steps of: (a) storing data representative of the vertices defining each polygon edge; (b) computing points of intersection along one of said raster lines of a scan-line with said polygon edges, and assigning a crossed-edge count and a parity value based on said crossed edge count to each of said of intersections; (c) combining at said point of intersection all horizontal edges which are colinear with said scan-line and all intersecting vertices into a colinear horizontal edge; (d) calculating the number of polygon edges positioned above said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into an above edge count; (e) calculating the number of polygon edges positioned below said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into a below edge count; (f) comparing said above edge count and said below edge count, whereby if both said above edge count and said below edge count have even parity, the parity of the crossed-edge count of the colinear horizontal edge is inverted; and (g) modifying the string of said pixels along said raster line from the current point of intersection to the next point of intersection accordinq to the parity of said crossed-edge count, said modification being executed if the parity of said crossed-edge count is odd and said modification not executed if the parity of said crossed-edge count is even.

Claim 5

A method of filling polygon shapes, said shapes formed on a matrix of pixels which is organized into individual horizontal raster lines, and whereby each polygon is represented in computer memory as a set of polygon edges defined by the coordinates of the edge vertices, said method comprising the steps of: (a) computing points of intersection along one of said raster lines of a scan-line with said polygon edges, and assigning crossed-edge count and a parity value based on said crossed-edge count to each of said intersections,; (b) combining at said point of intersection all horizontal edges which are colinear with said scan-line and all intersecting vertices into a colinear horizontal edge; (c) calculating the number of polygon edges positioned above said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into an above edge count; (d) calculating the number of polygon edges positioned below said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into a below edge count; (e) comparing said above edge count and said below edge count whereby if both said above edge and said below edge count have even parity, the parity of the crossed-edge count of the colinear horizontal edge is inverted; and (f) modifying the string of said pixels along said raster line from the current point of intersection to the next point of intersection according to the parity of said crossed-edge count, said modification being executed if the parity of said crossed-edge count is odd and said modification not executed if the parity of said crossed-edge count is even.

Claim 6

A method of filling polygon shapes, said shapes formed on a matrix of pixels which is organized into individual horizontal raster lines, and whereby each polygon is represented in computer memory as a set of polygon edges defined by the coordinates of the edge vertices, said method comprising the steps of: (a) computing points of intersection along one of said raster lines of a scan-line with said polygon edges, and assigning crossed-edge count and a parity value based on said crossed-edge count to each of said intersections,; (b) combining at said point of intersection all horizontal edges which are colinear with said scan-line and all intersecting vertices into a colinear horizontal edge; (c) calculating the number of polygon edges positioned above said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into an above edge count; (d) calculating the number of polygon edges positioned below said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into a below edge count; (e) comparing said above edge count and said below edge count whereby if both said above edge and said below edge count have even parity, the parity of the crossed-edge count of the colinear horizontal edge is inverted; and (f) modifying the string of said pixels along said raster line from the current point of intersection to the next point of intersection according to the parity of said crossed-edge count, said modification being executed if the parity of said crossed-edge count is odd and said modification not executed if the parity of said crossed-edge count is even.

Claim 9

A method of filling a polygon as represented on a scan-line raster display, comprising the steps of, storing data representative of the location of a polygon edge, computing the points of intersection of a scan-line with each polygon edge, combining colinear horizontal edges at the points of intersection, calculating the number of polygon edges positioned above the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, calculating the number of polygon edges positioned below the colinear horizontal edge, inverting the parity of the crossed-edge count it the parity of both the above edge a count and the below edge count are even and modifying the string of pixels along the raster line from the current point of intersection to the next point of intersection according to the parity of the crossed count.

Claim 10

A method of filling a polygon as represented on a scan-line raster display, comprising the steps of, storing data representative of the location of a polygon edge, computing the points of intersection of a scan-line with each polygon edge, combining colinear horizontal edges at the points of intersection, calculating the number of polygon edges positioned above the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, calculating the number of polygon edges positioned below the colinear horizontal edge, inverting the parity of the crossed-edge count it the parity of both the above edge a count and the below edge count are even and modifying the string of pixels along the raster line from the current point of intersection to the next point of intersection according to the parity of the crossed count.

Claim 12

An apparatus for filling a polygon as represented on a scan-line raster display, comprising, means for storing data representative of the location of a polygon edge, means for computing the points of intersection of a scan-line with each polygon edge, means for combining colinear horizontal edges, means for calculating the number of polygon edges positioned above the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, means for calculating the number of polygon edges positioned below the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, means for modifying the crossed-edge count if the parity of the above edge count and the below edge count are even, and means for modifying the string of pixels along the raster line from the current point of intersection to the next point of intersection according to the parity of the crossed-edge count.

Claim 13

An apparatus for filling a polygon as represented on a scan-line raster display, comprising, means for storing data representative of the location of a polygon edge, means for computing the points of intersection of a scan-line with each polygon edge, means for combining colinear horizontal edges, means for calculating the number of polygon edges positioned above the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, means for calculating the number of polygon edges positioned below the colinear horizontal edge and which have a vertex coincident with the colinear horizontal edge, means for modifying the crossed-edge count if the parity of the above edge count and the below edge count are even, and means for modifying the string of pixels along the raster line from the current point of intersection to the next point of intersection according to the parity of the crossed-edge count.

Claim 17

A method of filling polygons represented on a scan-line raster display as a plurality of edges having common vertices, said scan-line crossing or intersecting the polygon edges a discernable number of times, said method comprising the steps of: (a) combining, at a point of intersection of the scan-line with a polygon edge, horizontal edges which are colinear with said scan-line and intersecting vertices into a colinear horizontal edge; (b) calculating the number of polygon edges positioned above said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into an above edge count; (c) calculating the number of polygon edges positioned below said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into a below edge count; (d) comparing said above edge count and said below edge count, whereby if both said above edge count and below edge count have even parity, the parity of the crossed-edge count at the current point of intersection is inverted; (e) modifying the string of pixels along scan-line from the current point of intersection to the next point of intersection if the parity of the crossed-edge count for the current point of intersection is odd.

Claim 18

A method of filling polygons represented on a scan-line raster display as a plurality of edges having common vertices, said scan-line crossing or intersecting the polygon edges a discernable number of times, said method comprising the steps of: (a) combining, at a point of intersection of the scan-line with a polygon edge, horizontal edges which are colinear with said scan-line and intersecting vertices into a colinear horizontal edge; (b) calculating the number of polygon edges positioned above said colinear horizontal edge which have a vertex coincident with said colinear horizontal edge into an above edge count; (c) calculating the number of polygon edges positioned below said colinear horizontal edge and which have a vertex coincident with said colinear horizontal edge into a below edge count; (d) comparing said above edge count and said below edge count, whereby if both said above edge count and below edge count have even parity, the parity of the crossed-edge count at the current point of intersection is inverted; (e) modifying the string of pixels along scan-line from the current point of intersection to the next point of intersection if the parity of the crossed-edge count for the current point of intersection is odd.