Method and system for tessellating a polygon
AssigneeMicrosoft Corporation
InventorMichael Kallay
Life of this patent
Estimating the term…
Abstract
A method and system for tessellating a polygon is provided, in which a polygon is divided into bands, each band being bounded by a pair of chains. Each chain is made up of one or more line segments of the polygon. The bands are merged with one another and/or split as needed. Each band is then subdivided into constituent triangles, which may then be sent to a graphics card of a computer. The graphics card then renders the polygon on a monitor by reassembling the constituent triangles.
Claims21
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.
A method of tessellating a polygon, the method comprising:
- scanning the polygon in at least a first pass and a second pass,
- the first pass comprising breaking the polygon into a plurality of chains;
- identifying at least one pair of chains that intersect;
- and splitting the at least one chain of the pair into two chains;
- and
- the second pass comprising organizing the polygon into a plurality of bands, each band being bounded on the left by a chain of the plurality of chains and on the right by another chain of the plurality of chains;
- dividing each of the plurality of bands into triangles;
- splitting at least one of the plurality of bands into multiple bands at a particular height in the polygon;
- and wherein the breaking step comprises inserting references to the chains into a main chain list that is sorted by the heights of the heads of the plurality of chains.
Dependencies are inferred from the claim text.