Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 50 ยท Polygons and Filling

Scanline Polygon Filling

Fill any polygon one row at a time with the scanline algorithm: edge table, active edge list, sorted intersections, vertex rules and a live software filler.

Outlines are only half of a picture. To draw a solid shape on a raster display you must decide, for every pixel, whether it lies inside the polygon. The brute-force answer is to run the inside test on every pixel of the bounding box. That works, but it repeats the same edge calculations thousands of times.

The scanline algorithm is much smarter. It walks down the image one horizontal row (a scanline) at a time and asks only: where does this row cross the polygon's edges? Between the first and second crossing the row is inside, between the second and third it is outside, between the third and fourth it is inside again, and so on. Each inside stretch is a span, and a span can be filled with a plain loop. The expensive geometry is done once per edge, not once per pixel.

The key idea: coherence

Neighboring scanlines look almost the same. An edge that crosses row y at x = 20.0 crosses row y + 1 at x = 20.0 + 1/m, where m is the edge's slope (dy/dx). So instead of recomputing the intersection with a division every row, we update it incrementally by adding the constant 1/m (the inverse slope). This property is called edge coherence, and it is why scanline filling is fast. It is the same trick the DDA and Bresenham algorithms use for lines.

Also, an edge only matters on the rows between its lower and upper end. Most edges are irrelevant for most rows, so we keep a list of the ones that are currently crossing the scanline.

Two data structures

For each edge that is not horizontal, we store a small record:

Field Meaning
yMax the row where the edge ends (exclusive, see below)
x the x-position where the edge crosses the current row; starts at the x of the end with the smaller y
invSlope dx / dy, the amount x changes per row
dir +1 if the edge was listed going down the image, -1 if going up (needed for the nonzero rule)

These records live in two structures:

  • The edge table (ET) is a bucket list indexed by the edge's starting row yMin. It is built once, up front. Row y of the table holds all edges that begin at y.
  • The active edge list (AEL) holds the edges that cross the current scanline. At each new row, edges whose yMax has been reached are removed, edges from the ET bucket for this row are added, and the list is sorted by x.
flowchart TB
  A["Build edge table<br/>(skip horizontal edges)"] --> B["y = smallest yMin"]
  B --> C["Remove edges with yMax <= y"]
  C --> D["Add edges whose yMin = y"]
  D --> E["Sort active edges by x"]
  E --> F["Fill spans between pairs<br/>(x1..x2, x3..x4, ...)"]
  F --> G["For each active edge: x += invSlope"]
  G --> H{"y reached the top?"}
  H -->|no| I["y = y + 1"] --> C
  H -->|yes| J["Done"]

The scanline loop. Everything below the first two boxes repeats once per row.

Vertices and horizontal edges

Real polygons are full of awkward cases, and the algorithm must handle them without special code everywhere.

Horizontal edges are skipped entirely. A horizontal edge is a stretch of the boundary that lies along one scanline. The edges attached to its two ends already produce the correct crossings on the rows next to it.

Shared vertices are the bigger problem. Imagine a scanline passing exactly through a vertex where two edges meet. If both edges count the crossing, the row would register two intersections at one place, and the even-odd pairing would go wrong.

  • At a "pass-through" vertex (one edge goes up, the next continues up) the vertex should count once.
  • At a local peak or valley (both edges go the same way) it should count zero or two times, so the pairing stays consistent.

The simple fix is the half-open rule: each edge covers rows from yMin up to but not including yMax. Then a vertex is counted only by the edge that starts there, never by the edge that ends there. A pass-through vertex is counted exactly once; a local peak or valley is counted zero or two times. No special cases are needed. The same rule makes sure that two polygons sharing an edge never double-draw or leave a gap along that edge.

Two further conventions keep the result predictable:

  • Pixel centers are at integer coordinates. A span from xa to xb fills the pixels x with xa <= x < xb, which is ceil(xa) up to ceil(xb) - 1.
  • Because of the half-open rule, the polygon covers rows yMin to yMax - 1, so a rectangle of height h fills exactly h rows. This is the same idea as the top-left rule used for triangles.

The algorithm in code

This function returns the list of spans. Drawing them is then a loop over fillRect or pixel writes.

JavaScript
function buildEdgeTable(poly) {
  const table = new Map();
  let minY = Infinity, maxY = -Infinity;
  for (let i = 0; i < poly.length; i++) {
    const a = poly[i], b = poly[(i + 1) % poly.length];
    if (a.y === b.y) continue;                       // horizontal: skip
    const down = a.y < b.y;
    const lo = down ? a : b, hi = down ? b : a;
    const edge = {
      yMax: hi.y,
      x: lo.x,
      invSlope: (hi.x - lo.x) / (hi.y - lo.y),
      dir: down ? 1 : -1
    };
    if (!table.has(lo.y)) table.set(lo.y, []);
    table.get(lo.y).push(edge);
    minY = Math.min(minY, lo.y);
    maxY = Math.max(maxY, hi.y);
  }
  return { table, minY, maxY };
}

