Patent ID: 7423643

Claim:
A computer-implemented method for tessellating a polygon, the polygon comprising a plurality of vertices, the method comprising: dividing the polygon into chains, wherein each chain comprises a segment or set of contiguous segments of the polygon; breaking the polygon into bands, wherein each band is bounded by two or more of the chains; merging at least two of bands at a point in the polygon where they coincide; determining a ceiling associated with each band; wherein the ceiling includes a sequence of points that connects the two or more of the chains; dividing into triangles a portion of each of the bands that is beneath the ceiling associated with the band; adjusting the ceiling in response to the dividing into triangles when additional portions of the band remain to be divided into triangles; determining the heights of the vertices of the chains; determining those chains of the plurality of chains that have edges at the current height at which the polygon is currently being processed; and rendering the triangles to a display.