Polygon Scan Conversion: Explanation

The polygon scan conversion algorithm is used for drawing a filled-in (solid) polygon. The algorithm can be used for both, convex polygons, as well as concave polygons. The algorithm also handles self-intersecting polygons, as well polygons with holes in them.

The algorithm works by scanning each row from left to right, and determining which points on the scan line lie within the polygon. This process is repeated for each line, and thus the whole polygon is scan converted.

The algorithm can be distinguished into three functional phases:

Part I: Find the intersection of all edges with a scan line. Repeat for all scan lines.
Part II: Sort the intersections found at each edge according to increasing x coordinates.
Part III: Fill in all pixels that lie between pairs of intersection points, using the odd parity rule.

Although this algorithm is relatively simple to describe, its implementation is somewhat complicated. In particular, we want an efficient method for computing the edge intersections on each scan line. Also, certain vertices/edges need to be treated differently. All these details will be examined later in this document.

Edge-Scanline Intersection

This part involves the computation of all the intersections of edges with the scanlines. The simplest method of doing this would be to

Take an edge.
Substitute the current y value into the equation of the line segment representing the edge.
Solve for x.
Repeat steps 1-3 for each edge that intersects the scanline.
Repeat steps 1-4 for each scanline.

From Graphica -- see details 26.11.1996