Patent ID: 6567182
Filing Date: 2003-05-20
Classification: G06T

Abstract:
A computer implemented method for converting a polygon into a set of scan line runs filling the same area comprising the steps of:(1) representing the polygon as a set of edges, each edge represented by minimum Y coordinate, a minimum X coordinate, a maximum Y coordinate and a slope; (2) sorting said set of edges in increasing values of minimum Y coordinate and storing said sorted set of edges as an array of edges; (3) setting a bottom scan line to be said minimum Y coordinate of a first entry in said array of edges; (4) forming an active edge table as an array of active edges, said array of active edges initially identical to said array of edges; (5) initializing an active edge count to zero; (6) counting a number of entries in said active edge table until an edge has a minimum Y coordinate different from the minimum Y coordinate of a first entry in said active edge table, thereby forming an active edge count and a next minimum Y coordinate; (7) sorting said active edge count number of initial edge entries in said active edge table by their respective minimum X coordinate; (8) determining a set of next edges of said edge array which include said next minimum Y; (9) storing said set of next edges in said active edge table; (10) determining X coordinates of said set of next edges employing said corresponding slopes; (11) determining if said set of next edges is sorted in order of X coordinate; (12) if said set of next edges is not sorted in order of X coordinate, then determining Y coordinates of edge intersections, forming scan line runs between pairs of active edges beginning at a scan line having said minimum Y coordinate until a scan line having a Y coordinate of a first of said edge intersections; forming sets of scan line runs between pairs of active edges beginning at respective scan lines having Y coordinates of successive edge intersections until reaching a last edge intersection; forming scan line runs between pairs of active edges beginning at a scan line having Y coordinates of said last edge intersection and until a scan line having Y coordinates of said next minimum Y coordinate; (13) if said set of next edges is sorted in order of X coordinate, then forming scan line runs between pairs of active edges beginning at said minimum Y coordinate and until said next minimum Y coordinate; (14) calculating an X coordinate value for all edge entries in the active edge table pointer employing respective slope values; (15) incrementing said bottom scan line by 1 to refer to a next scan line; (16) removing edges from said active edge table whose maximum Y coordinate equals the Y coordinate value of said incremented bottom scan line; and (17) repeating steps 5 to 16 until all edges in said edge array have been considered.