What Is Scanline Polygon Fill Algorithm?

What is the Scanline Polygon Fill Algorithm?

What is scan line polygon fill algorithm? In short, it is a rasterization technique used to fill polygons by scanning across each horizontal line. For every scan line, the algorithm computes the intersection points between the line and the polygon edges, then fills the horizontal spans that lie between paired intersections. This approach is foundational in rendering pipelines because it avoids pixel-by-pixel flood filling and provides deterministic, gap-free fills. A typical implementation leverages two data structures: an edge table that groups edges by their minimum y coordinate and an active edge table that tracks edges crossing the current scan line. Together, these structures enable efficient incremental updates as you move from one scan line to the next, reducing the amount of recomputation required. The key idea is to convert a polygon’s boundary into a dense set of horizontal runs that can be painted quickly on a raster display.

Core concepts and data structures

At the heart of the algorithm are two well known data structures: the Edge Table (ET) and the Active Edge Table (AET). The ET stores each non horizontal edge with its y minimum, y maximum, and the initial x coordinate where the edge intersects the first scan line. As the scan advances upward, edges ‘enter’ the AET when the current y reaches their y minimum, and they ‘exit’ once the current y equals their y maximum. The AET is kept sorted by the current x intersection; this order determines which spans to fill on each scan line. During each iteration, you match pairs of intersections to form filled spans, then advance the x values by the edge slope to prepare for the next line. This incremental approach minimizes arithmetic and makes the algorithm particularly suitable for hardware acceleration and real time rendering.

Handling horizontal edges and degeneracies

Horizontal edges are typically ignored in the ET because they do not contribute intersections with scan lines in the same way as sloped edges. Special care is needed for vertices where two edges meet, to avoid double filling at shared vertices. A common strategy is to apply a top-left rule or a parity rule that ensures each scan line produces a consistent fill region without gaps or overlaps. In practice this means treating the upper endpoint of an edge as inclusive and the lower endpoint as exclusive, or adopting a small half-open interval convention. When implemented carefully, this avoids artifacts at polygon corners and keeps the fill visually clean across different polygons and edge configurations.

Step by step: from edges to spans

1. Build an Edge Table that catalogs all polygon edges by their y minima. 2) Initialize the Active Edge Table with edges starting at the lowest scan line. 3) For each scan line, remove finished edges, add new edges whose y minimum equals the current line, and sort the AET by current x. 4) Fill between pairs of intersection points, moving across the line from left to right. 5) Increment x for each edge in the AET using the inverse slope, then advance to the next scan line. 6) Repeat until you reach the maximum y of the polygon. This flow yields solid fills for even complex, non-convex polygons.

Practical implementation tips and optimizations

To maximize performance, many implementations separate geometry preprocessing from rasterization. Precompute a Global Edge Table (GET) that stores edges only once, then accumulate an Active Edge Table (AET) per scan line. Use fixed point arithmetic or integer arithmetic with scaled coordinates to avoid floating point costs on limited hardware. Sorting by x can be optimized with insertion sort on a small, usually short, AET. Anti-aliasing can be layered on later by sampling multiple scan lines or by applying a perimeter filter, but the base algorithm remains fast and robust for classic 2D rendering tasks, including font rendering, vector graphics, and sprite-based art.

Pseudocode sketch for a basic scanline fill

• Build GET from polygon edges (ignoring horizontal edges).
• yMin = minimum y of all vertices; yMax = maximum y of all vertices.
• AET = empty list.
• For y from yMin to yMax:
  • Move edges starting at y from GET into AET.
  • Remove edges from AET where y >= yMax of the edge.
  • Sort AET by current x.
  • For i in 0 to length(AET) step 2:
    • fill from ceil(AET[i].x) to floor(AET[i+1].x)
  • For each edge in AET: AET[i].x += AET[i].dx where dx is the inverse slope.
  • Proceed to next scan line.

This minimalist outline omits anti-aliasing and texture mapping, but it captures the essential flow that makes scanline filling both intuitive and efficient.

Comparisons with other fill methods and when to use them

Compared to a flood fill approach, the scanline method scales well with polygon complexity and remains deterministic. It handles non-convex and self-intersecting polygons by filling paired intersections, whereas boundary-fill approaches can struggle with intricate boundaries. For fonts and vector graphics, scanline filling integrates neatly with a pipeline that already processes edges and vertices. In scenarios requiring per-pixel accuracy with anti-aliasing or texture mapping, the base scanline fill is often followed by additional shading passes or supersampling. Overall, it is a robust foundation for 2D rendering that balances correctness, performance, and implementation simplicity.

Real world applications, limitations, and reading paths

You will see scanline fill in many classic rendering pipelines, including 2D game engines, GUI toolkits, and font rasterizers. A limitation is that anti-aliasing and high-resolution textures demand extra steps beyond the basic fill, which may increase complexity and memory usage. For embedded systems and GPU pipelines, the concept translates to shader-based work where parallelism can accelerate the edge-table updates and span filling. As a reader looking to implement this, focus on getting edge-table construction correct, handle degenerate cases consistently, and profile the performance on representative polygons to guide optimizations.

Authority sources and further reading

For deeper reading and formal treatments of scanline filling and rasterization, consult the following sources:

• https://en.wikipedia.org/wiki/Scanline_rendering
• https://en.wikipedia.org/wiki/Polygon_filling
• https://www.cs.ubc.ca/~rbridson/press/brush/scanline_geometry.html