PadhaikoAll subjects

Scan-Line, Boundary & Flood Fill

Computer Graphics and Visualization (ENCT 201)

Open in the Padhaiko app

2.4 Scan-Line Polygon Fill Algorithm

Area filling is the process of illuminating interior pixels bounded by a set of geometric edges. While wireframe representations display only boundaries, raster displays require solid interior coloring for shading, visible-surface determination, and realistic rendering.

The scan-line polygon fill algorithm operates in image space by sweeping horizontal scan lines from bottom to top across the polygon. For each scan line , the algorithm computes the intersection points of the line with all non-horizontal polygon edges, sorts these intersection points in ascending order of their coordinates, and fills all pixels between consecutive odd and even pairs of intersections.

Scan Line y:
Outside  |==== Inside Span ====|  Outside  |==== Inside Span ====| Outside
Parity:0 |  1 (Fill Pixels)    |     0     |   1 (Fill Pixels)   |    0
        x_1                   x_2         x_3                   x_4

The Inside-Outside Test and Parity Rule

To determine which spans along a scan line belong to the interior of a polygon, graphics systems evaluate the parity rule (also known as the even-odd rule):

Definition

The Even-Odd Parity Rule

Let a point lie on scan line . Construct an imaginary ray extending from along the scan line toward infinity (or from to ). Count the number of polygon boundary edge crossings:

Along any scan line , initializing at the left boundary of the frame buffer and toggling at every edge intersection yields interior pixel spans .

AspectEven-Odd RuleNonzero Winding Number Rule
Edge OrientationDirection of edges is ignored; each intersection toggles state.Edges are directed; crossings from right-to-left add , left-to-right subtract .
Interior CriterionPoint is inside if crossing count is odd.Point is inside if net winding sum .
Self-Intersecting ShapesLeaves central overlap of self-intersecting polygons as a "hole".Treats overlapping self-intersecting regions as solid interior.
Computational CostMinimal; single bit-toggle per edge intersection.Requires tracking edge traversal directions and signed summation.

Vertex Singularities and Intersection Counting

When a horizontal scan line passes exactly through a polygon vertex , two adjacent edges meet at that point. If both edges are naively counted as separate intersections, the parity counter increments by , leaving the parity unchanged and failing to open an interior span.

To maintain correct parity, vertex intersections are classified according to whether the vertex represents a local extremum or a monotonic crossing:

Definition

Vertex Intersection Rules

Let be a vertex joining edge and edge :

  1. Local Extremum (Local Minimum or Maximum): Both adjacent edges lie on the same side of the scan line:
    • For a local minimum ( for both edges), the scan line enters the polygon vertex from outside without traversing the interior.
    • For a local maximum ( for both edges), the scan line touches the vertex and exits.
    • Rule: Count the vertex as two intersections (or zero), so parity is toggled twice (net change ), correctly preserving the inside/outside status.
  2. Monotonic Crossing: One adjacent edge lies above the scan line () and the other lies below (). The scan line enters or leaves the polygon interior across this boundary.
    • Rule: Count the vertex as one intersection, so parity is toggled once.
    • Implementation: Shorten one of the two edges by scan line (typically reducing the upper edge's to , or reducing the lower edge's to ).
  3. Horizontal Edges: Edges where () have undefined inverse slope ().
    • Rule: Discard horizontal edges from the Edge Table; the adjacent non-horizontal edges generate the appropriate span endpoints at that scan line.

Coherence Principles in Rasterization

Computing floating-point edge-line intersections from scratch for every scan line is computationally prohibitive. Practical scan-line algorithms exploit spatial coherence:

Coherence Principles in Scan-Line Fill
Coherence TypePhysical PrincipleAlgorithmic Exploitation
Edge CoherenceAn edge intersecting scan line typically intersects scan line .If an edge has slope , its intersection advances by .
Scan-Line CoherenceAdjacent pixels on the same scan line have the same interior/exterior status across a span.Spans between odd-even intersection pairs are filled by a single memory fill loop.
Area CoherenceAdjacent scan lines span nearly identical interior pixel intervals.The active edge list changes only when an edge terminates or a new edge begins.

Data Structures: Edge Table (ET) and Active Edge List (AEL)

Definition

Edge Table and Active Edge List

