Method for ascertaining and filling of bounded areas of a colored raster display
First Claim
1. A method for use in a bit-mapped presentation/display system for ascertaining the boundary of an arbitrarily-shaped, closed polygon filled with a first color-coded q×
- r pel subarray, where q and r>
1, and embedded in a raster color-coded domain of pels and for filling said ascertained polygon with a second color-coded q×
r pel subarray, where q and r>
1, comprising the steps of;
(a) identifying the first color-coded pel subarray;
(b) determining all unique raster runs of said identified first pel subarray and creating a counterpart data representation thereof by;
(1) ascertaining connected regions within the domain exhibiting said first pel subarray and forming a location list thereof by traversing the domain from an arbitrary point therein, said traverse being selected from a set consisting of a depth-first search and a nonrecursive traverse as if each unique run were a labeled node of a connected graph; and
(2) at the point in the traverse where it is ascertained that a domain region is not connected, resolving the boundary by comparing the pels of the first subarray in high resolution of at least one pel at a time with pels in the domain local to the connected and unconnected regions and amending the location list accordingly, the number of pels at a time in said high resolution comparison being less than that used for any coarse resolution; and
(c) filling in at least a portion of the raster color-coded domain with the second subarray according to the data representation.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for use in a bit-mapped presentation display system for ascertaining the boundary of an arbitrarily-shaped closed polygon filled with a first color-coded pel pattern and then filling the ascertained polygon with a second color-coded pel pattern. The method steps comprise identifying the first color-coded pattern; determining all unique raster runs of said identified first pattern, and creating a counterpart data representation thereof; and filling in at least a portion of the raster color-coded domain with the second pattern as controlled by the data representation.
30 Citations
3 Claims
-
1. A method for use in a bit-mapped presentation/display system for ascertaining the boundary of an arbitrarily-shaped, closed polygon filled with a first color-coded q×
- r pel subarray, where q and r>
1, and embedded in a raster color-coded domain of pels and for filling said ascertained polygon with a second color-coded q×
r pel subarray, where q and r>
1, comprising the steps of;(a) identifying the first color-coded pel subarray; (b) determining all unique raster runs of said identified first pel subarray and creating a counterpart data representation thereof by; (1) ascertaining connected regions within the domain exhibiting said first pel subarray and forming a location list thereof by traversing the domain from an arbitrary point therein, said traverse being selected from a set consisting of a depth-first search and a nonrecursive traverse as if each unique run were a labeled node of a connected graph; and (2) at the point in the traverse where it is ascertained that a domain region is not connected, resolving the boundary by comparing the pels of the first subarray in high resolution of at least one pel at a time with pels in the domain local to the connected and unconnected regions and amending the location list accordingly, the number of pels at a time in said high resolution comparison being less than that used for any coarse resolution; and (c) filling in at least a portion of the raster color-coded domain with the second subarray according to the data representation.
- r pel subarray, where q and r>
-
2. In a system comprising a raster display, an input device, a buffer for periodically refreshing the display, and a processor coupling said display device and buffer;
- the processor being responsive to the input device for altering the buffer contents;
the buffer containing a raster color-coded n×
m pel domain embedded with at least one closed polygon formed from contiguous raster runs, each run being selected from one of q rows of a first color-coded q×
r pel subarray;
each run being a rational number multiple of r pels in length, q and r>
1;a method for ascertaining the polygon shape and for filling the ascertained shape with contiguous raster runs selected from q rows of a second color-coded q×
r pel subarray;
comprising the steps of;(a) identifying the first subarray; (b) ascertaining contiguous raster runs in the domain by matching selected ones of the q rows in said first q×
r pel subarray in either a recursively descending or nonrecursive manner by comparing domain color-coded pels in a raster scan line direction with q pels of a given row in the first subarray and continuing the comparison of q pels at a time if equal, and upon mismatch, continuing the comparison on a one-pel-at-a-time basis to determine the extent of the match, a pel mismatch being indicative of the end of a run, and forming a list identifying each run by domain location and length; and(c) filling in at least a portion of the domain with contiguous raster runs formed from a rational number of multiples of r pels of a predetermined one of q rows of the second q×
r pel subarray, the replication and positioning of the runs constituting the fill in the domain being made according to the list location and length. - View Dependent Claims (3)
- the processor being responsive to the input device for altering the buffer contents;
Specification