Line Drawing Algorithms: DDA, Bresenham, Cohen-Sutherland

Core Concepts

1. Why Line Drawing Matters

Lines are the primitive building blocks of computer graphics. Efficient algorithms determine:

• Speed: Real-time rendering (e.g., games, simulations).
• Quality: Anti-aliasing, smooth curves.
• Precision: Avoiding jagged edges (staircase effect).

Applications:

• CAD/CAM: Technical drawings.
• Animation: Skeletal rigging, motion paths.
• User Interfaces: Icons, buttons, graphs.

2. Digital Line Representation

A line between two points $(x_0,y_0)$ and $(x_1,y_1)$ is represented as a sequence of rasterized pixels (discrete points on a grid). The challenge is to:

1. Approximate the continuous line with minimal error.
2. Optimize computational cost (fewer calculations = faster rendering).

Key Definitions:

• Pixel: Smallest addressable screen element (e.g., (x, y)).
• Staircase Effect: Jagged appearance due to discrete sampling.
• Error Term: Difference between the ideal line and the rasterized path.

3. Digital Differential Analyzer (DDA) Algorithm

The simplest incremental line-drawing algorithm, based on parametric equations.

How It Works

1. Calculate slope $m=\frac{\Delta y}{\Delta x}=\frac{y_1-y_0}{x_1-x_0}$.
2. Incrementally plot pixels using:
   • $x=x_0+t$
   • $y=y_0+m\cdot t$, where $t$ increases from 0 to 1.
3. Round $y$ to the nearest integer (or vice versa if $|m|>1$).

Algorithm Steps

def DDA(x0, y0, x1, y1):
    dx = x1 - x0
    dy = y1 - y0
    steps = max(abs(dx), abs(dy))  # Number of increments

    x_inc = dx / steps
    y_inc = dy / steps

    x, y = x0, y0
    plot(x, y)  # Draw pixel

    for _ in range(steps):
        x += x_inc
        y += y_inc
        plot(round(x), round(y))

Example: Trace from (2, 3) to (10, 8)

Pros:

• Simple to implement.
• Works for any slope.

Cons:

• Floating-point operations (slow on early hardware).
• Rounding errors accumulate, causing visible gaps.

4. Bresenham’s Line Algorithm

Optimized for integer arithmetic, making it faster and more efficient than DDA.

Key Idea

• Error term ($e$) tracks deviation from the ideal line.
• Decision parameter ($p$) determines the next pixel:
  • If $p<0$, choose the pixel closer to the major axis (x or y).
  • Else, adjust both axes.

Derivation

For a line with slope $0<m<1$:

1. Error equation: $e=2\cdot \text{error}-\Delta y$ (Error accumulates as we move right.)
2. Decision parameter: $p_k=2\cdot e_k+\Delta y$
   • If $p_k<0$, plot $(x_{k+1},y_k)$ (steeper slope).
   • Else, plot $(x_{k+1},y_{k+1})$ (shallower slope).

Algorithm Steps

def Bresenham(x0, y0, x1, y1):
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx - dy

    while True:
        plot(x0, y0)
        if x0 == x1 and y0 == y1: break
        e2 = 2 * err
        if e2 > -dy:
            err -= dy
            x0 += sx
        if e2 < dx:
            err += dx
            y0 += sy

Example: Trace from (6, 12) to (10, 5)

Pros:

• Integer arithmetic (no floating-point errors).
• Faster than DDA (fewer operations).
• Smoother lines (better error correction).

Cons:

• Complex derivation (harder to understand intuitively).
• Limited to axis-aligned lines (extensions needed for arbitrary slopes).

5. Comparison: DDA vs. Bresenham

6. Line Clipping: Cohen-Sutherland Algorithm

Clips a line segment to a rectangular window using region codes and trivial rejection.

Key Concepts

• Window: The visible rectangle $(x_{\text{min}},y_{\text{min}}),(x_{\text{max}},y_{\text{max}})$.
• Viewport: Where the clipped line is drawn (often the screen).
• Region Codes: 4-bit codes indicating a point’s position relative to the window.
  • 0001: Left of window
  • 0010: Right of window
  • 0100: Below window
  • 1000: Above window

Algorithm Steps

1. Compute region codes for both endpoints.
2. Trivial Acceptance/Rejection:
   • If both codes are 0000 → accept (fully inside).
   • If bitwise AND is non-zero → reject (fully outside).
3. Clip iteratively:
   • Find the closest edge to the line.
   • Compute intersection with that edge.
   • Update the endpoint and its region code.
   • Repeat until acceptance or rejection.

Example: Clip Line (10, 10) to (60, 30) in Window (15, 15) to (25, 25)

1. Region Codes:
   • $P_1(10,10)$: 1001 (left + below)
   • $P_2(60,30)$: 0110 (right + above)