The scan-line polygon fill algorithm utilizes two auxiliary data structures:

  1. Edge Table (ET): An array of linked lists indexed by scan line , covering the range . Every non-horizontal polygon edge is inserted into the bucket corresponding to its lower endpoint . Each edge node stores:
    • : the upper limit of the edge.
    • : the coordinate evaluated at .
    • : the inverse slope.
    • : pointer to the next edge node sharing the same .
  2. Active Edge List (AEL): A dynamic linked list holding all edges that intersect the current scan line . Edges in the AEL are maintained in sorted order of their current coordinate.
Theorem

Scan-Line Polygon Fill Algorithm

Let a polygon be defined by ordered vertices . The interior is rasterized as follows:

Proof

  1. Construct the Edge Table (ET):
    • For each edge :
      • If the edge is horizontal (), discard it.
      • Determine and .
      • Let be the coordinate at .
      • Compute .
      • If the vertex at or is a monotonic crossing, shorten the edge by setting (or ).
      • Insert the edge node into bucket , sorted by .
  2. Process Scan Lines:
    • Initialize the Active Edge List .
    • For to :
      • Add New Edges: Move all edge nodes from bucket into the AEL.
      • Remove Expired Edges: Delete all nodes from the AEL whose .
      • Sort AEL: Sort the active edges in ascending order of their current values.
      • Fill Spans: Traverse the sorted AEL in consecutive pairs :

2.5 Scan-Line Fill of Curved Boundary Areas

While polygonal boundaries consist of piecewise-linear segments with constant inverse slope , curved boundaries (circles, ellipses, and splines) possess continuously varying tangents. Three principal techniques are used to scan-convert curved regions:

Analytical Span Calculation

For quadric curves described by an implicit equation , the intersection of any horizontal scan line can be computed by solving directly for :

Definition

Analytical Span Fill for Quadric Curves

  1. Circle with Center and Radius :

Real solutions exist for all integer scan lines satisfying . The filled horizontal pixel span at scan line is:

  1. Ellipse with Center and Semi-Axes :

For each integer scan line in , compute and fill .

Incremental Midpoint Symmetry Span Filling

Instead of computing square roots per scan line, incremental midpoint circle and ellipse algorithms can be adapted to draw filled horizontal spans instead of isolated boundary pixels:

Theorem

Incremental Symmetry Span Generation

Whenever the midpoint circle algorithm calculates a boundary point in the first octant (relative to center ), eight-way symmetry yields two symmetric scan lines:

  1. At scan line : fill pixels from to .
  2. At scan line : fill pixels from to .
  3. When the octant swaps ( step): at scan line , fill from to ; at , fill from to .

Proof

Because circles and ellipses are convex, any horizontal scan line intersects the boundary at exactly two points and . Symmetry ensures that and , eliminating the need for an Edge Table or sorting.

2.6 Boundary-Fill Algorithm

The boundary-fill algorithm is an area-filling technique that begins at an interior seed point and paints outward in all directions until it reaches pixels possessing a specified boundary color.

4-Connected vs. 8-Connected Areas

Definition

Pixel Connectivity

4-Connected Neighbors:          8-Connected Neighbors:
        (x, y+1)                (x-1, y+1)  (x, y+1)  (x+1, y+1)
           |                                  \   |   /
(x-1, y)-(x, y)-(x+1, y)         (x-1, y)---(x, y)---(x+1, y)
           |                                  /   |   \
        (x, y-1)                (x-1, y-1)  (x, y-1)  (x+1, y-1)

The choice of connectivity is critical:

Recursive Boundary-Fill Implementation

Definition

Recursive 4-Connected Boundary Fill

The standard recursive procedure tests each candidate pixel against the boundary color and the target fill color:

Recursive 4-Connected Boundary FillC
void boundaryFill4(int x, int y, int fillColor, int borderColor) {
    int current = getPixel(x, y);
    if (current != borderColor && current != fillColor) {
        setPixel(x, y, fillColor);
        boundaryFill4(x + 1, y,     fillColor, borderColor); // East
        boundaryFill4(x - 1, y,     fillColor, borderColor); // West
        boundaryFill4(x,     y + 1, fillColor, borderColor); // North
        boundaryFill4(x,     y - 1, fillColor, borderColor); // South
    }
}

Recursion Stack Limitations and Span-Based Optimization

