Line Drawing Algorithms: Bresenham, DDA, and Midpoint Circle

TAKEAWAYS:

• DDA vs. Bresenham: Understand why Bresenham’s integer arithmetic avoids floating-point errors and speeds up rasterization.
• Decision Parameters: Derive the general formula for Bresenham’s algorithm and apply it to diagonal lines (slope 1).
• Error Metrics: Learn how Bresenham’s algorithm minimizes pixel deviation using error terms $E$ and $2E$.
• Real-World Impact: See how these algorithms power UI rendering (e.g., WhatsApp’s message bubbles) and CAD tools (e.g., AutoCAD).
• Exam Pitfalls: Avoid mixing up 4-connected and 8-connected pixel neighbors in flood-fill or clipping edge cases.

Core Concepts: What is a Line-Drawing Algorithm?

A line-drawing algorithm is a computational method to approximate a straight line between two points on a raster display (pixel grid). Real lines are continuous, but digital screens show them as discrete pixels. The challenge is to choose the closest pixels to the ideal line while minimizing visual error (jagged edges).

Key Definitions

• Pixel: Smallest addressable element on a display (e.g., 1920×1080 pixels in Full HD).
• Rasterization: Process of converting vector graphics (lines, shapes) into pixels for display.
• Aliasing: Jagged stair-step appearance of lines due to pixel discretization.
• Error Term ($E$): Measures deviation from the ideal line; used in Bresenham’s algorithm to decide the next pixel.

1. Digital Differential Analyzer (DDA) Algorithm

The DDA algorithm is the simplest line-drawing method, using floating-point arithmetic to calculate pixel positions.

How DDA Works

1. Input: Two endpoints $(x_1,y_1)$ and $(x_2,y_2)$.
2. Calculate increments:
   • $\Delta x=x_2-x_1$
   • $\Delta y=y_2-y_1$
3. Compute step size:
   • $dx=\text{sign}(\Delta x)$
   • $dy=\text{sign}(\Delta y)$
   • $steps=\max (|\Delta x|,|\Delta y|)$
4. Incremental pixel placement:
   • $x=x_1+\frac{\Delta x}{steps}$
   • $y=y_1+\frac{\Delta y}{steps}$
   • Plot pixel at $(x,y)$ and repeat for all steps.

Limitations of DDA

• Floating-point operations: Slow and prone to rounding errors.
• No error correction: Produces visible aliasing for steep lines.

Worked Example: DDA for Line from (2,3) to (9,7)

graph LR
    A["Start: (2,3)"] --> B["Δx=7, Δy=4"]
    B --> C["steps=7, dx=+1, dy=+1"]
    C --> D["Loop 1: x=2+1=3, y=3+4/7≈3.57 → (3,4)"]
    D --> E["Loop 2: x=4, y≈4.14 → (4,4)"]
    E --> F["... Continue until (9,7)"]

Output: A jagged line due to floating-point rounding.

2. Bresenham’s Line Algorithm (Integer Arithmetic)

Bresenham’s algorithm eliminates floating-point operations by using integer arithmetic and an error term to decide the next pixel.

Key Idea: Error Term ($E$)

• Tracks deviation from the ideal line.
• Uses decision parameter $P_k$ to choose between two candidate pixels:
  • If $P_k<0$, choose the pixel closer to the major axis (e.g., $x$-axis for shallow lines).
  • Else, increment both $x$ and $y$.

General Formula for Decision Parameter

For a line with slope $m\le 1$ (shallow lines): $$P_k=2E_k+\Delta y$$ where:

• $E_k$ = error term at step $k$,
• $\Delta y$ = change in $y$ over the line’s length.

Derivation Steps

1. Initial error: $$E_0=\Delta y-\frac{\Delta x}{2}$$
2. Update rule:
   • If $P_k<0$: $E_{k+1}=E_k+\Delta y$
   • Else: $E_{k+1}=E_k+\Delta y-\Delta x$
3. Next pixel:
   • If $P_k<0$, increment $x$ only.
   • Else, increment both $x$ and $y$.

Worked Example: Bresenham for Line from (0,0) to (5,3)

graph TD
    A["Start: (0,0), Δx=5, Δy=3"] --> B["E₀ = 3 - 5/2 = 0.5 → E₀=1 (integer)"]
    B --> C["P₀ = 2*1 + 3 = 5 ≥ 0 → choose (1,1), E₁=1+3-5=-1"]
    C --> D["P₁ = 2*(-1) + 3 = 1 ≥ 0 → choose (2,2), E₂=-1+3-5=-3"]
    D --> E["P₂ = 2*(-3) + 3 = -3 < 0 → choose (3,2), E₃=-3+3=0"]
    E --> F["P₃ = 0 + 3 = 3 ≥ 0 → choose (4,3), E₄=0+3-5=-2"]
    F --> G["P₄ = -4 + 3 = -1 < 0 → choose (5,3), End"]

Pixel Path: (0,0) → (1,1) → (2,2) → (3,2) → (4,3) → (5,3) Visual Output:

(Note: The actual image will show a smooth-looking line with minimal aliasing.)

Why Integer Arithmetic?

• Speed: Avoids slow floating-point operations.
• Precision: Error term $E$ is scaled to integers, reducing rounding errors.
• Hardware Efficiency: Modern GPUs optimize integer operations.

