Rasterization

Scanline Fill Triangle

Fill a triangle one horizontal scanline at a time by computing the integer span on each row.

Example

Fill a triangle one horizontal scanline at a time.

highlighted = computed this step

Step 1 — Set up

Use scanlines across this triangle.

△ABC: (2,1), (6,5), (1,5)\triangle ABC:\ (2,1),\ (6,5),\ (1,5)
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 2 — Scanline A

Fill the integer pixels on this scanline.

y=1, xL=2, xR=2, fill (1,2)y=1,\ x_L=2,\ x_R=2,\ \text{fill }\hlmath{(1,2)}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 3 — Scanline B

Fill the integer pixels on this scanline.

y=2, xL=74, xR=3, fill (2,2), (2,3)y=2,\ x_L=\frac{7}{4},\ x_R=3,\ \text{fill }\hlmath{(2,2)},\ \hlmath{(2,3)}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 4 — Scanline C

Fill the integer pixels on this scanline.

y=3, xL=32, xR=4, fill (3,2), (3,3), (3,4)y=3,\ x_L=\frac{3}{2},\ x_R=4,\ \text{fill }\hlmath{(3,2)},\ \hlmath{(3,3)},\ \hlmath{(3,4)}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 5 — Scanline D

Fill the integer pixels on this scanline.

y=4, xL=54, xR=5, fill (4,2), (4,3), (4,4), (4,5)y=4,\ x_L=\frac{5}{4},\ x_R=5,\ \text{fill }\hlmath{(4,2)},\ \hlmath{(4,3)},\ \hlmath{(4,4)},\ \hlmath{(4,5)}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 6 — Scanline E

Fill the integer pixels on this scanline.

y=5, xL=1, xR=6, fill (5,1), (5,2), (5,3), (5,4), (5,5), (5,6)y=5,\ x_L=1,\ x_R=6,\ \text{fill }\hlmath{(5,1)},\ \hlmath{(5,2)},\ \hlmath{(5,3)},\ \hlmath{(5,4)},\ \hlmath{(5,5)},\ \hlmath{(5,6)}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456

Step 7 — Result

The filled triangle pixel set is complete.

triangle pixels complete\text{triangle pixels complete}
Scanline triangle fillTriangle pixels are filled row by row between edge spans.012345670123456
scanline-fill-triangle A scanline fill finds the left and right edge intersections for a row, then fills the integer pixels between them.