CS-460/560, Week 5-B,C
Spring, 1998
R. Eckert

AREA FILL ALGORITHMS

2 Classes:

Boundary/Flood Fill Algorithms and Scanline Algorithms.

Boundary/Flood Fill--
   Determine which points are inside the area by using pixel
   color information (interior color, boundary color, current
   pixel color). Color the ones that are inside.

Scanline--
   Look at horizontal scan lines spanning the area; i.e., scan
   the area, look for intersection points between current
   scanline and borders, and color pixels along the scanline
   between alternate pairs of intersection points. Especially
   useful for filling polygons since intersection point
   calculations are very simple. In practice vertical and horizontal
   coherence are used to get new intersection points from old
   intersection points rapidly.


1. CONNECTED AREA BOUNDARY FILL ALGORITHM (FOR ARBITRARY CLOSED AREAS)--

INPUT--Boundary Color (BC), Fill Color (FC), and the (x,y) coordinates
of a seed point known to be inside the fill area.

Define a recursive BndryFill(x,y,BC,FC) function. If the pixel at
(x,y) is not set to the boundary color or to the fill color, then set
the pixel at (x,y) to the fill color and call BndryFill() for
neighboring points.

To be able to implement this, we need an enquire function; e.g.
GetPixel(x,y) which should return the color of the pixel at (x,y).

THE ALGORITHM--

BndryFill(x,y,BC,FC)
{
   color = GetPixel(x,y)
   if ( (color != BC) && (color != FC))
   {
      SetPixel(x,y,FC);
      BndryFill(x+1,y,BC,FC);
      BndryFill(x,y+1,BC,FC);
      BndryFill(x-1,y,BC,FC);
      BndryFill(x,y-1,BC,FC);
   }
}

This would be called by code like:

BndryFill(50,100,5,8);  //last 2 parameters are colors

(Under the Windows GDI, the colors referred to in the algorithm would be
COLORREFs--and the RGB() macro could be used.)

A variation of this is the "FloodFill" algorithm, in which the fill
area is identified by the color of the interior instead of that of
the boundary.

These kinds of algorithms use enormous amounts of stack space.
Also they are slow since:
   There is extensive pushing/popping of stack
   Pixels may be visited more than once
   GetPixel() and SetPixel() must be called for each pixel ==>
      2 accesses to the frame buffer for each pixel plotted

Big advantage--can be used for arbitrary areas.


SCANLINE POLYGON FILL ALGORITHM--

Basic Idea--Look at individual scan lines; determine intersection points
with polygon edges; fill between alternate pairs.

More specifically--

   For each scanline spanning the polygon
      Find intersection points with all edges the scanline intersects
      Sort intersection points by increasing x
      Turn on all pixels between alternate pairs of intersection points

For this to work, a preprocessing step must be performed on intersection
points that coincide with polygon vertices that are not local maxima or
local minima.

We use the concept of an "active edge"--any polygon edge that is
intersected by the current scanline. As the polygon is scanned, polygon
edges will become active and inactive.

  Criterion for activating an edge: ysl = ymin of the edge

  Criterion for deactivating an edge: ysl = ymax of the edge

    (Here ysl = y value of the current scanline)


As we move from one scanline to the next, use  vertical coherence:

            y = y + 1

And, if an edge remains active, we can get the x value of the new
intersection point of the scanline with the edge by using horizontal
coherence:
            x = x + 1/m

Here 1/m is the inverse slope of the edge.


ALGORITHM INPUT--List of polygon vertices (xi,yi)


ALGORITHM DATA STRUCTURES--

1. Edge table: (for each edge-- edge number, ymin, ymax, x, 1/m).

2. Activation Table: (y, edge number activated at y). This table tells 
us which edge(s) become active for each new scanline. This table is
constructed by doing a "bin" or "bucket" sort.

3. Active Edge List: (active edge numbers sorted according to x). This
is a dynamic data structure in the sense that the contents of the active
edge list will change as we scan up the polygon.


THE ALGORITHM--

1. Set up the edge table from the vertex list; determine the range of
scanlines spanning the polygon (miny, maxy).

2. Preprocess any edges in the edge table whose endpoints are not local
maxima/minima.

3. Set up the activation table (bin sort)

4. For each scanline spanned by the polygon (y = miny to maxy)

     (a) add any new active edges to the active edge list using
         the activation table;

     (b) sort the active edge list on x;

     (c) fill between alternate pairs of points (x,y) in order of sorted
         active edges;

     (d) for each edge e in active edge list
          if (y != ymax[e])
              calculate & store the new x (x = x + 1/m);
          else
              delete edge e from the active edge list;


Adapting the Scanline Polygon Fill Algorithm for other primitives, e.g.
an ellipse--

   Use a midpoint algorithm to obtain intersection points with the next
   scanline.


Scanline Fill algorithms can be fast if sorting is done efficiently.


SCANLINE BOUNDARY FILL ALGORITHM--

   Combines Boundary Fill and Scanline Techniques.
   Uses much less stack space than Boundary Fill.

THE ALGORITHM--

   Select a Seed Point (x,y)
   Push (x,y) onto Stack
   While Stack is not empty
      Pop Stack (retrieve x,y)
      Fill current run y (iterate on x until boundaries are hit)
      Push left-most unfilled, unstacked pixel above-->new "above" seed
      Push left-most unfilled, unstacked pixel below-->new "below" seed