Chapter 7: Filling Algorithms

Once we have defined the outlines of our geometric shapes, we must decide how to color the interior pixels. This process is called "filling." In this chapter, we delve deeper into three key algorithms: Boundary Fill, Flood Fill, and the Scanline Fill algorithm.

Boundary Fill Algorithm

The Boundary Fill algorithm starts at an internal point (a "seed") and expands outward until it hits a specified boundary color.

1. Seed Point: An internal $(x, y)$ coordinate.
2. Boundary Color: The color of the outline we are filling.
3. Fill Color: The color we want to apply to the interior.

Algorithm (Recursive)

1. Check if the current pixel $(x, y)$ is either the boundary color or already filled with the fill color.
2. If not:
   • Set the pixel $(x, y)$ to the fill color.
   • Recursively call the algorithm for neighbors: $(x+1, y), (x-1, y), (x, y+1), (x, y-1)$.

• Connectivity: We can use 4-way (up, down, left, right) or 8-way (including diagonals) connectivity.
• Drawback: Recursive calls can lead to stack overflow on large shapes.

Flood Fill Algorithm

Flood Fill is similar to Boundary Fill but works based on an existing color rather than a boundary. It replaces all connected pixels of a specific "old color" with a "new color."

Algorithm (Recursive)

1. Check if the current pixel $(x, y)$ is the old color.
2. If it is:
   • Set the pixel $(x, y)$ to the new color.
   • Recursively call the algorithm for neighbors.

Flood Fill is the logic behind the "Paint Bucket" tool in graphics software.

Scanline Fill Algorithm: In-Depth

As introduced in Chapter 6, the Scanline algorithm is the most robust and commonly used method for filling polygons.

The Active Edge Table (AET)

To implement the Scanline algorithm efficiently, we use two tables:

1. Global Edge Table (GET): Contains all the edges of the polygon, sorted by their minimum $y$ value ($y_{min}$).
2. Active Edge Table (AET): Contains all the edges that currently intersect the current scanline.

Step-by-Step Scanline Process

1. Initialize: Sort all edges into the GET based on $y_{min}$.
2. Set Current Scanline ($y$): Start with the smallest $y_{min}$ from the GET.
3. Update AET: Move any edges from the GET whose $y_{min} = y$ into the AET.
4. Remove from AET: Remove any edges from the AET whose $y_{max} = y$.
5. Sort AET: Sort the edges in the AET by their current $x$ intersection coordinate.
6. Fill Pixels: Iterate through the AET in pairs. Fill all pixels between the $x$ coordinate of the first edge and the $x$ coordinate of the second edge.
7. Update X-Intersections: For each edge in the AET, update its $x$ coordinate for the next scanline: $x_{next} = x_{current} + 1/m$ (where $m$ is the slope of the edge).
8. Repeat: Increment $y$ and repeat from step 3 until both GET and AET are empty.

Why GET/AET?

This approach avoids redundant calculations. We only consider edges that are relevant to the current scanline, and we update their intersections incrementally.

Summary

Boundary Fill and Flood Fill are simple, seed-based methods ideal for interactive tools. The Scanline Fill algorithm, with its GET and AET structures, is a more sophisticated and efficient method used in high-performance rendering systems to rasterize and fill complex polygons reliably.