Scan-Line Polygon Fill Algorithm

1. Introduction

Polygon filling is required to display solid objects. The scan-line algorithm fills polygons efficiently by intersecting them with horizontal scan lines.

• Used for filled polygons
• Efficient for complex shapes

2. Basic Idea

Each horizontal scan line intersects polygon edges at certain points. Pixels between pairs of intersection points are filled.

• Scan line by line
• Fill between intersections

3. Scan Lines

Scan lines are horizontal lines that move from the bottom of the polygon to the top.

• Parallel to x-axis
• Incremented in y-direction

4. Edge Table (ET)

The Edge Table stores information about polygon edges sorted by their minimum y-coordinate.

• y_min
• y_max
• x at y_min
• 1/m (inverse slope)

5. Active Edge Table (AET)

The Active Edge Table contains edges that intersect the current scan line.

• Updated for each scan line
• Sorted by x-intersections

6. Filling Rule

Intersection points are paired from left to right, and pixels between each pair are filled.

• Odd-even rule
• Inside–outside test

7. Steps of Scan-Line Algorithm

• Initialize Edge Table
• Set scan line to minimum y
• Move edges to Active Edge Table
• Sort AET by x
• Fill pixels between x pairs
• Update x values and scan line

8. Advantages

• Efficient for complex polygons
• No recursion required
• Used in hardware rendering

9. Disadvantages

• Complex implementation
• Edge cases at vertices

10. Applications

• Polygon rendering
• Game graphics
• CAD systems

Practice Questions

1. What is scan-line polygon fill?
2. What is an edge table?
3. Explain active edge table.
4. Describe scan-line filling steps.
5. List advantages of scan-line algorithm.

Practice Task