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