Polygon Filling

Polygon Filling

Polygon filling (or area filling) determines which pixels inside a polygon boundary should be colored. This is essential for rendering solid shapes in 2D and 3D graphics.

Scan-Line Polygon Fill

The scan-line algorithm processes one horizontal line at a time. For each scan line, it finds intersection points with polygon edges and fills between pairs of intersections.

Scan-Line Algorithm:

  For each scan line y:
      1. Find all intersections with polygon edges
      2. Sort intersections by x-coordinate
      3. Fill pixels between pairs:
         (x1, x2), (x3, x4), ...

  Example:
      Scan line y = 5 intersects at x = 2, 7, 9, 14

      Fill: pixels 2-7, pixels 9-14

      +--+--+##--+--+--+##--+--+##--+--+--+--+--+
      |  |  |##|  |  |  |##|  |  |##|  |  |  |  |
      +--+--+##--+--+--+##--+--+##--+--+--+--+--+
           x2=2       x3=7  x4=9      x5=14

Edge Table

To efficiently find intersections, an edge table stores edges indexed by their minimum y-value. Each edge entry contains: y_max, x_of_y_min, and 1/slope.

Edge Table Entry:
  {
    y_max:    maximum y of edge
    x:        x coordinate at y_min
    inv_slope: 1/m (increment per scan line)
  }

Active Edge Table (AET):
  - Contains edges currently intersecting scan line
  - Updated as scan line moves upward
  - Sorted by x-coordinate for fill processing

Flood Fill

Flood fill replaces a connected region of one color with another color, starting from a seed point. Used in paint programs and region filling.

4-Connected Flood Fill (Recursive):

  flood_fill(x, y, old_color, new_color):
      if pixel(x,y) != old_color: return
      if pixel(x,y) == new_color: return

      set_pixel(x, y, new_color)

      flood_fill(x+1, y, old_color, new_color)
      flood_fill(x-1, y, old_color, new_color)
      flood_fill(x, y+1, old_color, new_color)
      flood_fill(x, y-1, old_color, new_color)

8-Connected adds diagonal directions:
      flood_fill(x+1, y+1, ...)
      flood_fill(x+1, y-1, ...)
      flood_fill(x-1, y+1, ...)
      flood_fill(x-1, y-1, ...)

Seed Fill (Stack-Based)

An iterative approach using a stack to avoid recursion depth limits. More practical for large regions.

Stack-Based Flood Fill:

  push(seed_x, seed_y)
  while stack not empty:
      (x, y) = pop()
      if pixel(x,y) != old_color: continue
      set_pixel(x, y, new_color)
      push(x+1, y), push(x-1, y)
      push(x, y+1), push(x, y-1)