Theory
From two endpoints to a row of pixels
This is the heart of the subject. Given a line's two endpoints, which exact pixels do you light up? Two classic algorithms answer this: DDA and Bresenham (with VECGEN in the same family). Both are exam favourites, and both are worth understanding pixel by pixel.
We will work the same line, from (0, 0) to (5, 3) (slope 0.6), through both algorithms, and get the same pixels, so you can compare them directly. Then we will see why Bresenham, using only integer arithmetic, is preferred. Follow the numbers closely; this is the material exams test hardest.
Theory
DDA: step and round
The DDA (Digital Differential Analyzer) samples the line at unit steps and rounds to the nearest pixel.
For (0,0) to (5,3): dx = 5, dy = 3. Take steps = max(|dx|, |dy|) = 5. The increments are xInc = dx/steps = 1 and yInc = dy/steps = 0.6. Start at (0,0) and repeatedly add the increments, rounding each point:
- (0, 0)
- (1, 0.6) rounds to (1, 1)
- (2, 1.2) rounds to (2, 1)
- (3, 1.8) rounds to (3, 2)
- (4, 2.4) rounds to (4, 2)
- (5, 3.0) is (5, 3)
Pixels: (0,0), (1,1), (2,1), (3,2), (4,2), (5,3). Simple, but it uses floating-point (the 0.6) and rounding at every step.
Practical
DDA line algorithm
void ddaLine(int x1, int y1, int x2, int y2) {
int dx = x2 - x1, dy = y2 - y1;
int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy); // max(|dx|,|dy|)
float xInc = (float)dx / steps; // 5/5 = 1.0
float yInc = (float)dy / steps; // 3/5 = 0.6
float x = x1, y = y1;
for (int i = 0; i <= steps; i++) {
putPixel(round(x), round(y)); // (0,0)(1,1)(2,1)(3,2)(4,2)(5,3)
x += xInc;
y += yInc;
}
}Theory
Bresenham: integers and a decision parameter
Bresenham's algorithm draws the same line using only integer arithmetic, no floating point. For a shallow line (slope between 0 and 1) it steps along x and, at each step, uses a decision parameter p to choose whether y stays the same or increases by 1.
The setup for (0,0) to (5,3): dx = 5, dy = 3. The initial decision parameter is p0 = 2dy - dx = 6 - 5 = 1. Precompute two constants: 2dy = 6 and 2dy - 2dx = -4. Then at each x, plot the pixel, and update: if p < 0, add 2dy to p (y stays); otherwise add 2dy - 2dx to p and increment y.
Follow along
Bresenham worked for (0,0) to (5,3)
- x=0, p=1 Plot (0,0). p >= 0, so p = 1 + (-4) = -3, and y becomes 1.
- x=1, p=-3 Plot (1,1). p < 0, so p = -3 + 6 = 3 (y stays 1).
- x=2, p=3 Plot (2,1). p >= 0, so p = 3 + (-4) = -1, and y becomes 2.
- x=3, p=-1 Plot (3,2). p < 0, so p = -1 + 6 = 5 (y stays 2).
- x=4, p=5 Plot (4,2). p >= 0, so p = 5 + (-4) = 1, and y becomes 3.
- x=5, p=1 Plot (5,3). Done.
Practical
Bresenham line algorithm (slope 0 to 1)
void bresenhamLine(int x1, int y1, int x2, int y2) {
int dx = x2 - x1, dy = y2 - y1;
int p = 2 * dy - dx; // p0 = 2dy - dx = 1
int y = y1;
for (int x = x1; x <= x2; x++) {
putPixel(x, y); // (0,0)(1,1)(2,1)(3,2)(4,2)(5,3)
if (p < 0) {
p = p + 2 * dy; // 2dy = 6
} else {
p = p + 2 * dy - 2 * dx; // 2dy - 2dx = -4
y = y + 1;
}
}
}Formula
DDA vs Bresenham: why Bresenham wins
Both produce the same pixels for our line, so why prefer Bresenham? DDA uses floating-point arithmetic (the 0.6 increment) and rounds at every step, which is slower and can accumulate rounding error on long lines. Bresenham uses only integer addition and comparison, no floats, no rounding, which is faster and exact, ideal for hardware.
That is why Bresenham (and integer line generators like VECGEN in the same family) became the standard. The decision parameter is the clever trick: it tracks whether the true line has risen enough to bump y, using only integers. Same result, cheaper arithmetic.
Quiz
In Bresenham's algorithm for the line (0,0) to (5,3), what is the initial decision parameter p0?
- p0 = dx - dy = 2
- p0 = 2dy - dx = 2(3) - 5 = 1
- p0 = 0 always
- p0 = dy/dx = 0.6
Show the answer
p0 = 2dy - dx = 2(3) - 5 = 1
For a line with slope between 0 and 1, Bresenham's initial decision parameter is p0 = 2dy - dx. Here dy = 3 and dx = 5, so p0 = 2(3) - 5 = 6 - 5 = 1. Option A uses the wrong formula (dx - dy). Option C is wrong: p0 depends on dx and dy, it is not always 0. Option D gives the slope (0.6) as a fraction, but the whole point of Bresenham is to avoid fractions, p0 is an INTEGER (1 here). Remember the setup: p0 = 2dy - dx, then at each step add 2dy if p < 0, or 2dy - 2dx (and increment y) if p >= 0.
Think first
Why is avoiding floating point such a big deal for Bresenham?
DDA works fine with its 0.6 increment. Why does Bresenham's integer-only arithmetic matter so much? Then tap.
Show the answer
Because integer arithmetic is FASTER, more ACCURATE, and better suited to HARDWARE than floating point, and line drawing happens so often that these savings are enormous in aggregate. Speed: on the machines where these algorithms matter (and especially in graphics hardware), integer addition and comparison are cheaper and quicker than floating-point operations, and Bresenham needs only a few integer adds and a compare per pixel, no multiplication or division in the inner loop. Since a single screen can contain thousands of lines and each line many pixels, and scenes redraw many times per second, shaving the cost of every pixel adds up to a huge overall gain. Accuracy: DDA carries a fractional increment (like 0.6) and ROUNDS at every step, and on a long line those tiny rounding errors can ACCUMULATE, causing the drawn line to drift slightly from the true path. Bresenham uses only integers and an exact decision test, so there is no accumulating floating-point error, the chosen pixels are exactly the best ones, every time. Hardware-friendliness: because it needs only integer add and compare, Bresenham is easy to implement directly in fast, simple circuitry, which is exactly what graphics chips did, making line drawing lightning fast. Historically, floating-point was also much slower or even absent on early hardware, so an integer-only method was not just faster but sometimes the only practical choice. All told, Bresenham gets the SAME visual result as DDA but with cheaper, exact, hardware-friendly integer math, which is why it became the classic, preferred line-drawing algorithm. Integers are fast and exact; avoiding floats is the whole clever point.
Summary
Key takeaways
- Line-drawing algorithms turn two endpoints into the pixels that best approximate the line.
- DDA: steps = max(|dx|,|dy|); increments xInc = dx/steps, yInc = dy/steps; add and round each step.
- DDA on (0,0)->(5,3): steps 5, yInc 0.6, pixels (0,0)(1,1)(2,1)(3,2)(4,2)(5,3); uses floating point.
- Bresenham (slope 0 to 1): p0 = 2dy - dx; if p < 0 add 2dy, else add 2dy - 2dx and increment y; integer only.
- Bresenham on the same line: p0 = 1, p-sequence 1, -3, 3, -1, 5, 1, giving the same pixels.
- Bresenham is preferred because integer arithmetic is faster, exact (no accumulating rounding), and hardware-friendly; VECGEN is a related integer line generator.
- Memory hook: DDA adds a fraction and rounds; Bresenham uses integers and a decision parameter p0 = 2dy - dx.