Goal

Draw a line using only integer arithmetic by maintaining a decision variable that tells us, after each step in the major axis, whether to also step in the minor axis.

Derivation Sketch (slope 0 < m < 1)

At step k we are at (x_k, y_k). Next pixel candidates are E = (x_k+1, y_k) and NE = (x_k+1, y_k+1). The actual line at x = x_k+1 has y = m(x_k+1) + c. Define decision variable p_k = 2 dy x_k - 2 dx y_k + 2 dy + (2c - 1) * dx, which simplifies recurrences to:

• if p_k < 0 -> choose E, p_(k+1) = p_k + 2*dy.
• if p_k >= 0 -> choose NE, p_(k+1) = p_k + 2dy - 2dx.

Initial p_0 = 2*dy - dx.

Worked Example

Line from (2, 3) to (10, 6). dx = 8, dy = 3.

• p_0 = 2*3 - 8 = -2.
• 2dy = 6, 2dy - 2dx = 6 - 16 = -10.

Pixels: (2,3) (3,3) (4,4) (5,4) (6,5) (7,5) (8,5) (9,6) (10,6).

DDA vs Bresenham

Generalization

Handle 8 octants by swapping/negating x,y and stepping in the major axis. Modern GPUs use rasterizers based on edge-equation evaluation, but Bresenham remains the textbook reference for line scan-conversion.