Polygon Filling

CSC-214 · Semester III · Computer Graphics

intermediate25 minAvailable

Polygon Filling (Scanline)

Fill a rectangle by computing span intersections per row.

Row 0 processed: .......... — every cell between the left and right boundary pixel is painted.

Scanline fill algorithm

For each horizontal scanline, find intersections with polygon edges.
Sort intersections left to right.
Pair them up: fill between (0,1), skip (1,2), fill (2,3)...

Handles concave polygons too, once the even-odd rule is applied consistently.

Scanline trace:

..........

Lab brief

Objective

Fill a polygon using the scan-line algorithm and a seed-fill algorithm, and compare their behaviour.

Theory & concepts

Scan-line fill finds where each horizontal scan line crosses the polygon edges, sorts the intersections left to right, and fills between each pair. Seed fill starts from an interior pixel and colors neighbors until it hits the boundary. The visualization runs both side by side on the same polygon.

Rendering diagram…

Scan-line fill versus seed fill

# scan-line
for y in ymin..ymax:
  xs = sort(intersections(edges, y))
  fill pairs (xs[0], xs[1]), (xs[2], xs[3]), ...

# seed fill (4-connected)
fill(x, y): if inside and uncolored: color, recurse neighbors

Concave polygons are the interesting test case: a scan line can cross the boundary more than twice, producing several interior runs, while a misplaced seed can leak through thin boundaries.

Prerequisites

Lesson: Polygon filling: scan line and seed fill
Lesson: Scan conversion and the raster pipeline

Instructions

1Draw a concave polygon on the grid (a star or L-shape works well).
2Run the scan-line fill and watch each row's intersections pair up.
3Select a seed point inside the polygon and run the seed fill.
4Compare the final fills for gaps, overshoot and performance.
5Place the seed outside the polygon and observe the flood behavior.
6Draw a self-intersecting polygon and note how each algorithm behaves.

Tasks

Fill a concave polygon
Fill a star shape with both algorithms and check for gaps.
Vertex double-counting
Construct a polygon with a horizontal edge at a scan line and observe the pairing.
Seed outside
Run seed fill from outside and explain what happens.

Self-check

Both algorithms fill the polygon without gaps or overshoot.
The student explains the pairing of intersections in scan-line fill.
The student compares the two algorithms' strengths and weaknesses.

Environment

polygon drawing toolscan-line animationseed point pickerside-by-side comparisonvertex highlighting