Graphics / Reference / Scanline fill

Scanline fill

Scanline filling processes a raster region one horizontal row at a time. Each row is represented by one or more horizontal spans bounded by the region's intersections with that scanline; a rectangle has one fixed span per row.

Scanline filling processes a raster region one horizontal row at a time. On each row, the region contributes one or more horizontal spans between boundary intersections; the simple axis-aligned rectangle case has one span whose limits remain constant from row to row.

Using the y-down convention used by the triangle experience, an axis-aligned rectangle can be filled with:

for y = top; y < bottom; y = y + 1 for x = left; x < right; x = x + 1 point(x,y)

Both ranges are half-open: bottom and right are excluded by the < comparisons.

The essential structure is an outer loop over scanlines and an inner operation that fills the horizontal span belonging to the current row. More complex shapes retain the row-by-row structure but obtain their span boundaries from changing intersections with the shape boundary.

If a coordinate system instead has y increasing upward, the direction of vertical iteration changes, but the scanline principle remains the same.

A three-by-three block of pixels fills an axis-aligned rectangle, with arrows showing left-to-right scanning on each row and downward movement between rows.
The rectangle fill visits rows from top to bottom and fills each row from left up to the excluded right boundary.

Builds on

Read

Playgrounds