While conceptually simple, recursive pixel-by-pixel filling suffers from severe memory overhead:

Theorem

Scan-Line Seed Fill (Span-Based Boundary Fill)

The stack overhead of boundary fill is mitigated by filling contiguous horizontal spans of pixels:

  1. Starting from seed , search left and right along the current scan line to determine the maximum continuous span of non-boundary pixels.
  2. Fill the entire horizontal span .
  3. Inspect the scan lines immediately above () and below () within the interval .
  4. For each contiguous sub-span of unvisited non-boundary pixels on those adjacent scan lines, push only the extreme rightmost pixel onto an explicit stack as a new seed.
  5. Pop a seed from the stack and repeat until the stack is empty.

Proof

Because entire spans are processed in single loops and only seeds of adjacent spans are pushed, the maximum stack depth is bounded by , reducing stack depth from thousands of frames to at most the vertical height of the polygon.

2.7 Flood-Fill Algorithm

The flood-fill algorithm is applied when a region is not bounded by a single uniform border color, but is instead characterized by an existing interior color that needs replacement (such as recoloring an area or using a "paint bucket" tool).

Definition

Recursive 4-Connected Flood Fill

Flood fill replaces an oldColor with a newColor starting from a seed point:

Recursive 4-Connected Flood FillC
void floodFill4(int x, int y, int newColor, int oldColor) {
    if (getPixel(x, y) == oldColor) {
        setPixel(x, y, newColor);
        floodFill4(x + 1, y,     newColor, oldColor); // East
        floodFill4(x - 1, y,     newColor, oldColor); // West
        floodFill4(x,     y + 1, newColor, oldColor); // North
        floodFill4(x,     y - 1, newColor, oldColor); // South
    }
}
AspectBoundary-Fill AlgorithmFlood-Fill Algorithm
Termination Conditionpixel != borderColor && pixel != fillColorpixel == oldColor
Boundary RequirementRequires a single, uniform boundary color surrounding the entire area.Does not require a uniform boundary; terminates whenever pixel color differs from oldColor.
Primary Use CaseFilling unpainted vector geometry with a solid border.Repainting or recoloring pre-existing raster regions containing multi-colored boundaries.
Failure ModeLeaks past any gap in the boundary color or if interior contains boundary-colored pixels.Replaces all connected pixels of oldColor; fails if interior has multiple colors.
ConnectivitySupports 4-connected and 8-connected variants.Supports 4-connected and 8-connected variants.

Worked Out Examples

Example 1

1

A polygon has vertices , , , and . Construct the Edge Table (ET), trace the Active Edge List (AEL) across all scan lines from to , handle vertex singularities, and determine the exact pixel spans filled on each scan line.

Classifying Polygon Edges and Computing Inverse Slopes: The polygon edges in circular order are:

  1. from to : Horizontal edge (). Discarded from the Edge Table; the base span on is rendered directly from to .
  2. from to :
  3. from to :
  4. from to :

Evaluating Vertex Singularities and Shortening Edges:

  • Vertex : Joined by (ascending from to ) and (ascending from to ). Because is strictly monotonic through , is a monotonic crossing and must count as a single intersection. To prevent double-counting at scan line , shorten the lower edge by setting:
  • Vertex : Joined by and . Both edges lie below , making a local maximum. Both edges terminate at ; counting twice preserves parity (net change ), so no edge shortening is needed.

Constructing the Edge Table (ET): Placing edges into buckets indexed by their :

Tracing Scan Lines and Active Edge List (AEL):

  • Scan line :
    • Add edges from : and .
    • Sorted AEL: .
    • Spans filled: .
    • Update for : ; .
  • Scan line :
    • Sorted AEL: .
    • Span filled: .
    • Update for : ; .
  • Scan line :
    • Sorted AEL: .
    • Span filled: .
    • Remove because .
    • Update for : .
  • Scan line :
    • Add edge from : .
    • Sorted AEL: .
    • Span filled: .
    • Update for : ; .
  • Scan line :
    • Sorted AEL: .
    • Both edges meet at vertex . Single pixel filled: .
    • Remove both edges because . AEL is now empty.
Answer:

The Edge Table and Active Edge List produce the following filled spans:

  • Scan line : pixels
  • Scan line : pixels
  • Scan line : pixels
  • Scan line : pixels
  • Scan line : pixel
Example 2

2

