Area Filling Algorithms: Scanline, Flood, Z-Buffer & Painter’s

Core Concepts

1. What is Area Filling?

Area filling is the process of determining which pixels inside a polygon (or region) should be colored based on a given seed point or boundary. It is fundamental in:

• Raster graphics (e.g., filling shapes in Photoshop, game sprites).
• Hidden surface removal (e.g., rendering 3D scenes where only visible surfaces are filled).
• UI design (e.g., filling buttons, icons, or charts).

Key Idea:

"Filling an area is not just about coloring pixels—it’s about deciding which pixels belong to the shape and how to traverse them efficiently."

2. Classification of Area Filling Algorithms

Area filling algorithms are broadly categorized into two types:

1. Boundary-Based Filling (e.g., Boundary Fill, Flood Fill)
   • Starts from a seed point and fills based on boundary conditions.
2. Scanline-Based Filling (e.g., Scanline Polygon Filling)
   • Processes the polygon row-by-row (scanline) and fills pixels between edges.

3. Boundary Fill Algorithm

How It Works

1. Seed Point: Start from a given pixel inside the region.
2. Boundary Check: Compare the color of neighboring pixels with the boundary color.
3. Fill Condition: If a pixel’s color matches the fill color and its neighbors are not the boundary color, fill it and repeat recursively/iteratively.

Types of Boundary Fill

Worked Example: 4-Connected Boundary Fill

