Apparatus and method for filling complex polygons

Claim 2

Computer graphics apparatus for filling a complex polygon, as defined by an enumeration of P vertices, with a fill quantity, said apparatus comprising: a) means for selecting a first vertex from said enumeration of P vertices and for decomposing said complex polygon into an set of P-2 triangles, each said triangle representable as a respective enumeration of T vertices including said first vertex and two successive vertices in said enumeration of P vertices; b) means, responsive to each said respective enumeration of T vertices, for deriving a sense value for each said triangle; and c) means, responsive to said deriving means, for successively filling the area bounded by each said triangle with a sense value qualified fill quantity.

Claim 3

The apparatus of Claim 1 wherein said deriving means derives each said sense value based on the respective vertices enumeration order and vertices values in each said enumeration of T vertices.

Claim 4

The apparatus of Claim 2 wherein said filling means includes means for summing respective sense value qualified fill quantities in areas mutually bounded by overlapping portions of said triangles.

Claim 5

The apparatus of Claim 3 wherein said filling means incrementally fills each said triangle, said filling means including first and second means for determining incremental boundary positions of each said triangle, said filling means being responsive to said first and second determining means for beginning and ending an incremental filling of a corresponding one of said triangles.

Claim 6

The apparatus of Claim 4 wherein each said triangle is incrementally filled by said filling means in respective succession.

Claim 7

The apparatus of Claim 5 wherein said sense value deriving means determines a sense value of plus or minus for each of said triangles, said summing means supports addition and negative fill quantity results and wherein said filling means supports filling said triangles with a negative sense value fill quantity.

Claim 8

The apparatus of Claim 6 wherein said filling means fills each said triangle in order corresponding to the successive enumeration of said enumeration of P vertices.

Claim 9

The apparatus of Claim 7 wherein said filling means selectively fills the shared boundary of any two said triangles, adjacent as sharing a uniquely enumerated vertex and said first vertex thereinbetween, the shared boundary being filled with the filling of the two adjacent said triangles depending on the respective sense values of the two adjacent said triangles.

Claim 10

The apparatus of Claim 8 wherein said filling means selectively does not twice fill the shared boundary between two adjacent said triangles with the respective filling of the two adjacent said triangles whenever the respective sense values of the two adjacent said triangles are the same.

Claim 11

The apparatus of Claim 9 further comprising: a) computation means for performing arithmetic and logical operations; and a) sequencer means for performing control functions including the control of said computation means to implement said selecting means, said deriving means and said filling means.

Claim 12

The apparatus of Claim 10 wherein said enumeration of P vertices includes a curvilinear factor for a pairs of said vertices, such that said triangles includes at least one said triangle having a curvilinear boundary, and wherein said first and second incremental boundary determining means of said filling means are resppctively responsive to curvilinear factors associated with respective pairs of said vertices.

Claim 13

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; 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.

Claim 14

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; 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.

Claim 15

The method of Claim 12 wherein said step of decomposing includes the step of selecting two vertices that are adjacent one another in said enumerated list as the two other vertices of each respective said triangle.

Claim 16

The method of Claim 13 further comprising the step of assigning the resulting combined value to the respective common portions of each said triangle.

Claim 17

The method of Claim 14 wherein said step of determining the sense of each said triangle includes the steps of: a) determining the relative order of the vertices of each said triangle with respect to their order in said enumerated list; and b) assigning the sense of each said triangle based on the corresponding vertices relative order.

Claim 18

The method of Claim 15 wherein said step of combining provides for the summing of the respective values to be combined.

Claim 19

The method of Claim 16 wherein said step of assigning the sense of each said triangle provides for the assignment of a respective one of two complementary sense values to each said triangle.

Claim 20

The method of Claim 17 wherein said step of filling includes the step of filling a boundary portion of each said triangle where each said boundary portion is shared by respectively adjacent said triangles that share a uniquely enumerated vertex and said reference vertex, each said boundary portion of adjacent said triangles having the same sense being filled only once with the filling of the respective adjacent said triangles.

Claim 21

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 means for performing data computations; and b) sequencer means, coupled to said ALU means, for controlling said ALU means and for providing data to said ALU means and receiving status and data from said ALU, said sequencer means in combination with said ALU means implementing: i) means for selecting three vertices of said polygon; ii) means for determining a sense value based on the respective data specifying said three vertices; and iii) means, responsive to said determining means, for effectively filling the area defined by said three vertices with a predetermined data value.

Claim 22

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 means for performing data computations; and b) sequencer means, coupled to said ALU means, for controlling said ALU means and for providing data to said ALU means and receiving status and data from said ALU, said sequencer means in combination with said ALU means implementing: i) means for selecting three vertices of said polygon; ii) means for determining a sense value based on the respective data specifying said three vertices; and iii) means, responsive to said determining means, for effectively filling the area defined by said three vertices with a predetermined data value.

Claim 23

The processor of Claim 19 wherein said selecting means initially selects a reference vertex from said enumerated list and wherein said three vertices selected include said reference vertex and two other vertices successively enumerated in said enumerated list.

Claim 24

The processor of Claim 20 wherein said determining means further determines said sense value based on the order of at least two of said three vertices as enumerated in said enumerated list.

Claim 25

The processor of Claim 21 wherein said filling means includes means for accessing the memory locations corresponding to the area defined by said three vertices, for adding said predetermined data value, qualified by said sense value, to the data stored at each memory location accessed and for storing the resultant data back to its respective memory location.

Claim 26

The processor of Claim 22 wherein said adding means of said filling means includes means for determining whether an accessed memory location is shared at a boundary between areas defined by respective sets of said three vertices and whether the respective sets of said three vertices have identical respective said sense values, said adding means adding said predetermined data value, qualified by said sense, to the data stored at each such shared memory location in the filling of the areas defined by both sets of said three vertices.

Claim 27

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 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, for 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 closed circuit sense value for 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.

Claim 28

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 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, for 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 closed circuit sense value for 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.

Claim 29

The co-processor of Claim 24 wherein said second determining procedure implemented by said sequencer determines to add said sense value qualified fill data value at each boundary pixel corresponding memory location only for one of said sets of three vertices and their associated curvilinear boundary definition factors if both are determined to have the same sense value.

Claim 30

The co-processor of Claim 25 wherein said procedures implemented by said sequencer includes a procedure implementing a curvilinear boundary definition factor sensitive interpolation selection of pixel corresponding memory locations corresponding to beginning and ending point curvilinear lines between paired vertices of said set of three vertices and their associated curvilinear boundary definition factors and an associated procedure implementing the sequential accessing of pixel corresponding memory locations located linearly between corresponding beginning and ending point curvilinear line pixels.