Compute the analytical scan-line fill intervals for a circular region centered at with radius on scan lines .

Formulating the Span Equation: The equation of the circle is:

For any valid scan line , the horizontal span extends from to , where . The integer pixel range filled is .

Evaluating Extents for Specified Scan Lines:

  • For :
  • For :
  • For :
  • For :
  • For :
Answer:

The filled horizontal pixel spans are:

  • : (9 pixels)
  • : (9 pixels)
  • : (11 pixels)
  • : (7 pixels)
  • : (1 pixel)
Example 3

3

A rectangular canvas area of pixels bounded by a solid boundary is filled using recursive 4-connected boundary fill. Calculate the worst-case call stack depth and memory consumption assuming 32 bytes per activation record, and explain how the scan-line seed fill algorithm reduces this overhead.

Worst-Case Stack Depth of Recursive Boundary Fill: In recursive 4-connected boundary fill:

  • Each interior pixel is visited and pushed onto the execution call stack before neighboring recursive calls terminate.
  • In a serpentine or spiral path, recursion can nest until every interior pixel has an active stack frame.
  • Total interior pixels .
  • Worst-case call stack depth frames.
  • Memory consumption .

Stack Analysis of Scan-Line Seed Fill: In span-based scan-line seed fill:

  • Horizontal spans of pixels are filled iteratively in a single loop rather than through recursive calls.
  • The stack stores only seed coordinates for disconnected adjacent spans above and below the current span.
  • For a convex or simple rectangular region of height , only seed point per scan line is pushed.
  • Maximum stack entries entries.
  • Memory consumption .
  • This represents an reduction in stack memory, completely preventing stack overflow.
Answer:

Recursive 4-connected boundary fill requires a maximum call stack depth of 200 frames (6,400 bytes). Scan-line seed fill processes entire horizontal lines in one iteration, reducing the stack requirement to at most 10 seed entries (80 bytes).

Exercises

Exercise — Scan-Line, Boundary & Flood Fill

Question 1

A triangle has vertices , , and . Construct the Edge Table (ET), Active Edge List (AEL), and compute the filled pixel spans on scan lines .

Edge Parameters and Inverse Slopes:

  1. Edge from to : Horizontal edge (). Omitted from the Edge Table; the base span is filled directly at .
  2. Edge from to :
  3. Edge from to :

Tracing AEL Across Scan Lines: Both edges enter the AEL at and advance symmetrically by :

  • At : ; . Span: .
  • At : ; . Span: .
  • At : ; . Span: .
  • At : ; . Span: .
  • At : ; . Span: .
  • At : Apex vertex . Both edges terminate ().
Answer:

The filled spans are:

  • :
  • :
  • :
  • :
  • :
Question 2

Explain how the scan-line polygon fill algorithm handles vertex intersections. Distinguish between local extrema and monotonic vertices, and explain why edge shortening is necessary.

The Parity Problem at Vertices: When a scan line intersects a polygon exactly at a vertex, it encounters two sharing edges simultaneously. Under the standard even-odd parity rule:

  • If both edges are incremented, the parity count changes by , which leaves the inside/outside state unchanged ().
  • If this occurs at an edge crossing where the scan line enters the interior, no interior pixels will be filled.

Classification and Edge Shortening:

  1. Local Extrema (Local Minima / Maxima):
    • Both edges lie entirely above the scan line (local minimum) or entirely below (local maximum).
    • The scan line grazes the polygon boundary without traversing from exterior to interior.
    • Parity should not change state. Counting two intersections () correctly leaves the parity bit unchanged. No adjustment is required.
  2. Monotonic Vertices:
    • One edge extends above the scan line and the other extends below.
    • The scan line actually enters or leaves the polygon interior across this vertex.
    • The vertex must count as exactly one intersection ().
    • To achieve this, the lower edge is shortened by setting its upper limit to . Consequently, the vertex is counted only once (by the entering upper edge).
Answer:

At local extrema (local minima/maxima), both edges lie on the same side of the scan line; counting two intersections preserves parity. At monotonic vertices, the scan line traverses the boundary; counting both edges would cause parity failure. One edge is shortened () so the vertex counts as exactly one intersection.

Question 3

Calculate the exact scan-line fill intervals for an ellipse centered at the origin with semi-major axis and semi-minor axis for scan lines .

