Skip to main content

DDA versus Bresenham line algorithm

Short answer

DDA uses floating-point arithmetic and rounding, causing slow speed and accumulated error. Bresenham’s algorithm uses only integer addition/subtraction with a decision parameter p, no rounding, no error accumulation, making it faster and hardware-friendly.

Differentiate between the DDA and Bresenham's line drawing algorithms: what are the demerits of DDA and how does Bresenham's algorithm address them (advantages of Bresenham's algorithm)?

PointDDABresenham's
ArithmeticFloating-point (slope m, increments)Integer only (additions, subtractions, shifts)
RoundingRound() needed at every stepNo rounding; uses a decision parameter
SpeedSlowerFaster
AccuracyRounding errors accumulate (drift) on long linesAccurate; error does not accumulate
Pixel choiceRounds the computed y to the nearest integerChooses the pixel closest to the true line using the sign of p
HardwareHard to implementEasy to implement in hardware
OperationsOne division for the increments, then a floating-point addition and rounding per stepInteger additions/subtractions only

Demerits of DDA

  • Uses floating-point operations and rounding at every step, which is slow.
  • Accumulated round-off error in x and y makes the pixel positions drift from the true line, especially for long lines.
  • Needs a division to find the slope or step size.

How Bresenham's algorithm addresses them (advantages)

  • Uses only integer arithmetic: decision parameter p_0 = 2Δy − Δx, with p_k+1 = p_k + 2Δy or p_k + 2Δy − 2Δx.
  • No rounding and no accumulated error: the sign of p_k gives the closest pixel exactly.
  • Faster and easy to implement in hardware, so it is used by most graphics systems.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Graphics chapter 2 questions →