3. Handling Steep Lines (Slope > 1)

For lines where $|\Delta y|>|\Delta x|$, swap $x$ and $y$ and plot accordingly. The decision parameter becomes: $$P_k=2E_k+\Delta x$$

Worked Example: Bresenham for Line from (0,0) to (3,5)

graph TD
    A["Swap: Δx'=5, Δy'=3"] --> B["E₀ = 3 - 5/2 = -0.5 → E₀=0"]
    B --> C["P₀ = 0 + 5 = 5 ≥ 0 → choose (1,0), E₁=0+5-3=2"]
    C --> D["P₁ = 4 + 5 = 9 ≥ 0 → choose (2,1), E₂=2+5-3=4"]
    D --> E["P₂ = 8 + 5 = 13 ≥ 0 → choose (3,2), E₃=4+5-3=6"]
    E --> F["P₃ = 12 + 5 = 17 ≥ 0 → choose (3,3), End"]

Pixel Path: (0,0) → (1,0) → (2,1) → (3,2) → (3,3) Visual Output:

4. Comparison: DDA vs. Bresenham

## In the Real World

1. WhatsApp UI (Meta)

   • Idea Used: Bresenham’s algorithm renders message bubbles and chat borders.
   • How: Integer arithmetic ensures crisp edges on low-end devices (e.g., Android phones with limited FPU).

2. AutoCAD (Autodesk)

   • Idea Used: DDA/Bresenham for drafting lines in engineering designs.
   • Example: Drawing a 45° line from (0,0) to (10,10) uses Bresenham to avoid floating-point artifacts in blueprints.

3. Nepal Rastra Bank’s Digital Currency (eNPR)

   • Idea Used: Line-drawing algorithms render transaction graphs in the bank’s dashboard.
   • Example: A line chart showing inflation rates uses Bresenham to plot data points smoothly on low-resolution dashboards.

4. Pathao’s Ride-Sharing App

   • Idea Used: DDA for real-time route visualization.
   • Example: The straight-line path from your location to the driver uses Bresenham to render the route on the map, even on slow devices.

5. Edge Cases and Exam Traps

A. Clipping Lines to a Window

When a line extends beyond the display bounds (e.g., from (10,10) to (20,20) on a 10×10 screen), Cohen-Sutherland clipping is used. Bresenham’s algorithm is applied only to the visible segment.

B. 4-Connected vs. 8-Connected Pixels

• 4-connected: Only up/down/left/right neighbors (used in flood-fill).
• 8-connected: Includes diagonals (used in Bresenham for smoother lines). Exam Pitfall: Mixing these in questions about flood-fill or clipping.

C. Floating-Point vs. Integer Arithmetic

• DDA: May produce incorrect pixels for steep lines due to rounding.
• Bresenham: Guarantees the closest pixel set by construction.

## Exam Tip

1. Derive the Decision Parameter:

   • For slope $m\le 1$: $P_k=2E_k+\Delta y$.
   • For slope $m>1$: Swap $x$ and $y$ and use $P_k=2E_k+\Delta x$.
   • Always show the initial error $E_0$ and update rule.

2. Trace the Pixel Path:

   • Draw the line and mark each pixel with its $(x,y)$ coordinates.
   • Example: For (0,0) to (5,3), list all 6 pixels (including endpoints).

3. Compare Algorithms:

   • DDA is simple but slow; Bresenham is efficient but requires understanding of $E_k$.
   • Memorize: Bresenham uses integer arithmetic to avoid floating-point errors.

4. Real-World Scenarios:

   • Banking: Loan repayment graphs use Bresenham for clarity.
   • E-commerce: Daraz’s product images use line algorithms for edge detection in filters.

5. Common Mistakes:

   • Forgetting to swap $x$ and $y$ for steep lines.
   • Misapplying the decision parameter (e.g., using $P_k=2E_k-\Delta y$).
   • Off-by-one errors in pixel counting (always include endpoints).

## Practice Questions (Exam-Style)

1. Derive the decision parameter for Bresenham’s algorithm for a line from (3,4) to (10,8). Trace the pixel path.
2. Why does DDA fail for the line from (0,0) to (1,100)? How would Bresenham handle it?
3. Draw and explain the pixel path for Bresenham’s algorithm for the line from (2,2) to (7,5).
4. Compare the output of DDA and Bresenham for the line from (0,0) to (4,1). Which is smoother? Why?
5. Scenario: A game renders a diagonal laser beam from (50,50) to (150,150) on a 200×200 screen. Which algorithm would you use and why?

## Summary Visual: Bresenham’s Algorithm Flow

flowchart TD
    A["Start: (x₁,y₁), (x₂,y₂)"] --> B["Calculate Δx, Δy"]
    B --> C["If |Δy| > |Δx|: Swap x & y"]
    C --> D["Initialize E₀ = Δy - Δx/2"]
    D --> E["Loop until x₂ reached:"]
    E --> F["P_k = 2E_k + Δy"]
    F --> G["If P_k < 0: Plot (x+k, y+k), E_{k+1} = E_k + Δy"]
    G --> H["Else: Plot (x+k, y+k+1), E_{k+1} = E_k + Δy - Δx"]
    H --> E