Patent Document ID: 20060066620
Application ID: 10952216
Patent Status: 0

Claim One:
1. A method of rendering one or more polygons comprising: reading an ordered plurality of coordinates of an ordered plurality of vertices that define a polygon; selecting one or more special vertices from the ordered plurality of vertices, based on two alternative criteria, including: a first criteria which specifies that there are two vertices that are immediately adjacent a candidate special vertex in the ordered plurality of vertices for which a first coordinate satisfies an inequality relation with respect to the first coordinate of the candidate special vertex; and a second criteria which specifies that in a case that there is a sequence of two or more vertices that have an equal first coordinate value and there is a first vertex preceding the sequence and a second vertex following the sequence that have first coordinate values that satisfy the inequality relation with respect to the equal first coordinate value of the sequence, one of the sequence is selected as a special vertex; initiating a variable corresponding to the first coordinate to a value that does not satisfy the inequality relation with respect to the first coordinate of any of the ordered plurality of vertices that define the polygon; incrementally changing the value of the variable to move through the polygon; at each particular value of the variable: checking if any special vertices have first coordinate values that correspond to the particular value of the variable; in case one or more special vertices that have first coordinates values corresponding to the particular value of the variable are found, for each particular special vertex that is found, initializing a clockwise-direction branch and a counterclockwise-direction branch extending from the particular special vertex, wherein each branch comprises a sequence of one or more edges, each connecting two vertices of the polygon, and wherein an edge in each branch closest to the particular special vertex of each branch, that is not defined by two vertices having equal first coordinates, is initially set as active within each branch; for each particular previously active branch checking if a previously active edge is still active, by checking if the previously active edge spans a range of the first coordinate that includes a current value of the variable; in case the previously active edge is no longer active checking if the particular previously active branch is still active by checking if a next vertex, proceeding in a direction of the particular previously active branch, for which the first coordinate is not equal to the first coordinate of a last vertex of the previously active edge furthest from a particular special vertex at which the particular previously active branch starts has a first coordinate that satisfies the inequality relation with respect to the last vertex of the previously active edge; in case the particular previously active branch is no longer active, ceasing to process the previously active branch; in case the previously active edge is no longer active, but the particular previously active branch is still active, changing an active edge for the particular previously active branch to a next edge along the particular previously active branch that has a vertex that satisfies the inequality relation with respect to the last vertex of the previously active edge; and computing a second coordinate value for each active edge in each active branch corresponding to the current value of the variable.