Notes on Filling Polygons

Copyright April 6, 1996, Dr. William T. Verts

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:

Const Limit = 1000 ; (* Maximum number of points in the polygon *) Type Range = 1..Limit ; (* for use as array index *) Count = 0..Limit ; (* for use as active points counter *) Point = Record X : Real ; Y : Real ; End ; Buffer = Array [Range] Of Point ; Var Table : Buffer ; (* The list of transformed points *) Top : Count ; (* How many points are actually in the list *) As we scan through the list of points (Table), we will generate for each scan line (raster) in viewport space a number of intersections of that scan line with the polygon edges (formed by successive pairs of points from the Table). Those intersections need to be stored in a separate list:

Type XBuffer= Array [Range] Of Real ; Var XTable : XBuffer ; (* The list of X intersections *) XTop : Count ; (* How many intersections are in the list *) Note that the intersections list does not need to be any larger than the list of polygon points, as the way we will structure the algorithm insures that there will be a maximum of one intersection per edge (and in practice there will be considerably fewer intersections).

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).

MinX := Table[1].X ; MinY := Table[1].Y ; MaxX := MinX ; MaxY := MinY ; For I := 2 To Top Do Begin If Table[I].X > MaxX Then MaxX := Table[I].X ; If Table[I].X < MinX Then MinX := Table[I].X ; If Table[I].Y > MaxY Then MaxY := Table[I].Y ; If Table[I].Y < MinY Then MinY := Table[I].Y ; End ; The next thing that needs to be done is to insure that no point in the list falls exactly on a scan line of the viewport. This is to eliminate problems with points being counted twice (once for one segment, once for the segment it connects to), and problems with horizontal lines (is the line inside or outside the polygon?). The points don't need to be modified by much: only a very small fraction needs to be added to each one. But should the fraction be positive or negative? If, say, you are scan converting a rectangle where all four points fall exactly on scan lines, then adding the same amount to all four Y-values will shift the entire rectangle in such a direction as to cause one of the legitimate scan lines to disappear! My solution is to shift points up by the fraction (add) if they occur in the upper half of the polygon, and shift them down by the fraction (subtract) if they appear in the lower half of the polygon. Since we already know the maximum and minimum Y values, this is fairly easy to accomplish:

Const Epsilon = 0.000001 ; ---------- MidY := (MaxY + MinY) / 2.0 ; For I := 1 To Top Do With Table[I] Do If Y = Trunc(Y) Then (* is the fraction zero? *) Begin If Y < MidY Then Y := Y - Epsilon Else Y := Y + Epsilon ; If Y > MaxY Then MaxY := Y ; If Y < MinY Then MinY := Y ; End ; Now, we can perform intersections with any of the segments and rest assured that none of the intersections will occur exactly on an endpoint of a segment. Won't the changes actually change the characteristics of the polygon that we are trying to fill? Technically, yes, but those changes are so minor that we should not notice any unusual pixels occuring (either pixels set that shouldn't be or pixels ignored that should be set). Also, with this algorithm there may be some minor problems with horizontal lines on the interior areas of concave polygons; you should not notice any problems with convex polygons at all.

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:

MinScan := Trunc(MinY) + 1 ; MaxScan := Trunc(MaxY) ; Since we know that MinY and MaxY can no longer be exactly on a scan line, and that the minimum Y value on the screen is zero (not negative), then simply performing Trunc(MinY) will actually get us one extra scan line to check, and that scan line will always be below (outside) the polygon. This is why we add one to its value.

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:

For Yscan := MinScan To MaxScan Do Begin XTop := 0 ; (* Clear the list of intersections *) X1 := Table[Top].X ; Y1 := Table[Top].Y ; For I := 1 To Top Do Begin X2 := Table[I].X ; (* Generate each segment as *) Y2 := Table[I].Y ; (* the pair (X1,Y1) to (X2,Y2) *) If (Yscan < Y1) <> (Yscan < Y2) Then (* Got one! *) Begin (* Compute intersection *) Xvalue := ((Yscan - Y1) / (Y2 - Y1)) * (X2 - X1) + X1 ; (* Add intersection to list *) XTop := XTop + 1 ; XTable[XTop] := Xvalue ; End ; X1 := X2 ; Y1 := Y2 ; End ; Sort (XTable, XTop) ; (* Use your favorite sort here! *) (* Step pairwise through the list of intersections, *) (* painting a horizontal line for each. *) I := 1 ; While (I < Xtop) Do Begin Horizontal_Line (Round(XTable[I]), Round(XTable[I+1]), Yscan) ; I := I + 2 ; End ; End ; A quick note may be in order about the strange line of code that determines if an intersection is present. The expression:

If (Yscan < Y1) <> (Yscan < Y2) Then..... is comparing two Boolean values. If Yscan is below both Y1 and Y2, then both inner comparisons will be true, and the overall comparison will be false (because they don't differ). If Yscan is above both Y1 and Y2, then both inner comparisons will be false, and the overall comparison will be false again. Only if Yscan is between two Y values, then one of the inner comparisons will be true and the other one will be false, and since they are different the overall comparison will be true.

Back to Dr. Bill's CS32 Page

Back to Dr. Bill's Page