Algorithm to transform generalized polygons to trapezoids

Abstract

General polygons are broken into trapezoids and/or triangles and exported to a graphics adapter for rendering. Intersecting line segments are broken at the point of inter-section. Simple polygons are then derived from the general polygon by starting at an outside corner and selecting line segments defining the general polygon utilizing criteria which will identify closed paths bounding a single area (e.g., always selecting the line segment which extends in a direction identical to or clockwise from the direction of the last selected line segment). Selected line segments are added to a current polygon definition. Each time an inter-section point is entered twice, the selected line segments from the first exit to the second entry of that intersection point are segregated into a separate polygon definition in the polygon list. Once all simple polygons have been identified, each polygon is broken into trapezoids and/or triangles. A base connection point or line segment having the lowest y-coordinate value is identified, together with adjoining line segments. A trapezoid or triangle is then delimited including at least one adjoining line segment, and the process in repeated until all line segments bounding the simple polygon have been added to at least one primitive definition in a primitive list. The primitives may then be exported to the graphics adapter for rendering. Although processor cycles are required to break the general polygon into primitives, in most cases the work required should be significantly less than that involves in breaking the general polygon into scan lines and generating pixel information for the graphics adapter.