Apparatus and methodology for automated filling of complex polygons

A computer method of performing a polygon area fill operation for a polygon described as an enumerated list of vertex coordinates, said method comprising the steps of:

• (a) selecting a reference vertex of said polygon;
• (b) decomposing said polygon into a plurality of triangles, each said triangle including said reference vertex and two other vertices;
• (c) determining the sense of each said triangle from the enumeration order of said reference vertex and said two other vertices about an axis perpendicular to a plane defined by said reference vertex and said two other vertices;
• (d) filling the area bounded by each said triangle with a value having a weighting based on the respective sense of each said triangle;
• and
• (e) combining the values corresponding to respective portions of each of said triangles as may bound a respectively common portion of said triangles.

A processor, responsive to an instruction to fill a polygon definable by data stored within a memory array at corresponding memory locations, said instruction providing an enumerated list of data specifying the respective vertices of said polygon, said processor being associated with said memory array for the selective accessing of memory locations and storage of data with respect thereto, said processor comprising:

• (a) ALU (arithmetic logic unit) means for performing data computations;
• and
• (b) sequencer means, coupled to said ALU means, for controlling said ALU means, said sequencer means providing data to said ALU means and receiving status and data from said ALU, said sequencer means including:
• (i) means for selecting three vertices of said polygon;
• (ii) means for determining a sense value based on the relative order of said three vertices in the enumerated list and the respective data specifying said three vertices, said sense value having a polarity corresponding to the relative direction about an axis perpendicular to a plane defined by said three vertices;
• and
• (iii) means, responsive to said determining means, for filling the area defined by said three vertices with a predetermined data value qualified by said sense value.

A graphics co-processor, responsive to a host processor for the receipt of instructions and related data and coupled to a graphics display memory array for the accessing and storage of pixel data at respective pixel corresponding memory locations, said co-processor comprising:

• (a) a graphics engine including a micro-coded sequencer responsive to a fill polygon instruction and associated polygon defining enumerated list of respectively unique vertices and curvilinear boundary definition factors;
• and
• (b) an arithmetic logic unit, responsive to said sequencer, for receiving data from said graphics engine and said graphics display memory array, for performing computations on the data provided thereto, said arithmetic logic unit providing resultant data to said graphics engine and said graphics display memory array and computation status information to said graphics engine, said sequencer implementing procedures, including procedures utilizing said arithmetic logic unit, for:
• (i) selecting a reference vertex of said polygon;
• (ii) selecting a set of three vertices of said polygon including said reference vertex and two vertices adjacently enumerated in said enumerated list of vertices;
• (iii) first determining a +1 or -1 closed circuit sense value for said set of three vertices based on the relative direction of rotation defined by the enumeration order of said set of three vertices in a plane defined by said set of three vertices;
• (iv) second determining whether a sense value qualified fill data value should be added to the pixel data stored at each pixel corresponding memory location shared at a boundary of any two areas as defined by respective said sets of three vertices and their associated curvilinear boundary definition factors where said sets of three vertices share a uniquely enumerated vertex other than said reference vertex;
• and
• (v) adding a sense value qualified fill data value to the pixel data stored at each pixel corresponding memory location within said graphics memory array and within and at the boarders of an area defined by said set of three vertices and their associated curvilinear boundary definition factors.