Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Line drawing: DDA and Bresenham's algorithms

DDA and Bresenham are two basic raster line-drawing algorithms used to convert a straight mathematical line into discrete pixel coordinates for raster displays.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Line drawing is the first step in drawing any shape on a raster screen. Engineers use these algorithms in graphics libraries, embedded displays, printers and any system that must convert continuous geometry to discrete pixels. Efficient and correct line rasterization affects rendering speed and visual quality (aliasing and gaps).

Key ideas

  • Endpoint: the given start and end points (x0,y0) and (x1,y1), typically integers for pixel coordinates.
  • Slope: m = (y1 - y0)/(x1 - x0) if x1 ≠ x0. Slope determines the algorithm's stepping direction.
  • Incremental algorithm: compute successive pixels using previous value(s) plus a small increment, avoiding expensive recomputation.
  • DDA (Digital Differential Analyzer): an incremental floating-point method. Choose the axis with the larger span as the driving axis, step by 1 in that axis, and increment the other coordinate by slope (or inverse slope). After each step round to nearest integer pixel.
    • Assumptions: endpoints given; we can use floating-point arithmetic and rounding.
    • Steps: compute dx = x1-x0, dy = y1-y0, steps = max(|dx|,|dy|); x_inc = dx/steps; y_inc = dy/steps; start at (x,y)=(x0,y0); for i=0..steps plot(round(x), round(y)); x+=x_inc; y+=y_inc.
  • Bresenham's algorithm: an integer (or fixed-point) incremental algorithm that avoids floating-point by using a decision parameter. Works fastest when implemented with integer arithmetic.
    • Key idea: for slope 0 < m < 1 (other cases handled by symmetry and sign adjustments) at each x step we must choose between two candidate pixels: the pixel at the current y or the one at y+1. We form a decision variable based on the line's distance to the midpoint between these two pixel centers. Using algebraic manipulation, this decision variable can be updated by adding constants, avoiding multiplications or divisions at each step.
    • Assumptions: integer endpoints; we handle octants by reflecting/ swapping coordinates so we always process the case 0 ≤ m ≤ 1 with left-to-right increments. The derivation assumes a pixel center model and comparing midpoints.

Derivation of Bresenham's decision variable (case 0 ≤ m ≤ 1):

  1. Write the line in implicit form: F(x,y) = dy·x - dx·y + c = 0. One convenient c is chosen so that F(x0,y0)=0 (substitute x0,y0 to find c). For decision we evaluate sign of F at midpoint between candidate pixels.
  2. For step from xk to xk+1, two candidate pixels have centers (xk+1, yk) and (xk+1, yk+1). Compare the line's y at xk+1 with yk+0.5. The sign of a decision expression D = dy*(xk+1) - dx*(yk+0.5) + c decides whether to keep y or increment y.
  3. Multiply by 2 to avoid fractions. The initial decision parameter simplifies to p0 = 2·dy - dx (after algebra and using c). Update rules follow:
    • if pk < 0: choose pixel (x+1, y); pk+1 = pk + 2·dy
    • else: choose pixel (x+1, y+1); pk+1 = pk + 2·(dy - dx)
  • Octants and symmetry: To handle any slope and direction, map the general line into the canonical case (0 ≤ m ≤ 1 and left-to-right) by:

    • If |dy| > |dx|, swap roles of x and y (stepping in y instead).
    • If x1 < x0, swap endpoints (process left-to-right) and re-map final coordinates.
    • If slope negative, adjust sign of y increments.
  • Complexity: Both algorithms are O(max(|dx|,|dy|)) in number of plotted pixels. DDA uses float additions and rounding; Bresenham uses integer additions and branching and is faster on integer-only hardware.

What to draw for an exam diagram (exactly):

  • Draw a grid of pixels (small squares). Mark two pixel centers as (x0,y0) and (x1,y1). Draw the straight line through these centers. For Bresenham, at one x-step show the two candidate pixel centers (x+1,y) and (x+1,y+1); draw midpoint between them and label the vertical distance from the line to the midpoint; label the decision variable D = dy*(x+1) - dx*(y+0.5). Also show dx and dy on axes.

Formulas

dx = x1 - x0 — difference in x (pixels)

dy = y1 - y0 — difference in y (pixels)

steps = max(|dx|, |dy|) — number of increments for DDA

x_inc = dx / steps — increment in x per step (pixels/step)

y_inc = dy / steps — increment in y per step (pixels/step)

DDA plot: for i=0..steps plot(round(x), round(y)); x += x_inc; y += y_inc — rounding rule: nearest integer; ties (fractional part exactly ±0.5) round away from zero (matches C++ std::round).

Bresenham initial p = 2*dy - dx — decision parameter (integer)

If p < 0 then p = p + 2*dy else p = p + 2*(dy - dx); (and increase y when p >= 0) — update rules for 0 ≤ m ≤ 1

Symbols: x0,y0,x1,y1 are integer pixel coordinates (unit = pixels); dx, dy are in pixels; steps is a count (unit = steps); x_inc,y_inc are pixels per step (may be fractional). Assume a Cartesian coordinate system with y increasing upward; if using screen coordinates where y increases downward, invert the interpretation of 'increase y' accordingly.

Worked examples

