Line Drawing

Line Drawing Algorithms

Drawing a line between two points on a pixel grid is a fundamental operation in computer graphics. Since pixels are discrete, we must choose which pixels to illuminate to best approximate a straight line.

DDA (Digital Differential Analyzer)

DDA computes points along a line by incrementally calculating x and y values using the slope. It works by sampling the line at unit intervals.

DDA Algorithm:
  Input: (x1,y1) to (x2,y2)

  dx = x2 - x1
  dy = y2 - y1
  steps = max(|dx|, |dy|)

  x_inc = dx / steps
  y_inc = dy / steps

  x = x1, y = y1
  for i = 0 to steps:
      plot(round(x), round(y))
      x += x_inc
      y += y_inc

Drawback: Uses floating-point arithmetic, which is slower on integer-based hardware.

Bresenham's Line Algorithm

An efficient algorithm that uses only integer addition, subtraction, and bit shifting. It decides which pixel to plot by tracking a decision parameter.

Bresenham's Algorithm (for slope 0 < m < 1):

  dx = x2 - x1
  dy = y2 - y1
  p0 = 2*dy - dx

  x = x1, y = y1

  for i = 0 to dx:
      plot(x, y)
      if p < 0:
          p = p + 2*dy
      else:
          y = y + 1
          p = p + 2*dy - 2*dx
      x = x + 1

Decision parameter tracks error:
  p < 0 → choose east pixel (x+1, y)
  p ≥ 0 → choose NE pixel (x+1, y+1)

Midpoint Line Algorithm

A variant of Bresenham's that evaluates the line at the midpoint between candidate pixels. It produces identical results with a slightly different formulation.

Midpoint decision:
  Evaluate f(x,y) at midpoint between
  candidate pixels E and NE.

  If f(mid) < 0 → midpoint is above line → choose E
  If f(mid) ≥ 0 → midpoint is below line → choose NE

Anti-Aliasing Lines

To produce smooth-looking lines, intensity can be varied based on how close each pixel center is to the true line. This reduces the appearance of jagged edges (aliasing).