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:
<![CDATA[
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:
<![CDATA[
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).
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
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