Patent ID: 7002574
Filing Date: 2006-02-21
Classification: G06T

Abstract:
1. A method for tessellating a polygon, the polygon comprising a plurality of vertices, the method comprising: dividing the polygon into a plurality of chains, wherein each chain comprises a segment or set of contiguous segments of the polygon; breaking the polygon into a plurality of bands, wherein each band of the plurality is bounded by two or more of the plurality of chains; merging at least two of the plurality of bands at a point in the polygon where they coincide; dividing each of the plurality of bands into triangles; maintaining a first list containing references to those chains of the plurality of chains that have edges at the current height at which the polygon is currently being processed; and maintaining a second list containing references to those chains of the plurality of chains that are active, the second list being sorted by the heights of the vertices that are contiguous to the active chains.