Filled Area Primitives: Algorithms, Polygons & Scan Conversion

TAKEAWAYS:

• Scan Line Algorithm fills polygons by traversing horizontal spans between edges, ideal for convex polygons.
• Flood Fill Algorithm uses boundary checks to fill regions recursively or iteratively, useful for flood-filling in image editing.
• Area Subdivision Methods (e.g., Even-Odd Rule, Non-Zero Winding Rule) determine inside/outside points for complex polygons.
• Edge Traversal (e.g., Bresenham’s Line Algorithm) is critical for accurately detecting polygon boundaries.
• Real-world applications include game sprites, CAD tools, and UI rendering (e.g., filling shapes in Khalti’s transaction confirmation screens or Pathao’s ride area markers).

---

1. Introduction to Filled Area Primitives

Filled area primitives are fundamental in computer graphics for rendering polygons, shapes, and regions. Filling algorithms determine how pixels inside a boundary are colored or shaded. Key applications:

• Game Development: Filling sprites (e.g., characters in mobile games).
• CAD Systems: Rendering technical drawings (e.g., AutoCAD).
• Image Editing: Tools like Photoshop’s Magic Wand (uses flood fill).

Why Fill Primitives?

• Visual Realism: Filling polygons makes 2D/3D objects appear solid.
• Efficiency: Scan line algorithms minimize redundant calculations.
• Complexity Handling: Area subdivision rules (e.g., Even-Odd Rule) handle self-intersecting polygons.

---

2. Scan Line Algorithm for Polygon Filling

The Scan Line Algorithm fills a polygon by processing it horizontally, one scan line at a time. It is efficient for convex polygons but requires edge sorting.

How It Works

1. Sort Edges: Organize polygon edges by their y-coordinates (top to bottom).
2. Traverse Scan Lines: For each horizontal line, find intersections with edges.
3. Fill Spans: Between intersection points, fill the pixels (using Bresenham’s Line Algorithm for edges).

Visual: Scan Line Traversal

Worked Example: Filling a Triangle Consider a triangle with vertices (2,2), (4,5), (7,3).

1. Sort edges by y:
   • Edge 1: (2,2) → (4,5) (y increases)
   • Edge 2: (4,5) → (7,3) (y decreases)
   • Edge 3: (7,3) → (2,2) (y decreases)
2. Scan Line y=2:
   • Intersects Edge 1 at x=2, Edge 3 at x=2 → No span (degenerate).
3. Scan Line y=3:
   • Intersects Edge 1 at x=3, Edge 3 at x=5 → Fill x=3 to x=5.
4. Scan Line y=4:
   • Intersects Edge 1 at x=3.5, Edge 2 at x=5.5 → Fill x=3.5 to x=5.5.

---

3. Flood Fill Algorithm

The Flood Fill Algorithm fills a region by expanding from a seed point until a boundary is hit. Used in:

• Image Editing (e.g., Photoshop’s Fill Tool).
• Game Development (e.g., Minecraft’s block filling).

Types of Flood Fill

Worked Example: Flood Filling a Rectangle

Consider a 5x5 rectangle with boundary color black and fill color red, starting at (2,2).

1. Seed Point: (2,2) is red → fill it.
2. Check Neighbors:
   • (1,2): Black (boundary) → stop.
   • (2,1): Black → stop.
   • (2,3): White → fill and enqueue.
   • (3,2): White → fill and enqueue.
3. Repeat until all connected white pixels are filled.

---

4. Area Subdivision Methods

For complex polygons (e.g., self-intersecting or concave), area subdivision rules determine if a point is inside/outside:

1. Even-Odd Rule (Parity Rule):
   • Count edge crossings. If odd, the point is inside.
   • Example: A star polygon may have some points inside due to intersections.
2. Non-Zero Winding Rule:
   • Sum the winding numbers (direction of edges). If non-zero, the point is inside.
   • Example: Used in SVG path rendering.

Comparison Table

Visual: Even-Odd Rule

---

5. Edge Traversal for Boundary Detection

Before filling, we must detect polygon edges accurately. Bresenham’s Line Algorithm is used to:

• Draw edges between vertices.
• Find intersection points for scan line filling.

Bresenham’s Algorithm Steps

1. Calculate slope: $m=\frac{\Delta y}{\Delta x}$.
2. Error term: Track pixel errors to decide next step.
3. Plot pixels: Move right/up based on error.

Worked Example: Drawing Edge from (2,2) to (5,4)

1. Δx = 3, Δy = 2 → Slope = 2/3.
2. Error term: Initialize $e=2-3=-1$.
3. Steps:
   • Start at (2,2).
   • $e=-1+3=2$ → Move right to (3,2).
   • $e=2-3=-1$ → Move right to (4,2).
   • $e=-1+3=2$ → Move right and up to (5,3).
   • Final pixel: (5,4).

---

6. Real-World Applications

a) Khalti’s Transaction Confirmation Screen

• Idea Used: Scan Line Filling for rendering the green checkmark in payment success screens.
• How: The app fills a polygon representing the checkmark using scan line conversion for smooth rendering.

b) Pathao’s Ride Area Marker

• Idea Used: Flood Fill to highlight the ride pickup zone on the map.
• How: Starting from a seed point (driver’s location), the algorithm fills the circular area where the rider can be picked up.

c) Daraz’s Product Image Background Removal

• Idea Used: Even-Odd Rule for magic wand tool in image editing.
• How: The tool detects the product boundary and fills the background (or removes it) based on pixel parity.

---

7. Exam Tip

• Scan Line vs. Flood Fill:
  • Scan Line: Best for polygons (uses edge sorting).
  • Flood Fill: Best for regions (uses boundary checks).
• Area Subdivision Rules:
  • Even-Odd Rule is simpler but fails for complex shapes.
  • Non-Zero Winding is more accurate for text and paths.
• Worked Examples:
  • Always draw the polygon and mark scan lines/edges.
  • For flood fill, show the queue/stack steps.
• Common Mistakes:
  • Forgetting to sort edges in scan line filling.
  • Misapplying boundary conditions in flood fill (e.g., ignoring diagonal neighbors).

---

8. Summary Table

---

9. Practice Questions (Exam Style)

1. Short Notes:
   • Explain how Bresenham’s Algorithm helps in polygon filling.
   • Differentiate between Even-Odd Rule and Non-Zero Winding Rule with examples.
2. Worked Problem:
   • Fill the polygon with vertices (1,1), (3,4), (6,2) using the Scan Line Algorithm. Show all scan lines and intersections.
3. Application:
   • How would you implement flood fill in a mobile game to fill a player’s health bar? Describe the steps.

---

Final Note: Mastering these algorithms is crucial for game engines, CAD software, and UI rendering. Always visualize the steps—drawing helps!