Example 1 (numerical) — short, slope between 0 and 1 Given endpoints (x0,y0)=(2,3) and (x1,y1)=(10,7).

  1. Compute differences: dx = 10 - 2 = 8 pixels; dy = 7 - 3 = 4 pixels.
  2. DDA: steps = max(8,4) = 8; x_inc = 8/8 = 1.0; y_inc = 4/8 = 0.5. Start (x,y)=(2,3). For i from 0 to 8 plot round(x), round(y):
    • i0: (2,3)
    • i1: (3,4) (x=3, y=3.5 → round to 4)
    • i2: (4,4) (y=4.0)
    • i3: (5,5) (y=4.5 → 5)
    • i4: (6,5)
    • i5: (7,6)
    • i6: (8,6)
    • i7: (9,7)
    • i8: (10,7) Final pixel list: (2,3), (3,4), (4,4), (5,5), (6,5), (7,6), (8,6), (9,7), (10,7).
  3. Bresenham (0 ≤ m ≤ 1): p0 = 2*dy - dx = 8 - 8 = 0. Iterate x from 2 to 10, starting y=3:
    • plot (2,3); p>=0 so y→4, p = p + 2*(dy-dx) = 0 + 2*(4-8) = -8
    • plot (3,4); p<0 so p = p + 2*dy = -8 + 8 = 0
    • plot (4,4); p>=0 so y→5; p = 0 + 2*(4-8) = -8
    • plot (5,5); p<0 so p = -8 + 8 = 0
    • plot (6,5); p>=0 so y→6; p = -8
    • plot (7,6); p<0 so p = 0
    • plot (8,6); p>=0 so y→7; p = -8
    • plot (9,7); p<0 so p = 0
    • plot (10,7) Same pixel list as DDA: (2,3), (3,4), (4,4), (5,5), (6,5), (7,6), (8,6), (9,7), (10,7).

Example 2 (programming) — C++ implementations that print pixel coordinates.

Program A: DDA (prints list of pixel coordinates)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x0,y0,x1,y1;
    if(!(cin>>x0>>y0>>x1>>y1)) return 0;
    int dx = x1 - x0, dy = y1 - y0;
    int steps = max(abs(dx), abs(dy));
    double x_inc = dx / (double)steps;
    double y_inc = dy / (double)steps;
    double x = x0, y = y0;
    for(int i=0;i<=steps;i++){
        cout<<"("<< (int)round(x) <<","<< (int)round(y) <<")\n";
        x += x_inc; y += y_inc;
    }
    return 0;
}

Sample input: 2 3 10 7 Exact output: (2,3) (3,4) (4,4) (5,5) (6,5) (7,6) (8,6) (9,7) (10,7)

Program B: Bresenham (assumes |dx| ≥ |dy|; uses xstep/ystep to handle direction; generalize by swapping axes when |dy| > |dx|)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x0,y0,x1,y1;
    if(!(cin>>x0>>y0>>x1>>y1)) return 0;
    int dx = x1 - x0, dy = y1 - y0;
    int x = x0, y = y0;
    int p = 2*abs(dy) - abs(dx);
    int xstep = (dx>=0)?1:-1;
    int ystep = (dy>=0)?1:-1;
    int steps = abs(dx);
    for(int i=0;i<=steps;i++){
        cout<<"("<<x<<","<<y<<")\n";
        x += xstep;
        if(p < 0) p += 2*abs(dy);
        else { y += ystep; p += 2*(abs(dy) - abs(dx)); }
    }
    return 0;
}

Sample input: 2 3 10 7 Exact output: (2,3) (3,4) (4,4) (5,5) (6,5) (7,6) (8,6) (9,7) (10,7)

Note: Program B above handles simple sign cases but assumes |dx| ≥ |dy|; for full generality you must swap axes when |dy| > |dx| (see Key ideas).

Common mistakes

  • Off-by-one in loop bounds: include both endpoints. Use for i=0..steps inclusive for DDA.
  • Initial decision parameter wrong sign or wrong value (p0 = 2*dy - dx is for 0 ≤ m ≤ 1; mixing absolute values without consistency causes errors).
  • Using floating comparisons directly (==) for stopping conditions.
  • Overflow if dx and dy are very large and you multiply without using appropriate integer size — use types that fit (32-bit int usually OK for screen coordinates, but verify).

For your exam

Typical question types:

  • Define and compare DDA and Bresenham (short note).
  • Derive Bresenham's decision parameter and update formula (step-by-step algebra) — show intermediate expressions and explain midpoint test.
  • Numerical rasterization: given endpoints, list the pixels using DDA or Bresenham (show each step and rounding/decision updates).
  • Write or explain C/C++ pseudocode for each algorithm and explain complexity and why one is faster on integer hardware.

What a full-marks answer must include:

  • Clear definitions of raster, pixel, slope, dx, dy.
  • For derivations: show the implicit line form used, the midpoint test expression, multiplication to remove fractions, and the final integer update rules with explanation of each term.
  • For numericals: show initial values, each iteration, and final pixel list. Indicate rounding rule used for DDA.
  • Mention octant handling, how to swap axes, and how to restore coordinates.

Quick check

  1. In DDA, how many steps do you take? (Answer in short form)
  2. What is the initial decision parameter p0 for Bresenham when 0 ≤ slope ≤ 1?
  3. Give one advantage of Bresenham over DDA.

Answers: 1) steps = max(|dx|,|dy|). 2) p0 = 2·dy - dx. 3) Uses integer arithmetic (faster, no floating point).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?