Perfect 👌 — let’s now go through the Scanline Polygon Fill Algorithm example step-by-
step for a triangle, just like we did for the square.
We’ll include:
✅ Algorithm (quick recap)
✅ Example with triangle vertices
✅ Step-by-step scanline calculations
✅ Visual idea of how filling happens
🧠 SCANLINE POLYGON FILL ALGORITHM (Recap)
Goal: To fill a polygon by drawing horizontal lines (scanlines) between pairs of intersection
points of the polygon edges and the scanline.
Steps:
1. Input all polygon vertices.
2. Find ymin and ymax.
3. Compute inverse slope (dx/dy) for all edges.
4. For each scanline from ymin → ymax:
o Find intersection points (x-intersections) of the scanline with polygon edges.
o Sort these intersection x-values.
o Fill between pairs of intersection points.
🔺 Example: Triangle Polygon
Let’s consider a triangle with vertices:
Vertex Coordinates (x, y)
A (100, 100)
B (300, 100)
C (200, 300)
C(200,300)
/\
/ \
/____\
A(100,100) B(300,100)
Step 1: Find ymin and ymax
ymin = 100
ymax = 300
Step 2: Calculate inverse slopes
We have 3 edges:
slopeInv
Edge From To Formula
(dx/dy)
(100,100) →
1 Horizontal 0
(300,100)
(300,100) → (200−300)/(300−100) = −100/200 =
2
(200,300) −0.5
(200,300) → (100−200)/(100−300) = (−100)/(−200)
3
(100,100) = 0.5
Step 3: Scanline at y = 120
We check which edges this scanline (y = 120) crosses.
Edge 1: y = 100 (horizontal edge) → ignore for filling top/bottom.
Edge 2: between y = 100 and y = 300 → ✅ intersects
Edge 3: between y = 300 and y = 100 → ✅ intersects
Find intersection points:
For Edge 2 (300,100)–(200,300):
[
x = x_1 + slopeInv \times (y - y_1)
]
[
x = 300 + (-0.5) \times (120 - 100) = 300 - 10 = 290
]
For Edge 3 (200,300)–(100,100):
[
x = 200 + 0.5 \times (120 - 300) = 200 - 90 = 110
]
→ Intersections: x = 110, 290
✅ Fill between x = 110 to 290 at y = 120
Step 4: Next scanline at y = 200
Edge 2: (300,100)–(200,300)
[
x = 300 + (-0.5) \times (200 - 100) = 300 - 50 = 250
]
Edge 3: (200,300)–(100,100)
[
x = 200 + 0.5 \times (200 - 300) = 200 - 50 = 150
]
→ Intersections: x = 150, 250
✅ Fill between x = 150 to 250 at y = 200
Step 5: Scanline at y = 280
Edge 2:
[
x = 300 + (-0.5) \times (280 - 100) = 300 - 90 = 210
]
Edge 3:
[
x = 200 + 0.5 \times (280 - 300) = 200 - 10 = 190
]
→ Intersections: x = 190, 210
✅ Fill between x = 190 to 210 at y = 280
Step 6: Filled Output (Conceptually)
y ↑
|
| C(200,300)
| /\
| /##\
| /####\
| /######\
| /########\
| /##########\
| A(100,100)------B(300,100)
|______________________________→ x
Red scanlines fill between pairs of x-intersections — the filled area gradually narrows as you
go up the triangle.
🧩 Summary Table
Scanline (y) x₁ x₂ Fill Range
120 110 290 110–290
160 130 270 130–270
200 150 250 150–250
240 170 230 170–230
280 190 210 190–210
✅ Result
When you run your OpenGL scanline fill code with the triangle:
n = 3
(100,100)
(300,100)
(200,300)
You’ll see:
A white triangle outline, and
A red color fill gradually drawn inside using horizontal lines (scanlines).
Would you like me to modify your OpenGL code slightly to animate this triangle filling line-
by-line (so you can show it in class)?