Line Drawing Algorithms: DDA, Bresenham, Midpoint & Clipping

1. Why Lines Matter in Computer Graphics

Lines are the building blocks of 2D/3D graphics:

• Define edges of shapes (polygons, curves).
• Used in UI elements (buttons, menus), maps (GPS routes), and animations (motion paths).
• Clipping ensures lines stay within visible windows (e.g., a map zoomed into Kathmandu).

2. Line Representation: Parametric vs. Raster

A line between two points $A(x_1,y_1)$ and $B(x_2,y_2)$ can be:

• Parametric: $x=x_1+t(x_2-x_1)$, $y=y_1+t(y_2-y_1)$, where $t\in [0,1]$.
• Raster (discrete): Approximated by pixels using algorithms like DDA or Bresenham’s.

Mermaid diagram of parametric line:

graph TD
    A["Point A(x₁,y₁)"] --> B["Point B(x₂,y₂)"]
    B -->|"t=0"| A
    B -->|"t=1"| C["Point B(x₂,y₂)"]
    B --> D["Intermediate Point (x₁+tΔx, y₁+tΔy)"]

3. Digital Differential Analyzer (DDA) Algorithm

How it works:

1. Calculate slope $m=\frac{y_2-y_1}{x_2-x_1}$ and step size $\Delta x=1$, $\Delta y=m$.
2. For each $x$ from $x_1$ to $x_2$, compute $y=y_1+\Delta y\cdot (x-x_1)$.
3. Round $y$ to the nearest integer and plot $(x,\text{round}(y))$.

Example: Draw line from $A(10,6)$ to $B(12,1)$.

• $\Delta x=2$, $\Delta y=-5$.
• Steps:
  • $x=10$: $y=6+(-5/2)\times 0=6$ → (10, 6)
  • $x=11$: $y=6+(-5/2)\times 1=3.5$ → (11, 4)
  • $x=12$: $y=6+(-5/2)\times 2=1$ → (12, 1)

Mermaid trace of DDA steps:

graph TD
    A["(10,6)"] --> B["(11,4)"] --> C["(12,1)"]
    A -->|"Δx=2, Δy=-5"| D["y=6-2.5*(x-10)"]

Advantages:

• Simple to implement.
• Works for any slope (including vertical/horizontal).

Disadvantages:

• Slow for long lines (floating-point operations).
• Not optimal for diagonal lines (wastes computation).

4. Bresenham’s Line Algorithm

How it works: Uses integer arithmetic to minimize error and speed:

1. Calculate $dx=|x_2-x_1|$, $dy=|y_2-y_1|$, and error term $e=2dy-dx$.
2. For each $x$, decide whether to increment $y$ based on $e$:
   • If $e\ge 0$, increment $y$ and update $e=e-2dx$.
   • Else, update $e=e+2dy$.

Example: Same line $A(10,6)$ to $B(12,1)$.

• $dx=2$, $dy=5$, $e=10-2=8$.
• Steps:
  • $x=10$: $e=8\ge 0$ → plot (10,6), $e=8-4=4$.
  • $x=11$: $e=4\ge 0$ → plot (11,5), $e=4-4=0$.
  • $x=12$: $e=0\ge 0$ → plot (12,4), but actual $y=1$. Correction: Bresenham rounds to nearest pixel, so final point is (12,1).

Mermaid comparison (DDA vs. Bresenham):

graph TD
    subgraph DDA["DDA Steps"]
        D1["(10,6)"] --> D2["(11,4)"] --> D3["(12,1)"]
    end
    subgraph Bresenham["Bresenham Steps"]
        B1["(10,6)"] --> B2["(11,5)"] --> B3["(12,1)"]
    end
    DDA -->|"Less accurate"| Bresenham

Advantages:

• Faster (integer math).
• More accurate for diagonal lines.

Disadvantages:

• Complex logic for slope > 1 (requires swapping $x$ and $y$).

5. Midpoint Circle Algorithm (Bonus: Extending to Lines)

While this unit focuses on lines, the midpoint circle algorithm (used in Unit 4) shares Bresenham’s integer-precision approach. For lines, Bresenham is superior, but midpoint is useful for curves.

6. Line Clipping: Cohen-Sutherland Algorithm

Why clip?

• Remove lines outside the visible window (e.g., a map zoomed into a city).
• Improves rendering efficiency.

How it works:

1. Assign each endpoint a region code (3-bit binary):
   • 000: Inside window.
   • 100: Left of window.
   • 010: Right of window.
   • 001: Below window.
   • 011: Above window.
2. If both endpoints are inside, draw the line.
3. If both are outside, discard.
4. If one is inside/outside, compute intersection and recode.

Example: Clip line $A(20,10)$ to $B(30,18)$ with window $x\in [10,30]$, $y\in [5,20]$.

• Region codes:
  • $A$: 000 (inside).
  • $B$: 000 (inside).
• Result: Draw the entire line.

Mermaid Cohen-Sutherland steps:

graph TD
    A["A(20,10): 000"] --> B["B(30,18): 000"]
    B -->|"Both inside"| C["Draw line AB"]

Advantages:

• Fast rejection of fully outside lines.
• Simple to implement.

Disadvantages:

• Not optimal for complex clipping regions (e.g., polygons).

7. Real-World Applications

In the real world

1. Daraz Order Paths:

   • Idea: Line clipping ensures delivery routes stay within city boundaries (e.g., Kathmandu’s roads).
   • How: Clipping algorithms filter out paths that go outside the map’s visible area, optimizing logistics.

2. Pathao Ride Routing:

   • Idea: Bresenham’s algorithm approximates driver paths between stops on a grid map.
   • How: The app uses rasterized lines to show the shortest pixel-path between two points, avoiding unnecessary detours.

3. NTC/Ncell Network Maps:

   • Idea: Line drawing renders roads and signal towers on mobile maps.
   • How: DDA/Bresenham’s algorithms convert vector road data into pixels for smooth display on small screens.

Worked Example: Daraz’s Clipped Route

• Scenario: A seller in Thapathali wants to ship to Pokhara. The map window shows only Kathmandu.
• Clipping: The algorithm clips the full route (Kathmandu → Pokhara) to only the visible segment (Thapathali → Airport), saving bandwidth and computation.

8. Comparison Table: DDA vs. Bresenham

9. Exam Tips

1. Master Bresenham’s Algorithm:

   • Always check if $dx>dy$. If not, swap $x$ and $y$ and adjust the error term.
   • Common mistake: Forgetting to round the final point (e.g., in the $A(10,6)$ to $B(12,1)$ example, Bresenham plots (12,1) but intermediate steps may seem off).

2. Cohen-Sutherland Clipping:

   • Draw the region code table in your answer:

     | Bit | 2 (Left) | 1 (Right) | 0 (Bottom) | 3 (Top) |
     |-----|----------|-----------|-------------|---------|
     | 000 | Inside   | Inside    | Inside      | Inside  |
     | 100 | Left     | Inside    | Inside      | Left    |
     

   • For partial clipping, show the intersection equation derivation (e.g., $x=x_1+(y_2-y_1)(x_2-x_1)/(y_2-y_1)$).

3. Visualize Every Step:

   • For DDA/Bresenham, plot the points on graph paper or use a tool like GeoGebra.
   • For clipping, label the window boundaries and show the clipped segment.

4. Time Management:

   • Spend 20 minutes on DDA/Bresenham examples (show all intermediate steps).
   • Allocate 15 minutes for Cohen-Sutherland (focus on region codes and intersection logic).