function fillSpans(poly, rule = "evenodd") {
  const { table, minY, maxY } = buildEdgeTable(poly);
  const spans = [];
  let active = [];
  for (let y = minY; y < maxY; y++) {
    active = active.filter((e) => e.yMax > y);       // half-open: drop finished edges
    if (table.has(y)) active.push(...table.get(y));
    active.sort((p, q) => p.x - q.x);

    let state = 0;                                   // parity or winding number
    for (let k = 0; k < active.length - 1; k++) {
      state = rule === "evenodd" ? state ^ 1 : state + active[k].dir;
      const inside = rule === "evenodd" ? state === 1 : state !== 0;
      if (inside) {
        const x0 = Math.ceil(active[k].x - 1e-9);
        const x1 = Math.ceil(active[k + 1].x - 1e-9);
        if (x1 > x0) spans.push({ y, x0, x1 });      // x1 is exclusive
      }
    }
    for (const e of active) e.x += e.invSlope;       // edge coherence
  }
  return spans;
}

The 1e-9 guards against a crossing that should be exactly 10 being stored as 10.000000000000002 after repeated additions. Production code avoids floating-point entirely by keeping x as an integer plus a fractional numerator, exactly like Bresenham's error term.

Watching it work

The first live example uses a concave polygon with horizontal edges, a local peak and a local valley. Drag the slider to move the scanline. The filled area grows row by row, the current row is highlighted, and the text lists the active edges with their current x values. Notice how the list always holds an even number of edges and how entries leave and join as the row passes the vertices.

Step through the scanline

Move the line to row 5 and note that only the edges starting on that row appear (the horizontal edges are absent). Around rows 18 and 22 you can see the peak and valley vertices change the number of spans on the row.

Fill rules in a scanline filler

Notice the two variables in fillSpans: state is either a parity bit (even-odd rule) or a running winding number (nonzero rule). Each active edge carries dir, so passing an edge changes the winding by +1 or -1. A span is filled whenever the state says "inside". With a self-intersecting polygon the two rules differ, exactly as in the previous lesson.

Filling a pentagram with both rules

For a convex polygon the active list never holds more than two edges, so the whole fill collapses to one span per row. That special case is what triangle rasterizers use, and it is the subject of the triangle rasterization lesson.

Cost and refinements

  • Time. The work is proportional to the number of scanlines times the number of active edges, plus sorting. Since the list is almost sorted from one row to the next, an insertion sort is nearly linear.
  • Memory. The edge table has one record per non-horizontal edge. The span list can be streamed to the display instead of stored.
  • Bounding box. The whole algorithm lives between minY and maxY. You never touch pixels outside the polygon's vertical extent.
  • Antialiasing. The plain version produces hard edges. Computing the fractional coverage of the first and last pixel of each span (see antialiasing) gives soft edges.
  • Pattern fills. Instead of one color, each span pixel can be taken from a repeating tile or a gradient.
  • Alternatives. Flood fill fills a region by its pixels, not by its geometry. It is useful when only the pixels exist, as in a paint program.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does edge coherence let the scanline algorithm avoid?

    An edge's intersection moves by a constant inverse slope from one row to the next, so it can be updated with one addition.
  2. 2. Why are horizontal edges left out of the edge table?

    A horizontal edge has no vertical extent (1/slope would require division by zero); the edges attached to its ends define the spans around it.
  3. 3. What problem does the half-open rule (yMin included, yMax excluded) solve?

    Only the edge that starts at a vertex counts it, so pass-through vertices count once and peaks or valleys count zero or two times, keeping the pairing of crossings correct.
  4. 4. The active edge list at some row contains the x-values 12.0, 4.5, 20.3 and 30.1 after sorting. Which pixel ranges are filled with the even-odd rule?

    After sorting (4.5, 12.0, 20.3, 30.1) the first pair (4.5 to 12.0) and the second pair (20.3 to 30.1) are inside.
  5. 5. Why does the nonzero version of the filler store a dir value on every edge?

    The winding number is the sum of signed crossings, so each edge must remember whether it goes down or up.

Summary

  • The scanline algorithm fills a polygon row by row, filling spans between pairs of edge crossings.
  • The edge table buckets non-horizontal edges by their starting row; the active edge list holds the edges crossing the current row, sorted by x.
  • Edge coherence: each active edge's x advances by its inverse slope per row.
  • The half-open rule (an edge covers yMin to yMax - 1) removes all vertex special cases.
  • Even-odd uses parity; nonzero keeps a running winding number using each edge's direction.
  • Convex polygons never have more than two active edges, which leads to the triangle filling methods used by GPUs.

Next: Flood Fill and Boundary Fill.