Scenario: Fill a rectangle with vertices (10,10), (30,10), (30,20), (10,20) using seed (15,15). Boundary Color: Black (#000000), Fill Color: Red (#FF0000).

graph TD
    A["Seed (15,15)"] --> B["Check 4 neighbors"]
    B --> C["Left (14,15): Boundary? No → Fill Red"]
    B --> D["Right (16,15): Boundary? No → Fill Red"]
    B --> E["Up (15,14): Boundary? No → Fill Red"]
    B --> F["Down (15,16): Boundary? No → Fill Red"]
    C --> G["Recurse on (14,15)"]
    D --> H["Recurse on (16,15)"]
    E --> I["Recurse on (15,14)"]
    F --> J["Recurse on (15,16)"]

Output:

Boundary (Black):
+---------------------+
|                     |
|                     |
|                     |
+---------------------+
Filled (Red):
+---------------------+
| RRRRRRRRRRRRRRRRRRR |
| RRRRRRRRRRRRRRRRRRR |
| RRRRRRRRRRRRRRRRRRR |
+---------------------+

Pseudocode:

def boundary_fill(x, y, boundary_color, fill_color):
    if (x,y) is outside canvas: return
    if pixel(x,y) == boundary_color: return
    if pixel(x,y) == fill_color: return
    pixel(x,y) = fill_color
    boundary_fill(x+1, y, boundary_color, fill_color)  # Right
    boundary_fill(x-1, y, boundary_color, fill_color)  # Left
    boundary_fill(x, y+1, boundary_color, fill_color)  # Down
    boundary_fill(x, y-1, boundary_color, fill_color)  # Up

4. Flood Fill Algorithm

Key Differences from Boundary Fill

Worked Example: Flood Fill (8-Connected)

Scenario: Fill all connected blue pixels (#0000FF) with red (#FF0000) starting from (5,5) in an image. Grid: (Image: 些細な日常, CC BY-SA 4.0, via Wikimedia Commons)

Row 1: B B B W W W
Row 2: B W W W W W
Row 3: B B B B W W
Row 4: W W W W W W

• B = Blue (#0000FF), W = White (#FFFFFF), R = Red (#FF0000).
• Seed: (5,5) is white → no fill.
• Seed: (1,1) is blue → fill all connected blues.

Output:

Row 1: R R R W W W
Row 2: R W W W W W
Row 3: R R R R W W
Row 4: W W W W W W

Optimization: Use a queue (BFS) or stack (DFS) to avoid recursion limits.

from collections import deque

def flood_fill(image, x, y, old_color, new_color):
    rows, cols = len(image), len(image[0])
    queue = deque([(x, y)])
    while queue:
        i, j = queue.popleft()
        if image[i][j] != old_color: continue

        for di, dj in [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < rows and 0 <= nj < cols and image[ni][nj] == old_color:
                queue.append((ni, nj))

5. Scanline Polygon Filling Algorithm

How It Works

1. Sort Edges: Find all edges of the polygon and sort them by their y-coordinate.
2. Active Edge Table: Track edges that intersect the current scanline.
3. Fill Pixels: For each scanline, compute the intersection points with edges and fill pixels between them.

Steps

1. Find Intersections: For each scanline y, find where it intersects the polygon edges.
2. Sort Intersections: Pair the leftmost and rightmost intersections.
3. Fill Pixels: Fill all pixels between the left and right intersections.

Worked Example: Scanline Filling for a Triangle

Vertices: (10,10), (30,10), (20,30). Scanlines: y = 10 to y = 30.

Output:

y=10: 10---------------------30
y=20: 15---------------------25
y=30:   20

Pseudocode:

def scanline_fill(polygon, color):
    edges = compute_edges(polygon)
    edges.sort(key=lambda e: e.y1)
    active_edges = []
    for y in range(min_y, max_y):
        update_active_edges(edges, y, active_edges)
        intersections = [edge.x_at_y(y) for edge in active_edges]
        intersections.sort()
        for x in range(intersections[0], intersections[1]):
            plot_pixel(x, y, color)

6. Visible Surface Detection: Z-Buffer vs. Painter’s Algorithm

Comparison Table

When Do They Differ?

Scenario: A spiral staircase where polygons intersect.

• Z-Buffer: Correctly renders overlapping surfaces by depth.
• Painter’s: Fails because it cannot determine which surface is "behind" another at intersections.

Visual Comparison:

Worked Example: Z-Buffer for Two Overlapping Triangles Triangles:

1. Triangle 1: (0,0,1), (2,0,0.5), (1,2,0.8) (closer to camera).
2. Triangle 2: (1,1,0.6), (3,1,0.4), (2,3,0.7) (farther).

Z-Buffer Steps:

1. Initialize z_buffer with ∞ and frame_buffer with background color.
2. For each pixel, compute depth (z) of both triangles.
3. Keep the pixel with the smallest z (closest to camera).

Output:

Pixel (1,1):
- Triangle 1: z = 0.8
- Triangle 2: z = 0.6 → **Triangle 2 wins**

In the Real World

1. eSewa App (Nepal)

• Idea Used: Boundary Fill + Scanline Filling
• How: When you select a digital signature area in eSewa’s mobile app, the app uses flood fill (8-connected) to detect the region you draw. For complex shapes (e.g., a signature), it may use scanline filling to ensure smooth rendering.

2. Pathao Driver UI

• Idea Used: Z-Buffer for 3D Maps
• How: Pathao’s 3D building and road rendering uses the Z-buffer algorithm to ensure that closer buildings appear in front of farther ones. Without Z-buffer, buildings would overlap incorrectly (like in Painter’s algorithm).

3. Kathmandu Traffic Simulation (NTC)

• Idea Used: Scanline + Painter’s Algorithm
• How: NTC’s traffic light simulation tools use scanline filling to render road segments and Painter’s algorithm to prioritize vehicles (e.g., ambulances over cars). However, for complex intersections, Z-buffer is preferred to avoid rendering errors.

Exam Tip

What Examiners Look For

1. Definitions: Clearly define terms like seed point, active edge table, and depth buffer.
2. Step-by-Step Traces: For algorithms like scanline filling, show:
   • Edge sorting.
   • Intersection calculations.
   • Pixel filling logic.
3. Comparisons: Always compare Z-buffer vs. Painter’s in terms of:
   • Correctness (intersections).
   • Performance (memory vs. speed).
4. Real-World Links: Relate algorithms to games (Z-buffer), UI design (flood fill), or CAD (scanline).
5. Pseudocode: Write clean, commented pseudocode for boundary/flood/scanline fill.

Common Mistakes to Avoid

• Assuming Painter’s works for all cases: Always mention its limitation with intersecting polygons.
• Forgetting edge cases: E.g., vertical edges in scanline filling.
• Incorrect boundary checks: In flood fill, ensure you check all 8 neighbors for 8-connected.

High-Score Answer Structure

Use this template for exam questions:

1. Title: Clearly state the algorithm (e.g., "Scanline Polygon Filling Algorithm").
2. Definition: 1-2 sentences.
3. Steps: Numbered list with diagrams (e.g., active edge table updates).
4. Worked Example: Use small numbers (e.g., triangle with vertices (10,10), (20,20), (30,10)).
5. Comparison: If comparing algorithms, use a table (like Z-buffer vs. Painter’s).
6. Real-World Tie: Mention one application (e.g., "Used in Pathao’s 3D maps").