Deriving the Analytical Ellipse Span Formula: The implicit equation of the ellipse is:

Solving for in terms of scan line :

The filled integer pixel range is .

Evaluating Spans for Given Scan Lines:

  1. For (Major Axis):
  1. For :

Integer span:

  1. For :

Integer span:

Answer:

The filled spans for the ellipse are:

  • :
  • :
  • :
Question 4

Compare the boundary-fill and flood-fill algorithms. Under what conditions must flood-fill be used instead of boundary-fill?

Algorithmic Differences:

  • Boundary-Fill: Tests whether a pixel is not equal to a designated borderColor and not equal to the fillColor. It paints outward from a seed until hitting the boundary color.
  • Flood-Fill: Tests whether a pixel is equal to a designated oldColor. It replaces all connected instances of oldColor with newColor.

Scenarios Requiring Flood-Fill:

  1. Multi-Colored Boundaries: When an interior region is enclosed by borders of differing colors (e.g. red on top, green on sides, blue on bottom), boundary-fill cannot define a single stopping color and will leak through edges colored differently. Flood-fill operates purely on the uniform interior color, ignoring border variations.
  2. Re-coloring Existing Images: When modifying an existing raster graphic (such as recoloring a green shirt to yellow), the boundary consists of complex antialiased edges, gradients, and neighboring scene features. Flood-fill selectively transforms the target color without requiring an explicit bounding line.
Answer:

Boundary-fill terminates upon reaching a single designated border color. Flood-fill terminates when encountering any color different from the initial seed's interior color. Flood-fill must be used when:

  1. The region has multi-colored boundaries.
  2. An existing interior region is being recolored without a uniform boundary color.
Question 5

Explain why a 4-connected boundary fill algorithm can fail to fill a region bounded by diagonally connected pixels, and why an 8-connected fill algorithm can leak through a 4-connected boundary.

Failure of 4-Connected Fill in Diagonal Regions: A 4-connected algorithm only inspects horizontal and vertical neighbors ( and ). If a narrow polygon passage or interior region connects only across diagonal corners:

[Fill] [Boundary]
[Boundary] [Unfilled]

The 4-connected traversal cannot take diagonal steps and halts, leaving the second compartment completely unfilled.

Leakage of 8-Connected Fill Through 4-Connected Boundaries: If a boundary is drawn with 4-connectivity, adjacent boundary pixels may touch only at corners:

Canvas:
.  .  B  .  .
.  B  .  .  .
B  .  .  .  .

An 8-connected fill algorithm evaluates diagonal neighbors. When inspecting the corner between boundary pixels and , the 8-connected fill steps diagonally through the gap, "leaking" out of the polygon into the surrounding background canvas. Therefore: 4-connected interiors require 8-connected boundaries, while 8-connected interiors require 4-connected boundaries.

Answer:

A 4-connected fill cannot cross diagonal gaps, leaving diagonally connected interior pockets unfilled. An 8-connected fill tests diagonal neighbors and will leak through diagonal corner gaps of a 4-connected boundary. Correct pairing: 4-connected fill requires 8-connected boundaries; 8-connected fill requires continuous 4-connected boundaries.

Question 6

Describe the components of an edge record in the Edge Table (ET) of the scan-line polygon fill algorithm, and derive the formula that enables incremental calculation of along an edge.

Components of the Edge Table Record: Each non-horizontal polygon edge is stored as a linked list node in the Edge Table at index :

  1. : The maximum scan line reached by the edge (where the edge terminates and is removed from the Active Edge List).
  2. : The coordinate of the edge evaluated at its lower endpoint .
  3. : The inverse slope of the edge, .
  4. : A pointer to the next edge node sharing the same .

Derivation of Incremental Calculation: The mathematical equation of an edge line is:

For consecutive horizontal scan lines, :

Thus, the intersection on the next scan line is obtained by a single addition:

This eliminates all floating-point divisions inside the scan-line rendering loop.

Answer:

An edge record contains , , inverse slope , and a pointer to the next edge. Because increments by per scan line, . This incremental formula replaces costly line-equation re-evaluation with a single addition per scan line.

Past exam questions for Computer Graphics and Visualization

← Mid-Point Circle & Ellipse AlgorithmsPoint, Line (Cohen–Sutherland, Liang–Barsky), Polygon & Text Clipping →