Filling polygons is one of the most critical aspects of your project, since it is involved in filling circles, ellipses, rectangles, wide lines, and user specified polygons, but it also may be one of the hardest routines to get working correctly. Here are some tips and pointers for getting polygon fill to work. I've written this document using the most "general" form of Pascal that I could, in order that you may adapt it with ease to the programming language, development environment, and style of your choice.

Firstly, I will make the broad assumption that all of the points in the polygon have already been passed through the transformation matrix, and are now in the viewport coordinate system (not the world coordinate system), but are still real numbers (they have not yet been converted to integers). Also, I assume that the last point in the list is the same as the first point in the list (the polygon has been closed), and that there are at least two unique points in the polygon. A sample structure to hold these transformed points might be as follows:

Now, the first thing that needs to be done is to find the extent of the box that surrounds all points in the polygon. This is to minimize the size of the affected region of the viewport. (Note that I will not show the declarations of simple variables if their meanings can be obtained from the context of the code fragment. For example, it is pretty obvious that I is of type Count (or at least an Integer), and that MinX, MinY, MaxX, and MaxY are of type Real).

The next thing is to identify the actual scan line extents: what are the minimum and maximum raster lines in the viewport that may be affected by the polygon fill? These are as follows:

Now we have to generate each scan line, and for each line generate the list of X intersections. Because of the way that we have modified the point values, we can be assured that the list of X intersections will always have an even number of entries: each pair describing the left hand and right hand values of a horizontal line to paint. Unfortunately, the order in which polygon segments are traversed means that as we add intersections to the list, we cannot be guaranteed that the list will be in strictly increasing order of X value. Thus, once all the intersections are known, the list of intersections must be sorted. In my solution I used a QuickSort, but you may use any sorting algorithm that you wish (even the hoary old Bubble-Sort works pretty well in this problem, as the number of points to sort is usually 2 exactly!). The major portion of the algorithm is thus:

Back to Dr. Bill's CS32 Page

Back to Dr. Bill's Page