2. Bitwise AND: 1001 & 0110 = 0000 → not trivial.
3. Closest Edge: Left edge ($x=15$).
   • Intersection: $y=10+\frac{20}{50}\times (15-10)=11.6$.
   • New $P_1=(15,12)$ (rounded).
4. Repeat:
   • New codes: $P_1=0000$, $P_2=0110$.
   • Next closest edge: Bottom ($y=15$).
   • Intersection: $x=10+\frac{50}{20}\times (15-10)=22.5$.
   • New $P_2=(22,15)$.
5. Final Check:
   • Both points inside → accept clipped line from (15, 12) to (22, 15).

Pros:

• Efficient (early rejection).
• Works for any rectangle.

Cons:

• Only rectangular windows.
• Complex for non-axis-aligned clipping (use Liang-Barsky for generalization).

7. Midpoint Circle Algorithm

Extends Bresenham’s idea to circles using symmetry.

Key Idea

• Symmetry: Only calculate 1/8th of the circle (rest mirrored).
• Decision Parameter: $p_k=F_{k+1}-F_k$, where $F_k$ is the error function.

Algorithm Steps

def MidpointCircle(xc, yc, r):
    x = 0
    y = r
    p = 1 - r  # Initial decision parameter

    while x <= y:
        plot(xc + x, yc + y)  # Octant 1
        plot(xc - x, yc + y)  # Octant 2
        plot(xc + x, yc - y)  # Octant 8
        plot(xc - x, yc - y)  # Octant 7

        if p < 0:
            p += 2*x + 3
        else:
            p += 2*(x - y) + 5
            y -= 1
        x += 1

Example: Circle with Radius 5

Pros:

• Efficient (only 1/8th calculated).
• Integer arithmetic.

Cons:

• Limited to circles (extensions for ellipses exist).

8. Applications and Extensions

Real-World Uses

• CAD Software: AutoCAD, SolidWorks (line clipping for views).
• Games: Wireframe rendering, minimaps.
• Medical Imaging: MRI/CT scan line tracing.

Advanced Topics

• Anti-Aliasing: Smooths jagged lines (e.g., supersampling).
• Parametric Curves: Bézier, B-splines (for smooth lines).
• 3D Line Drawing: Perspective projection, depth testing.

Exam Tip

What Examiners Look For

1. Derivations:

   • Show step-by-step math for Bresenham/DDA (e.g., error term, decision parameter).
   • Example: For Bresenham, derive $p_k=2e_k+\Delta y$.

2. Tracing Examples:

   • Plot every pixel in the path (e.g., Bresenham from (2,3) to (10,8)).
   • Label error terms in midpoint circle.

3. Region Codes:

   • Binary masks for Cohen-Sutherland (e.g., 1001 for left + below).
   • Show intersection calculations with edges.

4. Comparisons:

   • Table format for DDA vs. Bresenham (speed, error, use case).
   • Pros/cons of clipping algorithms (e.g., Cohen-Sutherland vs. Liang-Barsky).

5. Common Pitfalls

   • Floating-point rounding in DDA (use Bresenham for precision).
   • Symmetry assumptions in circle algorithms (only plot 1/8th).
   • Edge cases in clipping (e.g., vertical/horizontal lines).

Model Answer Structure

**Part A: Derive Bresenham’s Algorithm**
1. Start with line equation $y=mx+c$.
2. Define error term $e=\text{actual}-\text{ideal}$.
3. Show decision parameter $p_k=2e_k+\Delta y$.
4. **Trace example**: Plot (6,12) to (10,5) with table of $(x,y)$, $e$, and decisions.

**Part B: Cohen-Sutherland Clipping**
1. Define region codes for $P_1(10,10)$ and $P_2(60,30)$.
2. Show bitwise AND → non-trivial.
3. **Clip iteratively**:
   - Left edge intersection → new $P_1$.
   - Bottom edge intersection → new $P_2$.
4. Final clipped line: $(15,12)$ to $(22,15)$.

**Part C: Comparison**
| Algorithm      | Advantage               | Disadvantage          |
|----------------|-------------------------|-----------------------|
| DDA            | Simple                  | Floating-point errors |
| Bresenham      | Integer arithmetic      | Complex derivation    |
| Cohen-Sutherland| Fast rejection         | Only rectangles      |

Example pixel path from (0,0) to (5,3) using Bresenham’s method (Image: Dnttllthmmnm, CC BY-SA 4.0, via Wikimedia Commons)

flowchart TD
    A[Start: Line Endpoints] --> B{Both Inside?}
    B -->|Yes| C[Accept Line]
    B -->|No| D{Bitwise AND Non-Zero?}
    D -->|Yes| E[Reject Line]
    D -->|No| F[Find Closest Edge]
    F --> G[Compute Intersection]
    G --> H[Update Endpoint]
    H --> B